邻域搜索算法（共7篇）
邻域搜索算法 篇1
0 引言
电力系统无功优化是一个多变量、多约束的非凸、非线性问题,其中潮流计算、优化模型和优化算法是其中的核心要素。传统的无功优化方法主要包括线性规划法、非线性规划法、混合整数规划法、动态规划法等[1],其理论基础成熟,快速可靠,但是这些方法一般都要求目标函数线性化和可微性,使得其在离散变量和连续变量混合优化问题的精确处理上存在局限性。近年来,随着计算机技术的发展,国内外学者提出了遗传算法、模拟退火算法、人工神经网络法、模糊优化法等人工智能方法[1],因其在处理非线性离散问题以及全局寻优能力上都有较优良的性能,得到了广泛的应用。
禁忌搜索(TS)算法最早由Glover Fred于1977年提出[2],是由局部搜索扩展到全局搜索的寻优算法,具有较强的“爬山”能力,采用记忆指导搜索策略,搜索时能够跳出局部最优解,避免了算法陷入局部最优和大范围的搜索,适合解决多变量、非线性、不连续、多约束的全局优化问题,但是TS算法的单点搜索方式对初始解和邻域结构有较强的依赖性。
近年来,国内外学者提出各种改进方法,其中摄伟提出了采用扩大邻域结构的禁忌搜索(ITS)算法[3],有效降低了系统网损,但是ITS算法采用双点同向移动搜索,依然无法很好克服算法陷入局部最优的弊端。因此,本文进一步提出了改进扩大邻域结构禁忌搜索(FITS)算法,建立了基于FITS算法的无功优化数学模型,并采用IEEE 14节点模型进行算例分析,证明了FITS算法在电力系统经济运行中的优越性。
1 无功优化的数学模型
无功优化问题,其中既有连续变量(如发电机的机端电压),又有离散变量(如有载调压变压器分接头和无功补偿电容器或电抗器装置的投入组数等)。因此,无功优化是在系统的结构参数及负荷给定的情况下,通过控制变量的优选,找到能够满足所有约束条件,并使得系统的某些性能指标或目标函数达到最优时的潮流分布。
1.1 目标函数
基于无功损耗最小、电压合格率最高的目标,可以建立无功优化控制的目标函数:
式中:w1、w2分别为有功网损惩罚因子和电压越界惩罚因子;n为电网节点总数;ΔP为系统有功网损;ΔUi为节点压降,可由式(2)和式(3)表示或约束:
式中:Ui、Uimax/Uiman分别为节点的节点电压、电压上限、电压下限,上下限差值可由ΔUim=Uimax-Uimin表示;Uj为与节点i直接连接的节点j的电压;Gij、Bij、δij分别为节点i和节点j之间的支路电导、电纳和相角差。
1.2 约束条件
无功优化控制的约束条件分为等式约束和不等式约束[4],其中等式约束条件反映全网的功率平衡,分别为节点无功功率和有功功率约束,如式(4)所示:
不等式约束条件是安全约束,来源于电网的技术指标和设备的电气运行极限,可调无功出力、节点电压和可调变压器的变比必须在给定的上下限之间,由式(5)表示:
式中:Qi为节点注入无功;Ci为无功补偿装置的投入组数;Ti、Timin、Timax分别为节点i变压器分接头的档位、档位下限、档位上限。其中,变压器档位和电容器投入组数均取整数,通常以此作为基本解域进行潮流计算,使得等式约束(4)自动满足,然后检查不等式约束(5)是否满足。不能满足条件的则作为较大惩罚项附加在目标函数(1)上,以迫使最终解尽可能满足所有约束条件。
2 扩大邻域禁忌搜索算法及其改进
2.1 扩大邻域禁忌搜索(ITS)算法
传统禁忌搜索(TS)算法的基本思想是利用灵活的“记忆”技术,以及相应的存储结构和禁忌准则来避免迂回搜索,并通过特赦准则来赦免被禁忌的优良状态,进而保证有效搜索并实现全局优化[5]。ITS算法是从一个给定初始解及其对应的单点变化邻域结构1开始搜索,对当前解应用“移动”操作符,产生1组当前解的邻域试验解,挑选最能改善评价函数或对其恶化最小的解作为当前局部最优解;再以此为初始解,采用扩大邻域结构2重新进行搜索,每次同向改变2个控制变量的数值,这样提高了获得全局最优解的概率。其中,藐视准则、禁忌表长度、终止准则和邻域结构对算法性能影响较大。
2.2 改进扩大邻域禁忌搜索(FITS)算法
FITS算法针对ITS算法进一步改进,在得到ITS最优解的基础上,引入2个控制量反向移动的第三种邻域结构进行搜索,在保证原有算法较强爬山能力的前提下,提高了搜索的多样性与精细性,进一步降低了搜索陷入局部最优的可能性,FITS算法改进算法流程图如图1所示。
当程序进入扩大邻域搜索中后,采用期望水平1和期望水平2相结合的释放准则,其中期望水平1指本次迭代所产生的候选解中,若某个解对应的目标函数值小于当前最优解的,则无视其禁忌属性,直接替换成为新的当前最优解。期望水平2是指如果一个移动作用于目标函数后,所得到的目标函数值小于本次迭代中产生的所有候选解,则无视其禁忌属性,将其作为新的当前局部最优解,产生下一次迭代邻域;若发现满足期望水平2,则开始使用邻域结构3开始搜索,即同时改变2个控制变量的值,与ITS算法中的邻域结构1和2不同的是,邻域结构3中2个变量为反向移动,这样搜索更加完全,解的可靠性更优,更大限度地防止解陷入局部最优,最终得到全局最优解。此外,FIST算法采用规定迭代次数与设定最优解保持不变的迭代次数相结合的方法作为搜索终止条件,当退出邻域结构3中的搜索后,继续进行邻域结构2中的搜索,邻域结构3的搜索不影响邻域结构2的迭代次数记录,充分保证得到解的全局最优性。
3 算例分析
为了验证算法有效性,本文基于IEEE 14节点模型来分析TS算法、ITS算法以及FITS算法的无功优化效果,在给定系统状态的基础上,计算了系统各节点处电压、损耗、运行时间等。计算中设定系统的基准容量为SB=100 MVA,采用牛顿-拉夫逊法进行潮流计算。变压器初始变比与系统初始运行状态分别见表1、表2。
初始解下系统网损为0.133 51 MW,系统电压最低水平为1.012 47 p.u.,此时各个负荷节点的电压满足约束条件,则将此时解作为可行初始解。由表3可看出,采用FITS算法后,系统整体电压水平有显著提高,网损降低了8.168 1%,优于ITS算法的8.015 4%,此时系统整体性能更为优良。不过,FITS算法运行时间略长于ITS算法。
基于以上分析,在实时性要求较高的情况下,采用ITS算法更加高效,但系统性能相对较差;在实时性要求不高,但对网损要求较为严格的情况下,采用FITS算法更具经济价值。
4 结论
禁忌搜索算法具有灵活的“记忆”功能和藐视准则,是一种局部搜索能力很强的全局迭代优化算法。本文提出了改进的扩大邻域禁忌搜索算法,基于IEEE 14模型进行算例分析,并与TS算法、ITS算法优化结果进行对比,结果表明FITS算法寻优能力最强,具有较高的经济价值与实用性。
参考文献
[1]田义恒,任勇.地区电网无功优化系统的应用现状分析[J].中国电力教育,2011,(30):139-140.
[2]朱向阳.基于改进禁忌搜索算法的配电网电压无功优化控制[J].继电器,2006,34(14):35-37.
[3]摄伟.基于禁忌搜索算法的区域电网无功优化[D].西安:西安科技大学,2008.
[4]孙蕾,刘崇新,侍乔明,等.基于引入禁忌表的改进遗传算法的地区电网无功优化[J].陕西电力,2011,39(9):1-5.
[5]孙蕾,魏宇存,刘崇新,等.引入改进tent映射的遗传禁忌混合算法及其在地区无功优化中的应用[J].陕西电力,2012,40(11):1-7.
[6]扬帆.无功补偿培训教程基础篇[M].北京:全球杂志出版社,2005.
[7]王明兴.连续禁忌搜索算法改进及应用研究[D].浙江大学,2005.
[8]任晓莉,程红丽,刘健,等.基于禁忌搜索算法的变电站电压无功优化控制[J].继电器,2008,36(8):31-34,39.
邻域搜索算法 篇2
随着钢铁企业的迅速发展, 一体化生产计划与调度问题得到了国内外学者的广泛关注[1,2,3], 然而对于生产过程中钢坯库的研究较少, 钢坯库的优化管理是实现一体化生产计划和调度中的一项重要研究内容。热轧工序是按照轧制单元计划进行组织生产的, 每个轧制单元实质上就是一个钢坯的加工序列。一般情况下, 在制定轧制单元计划时, 钢坯的实际垛位情况是未知的, 因而在轧制单元计划实施前, 需要根据钢坯的实际垛位情况, 对轧制单元计划中的每一个轧制位置从其对应的可交换钢坯组中选择合适的轧制钢坯。钢坯倒垛问题就是在已知钢坯实际垛位情况下对轧制计划进行调整时, 确定如何从同规格、同材质的可交换钢坯组中选出每个轧制位置对应的钢坯, 使得序列的总倒垛数和吊车运行距离最少。目前, 随着客户订单的多品种、小批量的发展, 有一些截面半径较大、客户交货期紧的钢坯以一种多层多列同方向形式存放 (图1) 。这种存放方式具有便于管理、较少倒垛数的优势, 但也有一定的缺点, 如空间利用率较小、垛位稳定性较差、需要外界工具固定等。
目前, 倒垛问题的研究主要集中在板坯倒垛和集装箱翻箱中, 而对于钢坯倒垛问题的研究很少。唐立新等[4]对板坯倒垛问题进行了定义, 构造了一种新的多回路启发式算法;根据不同轧制位置间是否存在重叠, 王敏等[5]针对多对多板坯倒垛问题提出了一种Sequence邻域搜索算法;任会之等[6]研究了在考虑板坯存储各库区吊机能力限制下的倒垛问题, 利用提出的问题性质, 降低了模型求解复杂性;唐立新等[7]针对钢铁企业板坯库中的最优倒垛问题建立了0-1规划模型, 并构造了增加培育过程的改进遗传算法;李耀华等[8]将板坯出库计划分解为板坯出库优化决策和板坯最优倒垛决策组合优化问题, 分别建立模型, 并设计了一种离散粒子群优化算法;Kumar等[9]针对板坯倒垛问题设计了一种改进的并行遗传算法 (iP-GA) ;Lixin T等[10]针对板坯倒垛问题建立了分段动态规划模型, 并设计了基于该模型的启发式算法 (SDP-based Heuristic) ;徐亚等[11]提出了一种针对翻倒箱落箱位置的确定问题的启发式算法H及其改进算法IH。
本文在以上研究的指导下对钢坯倒垛问题进行了研究, 建立了最优倒垛模型, 并设计了基于Stacking邻域搜索启发式算法。
2 问题特征分析与建模
2.1 问题描述
在钢铁生产过程中, 热轧是按照热轧计划来组织生产的, 计划的内容实质是一个在规格、钢种、工艺参数及总重量等方面均满足连续轧制工艺约束的钢坯加工序列[12,13]。加工序列中的每支钢坯在钢坯库的计划预选池中都有若干支符合条件的钢坯作为交换钢坯。那么如何根据钢坯库的实际情况确定合适的轧制对象, 使得一个出库批次的倒垛数最少、同时吊车运行距离最少, 称此问题为钢坯倒垛问题。轧制计划的钢坯出库顺序要求与钢坯库内钢坯的物理存放位置顺序不一致, 是造成大量不必要倒垛作业的主要原因, 因而需要重新确定钢坯的出库加工序列, 以构成倒垛次数最小的钢坯加工序列。钢坯倒垛是指已编入轧制计划的钢坯上面的三角区域 (图2) , 有一根或几根未编入轧制计划的钢坯, 当该钢坯出库时, 需要将压在上面的钢坯倒出到其他位置, 这里将同一根钢坯的吊出和移回记作一次倒垛。图2为钢坯库中每一个垛位结构。
一般在钢坯库作业中, 影响倒垛操作的因素主要包括到来的钢坯的堆放位置、提坯顺序及倒垛钢坯的落地位置。具体可描述为:①钢坯到达钢坯库的顺序虽然是已知的, 但是采用的是先到先服务的策略, 不可避免的存在不同属性级、不同轧制顺序的钢坯混合堆放;②在钢坯库的任何一个垛位中, 钢坯的操作只能是自上而下的, 这是由钢坯库出库作业的特征决定的, 不可避免产生钢坯出库时的倒垛现象;③仓库管理员一般是根据经验确定选择哪根钢坯出库, 往往缺乏对整个出库作业的全局考虑, 不能从根本上减少倒垛操作;④轧制计划的出库顺序要求与其物理放置顺序不一致, 是造成大量不必要倒垛作业的原因, 需要重新确定钢坯的加工序列;⑤倒垛过程中, 倒垛钢坯的落位位置是有选择的, 不合理的落位位置对后续操作可能造成二次倒垛, 甚至多次倒垛等。
钢坯倒垛问题是钢铁企业仓库管理与控制问题中遇到的典型运筹学问题, 在冷装工艺下, 热轧所需的原料主要来源于钢坯库, 若将轧制位置视作分配的任务, 库内的钢坯视作具有承担任务资格的人员, 每个轧制位置只能从若干满足约束要求的垛位中匹配, 每个垛位可以匹配多个轧制位置, 那么可将钢坯倒垛问题归结为一类带顺序约束的广义指派问题, 广义指派问题已被证明是NP难问题。在实际生产中, 一般一个班的轧制计划钢坯数可高达60, 而库内钢坯又是以多层多列形式存储的, 因此对如此大规模的组合优化问题, 用传统的最优化算法求解难度是非常大。因此, 研究针对该问题的近似算法尤为重要。
2.2 问题建模
为了便于描述模型和理解算法, 符合定义如下:
(1) 索引和集合
i为轧制项目, i∈I, I为轧制项目集合;k为仓库内垛位, k∈K, K为仓库垛位集合;j为预选钢坯, j∈S, S={1, 2, …, N}为整个计划预选池中钢坯集合;Si为轧制位置i对应的可交换钢坯集合, Si∩Si′=Ø, 其中i, i′∈I但i≠i′.
(2) 参数
gi, li, si, pi分别为轧制项目i处对应的要求钢坯钢种、长度、规格、特殊要求;Uk, Vk为垛位k距离加热炉和临时存放区的距离, 令UVmax=max{Uk, Vk|k∈K};Hk为垛位k上的倒垛次数上限, 此约束主要是考虑吊机的能力及向轧线输送的时间的均衡性;bk为垛位k上阻碍纳入轧制计划里所有钢坯出库的障碍钢坯 (即没有纳入轧制计划的钢坯) 数;Ak为垛位k上纳入轧制计划的可交换钢坯集合;Bkj为轧制计划执行前, 垛位k上压在的钢坯j上的三角区域内的钢坯集合, ‖Bkj‖表示集合Bkj中元素的个数, j∈S, k∈K;Dk为垛位k到钢坯临时存放区的距离;DSk为垛位k到加热炉的距离;U为一个较大的正整数。
(3) 决策变量
(4) 辅助变量
Ckij为轧制计划执行时, 如果垛位k上的钢坯j充当轧制位置对象i, 钢坯j需要的净倒垛次数。
据以上研究分析, 本文建立以最小化轧制单元出库引起的总倒垛数和天车总行程的多目标整数规划模型, 模型描述如下:
[P0]
模型中, 目标函数 (1) ~ (2) 为最小化轧制序列出库时引起垛位的总倒垛次数及天车总行程两个目标函数;约束 (3) 要求每一个轧制单元项目必须选择一根钢坯;约束 (4) 限制每一根钢坯至多只能被一个轧制单元项目选中;约束 (5) 要求轧制单元项目只能选择可选钢坯集合内的钢坯;约束 (6) 给出了一种计算净倒垛次数的求解公式, 这里把选中钢坯的倒出看作一次倒垛;约束 (7) 限制仓库内各垛位上倒垛次数, 以保证各垛位上倒垛均衡性, 保证吊机能力和轧制序列供应时间的均衡;约束 (8) 表示被选中的垛位中至少有一根纳入轧制计划的钢坯;约束 (9) 表示纳入候选钢坯集合中的钢坯需满足钢种、长度、规格、特殊要求一致;约束 (10) 给出决策变量的取值范围。
模型中参数Ckij在求解过程中是动态变化的, 是二次规划问题[7], 求解具有NP难特性, 采用传统的求解多目标规划的方法无法对其进行求解, 因此构造一种启发式算法对其进行求解显得尤为重要。采用加权系数将多目标规划问题转化为单目标规划问题进行求解, 从而达到了简化模型的效果。
2.3 模型转化
由于模型的两个目标量纲不同, 而且模型参数、约束较多而且复杂, 无法直接采用传统优化算法求解, 所以这里对两个目标函数进行统一量纲后采用加权系数将多目标规划问题转化为单目标规划问题。首先, 将模型分解为如下两个单目标整数规划模型:
[P1]
[P2]
其次, 分别计算模型[P1]和模型[P2]的最优解及最差解 (C*, C*) 及 (D*, D*) , 这里的最优解和最差解都是相对最优、最差解, 则求解模型[P1]和模型[P2]就等价于求解以下两个模型:
[P1]*
[P2]*
则求解模型[P0]就等价于求解如下模型:
[P0]*
参数δ1和δ2为对应轧制序列出库总倒垛数及天车总距离的权重系数, 该值主要通过工厂实际生产中的历史数据统计获得, 一般情况下δ1>δ2, 这里取统计平均值δ1=0.63, δ2=0.37。δ1、δ2的值可以根据实际的仓库垛位与加热炉分布情况而确定。
3 求解算法
目前倒垛问题已有的研究主要是针对板坯的, 而钢坯倒垛问题与板坯倒垛问题有较大的不同:①产品的存储方式不同。板坯主要是以单层单列的方式进行存储, 而钢坯是以多层多列的存储方式, 比板坯的存储要复杂得多;②轧制加工序列不同。板坯轧制单元是由具有一定宽度、长度、厚度的轧制板坯组成, 而钢坯轧制单元是由具有相同轧制规格的钢坯序列组成, 一般垛位堆放时是按照轧制规格相同尽量一起堆放。因此不能将板坯倒垛的算法直接应用于钢坯倒垛问题上, 需要将理论上的钢坯倒垛问题与实际生产和垛位情况结合为其设计符合实际生产需求的算法。
本文研究的钢坯倒垛问题, 由于其规模大、约束多, 采用智能优化算法往往会遇到编码可行度低、陷入局部最优、计算效率低下等问题, 所以根据轧制序列及钢坯库垛位的实际情况设计了一种考虑最小化轧制序列出库引起的仓库垛位总倒垛次数, 同时优化吊车到临时存放库位及加热炉距离的启发式算法, 即基于Stacking邻域搜索算法。
3.1 原启发式算法的推广
文献[5]给出了关于板坯倒垛问题的原系统启发式算法, 原系统启发式算法的主要思想为:从轧制序列的第一个轧制项目开始, 根据设定的规则依次确定其最佳钢坯, 每一个位置的最佳钢坯都是从该位置对应的可交换钢坯组中进行选择。本文在该算法的基础上结合钢厂的实际生产情况将原启发式算法进行推广, 在垛位条件适应值的计算中考虑了钢坯到临时存放区和加热炉的距离, 比原启发式算法更加接近实际生产情况。由于板坯与钢坯的存储方式不同, 推广算法中的最佳钢坯是指在垛位中位于其上三角区域内的钢坯数最少的可交换钢坯 (图2) , 如果有多个可交换钢坯同时满足这一条件, 则选择垛位条件值最大的钢坯作为最佳钢坯。推广算法的流程如图3所示。
算法求解步骤如下:
Step1:初始化轧制项目与库存堆存信息, 令p=1, 对应轧制序列的第一个项目;
Step2:计算轧制位置p的所有可交换钢坯的Bkj, j∈S;
Step3:对Bkj进行排序, 确定使Bkj最小的集合Bk.若集合Bk只有一个元素, 则转Step7;否则, 转Step4;
Step4:计算轧制项目p对应的可交换钢坯j在垛位k上的‖Bkj‖, j∈S和其所在垛位上的倒垛次数Ckpj;
Step5:计算垛位k上纳入轧制序列的钢坯数目Ak, k∈K;
Step6:计算轧制项目p的候选钢坯j的垛位条件值Wj, j∈S, Wj的计算式如下:
其中, λ1, λ2, λ3, λ4分别为对应属性的权重系数, 该组权重值由大量实际生产数据统计获得, 确定使得Wj最大的钢坯m, 即
Step7:选择该钢坯作为轧制项目p的最佳钢坯;
Step8:若p>M, 则转Step7, 否则置p=p+1, 转Step2;
Step9:输出整个轧制序列对应钢坯的出库计划。
3.2 基于Stacking邻域的启发式算法
基于Stacking邻域搜索的启发式算法主要分为两个阶段:第一阶段是从轧制单元计划的第一个轧制项目开始到最后一个依次确定轧制序列的最佳钢坯。每一个位置的最佳钢坯都是从该轧制位置的可交换钢坯组中选择垛位中位于其上部三角区域的钢坯数最小的钢坯, 如果有多个位置的钢坯被选中, 选择垛位条件值最大的垛位;第二阶段是通过Stacking邻域搜索算法改进第一个阶段产生产的解, 为了描述Stacking邻域结构及算法方便, 给出以下相关定义。
定义1[5]Sequence邻域:在轧制序列J中, 将位于轧制项目i和j之间所有的轧制项目构成的集合视为一个加工序列邻域, 称为Sequence邻域, 即δ={k|i≤k≤j, |j-i|≤P, i, j, k∈J}。其中, P为Sequence邻域最大允许长度。
定义2 Stacking邻域:将Sequence邻域与垛位上纳入当前轧制序列的钢坯集合Ak中元素 (轧制序列中钢坯对应垛位上多个替换钢坯时, 只算一次) 最多的垛位视为Stacking邻域 (图4) 。
由图4可知, 编号为5的钢坯对应垛位上有两个替换钢坯, 此时计算交集时只算一个, 若当前所有垛位中只有垛位A中纳入轧制序列中的钢坯最多, 则称垛位A为轧制序列S的Stacking邻域, 邻域中的元素集合为钢坯编号为{1, 3, 4, 5}的集合。文献[4]和文献[5]分别考虑了垛位上板坯的横向邻域及轧制序列的纵向邻域, 都得到了相对原启发式算法较优的计算结果, 本文在同时考虑两邻域的基础上设计了一种轧制序列在垛位上的邻域结构, 即Stacking邻域。这里提出的Stacking邻域不同于文献[4]、文献[5]提出的替换邻域和Sequence邻域:①替换邻域只考虑了比较匹配轧制序列中同一个轧制项目的不同钢坯所产生的倒垛次数的多少, Sequence邻域虽然进一步考虑了相邻轧制项目的连续性, 但是没有考虑一个序列对应的轧制钢坯在每个垛位上的存储情况及序列相邻或间隔提取钢坯时的可以不倒回、暂存在临时区的情况而带来的相对较少的倒垛次数;②替换邻域结构在对某个轧制项目进行寻优替换时, 其他位置保持不变, Sequence邻域相对替换邻域同时考虑了序列中相邻元素在该选中垛位上的分布情况, 主要考虑了不间断的、邻域内顺序提取钢坯不产生倒垛作业量的情况, 而Stacking邻域是在考虑有临时轧制钢坯存放区存在的前提下考虑将轧制序列作为整体去每个垛位上找最佳轧制项目, 对于序列中相邻或间隔的提取钢坯不产生倒垛作业的情况进行了充分的利用;③替换邻域结构和Sequence邻域结构对垛位上各元素不同的要求比较苛刻, 不符合实际的生产情况, 一般在一个垛位可能会存在某个轧制对象对应的多个可替换钢坯, 此时针对本文研究的钢坯存储结构, 考虑针对较优的垛位产生多个Stacking邻域集合, 为搜索算法做准备;④Stacking邻域选择的过程中综合考虑了垛位倒垛数及天车行程的因素, 因为天车的使用成本体现在障碍钢坯倒出、倒回及序列钢坯的倒出天车所走的行程中, 而Sequence邻域及替换邻域并未考虑这一重要优化目标。综上所述, Stacking邻域不仅考虑了轧制序列和轧制序列在每个垛位上分布情况, 而且考虑了一个垛位上连续提取钢坯不产生倒垛以及轧制项目连续或间断出库不需要将钢坯倒回的优势。
Stacking邻域搜索过程中, 会出现一个垛位上出现包含在轧制序列中的某个轧制对象不止一个 (即一个轧制对象同时有多个替换钢坯在一个垛位上) 的情况, Stacking邻域搜索计算倒垛数及吊车距离时, 会综合考虑每个替换钢坯生成的多个出库倒垛方案, 对比选择最优的方案进行输出。基于Stacking邻域搜索的两阶段启发式算法的求解框架如图5。
3.3 算法步骤
基于Stacking邻域搜索的两阶段算法 (Two-phase Algorithm based on Stacking Neighborhood Search, TASNS) 步骤:
Step1:初始化轧制序列及仓库垛位信息;
Step2:调用3.1节中推广算法求得问题初始解T*, 则T=T*, 令j=1, 对应轧制序列的第一个轧制项目;
Step3:构造轧制序列项目j的Sequence邻域集合Pj;
Step4:计算轧制序列Sequence邻域集合Pj对应的Stacking邻域中钢坯集合Qk及各垛位分别距离加热炉和临时存放区的距离Lk和Sk.令Stcokk为垛位选择条件值, 则Stcokk=α1 (‖Qk‖/‖Pj‖) +2- (α2 (|Lk|/UVmax) +α3 (|Sk|/UVmax) ) , 其中, α1, α2, α3分别为对应项的权重系数, 该值由钢厂的实际生产数据统计获得, 对Stcokk值进行非增排序;
Step5:选择Stcokk值最大的垛位为首选垛位, 若该垛位上出现某个轧制位置对应的多个可替换钢坯, 需要对每个替换钢坯集合进行搜索生成多个钢坯出库方案, 选择倒垛次数最少的方案, 用该方案对集合Pj中纳入该垛位的轧制钢坯进行赋值, 计算该垛位倒垛数Ck, 若Ck≤Hk且Pj-Qk=Ø, 转Step6, 若Ck≤Hk且Pj-Qk≠Ø, 转Step7, 若Ck>Hk, 转Step9;
Step6:为集合Pj中所有元素进行赋值, 计算当前最新解T′, 若T′≤T*, 令T=T′, 若T′>T*, 令T=T*, 转Step8;
Step7:若Pj中有未经以上过程赋值的变量, 则将剩余变量构造成新的集合Pj′, 令j=Pj′ (1) , 即集合Pj′中索引号最小的元素编号, 转Step3;
Step8:若j>M, 转Step10, 否则令j=j+1, 转Step3;
Step9:选择Stcokk值次优的垛位作为理想垛位, 转Step5;
Step10:输出轧制计划序列及其引起的垛位总倒垛数、吊车运行总距离。
本文设计的TASNS算法不仅融合了文献[4]、文献[5]中提出的Sequence邻域搜索算法及替换邻域搜索算法的优势, 而且考虑了实际生产中轧制序列及钢坯库垛位分布情况, 同时对吊车在吊运过程中的总行程进行了优化。算法采用原启发式算法的推广算法获得初始解, 以初始解为初始优化对象, 提高了算法的求解效率, 相对于文献[4]、文献[5]的算法与实际生产联系更加紧密。
4 实例计算与分析
4.1 测试数据
由于钢坯库垛位的复杂性, 使得倒垛量与许多随机因素有关, 如每个轧制项目对应的钢坯数量及其位置分布等。目前钢厂生产是按照合同进行生产的, 因此在连续到达的钢坯中, 同种轧制规格的钢坯往往比较集中, 即钢坯的轧制规格分布并不是完全随机的, 因此在钢坯入库堆放时需考虑将同轧制规格、同客户的钢坯存放在一个或相邻垛位中, 在设计算法时需要综合考虑轧制序列及垛位上钢坯存放的连续性等因素。根据西部某钢铁企业热轧厂钢坯库的实际轧制计划数据情况进行算法的数据模拟:①轧制序列长度∈[5, 50], 一般钢厂一个班的轧制序列长度约为40~50, 这里考虑一个班的轧制序列长度;②库容为20个垛位, 堆放钢坯规格达50种, 每种规格包含的钢坯支数∈[1, 15], 钢坯共计500支;③垛高受限, 高度不超过12层, 最上层钢坯支数不小于4, 平均层数在4~8;④同一垛位上存在同种规格钢坯连续分布的情况;⑤考虑吊车在倒垛钢坯时的行程, 这里根据实际垛位的分布情况, 以垛位到加热炉的距离为标准距离。
4.2 实验结果与分析
本文采用Microsoft Visual Studio C#编程实现了Stacking领域搜索算法的钢坯倒垛优化测试, 环境为Pentium4/1Ghz/2G/Windows XP Professional。在实验中将算法与文献[5]中的Sequence邻域搜索算法以及文献[4]中的多回路启发式算法就算法性能进行了对比, 即随着轧制序列长度的增大, 轧制序列倒垛次数及吊车运行距离的相对变化情况进行对比, 取δ1=0.63, δ2=0.37作为目标函数的两个权重系数, 采集某钢厂实际轧制生产数据进行归一化处理, 分别采用三种算法进行实验40次, 取实验结果的平均值作为比较数据。设CC*为三种算法求得的轧制序列最大平均倒垛次数、DD*为三种算法求得的吊车最长的运行距离, 则计算平均倒垛次数与天车运行距离的相对值作为对比数据, 其中, L、Cave、Dave分别代表序列的长度、平均相对倒垛次数和平均相对吊车运行距离, 实验过程中也就平均计算时间这个指标对三个算法进行了对比。对比结果见表1和表2。
由表2可知, 由于TASNS算法不仅搜索了整个序列的各个轧制项目, 还对每个垛位上的钢坯进行了多次搜索, 所以其计算时间会相对较长, 但即使在序列数达到100的情况下也能在2分钟之内完成, 这在实际生产中是可用的。
为进一步说明TASNS算法的优势, 就倒垛次数增加量对三种算法进行实验50次并取平均值, 实验结果如图6所示。
通过以上实验结果得出如下结论:
①针对钢坯库倒垛问题特点设计的TASNS算法在倒垛次数上明显优于Sequence邻域搜索算法及多回路启发式算法, 平均改进率达到53.19%, 这是因为在设计TASNS算法时, 不仅考虑了轧制序列按顺序出库的纵向制约关系, 而且考虑了轧制序列中相邻或间隔出库钢坯之间在同一个垛位上连续出库时不引起倒垛或产生较少倒垛次数的情况。此外, TASNS算法还综合考虑了尽量减少吊车的总行程, 降低了吊车的作业成本, 而另两种算法并未将降低吊车运行成本考虑进去。
②由于TASNS算法在设计过程中不仅要对每个垛位上存储钢坯进行搜索, 构造轧制序列对应的Stacking邻域, 而且还要搜索轧制序列中各元素的候选替换钢坯集合, 生成多个轧制钢坯出库方案, 再对多个方案进行比较选出最优的方案, 所以TASNS算法在运行时间上明显劣于Sequence邻域搜索算法和多回路启发式算法 (表2) , 但也能在2分钟之内完成对长度为100的轧制序列进行指派钢坯, 这在实际生产中完全可用。
③随着轧制序列的长度的增加, TASNS算法得出的倒垛数增加量变化不大 (图6) , 而其余两种算法的倒垛次数增加量变化幅度较大, 而在实际生产中应当考虑序列增加时倒垛次数增加的均衡性, 保持序列长度增加时倒垛次数的均匀增长, 确保吊车工作量的均衡变化, 不会出现由于序列长度的增加而导致骤然增加吊车工作量的情况。
5 结论
本文针对钢坯库倒垛问题进行了深入研究, 将该问题归结为一类带顺序约束的广义指派问题。建立了以最小化轧制序列出库的总倒垛次数及吊车总运行距离的多目标整数规划模型。在Sequence邻域搜索算法及多回路启发式算法基础上设计了TASNS算法, 算法充分考虑了轧制钢坯之间的制约关系和不同序列元素在同垛位上出库时直接或间接减少倒垛数的优势。通过实际生产轧制数据对三种算法分别进行验证。结果表明, TASNS算法能明显降低轧制序列出库时的总倒垛次数, 同时还优化了天车的总运行距离, 具有很好实际应用价值和推广性。
摘要：以钢坯倒垛问题为研究对象, 建立以最小化轧制序列总倒垛数和吊车运行距离的多目标整数规划模型, 并在已有的多回路启发式算法及Sequence邻域搜索算法的基础上设计了基于Stacking邻域搜索的两阶段启发式 (TASNS) 算法。算法综合考虑了入库钢坯的钢种、规格、长度等属性在垛位上具有连续堆放以及轧制轧序列之间规格相近性的特点。基于实际钢厂数据的验证, 表明算法在实际生产中是有效且可行的。
邻域搜索算法 篇3
关键词：流水车间调度,阻塞限制,变邻域搜索,分散搜索
1 引言
传统的流水车间调度问题 (permutation flowshop scheduling problem, PFSP) 由于具有较强的工业背景, 一直是生产调度领域的重点研究课题[1]。该问题通常假设相邻的机器之间具有存储能力无限的中间库, 工件的存储不受任何限制。但是, 在许多实际工业过程中, 由于需要进行连续生产, 一条生产线上的相邻工序之间经常是没有中间库的[2]。在这种情况下, 当一个工件i在一台机器j上完成加工后, 如果下一机器j+1仍处于加工状态, 那么该工件i就必须存储在当前机器j上, 直到机器j+1的状态变为空闲 (可加工工件) 为止。这样, 工件i和机器j就出现了阻塞现象。这种类型的PFSP问题通常被称为阻塞流水车间调度问题 (blocking PFSP) 。如果问题的优化目标是工件的最大完成时间 (makespan, 记为Cmax) , 那么该问题也可以表示为Fm/blocking/Cmax.近年来, 该问题逐渐受到了国内外众多学者的关注。
Hall等[3]对Fm/blocking/Cmax问题进行了综述, 并介绍了该问题在实际工业生产中的一些实例。由于该问题被证明当机器数m≥3时是NP-完全问题[4], 因此基于分支定界的最优化算法只能求解很小规模的问题, 对于大规模问题, 需要使用启发式算法或智能优化算法进行求解。
针对启发式算法, McCormick等[5]提出了一个名为PF的启发式算法, 该算法在每次迭代中都会将待调度工件插入到已得到的部分工件序列的一个位置上-使得插入后增加的机器空闲和阻塞时间之和的增加量最小。基于PF和Nawaz等[6]所提出的NEH启发式算法, Ronconi等[7]设计了PF与NEH的混合算法, 并取得了较好的结果。洪宗友和庞哈利[8]提出了一个基于折衷策略的构造启发式算法。李彦平等[9]提出了一个启发式动态规划算法。针对智能优化算法, Caraffa等[10]提出了一个改进的遗传算法求解该问题以最小化Cmax, 实验结果表明该算法比较有效, 并且其性能要优于Abadi等[11]所提出的启发式算法。Grabowski和Pempera[2]为该问题提出了一个禁忌搜索算法 (TS+M) , 基于标准问题的测试结果表明该算法要优于以往文献中性能较好的算法。Jaboui等[12]为该问题设计了一个混合分布估计算法 (hybrid estimation of distribution algorithm, H-EDA) , 测试结果表明该算法要优于文献[10]中的GA算法以及文献[2]中的TS+M算法。Liang等[13]提出了一个基于多种群的粒子群算法 (DMS-PSO) , 基于标准测试问题的结果表明该算法要优于TS+M算法。Wang和Tang[14]提出了一个基于自适应种群控制策略的离散粒子群算法, 在算法中使用变邻域搜索作为局部搜索, 结果表明算法优于TS+M算法。张其亮和陈永生[15]为该问题提出了一个改进的粒子群算法, 实验结果证明了算法的良好性能, 该算法采用迭代次数作为终止准则, 而不是以往文献中通常采用的算法最大运行时间。郭丽萍等[16]提出了一个改进的萤火虫算法求解该问题, 使用10个算例的测试结果表明了算法的有效性。
变邻域搜索 (variable neighborhood search, VNS) 是一种简单而有效的智能优化算法[17], 与传统的局域搜索算法只针对一个邻域进行搜索不同, 其思想是利用两个或两个以上的邻域, 在搜索的过程中, 算法会在不同的邻域中按照给定的规则交替进行搜索。由于邻域结构不同, 在某一邻域内的局部最优解在其它邻域就可能不是局部最优解, 从而帮助算法跳出局部最优, 增强算法的广域搜索能力。VNS算法已经广泛应用于求解各类组合优化问题, 并取得了较好的结果[18]。分散搜索 (scatter search, SS) 是一种基于种群的方法[19], 其思想是从种群中选取质量较好和分散性较好的解组成参考集, 利用参考集来生成下一代的种群, 以增强算法的广域搜索能力。该算法已经在许多组合最优化问题中得到了成功的应用, 例如车辆调度问题[20]和生产调度问题[21]。
因此, 本文将VNS算法与SS算法根据各自的特点进行混合, 提出一个分散变邻域搜索算法 (scatter VNS, SVNS) , 并设计了基于工件块的邻域搜索, 以实现Fm/blocking/Cmax问题的高效求解。
2 Fm/blocking/Cmax问题描述
Fm/blocking/Cmax问题可以描述为:有n个待加工工件{1, 2, …, n}需要在m个机器{1, 2, …, m}上进行加工。主要的约束条件包括:①每个工件i都必须从第1个机器开始, 依次经过这m个机器进行m道工序的加工, 即各工件的加工顺序相同;②工件一旦开始加工, 其加工过程不可中断;③每个机器一次最多只能加工一个工件;④工件在当前机器加工完成后, 只有当下一机器空闲时才能离开当前机器到达下一机器进行加工, 在下一机器空闲之前的时间内, 该工件及当前机器都被阻塞。
设工件i在机器j上的处理时间表示为pij;s= (s (1) , s (2) , …, s (n) ) 表示一个工件加工序列, 其中s (k) 表示排在第k个位置上的工件号;工件s (k) 在机器j上的离开时间 (记为Ds (k) , j) 可以由以下公式计算:
那么所有工件的最大完成时间makespan就可以定义为Cmax (s) =Ds (n) , m.
3 基于分散搜索和变邻域搜索的混合SVNS算法
3.1 传统的VNS算法
如前所述, VNS算法主要是基于某一邻域内的局部最优未必是其它邻域内的局部最优这一客观事实, 通过不断变换邻域类型, 实现解的不断改进, 从而帮助算法跳出局部最优, 接近或达到全局最优解。
传统VNS算法的流程见图1。算法首先产生初始解s, 然后在每一次迭代过程中, 都是按照给定的邻域顺序进行搜索。内循环中的搜索主要包括三个过程:①Shaking:在当前解s的邻域Nk内随机产生一个新解s′;②Local Search:对这个新解s′进行局域搜索;③Move or not:根据局域搜索后的改进解s″是否能更新当前解s, 决定是否切换邻域。
3.2 SVNS算法
在图1所示的传统VN算法中, Shaking过程主要用来帮助算法跳出局部最优, 但是经过Shaking过程所得到的解s′的质量如果很差, 那么即使对其进行局部搜索后, 所得到的改进解s″通常很难优于解s, 从而导致无效搜索的情况。为了避免这种情况, 本文将分散搜索中的参考集R引入到VNS算法中来, 提出了分散变邻域搜索算法, 即SVNS.在算法中, 参考集R用来存储VNS算法搜索过程中所得到的质量和分散性较好的解。Shaking过程变为从参考集R中选取质量和分散性较好的解, 来生成新解s′, 从而使得新解s′既能够具有良好的质量, 又能够兼顾分散性, 同时避免了传统VNS算法容易出现无效搜索的情况。
此外, 在邻域结构的设计上, 传统VNS算法针对PF-SP问题, 通常采用基于insertion移动 (从一个工件序列中删除一个工件并将它插入到工件序列的其它位置上) 和swap移动 (交换工件序列中两个相邻或不相邻的工件) 的邻域结构。Bozejko等[22]指出, 针对以工件序列作为解的生产调度问题, 复合移动 (即一次执行多个insertion或swap移动) 的性能要优于这两个简单移动, 其原因是复合移动的邻域规模更大, 其能够达到的搜索空间也更大。因此, 本文提出了基于工件块的邻域结构, 其邻域规模能够根据工件块的大小进行变化。在所提出的SVNS算法中, 邻域规模按照从小到大进行变化, 从而实现在兼顾局域搜索能力的前提下, 提高算法的广域搜索能力。
基于以上所提出的改进策略, 本文所提出的SVNS算法的流程如图2所示, 其中N1, N2, …, Nk表示工件块大小分别为1, 2, …, k时的邻域。从图2中可以看出, 与传统VNS相比, 本文所提出的SVNS算法的特点主要是:①使用分散搜索的参考集R来产生VNS搜索的初始解, 而不是在当前的邻域Nk内随机产生一个解;②参考集R的更新机制中同时考虑了解的质量和分散性;③局域搜索基于当前的邻域Nk, 其规模可以不断增大。在本文的以下部分, 将对图2中各部分进行详细介绍。
(1) 初始解产生方法
对一般的PFSP问题, NEH方法[6]能够获得高资量的初始解, 本文采用NEH方法来产生Fm/blocking/Cmax问题的初始解, 然后再对该解执行局部搜索。该算法的过程可以描述如下:
Step1:按照各工件在所有阶段的处理时间之和的非增顺序把所有的n个工件排序, 并设得到的序列为x= (x (1) , x (2) , …, x (n) ) 。
Step2:从这个序列中取出前两个工件x (1) 和x (2) , 并假定只有这两个工件要进行加工, 然后确定这两个工件的最优排序, 假定为x′= (x′ (1) , x′ (2) ) 。
Step3:将工件序列x中的下一个工件插入到前面所得到的部分解x′的最好位置上 (该位置能使得目标函数的增加量最小) 。重复这一过程直到所有的工件都被插入到x′中, 从而得到一个初始解。
Step4:对得到的初始解使用N1邻域进行局域搜索。
(2) 参考集的更新
为保证参考集R (其大小为b) 中的解能够具有良好的质量和分散性, 提出了以下的更新策略。针对VNS搜索过程中由局部搜索得到的改进解s″, 如果参考集R中解的个数未达到b, 则直接将其加入到R中。如果参考集R中解的个数已经达到b, 则需要判断解s″是否达到可插入到R中的条件, 即是否满足 (Cmax (s″) -Cmax (sworst) ) /Cmax (sworst) ≤a, 其中sworst表示参考集R中质量最差的一个解, a是一个给定的门槛值。若解s″满足加入条件, 即该解的质量在可接受的范围内, 则先将解s″插入到R中;然后再将参考集R中分散性最差的解删除 (不包括当前最好解) 。
在此, 给出解的分散性的定义, 即该解与集合R中其它解之间的最小距离。两个解s1= (s1 (1) , s1 (2) , …, s1 (n) ) 与s2= (s2 (1) , s2 (2) , …, s2 (n) ) 之间的距离定义为, 其中当s1 (j) ≠s2 (j) 时, sgn (j) =1;否则sgn (j) =0。当两个解的分散性指标相等时, 删除质量较差的那个解。
(3) 从参考集中产生解
在图2所示的Shaking过程中, VNS搜索的起始解s′从参考集R中随机选择。但是, 每个解的选择概率不是相等的, 而是由每个解已经被选择进行局域搜索的次数, 以及进行搜索后是否得到更好解的结果来决定的。在算法中, 记录参考集R中每个解si已经被选择进行局域搜索的次数seli, 当一个新解加入到R中时, 该次数为1 (为了防止计算过程中出现除以0的情况) 。
初始情况下, 每个解的选择概率相同;如果某一个解si被选择进行局域搜索, 而得到的改进解未能进入参考集R中, 则seli=seli+1;否则, 将维持seli不变 (因为对该解的搜索结果是可以接受的, 说明继续对其进行搜索有较大可能获得更好的解) 。根据seli, 可以得到b个解的选择概率:
其中.从该式中可以看出, 解si被选择的次数越多并且其改进解进入R中的次数越少, 那么该解的选择概率就会越小。从而保证局域搜索只针对搜索质量较好的解进行, 避免无效搜索。
(4) 基于工件块的邻域搜索
基于工件块的邻域属于复合移动型邻域, 在执行一次基于工件块的移动来产生一个新的邻域解时, 针对的是工件块内的多个工件。该移动的思想是首先从解 (一个工件序列) 中删除一个由相邻的k (k≥1) 个工件构成的工件块, 然后从该工件块中的第一个工件开始, 依次将其插入到原工件序列的最好位置上 (即使目标函数的增加量最小) 。
针对一个给定的解s= (s (1) , …, s (n) ) , 基于大小为k的工件块的邻域 (该邻域记为Nk) 搜索过程可以描述如下:
Step1:设置邻域搜索的迭代次数l=1, 设置最好解sb=s.
Step2:随机删除s中k个相邻的工件, 并假设被删除工件的顺序记为s (d1) , s (d2) , …, s (dk) , 剩余工件所组成的部分解记为s′.
Step3:令j=1。
Step4:将s (dj) 插入到s′中最好的位置上 (即插入到该位置上后目标函数的增加量最小) 。
Step5:令j=j+1。如果j≤k, 转Step4;否则, 得到一个新解s′, 转Step6。
Step6:如果Cmax (s′) <Cmax (sb) , 则令s=sb=s′.
Step7:令l=l+1。如果l≤lmax (最大迭代次数) , 转Step2;否则停止, 输出sb.
从以上描述可以看出, 针对邻域Nk的搜索不是对整个邻域进行全搜索, 而是随机进行lmax次搜索, 其复杂度为O (lmaxkn) 。这是因为基于工件块的移动比较复杂, 针对该邻域的全搜索需要消耗大量的计算时间。经过实验, 发现对于小规模问题进行lmax=10次搜索, 对于大规模问题进行lmax=20次搜索已经可以得到比较好的结果。此外, 在SVNS算法中, 按照邻域从小到大的顺序进行搜索, 即按照N1, N2, …, Nk的顺序, 以保证搜索的深度逐步增加, 邻域的规模逐渐变大, 从而兼顾局域搜索和广域搜索的平衡。经过实验, 在算法中k取值为5, 即最大的邻域为N5.由于lmax和k要远小于工件的数目n, 因此该邻域搜索的复杂度并不会超过针对传统insertion和swap邻域的全搜索, 二者的全搜索复杂度为O (n2) , 从而保证了在SVNS算法中使用这种类型的邻域搜索的效率。
4 实验结果
本文使用Taillard[23]所提出的PFSP问题的标准算例对所提出的SVNS算法进行了测试, 并将其结果与当前文献中性能较好的算法进行了比较。这些标准算例中包含12个规模, 每个规模中包含10个算例。其中, 工件数从20个到500个, 机器数从5台到20台。
本文所提出的SVNS算法使用C++语言实现, 并在CPU为Intel Core i3-540 (2.8GHz) , 内存为4GB, 操作系统为Windows XP的个人计算机上进行了测试。算法的停止准则取为最大运行时间Tmax=m×n×0.01秒。算法相关参数设置如下:参考集R的大小为10, 工件块最多由5个工件组成, 邻域搜索中的最大迭代次数为10 (针对工件数小于等于50的问题) 或20 (针对工件数大于等于100的问题) 。
为了与其它算法进行比较, 对每个算例分别进行R=10次独立测试, 计算最小相对偏差 (minimum percentage relative difference, minPRD) 与平均相对偏差 (average percentage relative difference, APRD) 。解的相对偏差计算公式为PRD=100× (Cmax (s) -Cmax (RON) ) /Cmax (RON) , 其中s和RON分别表示算法所得到的解以及文献[24]中给出的解。
4.1 嵌入参考集的性能测试
为了测试嵌入分散搜索的参考集对于算法性能的影响, 本节对所提出的SVNS算法以及在SVNS算法中去掉参考集后所得到的VNS1算法进行了对比测试, 结果如表1所示 (本文所列出的表中最好的结果均加粗显示) 。从表中的结果可以看出, 加入参考集后算法的性能得到了明显的改进, 这是因为参考集的加入提高了算法跳出局部最优解的能力, 从而帮助算法搜索到质量更好的解。
4.2 与其它算法的性能比较
为了证明算法的有效性, 将SVNS算法其与文献中已有的性能较好的算法进行了比较, 主要包括TS+M[2], H-EDA[12], DMS-PSO[13]。各算法的实验结果如表2所示, 表中其余三个算法的结果为相应文献中给出的结果值。从结果中可以看出, 针对APRD, H-EDA算法和本文所提出的SVNS算法均取得了最好的结果;而针对minPRD, 本文所提出的SVNS算法则取得了最好的结果, 并且均要优于H-EDA算法。除100×20和500×20两组算例之外, SVNS算法的性能针对APRD和minPRD均要优于DMS-PSO算法。
表3给出了各算法所获得的最好解, 由于文献[13]中没有给出该结果, 因此这些表中只给出了TS+M、EDA、和SVNS这三个算法的结果对比。从表中可以看出, 本文所提出的SVNS算法针对73个问题获得了更好的解。
5 结论
邻域搜索算法 篇4
1988年,Barnsley等人首次引入了迭代函数系统(IFS,Iterated Function Systems)来描述自然界中物体的自相似性,并将其应用于图像压缩[1]。1990年,Jacquin突破了IFS的局限,提出了局部迭代函数系统(PIFS,Partitioned Iterated Function Systems),指出一个图像不应该认为是整个图像的变形拷贝和粘贴,而应该是图像的小部分的变形拷贝和粘贴,并在此理论基础上提出了一种基于方块划分的分形图像压缩方案[2],使分形图像压缩从人工编码到自动编码成为现实。此方法具有压缩比高,解码速度快以及解码图像与分辨率无关等优点,但编码时间长、高压缩比时解码图像质量不高等缺点限制了它的广泛应用和进一步发展。针对上述问题,许多学者提出了改进方案[3,4,5,6,7]。
本文提出了一种基于HVS分类及邻域搜索的快速算法,通过减少需要搜索的子块数和子块搜索的父块数节约了编码时间。实验表明:尽管图像质量与基本分形算法相比有所下降,但该算法的编码时间大大减少。
2 基本分形图像压缩算法
2.1 基本分形编码
Jacquin提出了基于图像划块方式的全自动分形图像压缩方法。首先将图像分割成若干子块和父块,接着对每个子块寻找某个父块,使该父块经过某个指定的变换映射后与此子块最相似,记录下该父块的位置参数及变换,作为此子块的分形码。所有子块的分形码构成了整个图像的分形码。
在描述算法之前先定义度量子块与父块之间误差的公式。设A为r×r大小的子块,B为2r×2r大小的父块,则B经变换映射后与A的误差为:
其中,||·||是二维范数符号;I是灰度值均为1的大小为r×r的块。变换映射是以下三种变换的合成:
1)几何变换准:几何变换主要用于对父块进行空间压缩,使压缩后的父块和子块具有相同的尺度,一般采用四邻域平均法。对于父块B,令其灰阶函数为{Bi,j:i,j=0,…,2r-1},则几何变换的计算公式如下:
2)8种等距变换{Tn:n=0,1,…,7}:Jacquin提出了8种等距变换,使父块经等距变换后与子块尽可能具有相近的灰度分布。对于大小为r×r的图像块u,设它的灰阶函数为(μi,j:i,j=0,1,…,r-1),则其对应的8种等距变换如表1所示。
3)灰度变换G:灰度变换是一种线性变换。对于某图像块D,有G(D)=sD+gI,其中s为比例因子,g为灰度偏移量。s和g的求取可采用最小二乘法:
其中,A和B分别是A和B的均值,<·,·>是矩阵内积符号。求出的s不一定满足s≥0,为了确保渐进收敛性和压缩比,需要对s进行截断和量化处理。本文采用的量化截断方法如下[5]:参数s按5bit量化,g按7bit量化。若s≥0,则取s=31/32;若s<0,则s=0。若g>127,则g=127;若g<0,则g=0。将量化截断后得到的?s和?g代入式(1)求误差。
综上,基本分形图像编码算法描述如下:
Step1将M×M大小的原图X分割成NR个r×r大小的子块{R1,R2,…,RNR},满足且Ri∩Rj=准,坌i≠j(i,j∈{1,2,…,NR})。
Step2按水平步长Δh和垂直步长Δν将原图分割成ND个可重叠的2r×2r大小的父块{D1,D2,…,DND},满足,所有父块就构成了码本。
Step3对每一个子块Ri,在码本中搜索最优匹配父块Dm,即搜索使E(Ri,Dm)最小的父块Dm,搜索时对各父块进行8种等距变换。
Step4记录分形码:记录使E(Ri,Dm)最小的s赞、g赞、等距变换号tn以及最优匹配父块Dm的位置(dx,dy),进而得到子块Ri的分形码(dx dy,tn,s赞,g赞)。转Step3。
2.2 图像解码
解码时,用求得的局部迭代函数系统PIFS的吸引子来近似原始图像。具体做法如下:以与原始图像相同大小的任意灰度图像作为初始解码图像,根据分形码,对每个子块,用其最优匹配父块的变换映射去代替,反复迭代至收敛。一般迭代8次后基本收敛,此时得到的图像即为解码图像。
3 改进算法
在基本分形图像编码算法中,每一个子块都必须在全局码本中搜索最佳匹配父块,并且在搜索时需对每个父块进行8种等距变换,相当于码本数扩大了8倍,可见搜索量相当大,直接影响了编码速度。如果能减少需要搜索父块的子块数或者减少子块搜索的父块数,均可节约编码时间。基于上述分析,本文提出了一种快速分形图像编码算法。
首先,为了减少需要搜索父块的子块数,将子块分为两类:平滑类子块和非平滑类子块。其中,对于非平滑类子块,需要搜索匹配父块;对于平滑类子块,直接存储其均值,无需搜索匹配父块,从而减少了需要搜索父块的子块数目。分类方法采用文献[6]中所提到的根据HVS特性进行分类的方法。研究表明,在灰度图像中,如果相邻像素点的灰度相差不大,即使其包含丰富的信息,人眼也无法从图像中提取相应的信息,因为人眼分辨灰度的能力较差,一般只有几十个数量级。因此,利用此HVS特性对子块进行分类,当子块内像素灰度的最大值与最小值之差小于平滑性阈值H时,被划分为平滑类子块,否则为非平滑类子块。
其次,许多研究表明,大部分子块的相似区域就在其周围,所以大部分子块在其周边邻域内的父块中即可搜索到较优的匹配父块。因此,非平滑类子块在搜索匹配父块时,从离自身最近的父块开始向外搜索。子块在其邻域内搜索父块的顺序与文献[7]类似。另外,本文提出如下假设:某父块与某子块越相似(误差越小),则二者的标准差越接近;反之,如果标准差相差较大,则此父块是该子块的较优匹配父块的概率较小。实验结果已验证了上述假设的合理性。基于上述假设,规定当子块搜索到某个父块时,先计算子块和该父块标准差的近似度S(R,D),如果S(R,D)大于等于预先设定好的近似度阈值T,则剔除此父块,继续搜索下一个父块。近似度S(R,D)的定义如下:
其中,R和D分别为子块R和父块D的均值。另外,本文引进误差阈值E来控制子块的搜索过程。子块在搜索到某父块时,若与该父块的匹配误差小于给定的误差阈值E则停止搜索,否则继续搜索。然而,某些子块即使进行全局搜索,得到的最小误差也未必会小于E,为节约编码时间,本文限制子块搜索父块的最大次数为k。
根据上述思想,本文快速算法的具体编码过程如下:
Step1设定子块边长r、分割父块时的水平步长Δh和垂直步长Δν、平滑性阈值H、近似度阈值T、误差阈值E以及子块搜索父块的最大次数k。
Step2将原图X分割成互不重叠且覆盖原图的大小为r×r的子块{R1,R2,…,RNR},并按步长Δh和Δν分割成相互可重叠的2r×2r大小的父块{D1,D2,…,DND}。
Step3对每个子块Ri,计算该子块内最大灰度值与最小灰度值之差,记做Δf。
Step4若Δf
Step5若Δf≥H,则为非平滑类子块,从离自身最近的父块开始向外搜索。每搜索至某个父块时,先计算当前子块和该父块的近似度S(Ri,Dj)。若S(Ri,Dj)≥T,则终止对该父块的搜索过程,继续搜索下一个父块;否则计算父、子块的误差E(Ri,Dj)。若E(Ri,Dj)
解码方法与基本分形算法的解码方法相似,对于平滑类子块直接用存储的均值代替,对于非平滑类子块,用其局部最优匹配父块的变换映射去代替,迭代8次后得到最终的解码图像。
4 实验结果与分析
实验对象为256*256*8bit的peppers图像,实验环境为Pentium Dual CPU 1.73 GHz,768MB内存,用VC++6.0编程。测试性能参数为PSNR(单位:dB)、主观图像质量、编码时间(单位:s)。在实验中,均设置子块大小r=4,划分父块时的步长Δh=Δv=4。
本文快速算法的性能主要受以下参数的影响:
1)平滑性阈值H
H的取值直接影响了非平滑类子块的数目。H越大,非平滑类子块数越少,即需要搜索匹配父块的子块数越少,则编码时间越短;反之,H越小,非平滑类子块数越多,即需要搜索匹配父块的子块数越多,则编码时间越长。表2给出了参数H取不同值时的实验数据(T=20,E=30,k=80)。实验表明,随着H的增加,非平滑类子块数逐渐减少,编码时间逐渐减少,而PSNR先随着H的增加而增加,在H=10附近最高,然后随着H的增加反而降低。另外,当H>20时,解码图像有较为明显的方块效应。综合考虑,在后继实验中,固定H的取值为10。
2)误差阈值E及子块搜索父块的最大次数k
E越大,子块就能越快找到满足误差要求的父块,编码时间越短,但图像质量越差;反之,E越小,编码时间越长,图像质量越好。k越小,子块搜索的最大父块数越少,从而编码时间越短,但图像质量越差;反之,k越大,编码时间越长,图像质量越好。因此,若要求解码图像质量较高,则E应取小些,k取大些;若要求编码时间较短,则E应取大些,k取小些。
3)近似度阈值T
T的取值影响是否从码本中剔除当前父块,从而决定了当前子块可搜索的码本数。T的取值越大,某父块与子块满足近似度要求的可能性越大,即该父块被从码本中剔除的概率越小,则当前子块可搜索的码本数越多;反之,T的取值越小,某父块与子块满足近似度要求的可能性越小,即该父块被从码本中剔除的概率越大,则当前子块可搜索的码本数越少。
为了体现利用近似度来剔除部分父块这一思想的贡献,将本文快速算法中去除近似度限制的算法称为算法1,并对该算法进行了编码、解码实验。表3给出了基本分形算法、算法1以及本文快速算法对peppers图像进行测试的实验数据。其中,本文快速算法和算法1中平滑性阈值均取值为10,则此时本文快速算法受参数E、k、T控制,算法1受参数E、k控制。
通过对比表3中的前3组实验数据,可以看出,在相近编码时间的前提下,本文快速算法的PSNR比算法1高出0.6dB左右,从而说明了利用近似度来剔除部分父块这一思想的有效性。另外,与基本分形算法相比,在牺牲一定图像质量的情况下,本文快速算法可获得较快的编码速度。
图1中的(a)、(b)分别给出了基本分形算法和本文快速算法取表3中第一组参数时的解码图像,从主观图像质量来看,本文快速算法的解码图像质量不如基本分形算法,但此时本文快速算法的编码速度比基本分形算法快671.4倍,在某些实时性要求较高、图像质量要求相对较低的场合,该算法将会具有较好的应用前景。
5 结论
本文提出了一种基于HVS分类及邻域搜索的快速分形图像编码算法。首先,根据HVS特性将子块分为平滑类子块和非平滑类子块,其中平滑类子块无需搜索匹配父块,从而节约了编码时间。其次,非平滑类子块在其邻域内搜索父块时,并非在全局码本中搜索,而是先根据与子块的近似度剔除部分码本。此外,本文还使用误差阈值和子块搜索父块的最大次数来控制子块搜索的过程,从而大大降低了搜索量,节约了编码时间。实验结果验证了本文快速算法的有效性:与基本分形算法相比,尽管解码图像质量有一定的下降,但编码速度大大提高。在某些实时性要求较高,而对图像质量要求相对较低的场合,该算法有较好的应用前景。
摘要：针对基本分形图像编码算法时间过长的问题,提出了一种基于HVS分类及邻域搜索的快速算法。根据HVS特性将子块分为平滑类子块和非平滑类子块,对于平滑类子块直接存储其均值,以减少需要搜索匹配父块的子块数;对于非平滑类子块,从离其最近的父块开始搜索,在搜索父块时,剔除与当前子块的近似度不满足要求的父块,并引入误差阈值和搜索父块的最大次数来控制子块的搜索过程。实验结果证明,该算法大大提高了编码速度。
关键词：分形,图像编码,分类,邻域
参考文献
[1]BARNSLEY M F,SLOAN A D.A better way to compress image[J].Proceedings of the National Academic of Science,1988(1):215-223.
[2]JACQUIN A E.Image coding based on fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Pro-cessing,1992,1(1):18-30.
[3]WANG Xing-yuan,WANG Shu-guo.An improved no-search fractal image coding method based on a modified gray-level transform[J].Computers and Graphics,2008,32(4):445-450.
[4]TAMáS KOVáCS.A fast classification based method for fractal image encoding[J].Image and Vision Computing,2008,26(8):1129-1136.
[5]何传江,杨静.基于形态特征的快速分形图像编码[J].中国图像图形学报,2005,10(4):410-414.
[6]郑运平,陈传波.一种基于新型四叉树的快速分形图像压缩算法[J].小型微型计算机系统,2007,28(6):1465-1469.
邻域搜索算法 篇5
在图像测量中, 常对图像的边界进行跟踪提取, 得到目标区域的边缘坐标点, 从而获得目标区域的面积和周长等信息, 而目标区域的这些信息是识别目标的一个非常重要的特征, 需要根据目标区域的面积、周长等相关特征识别目标。因此, 目标区域面积及周长的精确计算对准确识别目标区域具有十分重要的意义。
针对任意封闭区域几何参数的测量, 人们做了大量的研究工作[1,2,3,4,5]。在文献[6]中, 采用Freeman链码来计算图像中多个区域面积, Freeman轮廓跟踪时需要对每个边界像素 (8个点邻域点) 进行判断, 计算时间较长;文献[7]中提出的方法, 首先利用边界点的前级矢量与次级矢量判断出边界内像素, 然后, 将边界内像素总数与边界像素总数相加, 所得总和再乘像素面积得到测量区域的面积, 此方法是一种简单、可靠、有效的方法, 但计算方法比较复杂, 计算量比较大, 不实用。针对上述问题, 本文提出了基于八邻域跟踪的目标区域几何参数测量方法, 该方法边缘跟踪速度快、算法实现容易、计算结果较准确。
1 八邻域跟踪
轮廓跟踪的方法主要有扫描线轮廓法、Freeman链码表示法[8]和八邻域法等。扫描线轮廓法简单, 容易实现, 就是逐行按列对图像进行扫描, 每找到一个目标点就记下该点坐标, 该方法提取的轮廓信息不是按轮廓的顺序记录, 且效率较低, 并对后续的数据处理造成困难, 一般很少采用此方法做跟踪测量。Freeman链码表示法是用中心像素指向它的八邻域点来定义的, 轮廓的跟踪根据链码的方向进行, 虽然, 避免了对所有像素点的扫描, 使轮廓跟踪效率得到了一定的提高, 但是需要对每个边界像素周围的8个点进行判断, 计算量仍比较大。因此, 为提高跟踪效率、减少运算时间, 本文采用八邻域轮廓跟踪方法对目标边缘进行轮廓跟踪。
在图像处理中, 图像上某个像素的点有8种可能的方向点与其相接, 如图1所示, 将这8个方向链码分别命名为1、2、3、4、5、6、7、8, 分别表示像素点的正右方、右上方、正上方、左上方、正左方、左下方、正下方、右下方, 如图2所示。
为了对目标区域边界进行编码, 首先设定目标区域为二值图象, 设前景为“0”, 背景为“1”。选如图3所示为目标边界, 对其作八邻域跟踪, 其步骤如下: (1) 按照从左到右、从下到上的扫描方式对目标区域边缘像素点进行搜索检查, 将最先检查出来的黑色像素点作为轮廓跟踪的第一个轮廓点O, 若在图像中搜索不到黑色像素点, 则搜索结束; (2) 从轮廓起始点O开始, 以O像素点正右方 (即‘1’方向) 作为初始搜索方向进行搜索, 如果‘1’方向的点是黑点, 则为轮廓点, 否则搜索方向顺时针旋转45°, 即搜索方向值减1, 如此继续搜索, 一直到找到黑色像素点为止; (3) 记录该黑点的坐标, 并将其作为新的搜索起始点, 在当前的搜索方向基础上逆时针旋转90°, 即搜索方向值加2; (4) 用同样的方法继续搜索下一个黑色像素点, 直到返回到第一轮廓点O。
由于理论上轮廓是连续的, 因此在O像素点八邻域方向中肯定能搜索到黑色像素点, 而且也只有在这个方向上才可能有轮廓像素点存在。
为验证上述八邻域跟踪算法的跟踪效果, 取CT扫描得到的汽车轮毂切片外边界为跟踪对象, 进行边界跟踪处理, 如图4所示。
由图4可知, 用本文的八邻域跟踪算法可以有效、准确地跟踪出轮毂边界, 跟踪后得到一系列有序连续的边界坐标点, 再利用几何计算公式, 计算得到目标区域的周长和面积。测量流程图见图5。
2 周长和面积的计算
在目标区域的测量中, 常用像素累加法, 该方法首先在二值图像上进行轮廓跟踪得到目标的边界, 对边缘进行排序, 并得到每个边缘点的方向, 以确定计算周长时所乘的系数。依次累加乘以系数以后的边缘点, 便得到目标的周长, 累加像素目标区域得到面积。但此方法计算耗时、精度低, 受像素的分辨率及边缘提取算法的精度限制。因此, 本文提出用格林公式和欧式距离公式计算目标区域的面积S和周长L。欧氏距离公式为:
格林公式为:
公式 (2) 经离散化后为:
其中:N为黑色像素点数。
3 实验结果与讨论
为了验证本文方法的测量精度, 构造一幅164×164像素的仿真圆, 如图6所示。圆的直径D为108像素, 圆面积S=π (D/2) 2=9 156.24 (像素) 2, 周长L=πD=339.12 (像素) 。采用本文的八邻域跟踪算法对该仿真圆边缘进行跟踪, 得到一系列的有序边缘坐标点 (图6 (b) ) ;再利用欧式距离公式和格林公式计算仿真圆的周长和面积, 见表1。
从表1可知, 采用本文的测量方法测量精度较高, 测量误差小。
4 结论
周长和面积的计算在目标识别和图像分析中运用广泛, 本文所提出的基于八邻域跟踪算法的任意形状封闭区域几何尺寸测量方法, 可以实现任意封闭单连通区域的测量。然而, 本测量方法只能测量单连通区域的几何参数, 如何在保证测量精度的前提下, 实现多连通区域的测量是下一个研究的重点。
摘要：提出了基于八邻域跟踪算法的任意形状封闭区域几何尺寸测量, 首先对目标图像进行二值化, 然后再利用八邻域跟踪目标区域边缘得到目标边缘坐标点, 最后根据欧氏距离公式和格林公式计算目标区域的周长和面积。该方法实现容易、计算结果准确、测量精度较高, 为图像的进一步分析提供了依据。
关键词：模式识别,图像处理,几何测量,边缘跟踪
参考文献
[1]党宏社, 洪英, 郭琴.基于图像处理的不规则形体面积测量系统的实现[J].计算机测量与控制, 2010 (7) :1507-1511.
[2]高荣华, 张有会, 曹清洁.顶点链码表示区域的面积计算[J].计算机应用与软件, 2005, 22 (8) :106-108.
[3]牛珂, 何东健.基于图像处理的植物叶片参数测量系统[J].农村经济与科技, 2011 (6) :205-206.
[4]陈优广.边界跟踪、区域填充及链码的应用研究[D].上海:华东师范大学, 2006:18-32.
[5]王厚大.一种计算任意封闭形状面积的方法[J].南京邮电学院学报, 1997, 17 (4) :23-25.
[6]吴元敏.基于Freeman链码的图像中多个区域面积的计算方法[J].计算机工程与应用, 2008 (15) :199-201.
[7]李祥林, 李月卿, 王昌元, 等.一种基于矢量分析的图像面积测量方法[J].泰山医学院学报, 2002 (1) :23-25.
邻域搜索算法 篇6
随着市场需求的多样化和个性化,能以较低成本快速响应市场需求的可重构制造系统(RMS)得到广泛关注[1]。布局设计问题是已知负载流量,根据给定系统可能的分布位置,确定各个工作站在车间的位置分布,以使得总物流成本最小化[2]。在可重构制造环境下,需要快速改变系统的构形,以适应不断变化的生产需求,对布局问题的求解时间和求解质量提出很高的要求。Meng等[3]提出可重构布局问题。本文针对基于AGV的RMS的布局设计要求,综合考虑AGV空载和负载路程,提出高效、求解质量高的变邻域遗传算法。
1 布局设计问题模型
本文作如下假设:每个工作站s有一个加载点Ps和一个卸载点Ds;车间中可分配的位置数量与待分配的工作站数量相等,每个位置只能分配一个工作站。AGV在工作站之间的路径段可双向行走。工作站w到工作站u之间的负载流量fwu给定,Ps、Dt之间的最短路径长度为LPs Dt,工作站的单位重构成本为CR,系统上一生产周期的初始布局为H0ws。工作站w到工作站u之间的空载流量为fEwu。
决策变量为Hws。假如工作站w分配到位置s,则Hws=1,否则为0。
布局设计问题的目标是最小化包括物流路程和工作站重构成本在内的总物流成本J:
其中∆w为工作站w是否重构的指示变量:
需要满足以下的约束条件:
位置约束:
流量约束:
布局设计问题是一个复杂的非线性规划问题,最优化方法难以求解大规模的问题,这里采用启发式方法:遗传算法(GA)。针对一般GA局部搜索能力的不足,提出变邻域遗传算法(VNS/GA)。
2 变邻域遗传算法
GA是一种有效的启发式方法,得到广泛应用[4,5]。GA方法是并行搜索,可以得到多个不同的较高质量的解,但是局部搜索能力较差,为此借鉴文献[5]的方法,在局部搜索中增加变邻域(VNS)搜索策略。根据GA的一般设计步骤,设计如图1所示的处理过程。
1)染色体编码
GA的个体编码采用工作站排序编码的方法,编码长度等于工作站的数量NW。某个编码为:π=(Wi1,Wi2,,WiNW),表示在位置Sk上分布的工作站为Wik。假设种群数量为Np,则种群可以表示为Π=(π1,π2,,πNp)。
2)适应度值计算
根据个体染色体编码计算其对应的总物流成本,将总成本的倒数作为个体的适应度值。
3)交叉操作
染色体的交叉采用部分映射交叉的方法。在选定的两个位置中间的基因,其排序按照另一个体中的基因排序。
4)变异操作
变异采用随机选择染色体的两个位置,交换这两个位置上的基因。
5)选择操作
根据适应度值按轮盘赌的方式选择个体。
6)小生境淘汰运算
比较个体编码之间的相似度,对编码距离较小的个体,其中适应度值更小的个体进行一定的排挤,即小生境淘汰运算。这为了产生较多的相异个体,避免种群过早收敛。
7)变邻域搜索
由于GA的局部搜索能力较差,采用VNS局部搜索策略对产生的个体进行局部搜索,以提高解的质量。为了降低搜索时间,以一个较小的概率pv对个体进行搜索。
编码πi与πj之间的海明距离Hπ(πi,πj)定义为不同放置不同工作站的位置数量。对于一个编码π,其邻域定义为:
对某编码πi的VNS搜索过程如下:
(1)初始化:根据海明距离定义邻域结构Nk,k=1,,kmax,设置局部搜索次数LSIt为停止条件。
(2)设置初始解为π=πi,令l=0。
(3)令k=1。
(4)随机生成一个解。
(6)if k≤kmax转Step 4。
(7)if l
(8)Setπi=π;
返回πi。
8)停止条件
完成一定进化代数Ng后停止。
9)参数设置
GAL算法的主要参数有:进化代数Ng,种群数量Np,交叉概率pc,变异概率pm,小生境参数h,变邻域搜索参数kmax,pv。经过一定尝试,将各个参数设置为:Ng=150,Np=20,pc=0.8,pm=0.2,h=max([1,NW/8]),kmax=[NW/3],pv=0.1。
3 计算实例
为了验证所提出方法的效果,设计了工作站数量分别为9和15的两个计算实例。实例1采用穷举方法得到最优解。而实例2由于规模较大,不能得到最优解,只给出GA方法的运行结果。
对每个实例,首先假设在初始生产周期,在给定的初始负载流量表(称为流量表1)情况下,不考虑工作站重构成本,进行初始布局设计。然后假设系统在初始布局情况下,在新的生产周期,根据新的生产任务得到新的负载流量表(称为流量表2),进行新的生产周期的布局设计,这时需要考虑工作站的重构成本,针对不同重构成本进行算例的比较分析。
1)实例1
本实例的工作站数量为9,各位置布局如图2所示,流量表1如表1所示,流量表2如表2所示。首先采用穷举法,得到各种设置情况下的最优解,然后GA方法分别10次,以得到平均物流成本和平均计算时间。本实例两种方法的计算结果如表3所示。
计算结果分析:穷举法的计算时间明显比GA方法更长。在不同的工作站单位重构成本条件下,有不同的最优布局。GA方法在各种设置下都能得到最优解。
2)实例2
本实例的工作站数量为15,系统位置布局为3行5列的格子布局,同样根据不同流量表进行布局求解。由于本实例的工作站数量较多,无法用穷举法求得最优结果,所以只给出GA方法的结果,如表4所示。
BMHC为最优物流成本,CT为计算时间,AMHC为平均物流成本,ACT为平均计算时间,DTB为与最优物流成本的差距(百分比),DTB=(AMHC-BMHC)/BMHC*100%
计算结果分析:在问题规模较大的情况下,穷举法不能在有限时间内完成,所以只能采用启发式方法。GAL方法的运行效果较好。
通过由以上计算实例说明,GA方法比穷举时间更短,在问题规模较大的情况下,GA方法能在有限时间内完成计算,得到较好结果,这说明GA方法是一种快速高效的求解方法。
4 结论
本文根据基于AGV的RMS布局设计特点,提出了变邻域遗传算法的布局设计方法,设计了两个计算实例进行计算分析。计算结果表明:在问题规模较小时,GA方法都能得到最优结果,在问题规模较大时,GA方法能在有限时间内完成计算,这说明GA方法是一种快速高效的求解方法。
摘要：针对采用AGV的可重构制造系统的布局设计问题,本文提出综合考虑AGV负载和空载路程以及工作站重构的布局设计模型,并采用变邻域遗传算法对该模型进行求解。为了验证提出方法的有效性,进行多个计算实例的计算分析。计算结果表明:所提出的方法能在有限时间内完成计算,在问题规模较小的时候能得到最优解。在问题规模较大的情况下,能得到较高质量的解,这说明了所提出的方法是有效的。
关键词：布局设计,可重构制造系统,自动导引车,遗传算法,变邻域
参考文献
[1]Z.M.Bi,et al.,Reconfigurable manufacturing systems:the state of the art.International Journal of Production Research,2008,46(4):967-992.
[2]A.Drira,H.Pierreval,and S.Hajri-Gabouj,Facility layout problems:A survey.Annual Reviews in Control,2007,31(2):255-267.
[3]G.Meng,S.S.Heragu,and H.Zijm,Reconfigurable layout problem.International Journal of Production Research,42:22,4709-4729.
[4]周明,孙树栋,遗传算法原理及应用[M].北京:国防工业出版社,1999.
邻域搜索算法 篇7
抑制数字图像中的噪声是图像处理中非常重要的一项工作,有助于图像复原、分割、特征提取、模式识别等后续工作。目前利用小波进行图像去噪处理[1,2]获得非常好的效果,例如Neigh Shrink方法[3,4]。但是Neigh Shrink方法会过度抑制图像边缘信息,或者人为地破坏相关性更强的邻域。为了保护边缘,宫霄霖博士等提出了一种利用边缘融合的方法进行图像去噪,取得了较好的效果[6]。
脉冲耦合神经网络是一种新型人工神经网络,具有在复杂图像环境中提取有效信息的特性,故广泛应用在图像处理中[7]。利用PCNN对图像进行分割,能根据图像自身特征分割出更符合图像结构特点的结果。
根据脉冲耦合神经网络的特点,结合平稳小波[8,9]对图像进行分割,本文作者因此提出了将Neigh Shrink方法中的邻域范围自适应地确定;宫霄霖博士据此进一步提出了和Neigh Shrink方法综合的想法,以对自适应邻域算法进行补充。本文综合叙述了PCNN自适应邻域的算法并利用实验证明,该算法可以有效地抑制噪声,较好地重建图像。
1 Neigh Shrink图像去噪方法
假设{dm,n}是对含噪图像进行小波变换后的系数。在各个子带上,小波系数都服从广义高斯分布(GGD)。定义邻域窗口Wm,n(d)包含所有落在以当前阈值化小波系数dm,n为中心,边长为d的正方形内所有小波系数。图1为Neigh Shrink方法[3,4,8]利用3×3邻域窗口处理图像小波系数的示意图。图中方框部分为邻域窗口包括的小波系数,实心圆点为待处理的系数。
对待阈值化的小波系数,用式(1)进行收缩
其中收缩因子αm,n定义为
其中λ为阈值。
2 基于PCNN图像分割的的改进的Neigh Shrink去噪方法
2.1 脉冲耦合神经网络
脉冲耦合神经网络(PCNN)是对高级哺乳动物视觉的仿生。在图Yl像处理中,包括图像融合[9,10]、图像分割[11]、图像去噪[12]等方面,有较多的应用。它是由若干个神经元互连而构成的反馈型网络,每一个神经元Nij都由接收部分、调制部分和脉冲产生部分三部分组成(如图2Ij所示)。
用PCNN对M×N大小的图像进行处理时,图像矩阵对应M×N个PCNN神经元构成的神经元网络。每个神经元Nij的活动可由式(2)描述:
式中:Sij、Uij和Yij分别为神经元Nij的外部刺激、内部行为和输出;Lij和Fij分别为神经元的连接域和反馈域两个输入通道,M和W为神经元之间的连接权系数矩阵,VF和VL分别是反馈域和链接域的放大系数;Tij和TV是变阈值函数输出和阈值放大系数;αL、αF和αT分别为链接域、反馈域和变阈值函数的时间常数;βij为连接权重。
2.2 基于PCNN图像区域分割及结合Neigh Shrink去噪方法
图像分割是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程,是图像分析和处理的重要内容。利用PCNN进行图像分割时,图像的每一个像素的灰度值对应为每个神经元的输入。PCNN模型具有独特的神经元捕获特性:某神经元点火会引起附近其他相近灰度像素对应的亮度相近的邻近神经元的激发,产生脉冲输出序列,相似的多个神经元就构成了一个神经元集群。该神经元集群就像一个巨神经元,同步地发出脉冲。每一个神经元集群对应着图像中性质相似的闭合区域。利用由PCNN的脉冲传播特性所引发的同步脉冲,就可以把图像分割成不同的封闭区域,各个邻域呈现不规则的形状,完全由图像自身所决定。
在图3所示的图中,25点为当前待阈值的系数。实心点为PCNN分割后和25点性质相近的系数,空心点表示和25点无关的系数。由于36、43、44点直接相连,所以将它们放入同一个邻域内;而27点由于和21所在的领域并不是直接相连,将它分割到另一个邻域。按照这种方式将直接相连的系数记为一个邻域。假设dm,n是当前待阈值的图像系数。domainPCNN为所在的PCNN分割后的图像邻域,则dm,n的邻域为
图3为某一个块图像数据利用PCNN分割的结果,相应的邻域都用方框标识出。25点为待阈值点,则其所在的邻域为1,2,3,10,15~17,24,25,32。
根据小波的层内相关性原理,如果邻域的范围较大,相关性会相应减小,对去噪效果会降低。于是将分割得到的结果和Neigh Shrink中的固定窗口相互重叠,进一步改进邻域区域。假设dm,n是当前待阈值的图像系数。domainPCNN为所在的PCNN分割后的图像邻域,domainNeighShrink为Neigh Shrink方法提出的图像邻域,则dm,n的邻域为
图4是对图3中区域加上5×5的窗口,其中25点为待阈值点,根据式(4),得到10,16,17,24,25,32点在当前处理25点所需要的邻域内,图中用蓝色粗线条标识出。
3 本文算法实现
步骤1:将噪声图像f(x,y)进行二维平稳小波变换,分别获得不同子带系数;
步骤2:对第一层的低频系数利用PCNN进行区域分割。利用式(3)或式(4)得到当前阈值处理所需要的封闭区域。将得到的分割后的图像信息记为template;
步骤3:将低频系数保持不变,对各层每个高频细节子带系数分别按照template进行Neigh Shrink处理;
步骤4:将各层系数进行平稳小波重构,即可得到去噪后图像fˆ。
4 实验结果与讨论
4.1 PCNN连接权系数矩阵大小讨论
不同的连接权系数矩阵大小会对图像产生较大的影响,较小时会将图像过分割,较大时忽略了图像自身的信息,因此在本文算法中存在一个合适尺寸的连接权系数矩阵。对图5(a)利用PCNN进行分割,当PCNN连接权系数方阵边长为8,13,18时,结果分别为图5(b),5(c),5(d)。通过图5发现,连接权系数方阵边长越大,分割的区域数越少,邻域系数越多;边长越小,区域数越多,邻域系数越少。图5(b)中由于边长较小,分割区域较多,图像本身边缘信息可能被破坏,造成过度分割。图5(d)边长较大,只将图像简单分割成几个区域;图5(c)边长较为适中,较好地减轻了噪声的影响,按照图像自身的信息分割。
对Camereman.tif图片进行加标准方差为15的噪声,采用sym8小波基,用平稳小波分解到3层,阈值采用贝叶斯软阈值,在不同连接权系数矩阵大小时,去噪情况如图6所示。
由图6可知,对于当前的测试图片,在边长为16处出现PSNR的极大值,若选择16及其左右范围内的数值,去噪效果较为平稳,同时计算的空间和时间复杂度也较合适。可以在确定边长的情况下,加上不同的固定滑窗。
4.2 不同噪声强度下的去噪效果
为了验证本文算法在不同噪声污染下的有效性,对Camereman.tif图片分别加标准方差为10、15、20及25的噪声,其余条件同4.1节,连接权系数矩阵边长为13,不加窗和加窗的情况下实验结果如表1。
d B
从表1给出的数据可以看出,使用本文算法中提出的基于PCNN区域分割的邻域阈值小波图像去噪算法可得到较高的峰值信噪比。图7(c)~(e)为Neigh Shrink方法在噪声标准方差为15下,利用不同窗口对加噪图像分别处理的结果,可见本文算法在很好地去除噪声的同时,也很好地保留了图像的边缘信息。
4.3 不同去噪方法的去噪效果比较
目前对Neigh Shrink改进的方法主要在阈值的处理,文献[13-14]提出了可调节阈值对通用阈值进行了改进,本文使用该方法在将邻域窗口均为5×5的情况下,和Neigh Shrink及本文算法进行比较。
从表2中可见本文的方法提高了去噪效果,效果明显好于对阈值改进的方法。说明对邻域的改进是一个新的重要的方向。
d B
5 结论