混合算法范文（精选12篇）
混合算法 第1篇
由于存在早熟收敛现象,遗传算法有可能得到的只是一个满意解,而非全局最优解,为弥补这个缺陷,已出现了多种改进遗传算法,例如:小生境遗传算法、自适应遗传算法、并行遗传算法、混合遗传算法等。
混合遗传算法就是将遗传算法与其它启发式的搜索算法相结合,从而弥补单一优化方法的某些不足之处。由于GA具有开放式的结构,与问题的关联性不大,很容易和其他算法进行结合。比较常见的混合遗传算法有:模拟退火遗传算法、免疫遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法等。本文中是将遗传算法与自由落体算法相结合进行求解二维装箱问题。
2 二维装箱
二维装箱问题有不同的描述方法,本文讨论条形装箱问题(strip bin packing)。描述是:给定n个矩形,设其长和宽分别为Li和Wi(i=1,2..n),现有宽度一定,高度不限的矩形箱子(假设矩形物体的宽度均不大于箱子的宽度),则如何放置这些矩形物体,使放完这些物体后,放置最后物品的总计高度最小,这里假定物体不能重叠和90度旋转圈。
3 算法设计
3.1 自由落体算法简介
自由落体算法也称为自由下坠算法,它是一种典型的不分层算法,其基本思想是:对于每一个物体,在装箱的时候寻找位置最低的合适区间装入。显然这是一种较好的装箱模式。但它仍然存在一些缺点,比如对于高度相同的各个方案,算法没有指出该如何选择。
针对上述算法存在的问题,本文对其进行了改进,其具体描述如下:
第一、从左到右进行扫描,对于扫描得到的各区间进行判断:如果该区间的宽度小于物品的宽度,则依次与右侧区间进行合并,直到合并的区间的宽度大于等于物品的宽度,并取所合并区间的最大的高度与物体的高度之和为合并后区间的高度,类似的,该区间也依次与左侧区间进行合并;第二、所得到的所有区间组中,寻找高度最小的区间组,如果高度相同,优先使用浪费面积最小的方案。
3.2 基于改进后自由落体算法的混合遗传算法
这里把新自由落体与遗传算法相结合,来解决条形装箱问题。
1)染色体的编码方法
假设k个箱子的编号分别为B1,B2,…,Bk,n件物品要装入这k箱子中,要说明的是,有时几件物品可以装入同一个箱子中,所以不一定要全部用完这k个箱子,各个物品ui(i=1,2,…,n)所装入箱子之编号的顺序排列就构成该问题的染色体编码,即我们使用的是等长度的字符代码编码方法,例如B1B3B4B4B1B2B2B3表示第1,5号物品装入箱子B1中,第6,7号物品装入箱子B2中,第2、8号物品装入箱子B3中,第3、4号物品装入箱子B4中。初始群体可以由B1,B2,B3,B4随机排列产生,由个体的染色体编码串可统计出某一装箱方案用了几只箱子。
2)适应度函数
这里以Max Maxheight-h作为适应度函数,其中Maxheight为较大的常数,h为装箱后的高度,这样保证了装下该物品后,箱子所剩空间为最大的情况。
3)选择
选择操作是建立在群体中个体的适应值的评估的基础上,在本算法中采用按正比与适应值的轮盘赌的方式进行随机选择,为了提高效率,选择轮盘时采用折半查找的方法,这样就能有效地减少比较次数,确保该过程的时间复杂度为0(log n)(n为种群大小)。
4)交叉
交叉是对两个配对的染色体以某种方法相互交换部分基因,从而形成两个新的个体,它是产生新的优良基因的主要方法,但这样会产生无效染色体。为了避免这种情况,需要对交叉出的结果做特殊的处理。在这里,用Grefenstette提出“巡回路线编码方法”的基本思想进行交叉操作,具体实施如下:
假设有十个物品为ui(i=1,2,...,10),欲装入一个大箱子,我们对装箱顺序进行编码,设现有如下两种装箱方案:
A1=(2,6,1,3,4,8,10,5,9,7)
A2=(1,5,8,3,2,7,9,6,4,10)
方案1表示根据自由落体算法装入物品的顺序为2,6,1,3,4,8,10,5,9,7;方案2表示根据自由落体算法装入物品的顺序为1,5,8,3,2,7,9,6,4,10。
下面我们对上述两种装箱方案进行编码,以A1方案为例,在此方案中8号物品装箱顺序排在了第六位,在此之前编号为2、6、1、3、4的物品已装入箱中,物品编号均小于8,即共五个数均小于8,故我们对其编码为:8-5=3。设方案A1编码后为A1',方案编码后为,按照此法得:
A1'=(2,5,1,1,1,3,4,1,2,1)
A2'=(1,4,6,2,1,3,3,2,1,1)
然后,对红题字部分进行交叉,即A1'中的1和A2'中的4进行交叉,得两种新的编码方案,设为T1、T2。则:
T1=(2,5,6,1,1,3,4,1,2,1)
T2=(1,4,1,2,1,3,3,2,1,1)
然后对其进行解码,便得到另外两种装箱方案:
T1'=(2,6,8,1,3,7,10,4,9,5)
T2'=(1,5,2,4,3,8,9,7,6,10)
可以看出采用这种方法,不管在哪个位置交叉,交叉后每一个装箱方案中物品没有重复。
5)变异
这里我们采用基本位变异的方法,即随机在一个染色体中取出一位,进行改变,但应该保证产生的染色体是一个有效染色体,因此该位的取值应该有一定的范围,它只能在(1,2,3,...,n-1-i)中选取。
4 实例检验
论文参见相关的资料,随机摘取一组数据进行验证:a(15,4),b(2,6),c(5,6),d(9,6),e(13,6),f(16,5),9(1,4),h(5,4),i(9.4),i(13,2),k(16,2),1(l,2),m(4,2),n(8,2),o(12,1)。(其中箱子宽度为20,物体第一个数据为宽度,第二个数据为高度)
交叉率:Pc=0.8;变异率:Pm=0.1;代数:Gen=40
采用改进后的自由落体算法与遗传算法相结合,可得到较优秀的装箱结果,装箱顺序为j m h a b g f k n d i e l o c,高度为26,装载率为89.9%(阴影为浪费面积),如图1所示。
5 结束语
二维装箱问题在工业领域有着广泛的应用,例如:切割问题,服装裁剪,装运问题,电路板设计问题,排版问题等。一种好的解决方案,能够节约生产成本,提高效益。遗传算法由于存在早熟收敛现象,有可能得到的解决方案并不是全局最优解,为此,本文利用基于自由落体算法的混合遗传算法进行求解,从而得到最优解。
参考文献
[1]姜义东,查建中,何大勇.集装箱装载矩形货物的布局研究仁[J].铁道学报,2000.
[2]邓向阳,等.算法分析与设计[M].北京:冶金工业出版社,2006.
[3]E G Coffman,M R Garey,D S Johnson.Approximation Algorithms for Binpacking:A survey[A].In:D Hochbaumed.Approximation Algorithmsfor NP Hard Problems[C].Boston:PWS Publishing,1996,46-93.
[4]Keqin Li,kam Hoi Cheng.A heuristic algorithms for On Line Packing in Three Dimensions[J].Journal of Algorithms,1992,(13):819-828.
[5]Gehring H.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research,1990,44(2):277-288.
[6]赵素芬.几何布局问题及其应用(一)[J].呼和浩特科技,1993,(2),12-19.
[7]武晓今,朱仲英.二维装箱问题的一种实现方法[J].微型电脑应用,2003.
[8]Yanasse H Hetal.Two-dimensional cutting stock with multiple stock sizes[J].Journal of Operationa Research Society,1991,42(8):673-683.
软件安全中混合加密算法 第2篇
【关键词】网络安全;加密;密码
一、前言
随着计算机网络技术的飞速发展，计算机系统的安全问题也越来越引起世界各国的广泛关注，信息网络的大规模全球互连趋势，以及人们的社会生活对计算机网络依赖性的与日俱增，使得计算机网络的安全性成为信息化建设的核心问题。
二、网络安全概况
1.网络安全的基本概念
一种多目标混合进化算法的研究 第3篇
摘 要：针对遗传算法的不足，提出将禁忌搜索方法、免疫算法、遗传算法融和的多目标混合进化算法。该算法引入禁忌搜索法，避免了传统遗传算法早熟现象的发生；引入基于浓度的自适应变异操作，克服算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免最优解的丢失，通过ZDT系列测试函数的仿真实验并与NSGA-Ⅱ算法进行比较，验证了算法的有效性。
关键词：多目标优化；遗传算法；多目标混合进化算法；ZDT测试函数
中图分类号：TP18 文献标识码：A
Abstract：A multiobjective hybrid evolutionary algorithm （MHEA） was put forward aiming at the shortcomings of the traditional genetic algorithm， which combines taboo search algorithm， immune algorithm and genetic algorithm. This algorithm avoids the premature phenomenon of the traditional genetic algorithm through importing the taboo search algorithm. The operator of adaptive mutation based on the density overcomes the problem of long solving process caused by the constant mutation probability and bad diversity of the solution. Then external elite set was introduced to avoid the loss of the optimal solution. Finally the simulation of ZDT series test functions and the comparison with NSGA-Ⅱ algorithm verifies the effectiveness of the algorithm.
Key words：Multiobjective optimization；genetic algorithm； MHEA； ZDT test functions
2.3 算法简介
遗传算法[4，5]因其高度的并行处理能力、强鲁棒性和全局搜索能力而被广泛地应用于诸多领域。理论上遗传算法依“概率1”收敛于问题的最优解，然而实践应用中，遗传算法会表现出早熟现象、局部寻优能力较差等不足，所以一些常规遗传算法并不一定是针对某一问题的最佳求解方法。
禁忌搜索法[6]具有灵活的记忆功能和藐视原则，并且在搜索过程中可以接受劣解，因而具有较强的爬山能力，搜索时能够跳出局部最优解，从而增强获得更好的全局最优解的概率。但其搜索性能完全依赖于邻域结构和初始解。
免疫算法[7]可以通过细胞的分裂和分化作用，对抗体的产生进行促进或者抑制，体现了自我调节功能，保证了个体的多样性。
由于遗传算法、禁忌搜索法、免疫算法各有优缺点，因此将三种算法相结合，互相取长补短，则可能设计出性能优良的新的全局搜索算法，可以加快算法的收敛性同时提高算法的多样性。
3 多目标混合进化算法（MHEA）
本文引入禁忌搜索法[8]，避免早熟现象的发生，提高了局部搜索能力；采用基于浓度的自适应变异操作，克服了算法由于变异概率不变导致的求解过程长，解的多样性差的缺陷；引入外部精英集，避免了最优解的丢失，下面介绍算法的实现：
3.1 算法的设计
1）将部分精英集中的个体加入到种群POP0中并进行选择操作，可以提高种群的收敛速度。
2）交叉操作：
由于交叉算子在搜索最优解的进程中是一个破坏性同时也是产生新解的过程，因此遗传算法常常很快收敛到比较好的解，但是往往不能收敛到最优解，本文采用单点交叉算子。
3）禁忌搜索法：利用遗传算法与禁忌搜索法相结合，克服遗传算法早熟和收敛慢的缺点，具体步骤如下：
（1）对选择操作产生的新种群的个体进行禁忌搜索；
（2）查找禁忌表中是否有此个体记录；
（3）如果有，再看是否满足特赦准则；
（4）如果满足特赦准则，再看是否满足收敛准则；
（5）满足收敛准则，继续进行交叉操作，产生新种群，然后转到1）；
（6）如果不满足特赦准则，禁忌表中也没有此个体记录，则放人禁忌表；
（7）继续查看是否满足收敛准则，满足后输出结果，否则进行上述的交叉操作。
4）基于浓度的自适应变异算子
相比变异概率不变情况下，自适应变异更加符合生物遗传规律，有利于提高种群多样性。借用免疫算法中对抗体产生进行促进或者抑制，可以自我调节，从而保证个体多样性的思想，本文提出了一种基于浓度的自适应变异算子。
3.2 外部精英集
由图1可知，最初的精英集由初始群体中适应度最高的个体填充，随后由交叉和变异操作产生的最优个体对精英集进行更新，如果个体的数量超过档案规模，则依据适应度值大小对精英集进行修剪。在种群外设置一个精英集合用于保存种群进化每一步搜索到的非支配解。精英集合的使用将有效防止算法在搜索过程中由于随机因素而丢失最优解，并且能加快算法收敛速度。
3.3 多目标混合进化算法的步骤
（如图1）可描述为：
1）初始化算法的参数（包括种群规模POP、禁忌表及其长度、迭代次数等），随机产生初始群体POP0。
2）计算种群中每个个体的适应度值，并将适应度最高的个体存入精英集1中。
3）将精英集中的部分个体加入到种群中，进行选择操作得到种群POP1。
4）对POP1进行禁忌搜索同时进行交叉操作得到种群POP2，将POP2中适应度最高的个体存入精英集2中。
5）对POP2进行基于浓度的自适应变异操作得到种群POP3，将POP3中适应度最高的个体存入精英集3中。
6）更新精英集，如果个体数量超过档案规模，则对精英集进行修剪。
7）如果满足终止条件，执行步骤8，否则，转到步骤3。
8）输出最优解。
4 仿真实验
4.1 仿真测试
为了验证MHEA算法解决多目标优化问题的性能优劣，将该算法与目前解决多目标问题较好的NSGA-Ⅱ[10]算法进行比较分析。本文选取一组具有不同特征的benchmark问题ZDT1、ZDT3和ZDT6作为测试函数，其中ZDT1具有Pareto最优前沿，ZDT3具有非连续Pareto最优前沿，ZDT6具有非凸性且非均匀Pareto最优前沿。
测试过程中，MHEA算法和NSGA-Ⅱ算法均采用实数编码，浓度阈值γ=0.7，交叉概率pm=0.9，变异概率pc=1/n（n为变量个数），种群规模M=200，迭代次数gen=300。在同一台计算机上分别独立运行20次，从中选取最优结果进行比较，试验结果如图所示。
4.3 实验结果分析
由表1可知，所提算法MHEA在优化测试函数ZDT中的收敛性能、分布性能及多样性均优于算法NSGA-Ⅱ，说明算法引用禁忌搜索法及基于浓度的自适应变异算子是可行有效的，它能够提高收敛性，增加群体的多样性，但MHEA的平均运行时间却较长，这是它在提高算法搜索性能的同时所付出的代价。
5 结 论
本文有效的结合了遗传算法、禁忌搜索法和免疫算法的优点，提出了一种多目标混合进化算法，提高了收敛性，同时保证了多样性。通过仿真实验验证了算法的有效性。
参考文献
[1] 雷德明，严新平.多目标智能优化算法及其应用[M].北京：科学出版社，2009：31-33.
[2] 张勇德，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策，2005，20（2）：170-173.
[3] COELLO COELLO C A，PULIDO G T.Handing multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.
[4] GOLDBERG D E.Genetic Algorithm in Search， Optimization and Machine Learning[J].NJ： Addtion Wesley，1989.
[5] 王娜，向凤红，毛剑琳.改进的自适应遗传算法求解0/1背包问题[J].计算机应用，2012，32（6）：1682-1684.
[6] 张文化，刘素华，侯惠芳.一种用于特征选择的禁忌搜索算法[J].计算机应用于软件，2010，27（5）：125-127.
[7] 崔逊学.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能，2001，14（3）：291-296.
[8] B T G TAN，S M LIM.Automated Parameter Optimization for Double Frequency Modulation Synthesis Using the Genetic Annealing Algorithm[J].J Audio Eng Soc.1996，44（1）.
[9] 王洁，高家全.一种新的的免疫遗传算法及应用[J].计算机应用与软件，2010，27（12）：89-91
[10]Deb K，Prata A，Agarwal S，Meyarivan T.A fast and elitist multiobjective geneticalgorithm： NSGAⅡ[C].IEEE Transactions on Evolutionary Computation， 2002， 6 （2）：182-197.
[11]郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.
混合算法 第4篇
支持向量机(Support vector machine, SVM)[1,2]是Vapnik等人于20世纪90年代提出的一种新的机器学习方法。它基于VC维理论和结构风险最小化原则,具有很强学习能力和泛化性能,解决了以往机器学习中存在的小样本、非线性、过学习、高维数等问题。由于这些优点,SVM已经在模式分类等领域取得了广泛的应用。
标准的SVM的训练算法涉及到求解线性约束的二次规划问题。二次规划问题求解受存储器容量和计算量的限制,当训练数集规模很大时,分类速度会受到很大影响,甚至无法完成。所以常规的高效的训练算法往往是将一个问题分解成若干个子问题,然后逐一求解优化。主要有Vapnik提出的chunking[2],Osuna提出的deposition[3]以及Platt提出的SMO[4]。这样做的的缺陷是结果可能得到的是一个次优解,而且可能需要多次分解才能达到为可解决的范畴。
混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)[5]是2000年由Eusuff和Lansey提出的一种基于群体智能的优化算法,根据全局信息交换和局部深度搜索的平衡策略来找到最优解[6,7]。用群体智能优化算法[8]训练SVM是一种全新的探索。Paquet等人首先提出将粒子群优化算法用于SVM训练[9],但结果并不理想。
本文提出用一种改进的混合蛙跳算法(ISFLA)训练SVM。该算法在SFLA基础上引入模拟退火思想,极易跳出局部最优解,改善了收敛精度和速度,且具有较强鲁棒性。并通过实验证明提出的算法具有良好的性能。
2 支持向量机简介
支持向量机最早应用于模式分类。不失一般性,以线性可分两分类问题为例。训练集包括L个训练样本:T={(x1, y1), …, (xL, yL)} xi∈X=Rn, yi∈Y={1, -1}。其中X为输入,Y为输出。训练过程就是寻求一个平面w×x+b=0,使两类数据点距离平面尽量远。这种最优分类面思想导致了对w和b的最优化问题:
yi{(w×xi)+b}≥i, i=1, …, L (1)
根据最优化理论,原始问题可转化为对偶问题来求解。因此式(1)可转化为式(2)求解。
st:
ai≥0, i=1, …, L
求解得到最优分类规则
在非线性可分问题中中,引入松弛变量ξ(ξi≥0),和惩罚系数C′,使式(1)优化问题转变为
st:yi{(w×xi)+b}+ξi≥1 (4)
ξi≥0;i=1,…,L
其对偶问题可转变为式(5)
得到最优分类规则
在式(6)中不为零的ai即为支持向量。SVM利用核函数方法将低维数据非线性映射到高维,使其线性可分,并由支持向量及其系数构造最优分类面。
3 改进的混合蛙跳算法训练SVM
3.1 SFLA算法
在一个D维的目标搜索空间中,随机生成P只青蛙(解)组成初始群体,第i只青蛙表示问题的解为Xi=(xi1,xi2,…,xiD)。青蛙个体按适应度值从优到劣排列,将整个群体分为M个子群体。其中排名第1的青蛙分入第1子群体,排名第2的青蛙分入第2子群体,第M只青蛙分入第M子群体,第M+1只青蛙分入第1子群体,第M+2只青蛙分入第2子群体,依次类推,直到全部青蛙划分完毕。
每个子群体进行局部深度搜索,即在子群体的每次迭代中,首先确定当前迭代中子群体的最差个体xw、最好个体Xb和全局最好个体Xg,只对该子群体当前最差的个体Xw进行更新,更新策略为:
Di=rand()*(Xb-Xw)(-Dmax≤Di≤Dmax) (7)
newXw=Xw+Di (8)
其中,rand()是均匀分布在[0,1]之间的随机数;Dmax表示青蛙所允许更新步长的最大值。如果newXw的适应度值优于原来的Xw,则取代原来种群中的解。如果没有改进,则用Xg取代Xb重复执行更新策略(7)(8)。如果仍没有改进,则随机产生一个新的解取代原来的Xw。重复这种更新操作,直至满足子群体的更新代数。当所有子群体的局部深度搜索完成以后,将所有的青蛙个体重新混合排序并再次划分子群体,然后再进行局部深度搜索,如此反复直到满足混合迭代次数。
3.2 模拟退火算法
SA算法的思想是由Metropolis在1953年提出的[10,11,12],它是一个全局最优算法,具有并行性,并且以概率1接近最优值[13]。SA来源于固体退火过程,当固体的温度充分高时,内部粒子变为无序状,内能较大,随着固体缓慢冷却,其内部粒子渐趋有序,内能逐渐减小;在每个温度都会达到平衡态,最后在常温时达到基态,内能减为最小[14,15]。此算法将优化问题比拟成一个物理系统,将优化问题的目标函数比拟为物理系统的能量,通过模拟物理系统逐步降温以达到最低能量状态的退火过程而获得优化问题的全局最优解[16,17,18]。具体步骤如下:
(1) 初始退火温度Tk(k=0),产生随机初始解X。
(2) 在温度Tk下重复执行如下操作,直至达到温度Tk的平衡状态:
在解X的领域中产生新的可行解X′;计算X′的目标函数f(X′)和X的目标函数f(X)的差值Δf;依照概率min{1,exp(-Δf/Tk)}>rand()接收X′,其中rand()表示[0,1]内的随机数。
(3) 退火操作:Tk+1=C*Tk,k←k+1,其中C∈(0,1)。若满足收敛判据,则退火过程结束;否则,转(2)。
本文利用公式x′=x+ηξ产生新解,式中η为扰动幅值参数,ξ为随机变量,一般服从正态分布。SA通过退火机制所得的子代,即随着温度的下降,接受劣解的概率逐渐减小,从而提高算法的性能。
3.3 改进的SFLA算法在SVM训练中的应用
SVM训练的数学本质即为求解支持向量系数,适应度函数为
用改进的SFLA算法训练SVM基本流程如下:
(1) 初始化蛙群,个体初始位置为[0,C′]间的随意数,种群个体总数N,个体的维数m,子种群个数M,子群局部搜索迭代次数cyc,退火的初始温度T,温度冷却系数C,扰动幅值η。
(2) 计算每个个体的适应度值,规定若某个个体位置不满足
(3) 将当前所有个体的适应度值从优到劣排序,依次将个体划分到各子种群。
(4) 利用SFLA的更新策略,对子种群的最差个体进行更新,获得一个较优解X。
(5) 利用SA算法,产生新解X′,利用退火机制比较X和X′的质量,获得较优解。
(6) 对该子种群适应度值排序,然后转步骤(4),重复该更新策略,直至子种群内的迭代次数满足事先给定的要求cyc。
(7) 当所有子种群完成了更新操作后,若当前最优个体满足收敛条件,则进化过程成功结束,返回全局最优解;否则修改种群的退火温度,即令T=C*T,转步骤(3)。
4 实验结果与分析
在此给出3组实验结果。第1组数据来自Breast-cancer数据集,第2组来自Iris数据集,第3组来自Heartstatlog数据集。这3个数据集均来自UCI数据库。
试验中SVM核函数采用高斯核函数:
改进的SFLA的参数如下:种群大小100,子群内个体数量20,子群体内迭代次数30,退火的初始温度10,基态温度1,降温系数0.8,扰动幅值η为5。
(1) Breast-cancer数据集分类实验。本数据集中训练样本100个,测试样本100个。由经验取C′=10,σ=4。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表1所示。
(2) Iris数据集分类实验。本数据集中训练样本50个,测试样本50个。由经验取C′=100,σ=2。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表2所示。
(3) Heartstatlog数据集分类实验。本数据集中训练样本50个,测试样本100个。由经验取C′=100,σ=50。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表3所示。
以Heartstatlog数据集分类实验为例,图1表现了标准sfla和改进的sfla在分类中的演化过程。
由表1-3看出,本文提出的基于改进的SFLA算法训练获得的识别率和标准SVM训练方法相当,比SFLA算法训练的性能有较大提高。由图1可以看出,改进的SFLA算法能够快速收敛,得到很高的识别率,而标准SFLA算法在第二步后就陷入局部极值,无法继续跳动,从而识别率较低。因为模拟退火方法以某种概率接收较差的个体,所以具有跳出局部最优解的能力,在一定条件下能以概率1收敛到全局最优值。
5 结束语
本文提出将混合蛙跳算法引入到SVM训练中,并提出一种改进的混合蛙跳算法,提出了加入模拟退火的蛙跳算法。以不同的概率接受较好的和较差的个体,使蛙跳具有跳出局部最优的能力,同时也加快了收敛速度,使训练算法的性能获得很大提升。通过实验,也证明了用群体优化算法作为SVM的算法作为一种新的方向具有良好的效果。
摘要：支持向量机的训练需要求解一个带约束的二次规划问题,但在数据规模很大情况下,经典训练方法将变得很困难。本文提出一种基于改进的混合蛙跳算法的SVM训练算法。针对混合蛙跳算法搜索速度慢且容易陷入局部极值的缺陷,将模拟退火思想引入到混合蛙跳算法中,提出一种改进的混合蛙跳算法。该算法保持了混合蛙跳算法参数少和容易实现的特点,同时通过模拟退火的降温过程来提高算法的进化速度和精度。实验结果表明,该算法能显著提高收敛速度,并能有效克服局部极值,在SVM训练中具有良好效果。
混合算法 第5篇
混合免疫算法求解对称TSP的仿真分析
针对对称TSP,将局部搜索方法与免疫算法相结合,构造了混合免疫算法.数值实验结果表明,混合免疫算法求解对称TSP是可行的.;新的算法既具有局部搜索方法较快的收敛速度和较强的局部寻优能力,又具有免疫算法的全局收敛特性.
作 者：张全兴 王海莉 Zhang Quanxing Wang Haili 作者单位：长安大学,理学院,陕西,西安,710064刊 名：宁夏大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF NINGXIA UNIVERSITY(NATURAL SCIENCE EDITION)年，卷(期)：29(3)分类号：O224关键词：免疫算法 混合免疫算法 局部搜索方法 对称TSP
混合算法 第6篇
关键词：视频处理；背景建模；混合高斯模型；历史背景
中图分类号：TN919文献标识码：A
背景减除是自动视频对象分析的一项关键技术，他在智能视频监控等领域中有着非常广泛的应用。对视频场景进行背景建模，将存储好的背景模型和新观察到的图片进行背景减除来提取运动目标是较为常用的方法＼[1＼]。原理虽然简单，但是真实世界中像素在时域和空域中的复杂变化，使得背景建模变得很困难。比如阴影检测、亮度的缓慢或剧烈改变等都是现在背景建模的难点＼[2-3＼]。近年来，国内外学者提出了许多建立背景模型的方法，包括针对含有纹理的动态场景，采用一种新的模糊色彩直方图特征来减弱运动背景造成的色彩改变＼[4＼]；为每一个像素点建立一个由4层前馈神经网络组成的背景模型＼[5＼]；结合颜色、梯度、不同特征来构建背景模型，采用支持向量机来进行背景分类＼[6-7＼]等。
湖南大学学报（自然科学版）2015年
第10期肖进胜等：一种基于历史背景的混合高斯背景建模算法
高斯模型是近年发展起来并得到广泛应用的一种技术。Stauffer等＼[2＼]提出利用混合高斯模型来建立背景模型，在每帧中对各个像素点建立由多个高斯分布组成的背景模型。自此以后，该方法以其能较为鲁棒地描述多峰分布的背景而被广泛应用，但其仍然具有处理速度较慢、无法应对突变背景等缺点＼[8＼]。此后的研究者对混合高斯背景建模方法做了各种改进。Zivkovic Z＼[9＼]针对自适应高斯混合模型的个数和参数问题进行了改进，利用最大似然估计进行高斯模型个数的选择。文献＼[10＼]考虑到全局抖动造成的运动目标检测不准确的问题，提出基于分区灰度投影稳像的高斯背景建模算法。文献＼[11＼]针对亮度场景的变化，建立亮和暗不同的模型进行亮度场景变化的检测和估计。文献＼[12＼]为了解决场景中存在的突变，提出基于记忆的混合高斯模型（Memory-based GMM， MGMM）的前景检测算法，取得了很好的检测效果，但是该算法中每个像素都要经过瞬时记忆、短时记忆和长时记忆3个空间的传输和处理，影响了算法效率和实用性。上述方法对混合高斯模型的修改多数集中在提高模型的处理效率与收敛速度方面。当现有的混合高斯建模算法应用到实际场景中时，若背景场景重复性出现时，如被重复性的遮挡与显露，受模型学习速度的影响，重新显露出的背景场景的变化不能被立即学入背景模型中，依然会被检测为前景，从而产生大量误判。
本文针对视频中背景经常重复性地被遮挡与显现的场景（如智能视频监控场景中），提出了一种基于历史背景的混合高斯模型（History Background-based GMM， HBGMM）。经过模型学习，基于历史背景的混合高斯模型对重复出现过的背景具有记忆功能；当重复性背景再次出现时，能及时判决出背景与前景，从而使被误判成为前景的背景快速消融至背景中。
1混合高斯模型原理分析
经典的混合高斯模型＼[2＼]对视频图像中的每一个像素点定义K个状态，其值一般取3～5。若每个像素点的像素值用Xt表示，则对应的概率密度函数可用K个高斯函数来表示：
f（Xt=x）=∑Ki=1ωi，tη（Xt，μi，t，Σi，t）。 （1）
式中：η（Xt，μi，t，Σi，t）为t时刻的第i个高斯模型；ωi，t为时刻t第i个高斯模型的权重，且有K个权重的和为1。 这里假定视频各帧图像中各点的像素值在R，G，B3个颜色通道＼[13＼]是相互独立的，并且具有相同的方差，σi，t为标准差，那么协方差矩阵可以取值为：
Σi，t=σi，t2I。 （2）
其中I为单位阵。所有K个高斯模型首先按照ωi，t由大到小排序，然后从首端选取B个高斯模型作为背景模型。其中B满足：
B=argminb（∑bi=1ωi，t>Thershold）。 （3）
式中：Thershold为预先给定的权重阈值，是用于选择模型个数的阈值，一般取值为0。7～0。9。对于新的一帧图片，若当前图片中点的像素值与其中某个高斯模型的均值和标准差满足：
Xt+1-μi，t<δσi，t。 （4）
则认为该像素值与高斯模型匹配（通常δ设为2～4）。高斯分布的参数采用在线K均值近似算法进行更新＼[9＼]，对于第1个匹配上的高斯模型，更新其所有参数，而对于其他K-1个高斯模型，仅更新权重，权重更新公式为：
ωi，t+1=（1-α）ωi，t+αOi，t+1。 （5）
对于首次匹配的模型，Oi，t+1取1，对于其他模型，Oi，t+1取0。ωi，t和ωi，t+1分别为更新前和更新后的权重。均值与方差更新的公式为：
μi，t+1=（1-α）μi，t+αXt+1； （6）
σ2i，t+1=（1-α）σ2i，t+α（Xt+1-μi，t+1）T×
（Xt+1-μi，t+1）。 （7）
式中：μi，t和μi，t+1分别为更新前后的均值；σ2i，t和σ2i，t+1分别为更新前后的方差；α为学习率，取值为0。002～0。005。如果当前像素点无法与所有模型匹配，就用一个新的均值为Xt+1、高方差和低权重的高斯分布取代尾端的高斯分布。
传统高斯模型应用于复杂的现实环境中时计算复杂，其计算量与所用的高斯模型的个数成正比，而且模型参数难以调整＼[14＼]。同时在有重复性的背景场景出现时，背景点则会因为像素值的突然变化，而被误检为前景点，造成误判。一个理想的背景减除系统应具有一定的自适应能力，其背景模型应可以根据场景的变化自适应地保持与更新背景模型。
2基于历史背景的混合高斯模型
针对经典混合高斯模型的问题，如果在使用混合高斯模型对背景进行建模实现背景减除的过程中，对曾经判断成为背景的模型进行标记，标记其为历史模型。在之后的更新与匹配过程中，对历史模型记录其匹配次数，在一个周期内，若匹配次数超过用户设定门限，则在下次匹配成功之后，额外为该模型增加T倍的α，通过模型的权重降序排列，使其迅速增长至模型队列前端，落入背景模型的背景权重范围内，从而被判决为背景而不是前景。就能够在一定程度上解决前面提到的问题。
本算法对经典的高斯模型改进有以下2点：
1）对历史背景进行标记，以P帧为周期，记录该周期内历史背景的匹配次数，若匹配次数超过用户设定门限N，则在下次匹配成功之后，额外为该模型增加T倍的α。权重更新公式（5）更改为如下所示。
ωi，t+1=（1-α）ωi，t+αOi，t+1+αci，t+1。 （8）
式中：α，ωi，t和ωi，t+1与式（5）含义相同。对于满足历史背景更新条件的模型，ci，t+1取值为T，对于其他模型，ci，t+1取0。这里历史背景更新条件是指：若当前模型被匹配上，且该模型权重处于前景范围，在周期P内匹配次数超过N次。P与N若取值过小，会对图像中的噪声较为敏感；若取值过大，建模算法又无法及时适应视频图像中前景对象与背景的变化，因此，本文中取P为10，N为5。符合该条件的模型，会在原始权重更新的基础上，再加上Tα的新权重。实验表明，当T≥3时，前景过快消融，而当T<2时，对重复背景的处理效果不明显，因此将T设为2。
2）当模型权重小于某一门限时，对于历史模型和非历史模型进行区别处理。非历史模型将会被删除；而历史模型仅将其权重置为0，并不删除。
算法的具体描述如下：
步骤1第1帧时初始化记忆空间，用当前帧的图像像素（Ri，Gi，Bi）创建每像素点的第1个高斯模型，将其权重赋为1，并分配初始方差。
步骤2对每一帧新的图像，将每个像素点的K个模型按权值从大到小排序。根据式（3）从首端选取B个高斯分布作为候选背景模型，Thershold为用户自定义的阈值。
步骤3将新的采样值Xt+1（R，G，B）依次与原有K个高斯模型进行匹配，若δ=3时，式（5）成立，则认为该点匹配当前模型，若匹配上的模型落在步骤2中的B个模型内，则判断该像素点为背景，同时将当前模型标记为历史模型，否则，该像素点为前景点。找到匹配模型后不再寻找其他匹配模型，执行步骤4；若当前点未匹配上任何模型，转步骤5。
步骤4如果找到匹配模型，按照式（8），（5），（6），（7）更新匹配模型的权重、均值和方差，若该模型为历史模型，则记忆其匹配次数。在固定周期内（如10帧），匹配次数超过N次，则权重额外增加T倍的α。其他未匹配模型只更新权重，同时对所有模型按权重进行降序排列。 在模型的权重更新完成后，若该模型的权重小于某给定值αCT，当其未被标记为历史模型时，删除当前模型；否则，只将当前模型权重置为0，不删除该模型。
步骤5如果当前点未匹配上任何模型，按照式（8）更新所有模型的权重。在模型个数未达到用户设定上限时，生成一个新的模型加入模型队列；否则，用这个新模型取代权重最小的模型。同样，最后对所有模型按权重进行降序排列并归一化。
根据上面的模型分析，基于历史背景的混合高斯背景建模算法流程如图1所示。
在传统混合高斯模型更新过程中，引入曾经是背景模型的标记，并根据这一标记，对历史背景模型进行不同的更新处理，则有可能实现记忆背景的作用，在背景重复出现时，避免将其误检为前景。
3实验结果及讨论
为验证本文所提历史模型算法的有效性，在2。4 GHz酷睿i3双核处理器上，VS2005编程环境下，用序列进行了测试，并与传统GMM方法＼[2＼]以及文献＼[12＼]的MGMM方法进行了对比。为保证方法比较的有效性，3种方法基本参数取值相同，分别为Thershold=0。75，ω =α，其中GMM和本文算法K
=5，σ=20；MGMM算法中K=4，N=1，σ=25。
学习率计算方法为：
α=1/（2frame），frame<500；0。002，frame≥500。 （9）
式中：frame为帧数。
图1像素级算法流程图
Fig。1Flow chart of the pixelwise algorithm
为了更好地测试重复性背景问题，在序列“fast move”中叠加一个每隔400帧出现的色块，用该色块来模拟重复出现的运动目标，初始50帧用于模型学习，不叠加色块。色块消失后，由原位置被误检为前景的部分消失所需的帧数来定量判决不同背景建模算法处理重复背景的能力。
图2（a）显示了用于测试的视频原始图像，图2（b）为原始视频叠加色块的效果。图3从左到右依次给出序列分别为608，612原始帧，采用经典GMM方法、文献＼[12＼]的MGMM方法以及本文提出的HBGMM方法的前景检测结果。 表1为3种方法在测试帧中重复出现的色块检测为前景的帧数。
由表1可见，有色方块在视频的51～200帧与601～999帧出现，当其第2次在600帧出现时，由于之前出现过，该像素值曾被学习入背景模型中，此时重新出现的色块应该快速地被吸收入背景，而不应被检测为前景目标。但传统的混合高斯模型经过了12帧才将其吸收成背景，而本文所用方法仅用了8帧。由图3可知，本文算法的检测结果被误检为前景的目标更少，消失速度更快。由此可见，在重复性背景出现时，本文方法能够更快地将其吸引消融成背景，而不会长时间内仍被检测为前景。
图2“Fast move”序列背景变化
Fig。2Background changes in “Fast move”
表13种背景建模方法检测效果对比
Tab。1Comparison of the three background
modeling methods
帧数
实际方块
GMM方法
MGMM
方法
HBGMM方法
51～200
51～81
51～200
51～81
601～999
601～612
201～700
601～608
为了更精确地测试建模算法的效果，本文选用了两段带有真实前景（Ground truth）的视频序列，并采用F1得分来评估检测出的前景与真实前景的相似程度。F1得分的计算方法为：
F1=2prp+r，p=tt+f，r=tt+n。 （10）
式中：F1为得分值；t，f，n分别为正确检测、错误检测和未检测出的前景点个数。检测出的前景点是否正确，可以通过与Ground truth对比得知。F1得分的最高分为1，最低分为0，分值越高表明检测出的前景越准确，建模效果越好＼[12＼]。
“Office”序列中，当人物离开站立位置，其身后的墙壁再次显露出来，根据Ground truth，此时该处墙壁应被检测为背景。因此，对此时视频序列的前景检测结果计算F1得分。图4分别给出了第2 002（上图）和第2 006帧（下图）的前景检测结果。
图3“Fast move”序列前景检测结果
Fig。3 The segmentation results of “Fast move”
图4“Office”序列前景检测结果
Fig。4 The segmentation results of “Office”
由图4可见，本文提出的HBGMM建模算法比GMM算法和MGMM算法能够更快地将重复出现的墙壁吸收为背景。3种建模算法检测结果的F1得分如表2所示。由表2可知，HBGMM算法的F1得分均高于GMM算法与MGMM算法，可见，当重复背景出现时，HBGMM算法检测出的前景更为准确。
表2对“Office”序列3种方法检测结果的得分对比
Tab。2Comparison of score for “Office” sequence
with three methods
帧号
F1
GMM方法
MGMM
方法
HBGMM方法
2 002
0。546 9
0。421 8
0。566 4
2 006
0。525 9
0。415 0
0。548 6
为了进一步测试HBGMM算法的效果，本文选用了另一段室内监控视频“Sofa”，当人物将原本置于沙发上的行李移走时，原被行李遮盖后显露的沙发应被检测为背景。图5显示了在该场景中的两帧画面（第2 471，2 486帧）及相应建模算法的检测结果。表3为该3帧前景检测结果的F1得分。
表3对“Sofa”序列3种方法检测结果的得分对比
Tab。3Comparison of score for “Sofa” sequence
with three methods
帧号
F1
GMM方法
MGMM
方法
HBGMM方法
2 471
0。737 1
0。527 3
0。746 7
2 486
0。782 6
0。658 5
0。784 1
由表3可知，相较于GMM和MGMM建模算法，HBGMM算法的F1得分最高。同时，由图5可知，HBGMM算法在处理重复背景问题时，能够更快地将误检为前景（见重新显露出的沙发部分）的像素点吸收为背景。
图5“Sofa”序列前景检测结果
Fig。5The segmentation results of “Sofa”
4结论
本文在传统混合高斯模型更新过程中，引入曾经是背景模型的标记，并根据这一标记，对历史背景模型进行不同的更新处理。同时，与传统的GMM方法及MGMM方法进行重复性背景的对比实验。结果显示，本文所提出的方法实现了记忆重复背景的功能，从而更快地适应场景的变化，减少前景误判，适用于存在重复性运动场景的建模。
参考文献
[1]BRUTZER S，HOFERLIN B，HEIDEMANN G。Evaluation of background subtraction techniques for video surveillance ＼[C＼]//IEEE Conference on Computer Vision and Pattern Recognition。Providence， RI，2011：1937-1944。
＼[2＼]STAUFFER C，GRIMSON W E L。Adaptive background mixture models for realtime tracking＼[C＼]//IEEE Conference on Computer Vision and Pattern Recognition。 Fort Collins，1999。
＼[3＼]WU Chuan，WANG Yuanyuan， KARIMI H R。 A robust aerial image registration method using Gaussian mixture models＼[J＼]。 Neurocomputing， 2014，144： 546-552。
＼[4＼]WONJUN Kim， CHANGICK Kim。 Background subtraction for dynamic texture scenes using fuzzy color histograms＼[J＼]。 IEEE Signal Processing Letters， 2012， 19（3）： 127-130。
＼[5＼]王志明， 张丽， 包宏。 基于混合结构神经网络的自适应背景模型 ＼[J＼]。 电子学报， 2011，39（5）： 1053-1058。
WANG Zhiming， ZHANG Li， BAO Hong。 Adaptive background model based on hybrid structure neural network ＼[J＼]。 Acta Electronica Sinica， 2011，39（5）： 1053-1058。（In Chinese）
＼[6＼]HAN B， DAVIS L S。 Densitybased multifeature background subtraction with support vector machine ＼[J＼]。 IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（5）： 1017-1023。
＼[7＼]YAO J，ODOBEZ J M。 Fast human detection from video using covariance features＼[C＼]//The Eighth International Workshop on Visual Surveillance。Marseille，2008。
＼[8＼]LIN Hornghorng， CHUANG Jenhui， LIU Tyngluh。 Regularized background adaptation： A novel learning rate control scheme for gaussian mixture modeling＼[J＼]。 IEEE Transactions on Image Processing， 2011， 20（3）： 822-836。
＼[9＼]ZIVKOVIC Z。 Improved adaptive Gaussian mixture model for background subtraction＼[C＼]//IEEE International Conference on Pattern Recognition。 IEEE，2004：28-31。
＼[10＼]肖进胜，单姗姗，易本顺， 等。基于区分灰度投影稳像的运动目标检测算法＼[J＼]。湖南大学学报：自然科学版，2013， 40（6）：96-102。
XIAO Jinsheng， SHAN Shanshan，YI Benshun， et al。 Moving targets detection based on subzone gray projection video stabilization＼[J＼]。Journal of Hunan University：Natural Sciences， 2013，40（6）：96-102。（In Chinese）
＼[11＼]CHENG Fanchieh，HUANG Shihchia，RUAN Shanqjang。 Illuminationsensitive background modeling approach for accurate moving object detection＼[J＼]。 IEEE Transactions on Broadcasting， 2011， 57（4）：794-801。
＼[12＼]齐玉娟， 王延江， 李永平。 基于记忆的混合高斯背景建模＼[J＼]。自动化学报， 2010， 36（11）： 1520-1526。
QI Yujuan，WANG Yanjiang， LI Yongping。 Memory based Gaussian mixture background modeling＼[J＼]。 Acta Automatica Sinica， 2010， 36（11）： 1520-1526。 （In Chinese）
＼[13＼]XIAO Jinsheng， LI Wenhao， LIU Guoxiong，et al。Hierarchical tone mapping based on image color appearance model＼[J＼]。IET Computer Vision， 2014， 8（4）： 358-364。
混合算法 第7篇
在实际离散制造过程中,产品生产过程一般包括零件加工、部件装配和产品总装,其生产形式是作业车间和流水车间集成的混流混合车间模式。零件加工车间、部件装配车间与产品总装车间在计划制定、物料供应和调度执行方面都紧密相关。生产调度及其执行过程中,优化多集中于单一车间而忽略与其他车间的关联影响。如零件加工车间往往以产品切换费用、换模费用的最少等目标来安排生产,而部件装配车间、产品总装车间以生产周期最短等目标来安排生产,从而导致零件的加工进度跟后续的部件装配或者产品总装不相匹配,造成大量的缓冲区在制品库存,拉长了产品的整个生产周期,影响了生产流程化,无法达到系统最优。在混流生产模式下,这种情况尤为严重。因此,对于具有自制件的混流装配生产过程,必须从整体优化的角度出发,建立多车间的集成调度。
目前的研究主要针对零部件车间的加工调度或者零部件装配车间的排序调度等单一车间展开,对作业车间和流水车间的集成研究较少。Lee等[1]研究了三机装配型流水车间的调度问题,优化目标是最小化最大完工时间。文献[2-3]以最小化最大完工时间为优化目标,研究了带装配操作的两机流水车间调度问题。上述研究考虑的加工装配车间过于简单,只是将装配车间看成一台机器,研究的是单品种生产,且没有考虑各个车间之间的缓冲区在制品库存问题。王炳刚等[4,5]研究了带有限缓冲区的流水车间集成调度问题,建立了带并行机的流水部件线和单机流水总装线的集成调度模型,有效弥补了上述研究的不足,但仍没有关于作业车间与流水车间的混合模型。
1 问题描述
1.1 混流混合车间模型
本文所要研究的混流混合车间由三部分组成:第一部分为加工零件的作业车间,以批为单位进行生产;第二部分为装配部件的流水车间,以个为单位进行装配;第三部分为产品总装的流水车间,以个为单位进行装配。图1所示为所要研究的混流混合车间简化模型。
混流混合车间主要有以下特点:(1)混合车间生产不同品种的产品,且以混流生产方式组织生产;(2)零件加工车间、部件装配车间、产品总装车间之间由缓冲区连接;(3)零件加工车间为部件装配车间和产品总装车间提供物料,部件装配车间为产品总装车间提供物料;(4)各生产单元间通过物料约束关联,适当的缓冲设置可在生产流畅的情况下减少生产运作成本;(5)同时具有作业车间调度和流水车间调度问题的各种约束条件;(6)加工零件的作业车间以批为单位进行生产,部件装配、产品总装的流水车间以个为单位进行生产。
1.2 混流混合车间调度模型的构建
在混流混合生产系统中,各生产单元是相对独立的子系统,虽然具有不同的生产特征和优化目标,但仍相互依赖、相互制约。在生产调度过程中,各生产单元通常单独制定调度方案,单方面进行各自生产单元的优化,虽然达到各自的生产目标,但却以其他单元生产目标的弱化为代价,使生产内部不协调,经常出现需要的零部件未生产,而暂时不需要的零部件却大量堆积,产生大量在制品库存,严重影响了生产物流的流畅性,增加了企业生产、场地和资源的成本。因此,集成调度零件加工车间、部件装配车间、产品总装车间,并控制其之间的缓冲区在制品库存具有非常重要的实际意义。针对混流混合车间调度问题,建立以最小化缓冲区在制品库存成本为目标的优化模型。
混流混合车间调度问题可描述为,以零件加工车间、部件装配车间和产品总装车间组成的三段生产系统中,零件加工车间有m台机器,加工n种零件,部件装配车间有l1个装配工位,生产r1种部件;产品总装车间有l2个装配工位,生产r2种产品,生产调度旨在安排各工件在各设备和工位上的生产顺序,实现既定目标的优化。为了便于研究混流混合车间调度问题,给出以下假设条件:
(1)只对自制件在流水车间装配的调度进行研究,外购外协件不在考虑范围内。
(2)若零件加工车间为部件装配车间、产品总装车间的装配工位加工了一批零件,或者部件装配车间为产品总装车间的装配工位加工了某种部件,而装配工位不需要,即装配工位已有的零部件能够满足装配所需要的数量,或者已加工的零部件不是装配工位所需要的类型,则将此批零件或者此种部件暂存在缓冲区,反之向相应工位配送,其中的配送时间假定为零。
(3)作业车间内零件的工序之间有工艺约束,不同零件之间不存在工艺约束。
(4)在零时刻,所有的零件都可以被加工。
(5)在零时刻,所有的机器及装配工位都已经准备就绪。
(6)工序加工时间已经包含了工序的准备时间和搬运时间。
目标函数为最小化缓冲区在制品库存成本,模型如下:
式中,Ai为一批自制零件i所占的面积;Ax为一个部件x所占的面积;Ci为单位面积的零件i在缓冲区存放单位时间所占用的成本;Cx为单位面积的部件x在缓冲区存放单位时间所占用的成本;Ti为一批零件i被加工出来的完工时刻;T′i为此批零件被下游领走的时刻;Tx为一个部件x被生产出来的完工时刻;T′x为此部件被下游领走的时刻。
1.2 模型约束
1.2.1 工艺顺序约束
(1)零件加工车间约束。自制零件的前一道工序加工完成后,才能加工后一道工序,其约束表达式为
式中,Eij、Eih分别为零件Ni在机器Mj和Mh上加工的完工时刻;D是一个足够大正数,作为对约束违背的惩罚系数;tij为一批自制零件Ni在机器Mj加工所需要的时间。
(2)部件装配车间约束。部件的前一道工序装配完成后,才能装配后一道工序,其约束表达式为
式中,Exk、ExH分别为部件装配流水车间中部件x在第k个装配工位和第H个装配工位上的完工时刻;txk为一个部件x在第k个装配工位上装配所需要的时间。
(3)产品总装车间约束。产品的前一道工序装配完成后,才能装配后一道工序,其约束表达式为
式中,Eys、EyK分别为产品总装流水车间产品y在第s个装配工位和第K个装配工位上的完工时刻;tys为一个产品y在第s个装配工位上装配所需要的时间。
1.2.2 资源约束
(1)零件加工作业车间约束。在同一台机器上,一批零件的加工任务完成后,方能开始下一批加工,其约束表达式为
(2)部件装配流水车间约束。在同一个装配工位上,一个装配任务完成后,方能开始下一个任务,其约束表达式为
(3)产品总装流水车间约束。在同一个装配工位上,一个装配任务完成后,方能开始下一个任务,其约束表达式为
1.2.3 时间约束
(1)部件装配完工时间等于该部件进入工位的时间与装配操作时间以及在该工位的等待时间之和:
式中,Bxk为部件装配流水车间中部件x在装配工位k上可以开始装配的时刻,即表示部件x已经完成前一道工序的装配任务,装配工位k已经完成前一个部件的装配任务;Δxk为部件装配车间部件x在装配工位k上开始装配的延迟时间(停工待料时间);Qikt、Qikt′分别为t和t′时刻部件装配车间的装配工位k含有的自制零件i的数量;Oixk为t时刻部件装配车间部件x在装配工位k上装配时需要的自制零件i的数量;txk为一个部件x在第k个装配工位上装配所需要的时间。
(2)总装配件完工时间等于该产品进入工位的时间与装配操作时间以及在该工位的等待时间之和:
式中,Bys为产品总装流水车间产品y在装配工位s上可以开始装配的时刻,即表示产品y已经完成前一道工序的装配任务,装配工位s已经完成前一个产品的装配任务;Δys为产品总装流水车间产品y在装配工位s上开始装配的延迟时间(停工待料时间);Qist为t时刻产品总装车间装配工位s含有自制零件i的数量;Qiys为产品总装车间的产品y在装配工位s进行装配时需要的自制零件i的数量;Qxst为t时刻产品总装车间装配工位s含有部件x的数量(前面已经假设零部件从缓冲区配送到装配工位的时间为零,此时的数量为装配工位和缓冲区中数量的总和);Qxys为产品总装车间产品y在装配工位s上进行装配时需要部件x的数量;tys为一个产品y在第s个装配工位上装配所需要的时间。
模型中,aihj、bigj、a′xHk、b′xgk、a′yKs、b′ygs为指示变量,aihj、a′xHk、a′yKs为0,表明该调度方案不符合工艺顺序约束要求;bigj、b′xgk、b′ygs为0,表明该调度方案不符合资源约束要求。
2 混合遗传算法求解调度模型
遗传算法是求解组合优化问题的优秀算法,具有良好的全局搜索能力,针对混流混合车间调度解空间大的特征,具有较好的优化效果。目前,GA在装配线和作业车间独立优化问题上已取得良好的应用效果[6?8],与模板退火算法结合的混合算法也取得了良好效果[9]。因此,将遗传算法作为算法主流程。为提高局部搜索能力,在遗传算法的流程中嵌入模拟退火算法,建立了一种混合算法。模拟退火算法可以对每一代种群中最好的部分个体执行退火操作,有效提高邻域搜索效率,弥补遗传算法在局部搜索方面的不足。
2.1 算法流程
图2所示为混合算法的主要流程。相关说明如下:(1)算法包含5个基本参数(种群规模N、最大迭代次数M、初始温度θ0、终止温度θend、退温系数λ),随机产生规模为N的初始种群P(T),初始代数T=0;(2)适应度计算,计算种群中每个个体的适应度值;(3)对种群进行选择、交叉、变异操作,产生新一代种群P(T+1),并将种群中具有最佳适应度值的个体集合作为P(x);(4)对种群P(x)进行模拟退火操作;(5)判断迭代条件,如果满足则输出最优解,并终止算法。
2.2 算法详细设计
2.2.1 编码
混流混合车间调度问题的编码规则如下:根据给定的生产任务,先将产品级分解为部件级、零件级,然后根据各种零件的数量、比例和加工批量确定零件生产车间的零件生产批量;部件装配车间和产品总装车间是流水车间,取各产品数量的最大公约数,并通过各产品数量除以该值确定各部分的最小生产循环,对一个循环中的产品装配工序进行编号;编码分成三部分,其中,第一部分为零件加工车间零件的批量编号,第二部分为部件装配车间的部件编号,第三部分是产品总装车间的产品编号。为了修正操作运算后产生的非法解,分别对零件加工工序和装配工序的对应编号从小到大进行重排序,从而保证产生的新种群都为合法解。
示例:产品总装流水车间要生产10个A、10个B;装配1个产品A需要1个部件U、1个零件a和1个零件b;装配1个产品B需要1个部件V、1个零件a和1个零件c;装配1个部件U需要1个零件d,装配1个部件V需要1个零件e。其中,各零件加工批量为10。假定零件加工作业车间由4台设备(M1、M2、M3、M4)组成,加工零件a、b、c、d、e。各零件工序作业时间及作业顺序如表1所示。表1中,逗号左侧的数字为加工时间(s),逗号右侧的数字为加工工序的顺序号。
由已知条件可以知道,生产10个产品A、10个产品B需要零件20个a、10个b、10个c、10个d、10个e,需要部件10个U、10个V,即零件加工作业车间需要加工2批a、1批b、1批c、1批d、1批e。零件序列为[a,a,b,c,d,e],分别对各零件工序进行编号,如表2所示。表2中,a出现2次,表示零件a的2个不同批次;部件装配流水车间需要装配10个U、10个V,则部件装配流水车间的最小生产循环为1个U、1个V,对其进行编号,如UV为1个最小生产循环;产品总装流水车间的最小生产循环为1个产品A和1个产品B,如AB为一个最小生产循环。
图3所示为一条染色体编码。染色体采用三段式的编码方法,S1段为作业车间编码,S2段为部件车间编码,S3段为装配车间编码。其中,编号1~4的码值为1,该码值按照顺序分别代表第一个工件即工件a的4个工序。采用该编码方法可在交叉变异操作时避免非法染色体的产生。
2.2.2 适应度函数
由于优化目标为缓冲区在制品成本最小化,因此将目标函数适当改变作为适应度函数:
2.2.3 种群选择
算法根据适应度函数值采用赌轮盘法选择个体遗传到下一代群体中。
2.2.4 交叉与变异
鉴于混流混合车间调度问题特点,零件加工车间、部件装配车间、产品总装车间的各段染色体编码进行各自独立的交叉和变异操作。交叉方法采用单点交叉;变异采用交换变异方法,即交换两个随机位置上的基因[10]。
2.2.5 模拟退火算法
为提高精英群体的质量,算法采用变温度的模拟退火算法对每代最优的群体P(x)执行模拟退火操作SA。最优解x操作后得到的新解x′=SA(x)。如果x′优于x则保留新解,否则以概率exp(-Δθ′/θ)接受新解,其中,θ为当前温度,Δθ′为原解与新解的适应度差。新解的产生通过交换变异的方法,分别对三段编码各自进行交叉,防止不同类调度工件的串码,从而保证染色体的合法性。算法进程由初始温度θ0、终止温度θend、退温系数λ控制。模拟退火算法增强了个体的局部搜索能力,但增加了时间和计算成本,为平衡算法效率,算法采用变温度的温度适应算法,其中,当前温度为
式中,T为当前迭代代数;ceil(*)表示对括号中内容向下取整。
为保证迭代末期的有效温度,设定θ′e不小于1。在变温度的支持下,算法初期可提高算法的全局寻优能力,算法后期可加快算法的收敛速度,从总体上提高了算法的执行效率。
2.2.6 终止准则
以预先设定的最大进化代数M为终止条件。
3 实例验证
混流混合车间在生产中应用广泛,现以某冰箱制造企业为例对模型和算法进行验证。该生产系统由零件加工车间、部件装配车间和一条总装配线组成。零件加工车间的主要任务为生产8种自制零件。自制件集合为{N1,N2,…,N8},作业车间机器集合为{M1,M2,…,M10}。自制件在各机器上的加工以批为单位,工艺顺序及加工时间如表3所示。
注:“-”表示自制件不需要在该机器上加工;逗号前的数字为工序加工顺序;逗号后的数字为工序加工时间,s。
部件装配车间主要负责门体A、B的装配,其装配工艺与时间如表4所示。
s
产品总装流水车间共有33个装配工位,流转产品Q1、Q2、Q3、Q4,对应的装配工序作业时间如表5所示。
s
表6为零部件对应的产品需求矩阵,对应值为所需数量。
注:“/”表示产品与需求部件没有需求关系。
元/(d·m2)
计划期内产品Q1、Q2、Q3、Q4的生产任务分别为320台、160台、320台、160台。门体A、B的生产任务均为480个;内胆A、内胆B、侧板A、U壳A、后背板A、后背板B,门壳A、门壳B的加工任务均为3批。因此,产品总装车间的产品Q1、Q2、Q3、Q4生产任务比例为2∶1∶2∶1;部件装配车间的门体A、B生产任务比例为1∶1;零件加工车间比例均为1∶1。算法初始种群大小设为100,交叉率为0.9,变异率为0.02,最大迭代次数100,θ0=10,θend=0.1,λ=0.9。根据已知条件,以MATLAB为算法软件编程平台进行求解运算。取最佳结果之一,得到三段式编码[1_1_1_2_2_2_3_5_7_4_6_3_8_7_6_3_3_4_4_5_5_5_6_6_7_8_8]-[1_2]-[2_1_3_3_1_4],对应总的最小成本费用为1643元。其中,部件段最小投产循环为[门体A,门体B],总装线最小投产顺序为[Q2,Q1,Q3,Q3,Q1,Q4],零件车间调度甘特图(图4)中,N11代表第1个工件的第1个工序,其余以此类推。
4 结语
混流混合车间是离散生产中常见的生产组织方式,本文描述了混流混合车间调度问题的特点,建立了混流混合车间缓冲区在制品成本最小优化模型,给出了集成模拟退火算法的混合遗传算法,并对模型进行求解,最后通过某冰箱企业混流混合车间调度问题的实例研究,验证了所建模型和算法的有效性。文中仅针对混流混合车间做了初步的集成调度研究,但混流混合车间作为一种混合生产系统,影响因素多,并涉及多个优化目标,后续研究应发掘影响生产系统的瓶颈因素,实现各子系统的多目标协调调度。
摘要：为解决一类具有多品种混流生产特征和作业车间与流水车间集成的混流混合车间协同调度问题,给出了以在制品成本最小为目标的混流混合车间调度问题模型;采用零件加工、部件装配、产品总装的三段协同编码方法,给出了一种集成模拟退火算法的混合遗传算法,并在模拟退火算法中引入变温度参数来平衡算法效率。最后,通过某冰箱混流装配企业典型实例验证了模型和算法的有效性。
关键词：混流混合车间,流水车间,作业车间,混合遗传算法,模拟退火算法
参考文献
[1]Lee C Y,Cheng T C E,Lin B M T.Minimizing theMakespan in the 3-Machine Assembly-type FlowShop Scheduling Problem[J].Management Science,1993,39(5):616-625.
[2]Cheng T C E,Wang G.Scheduling the Fabricationand Assembly of Components in a Two-machineFlow Shop[J].IIE Transactions,1999,31(2):135-143.
[3]Lin B M T,Cheng T C E.Fabrication and AssemblyScheduling in a Two-machine Flow Shop[J].IIETransactions,2002,34(11):1015-1020.
[4]王炳刚,饶运清,邵新宇,等.基于多目标遗传算法的混流加工/装配系统排序问题研究[J].中国机械工程,2009,20(12):1434-1438.
[5]王炳刚.混流加工/装配系统集成优化研究[J].机械工程学报,2010,46(17):114-122.
[6]苏平,于兆勤.基于混合遗传算法的混合装配线排序问题研究[J].计算机集成制造系统,2008,14(5):1001-1007.
[7]Chul J H,Kim Y.A Genetic Algorithm for MultipleObjective Sequencing Problems in Mixed Model As-sembly Lines[J].Computers and Research,1998,25(7):675-690.
[8]袁坤,朱剑英.一种求解多目标柔性Job Shop调度的改进遗传算法[J].中国机械工程,2007,18(2):156-160.
[9]鲁建厦,蒋玲玲,李修琳.基于混合粒子群算法求解装配线第二类平衡问题[J].中国机械工程,2010,21(4):420-424.
混合遗传算法及其应用 第8篇
遗传算法是近年来发展起来的一种新型优化算法, 是基于自然选择和遗传学机理的迭代自适应概率性搜索方法。它通过模拟生物进化的途径问题的解域中定向搜索最优解, 在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用。
遗传算法的实现涉及5个主要因素:参数编码、初始群体的设定、评估函数 (即适应函数) 的设计、遗传操作的设计和算法控制参数的设定。对于传统方法较难求解的一些NP问题, 遗传算法往往能得到更好的结果。但对传统方法已能较好解决的问题 (如一般的非线性优化问题) , 它并没有较强的优势。遗传算法主要采用群体搜索技术, 通过对解的不断组合、随机改变以及对候选解的评估和选择来完成求解过程。在达到全局最优解前, 它尚存在收敛慢的问题。设计遗传算法时往往需要在其通用性与有效性之间折衷。设计针对问题的特定遗传算子, 可以更有效地求解问题, 但缺乏通用性。另一种途径是将遗传算法与问题领域中一些传统的寻优方法 (如爬山法、模拟退火法、牛顿法等) 结合起来, 可在保持算法一定的通用性时提高算法的效率。
本文考虑一类非线性函数优化问题, 即:
其中f (x) 是n元连续函数, D是Rn的有界子集。本文探讨将梯度法与遗传算法相结合的算法, 梯度法对初始解的构成具有较强的依赖性, 算法执行过程中难于发现新的可能存在最优解的区域。通过将它与遗传算法相结合, 一方面可以利用其局部搜索能力, 另一方面可通过遗传算法来不断“发现”新的更有希望的搜索区域, 并动态调整可变多面体法的搜索方向, 从而使算法具有更好的灵活性, 也使算法更易于并行化。实验表明, 对于求解上述非线性优化问题, 混合遗传算法具有比传统遗传算法和梯度法都好的性能。
1 混合遗传算法
1.1 编码方式
编码的实质是在问题的解空间与算法的搜索空间之间建立一个映射。传统遗传算法一般采用一种将实数空间离散化的二进制编码方式。这种方式存在编码长度影响求解精度、操作费时、不直观等缺点, 因而提出了实数的直接编码方式并表明可以获得更好的性能。在实数编码方式下, 每个个体用一个n维的实向量来表示, 这种方式具有直观、易操作的优点, 且可以针对它设计非传统的交叉算子。本文采用此编码方式。
1.2 交叉和选择操作
正交遗传算法在非线性优化问题及其他组合优化问题中已显示出其有效性, 我们的算法采用了正交交叉算子。由两个父本交叉操作产生一组个体, 从新个体和两个父本中选择最优的进入下一代群体。由于采用局部选择而不是全局选择, 在一定程度上保持了群体的多样性。
1.3 变异操作
在实数编码方式下, 变异操作对个体X的每个分量X[i]作用一个随机偏差量, 即:
X′[i]=X[i]+δ, i=1, 2, …, n
在进化规划和进化策略中, 广泛采用了高斯变异算子, 用正态分布的随机变量来作为变异操作中的偏差量。
1.4 局部搜索
在本文中, 我们采用梯度法进行局部搜索, 梯度法步骤如下:
(1) 选定ε>0为终止限。选定初始点X (0) , 令k=0。
(2) 计算△f (X (k) ) 。如果‖△f (X (k) ) ‖<ε, 迭代停止, 取近试最优解X*=X (k) , 否则, 令S (k) =-△f (X (k) ) , 从X (k) 出发沿S (k) 作一维搜索, 求得λk使得mλ>i0nf (X (k) +λS (k) ) =f (X (k) +λkS (k) ) 。
(3) 令X (k+1) =X (k) +λkS (k) , k+1→k, 返回步骤 (2) 。
1.5 终止准则
算法运行停止的条件包括以下的一种或它们的结合形式:
(1) 算法收敛到一个不动点或连续几次迭代所获得的改变量小于要求的精度值。
(2) 达到算法规定的最大迭代次数、或最大执行时间、或函数的最大调用次数 (对解空间的最大采样次数) 。我们用最大采样次数和最大迭代次数来控制算法的终止。
1.6 算法描述
混合遗传算法的主要步骤为: (1) 初始化:随机产生一个分布均匀的初始群体 (包含N个初始解) ; (2) 交配:按两两配对的原则将群体中的个体配对并执行第1.2节的正交交叉操作; (3) 变异:群体中每个个体以Pm的概率进行变异; (4) 局部搜索:采用梯度法反复进行局部寻优操作; (5) 终止:若终止条件满足, 则算法中止, 否则转向步骤 (2) 。
2 实验结果
我们用实验的方法来比较标准遗传算法和混合遗传算法的性能。标准遗传算法采用与混合遗传算法相同的交叉和变异操作。在实验中, 我们选择了下面的函数:
该函数存在多个极值点, 其中x*=0.1275是唯一全局极大点, f (x*) =19.8949。
在我们的仿真中, 采用16位二进制编码, 群体规模取50, 试验40次, 迭代次数为100代, 结果如表1所示。
3 结束语
本文给出了一种求解非线性全局最优化问题的混合遗传算法, 它将梯度法与正交交叉算子结合起来, 既可利用遗传算法的全局搜索能力, 又能通过局部搜索加快算法的收敛。实验表明, 本文提出的混合遗传算法能有效地处理一些传统遗传算法和寻优方法较难处理的函数优化问题。
参考文献
[1]GOLDBERG D E.Genetic Algorithms in Search, Optimization and Machine Learning[M].Reading, MA:Addison-Wesley, 1989.
[2]RENDERS J-M, FLASSE S P.Hybrid methods using genetic algo-rithms for global optimization[J].IEEE Transactions on Systems, Man, and Cybernetics (Part B) , 1996 (2) .
[3]WRIGHT A H.Genetic algorithm for real parameter optimization.In:Rawlins G ed[D].Foundations of Genetic Algorithms.San Francis-co:Morgan Kaufmann, 1991.
[4]ESHELMAN L J, SCHAFFER J D.Real-coded genetic algorithms and interval-schemata[J].Foundations of Genetic Algorithms, 1993 (2) .
[5]陈国良, 王熙法, 庄镇泉.遗传算法及其应用[M].北京:人民邮电出版社, 1996.
[6]张晓缋, 戴冠中, 徐乃平.遗传算法种群多样性的分析研究[J].控制理论与应用, 1998 (1) .
混合算法 第9篇
粒子群算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart[1,2]在1995年提出的一种基于群体智能的随机进化算法,是在鸟群、鱼群和人类社会行为规律的启发下提出来的。由于算法收敛的速度快、设置参数少、实现简单,近年来受到学术界的广泛重视。现在,PSO在函数优化、神经网络训练、模式分类、模糊系统控制以及其它工程领域都得到了广泛的应用。尽管传统的PSO在低维空间的函数寻优问题上具有求解速度快、质量高的特点,但是一旦函数的维数增加,其优化性能便急剧下降,容易陷入局部极值,导致收敛精度降低和不易收敛到全局最优。
人工蜂群算法[3—6](Artificial Bee Colony,ABC)是Karaboga于2005年提出的一种基于群体智能的随机优化算法,算法模拟蜜蜂群体的采蜜行为。蜜蜂根据各自的分工进行不同的活动,并实现蜂群信息的共享和交流,从而找到问题的最优解。目前,关于ABC的研究与应用还处于初级阶段,但由于其控制参数少、易于实现、计算简洁等优点,已被越来越多的学者所关注。ABC已成功的应用于解决函数的数值优化、人工神经网络训练[7,8]、滤波器设计[9]、生产调度[10]、机器人路径规划[11]等工程领域问题。ABC较好的平衡了探索和开采的能力,但是由于进化方式和选择策略的影响,使算法在快速收敛的同时容易陷入局部最优。
为了克服PSO和ABC单个算法在求解全局优化问题时容易陷入局部最优的缺陷,本文基于PSO和ABC提出了一种新型的混合优化算法———PSO-ABC。PSOABC基于一种双种群进化策略,其中一个种群中的个体按照PSO操作进化,另一个种群的个体按照ABC操作进化,同时在ABC中按轮盘赌的选择方式选择个体进化所需的随机个体,此外,算法在进化过程中,每隔一定的迭代次数利用一种信息交流机制交流搜寻信息,避免各自种群陷入局部最优。
1 粒子群算法和人工蜂群算法
1.1 粒子群算法
粒子群算法是一种基于种群的优化算法,种群称为粒子群,粒子群中的个体称为粒子。设有N个粒子组成一个群体,其中第i个粒子表示为一个D维的向量xi=(xi1,xi2,…,xi D);i=1,2,…,N,即第i个粒子在D维的搜索空间中的位置是xi。第i个粒子的飞行速度也是一个D维的向量,记为vi=(vi1,vi2,…,vi D),记第i个粒子迄今为止搜索到的个体极值为pi=(pi1,pi2,…,pi D),整个种群迄今为止搜索到的全局极值为pg=(pg1,pg2,…,pg D),粒子群算法采用下列公式对粒子操作。
其中,i=1,2,…,N,d=1,2,…,D,w表示惯性权重,c1和c2表示学习因子,r1和r2是[0,1]上均匀分布的随机数,每一维粒子的速度都被限制在一个最大速度vmax(vmax>0)之间,若vi>vmax时,取vi=vmax;若vi<-vmax时,取vi=-vmax。
文献[12]在粒子群算法中引入了线性减小的惯性权重,将(1)式变换为
性权重的初始值和终值,I为当前迭代次数,Imax为最大迭代次数。
2.1 人工蜂群算法
在人工蜂群算法中,蜂群由采蜜蜂、观察蜂和侦察蜂三个部分组成,每个蜜源的位置代表优化问题的一个可能解,蜜源的收益度(蜜量)对应于问题的适应度(函数值)。首先,人工蜂群算法随机产生初始种群,即N个初始解(N为采蜜蜂的数目也为蜜源数目)。每个解xi(i=1,2,…,N)为一个D维的向量(D为搜索空间的维数)。经过初始化,采蜜蜂、观察蜂和侦察蜂开始进行循环搜索。采蜜蜂记住自己以前的最优解,在采蜜源附近邻域搜索,搜索公式为
式(4)中,k∈{1,2,…,N}和j∈{1,2,…,D}是随机选择的下标,并且k≠i,φ是[-1,1]上均匀分布的随机数。随着迭代次数的增加,(xij-xkj)之间的距离缩小,搜索的空间也缩小,即搜索的步长缩小,动态地调整步长有助于算法提高精度,并最终获得最优解。
采蜜蜂采用贪婪准则,比较记忆中的最优解和邻域搜索解,当搜索解优于记忆最优解时,替换记忆解;反之,保持不变。所有的采蜜蜂完成搜索过程后,将蜜源信息通过舞蹈区与观察蜂共享。观察蜂据此按与花蜜量相关的概率选择一个蜜源位置,蜜量大的采蜜蜂吸引观察蜂的概率大于蜜量小的采蜜蜂。观察蜂像采蜜蜂那样对记忆中的位置做一定的改变,并检查新位置的花蜜量。若新位置优于记忆中的位置,则用新位置替换原位置;反之,保持不变。一个观察蜂选择某个蜜源的概率为
式(5)中fi为第i个解的适应值。假如一个蜜源经过限定的的循环次数limit之后不能被改进,则该蜜源处的采蜜蜂成为侦察蜂,该蜜源位置将会被侦察蜂在解空间内发现的随机新位置代替。假设被放弃的位置为xi,则侦察蜂通过下列公式替换xi
3 基于PSO和ABC的混合优化算法
从上节描述中可以看出,PSO和ABC产生新个体的方式不同,因而它们在寻优时的效果也会不同。所以将它们相互融合,提出一种混合优化算法———PSOABC。PSOABC将种群随机地等分为两组,其中一组种群中的个体按照PSO操作进化,现选取文献[12]提出的粒子群算法,个体更新采用式(2)和式(3);另一组种群中的个体按照ABC操作进化,由于在原算法中,新个体由父代个体和另外一个不相同的随机个体组成,这虽有利于保持种群的多样性,但却使得搜索具有一定的盲目性,影响了算法的收敛速度。为加快算法的收敛速度,按轮盘赌的选择方式来选择式(4)中的xk,选择的概率为公式(5)。同时,在进化过程中,每隔一定的迭代次数利用一种信息交流机制交流搜寻信息使信息能够在两个种群中传递,有助于个体避免错误的信息判断而陷入局部最优点。通过对测试函数进行仿真实验,每隔50代进行一次信息交流,信息交流方式如下:
1)式(3)中pg用两个种群中的最优个体来替代;
2)式(4)中xk从采用PSO操作进化的种群中随机选取;
3)信息交流结束,继续下一步操作。
PSOABC算法的步骤为:
Step 1设置群体规模N,最大迭代次数Maxgen,限定的的循环次数limit,学习因子c1和c2,惯性权重的初始值w1和终值w2;
Step 2将群体等分为两个种群,种群1中的个体按照PSO操作进化,种群2中的个体按照ABC操作进化;
Step 3设置迭代计数器t=0;
Step 4判断是否满足信息交流条件,若满足则进行信息交流;
Step 5种群1和种群2分别按式(3)、式(2)和式(4)产生新解,并计算其适应值;
Step 6更新种群1中的pi和pg;
Step 7如果种群2中新解的适应值优于xi,则用其替换xi,否则不变;
Step 8计算xi的适应值,并根据式(4)计算概率qi;
Step 9观察蜂根据qi选择蜜源,并按式(4)产生新解,如果新解的适应值优于xi,则用其替换xi,否则不变;
Step 10经过limit次循环后,判断是否有需要丢掉的解,若有,则按式(6)产生满足约束条件的新解;
Step 11更新迭代计数器t=t+1并记录当前整个群体中最佳个体,如果满足精度要求或进化已达到最大迭代次数,则终止算法,否则转至Step 4。
4 仿真实验
为了验证改进算法的性能,选择4个测试函数用于优化实验,由于ABC在许多优化问题中都表现出优于PSO[6],故仅将提出的混合优化算法PSO-ABC与ABC的优化结果进行对比。进行测试时,蜂群群体规模为40。其中,PSOABC的参数设置为
ABC的参数设置为limit=1 000。
4个基准测试函数分别为:
1)Sphere函数
2)Rosenbrock函数
3)Rastrigin函数
4)Griewank函数
上述4个测试函数具有不同的特点,可以充分考察算法对不同类型问题的优化性能。它们可以分为单峰函数(f1(x)和f2(x))与多峰函数(f3(x)和f4(x))。f1(x)是较为简单的单峰函数,f2(x)虽是单峰函数,但其全局最优点隐藏于一条狭长的通道中不易获得;f3(x)和f4(x)是复杂的非线性多峰函数,具有许多局部极值点,一般算法较难找到全局最优值,可以用来检验算法的全局搜索性能。四个函数的搜索空间、初始范围和最小值如表1所示。
我们采用最优适应值(Best Fitness,BF)、最差适应值(Worst Fitness,WF)、平均最优适应值(Mean Best Fitness,MBF)和标准差(Standard Deviation,SD)来评价算法的性能。其中BF、WF、MBF、SD分别为算法独立运行10次的最优适应值、最差适应值、平均最优适应值和标准差。MBF反映了在给定迭代次数下算法所能达到的精度,SD反映了算法的稳定性和鲁棒性。
表2为PSOABC、ABC在上述参数的设置下对4个测试函数分别独立运行10次得到平均最优适应值和标准差。图1—图4分别给出4个测试函数的平均最好适应值进化曲线。
由表2可知,对于最简单的函数f1(x),两种算法都很快收敛到最优适应值。由于f1(x)是单峰函数,只有一个最优值,快速收敛到最优值不是问题。然而,如图1所示,PSOABC收敛速度在迭代初期与ABC相差不大,大约1 200代以后PSOABC收敛速度远远优于ABC算法。
对于经典的复杂优化函数f2(x),由于在取值区间内走势平坦,为算法提供少量信息,要收敛到全局最优点机会微乎其微。从表2可以看出,PSO-ABC性能明显优于ABC算法。在图2中,ABC在进化早期收敛速度很快,但在进化中后期收敛速度明显减慢,而PSOABC在进化过程中始终保持较快的收敛速度。
多峰函数Rastrigin、Griewank均是复杂的非线性全局优化问题,主要用来测试算法的全局搜索性能,从表2、图3、图4可以看出,PSOABC的精度和收敛速度均高于ABC。由于这些函数自身的特性,算法很容易陷入局部最优而导致搜索停滞,但PSO-ABC对信息的交流使其尽可能的跳出局部最优,提高了算法的收敛精度。可见,PSOABC具有良好的全局搜索性能和较快的搜索速度。
通过以上分析可知,PSOABC不论对单峰函数还是多峰函数,在求解精度、收敛速度以及稳定性和鲁棒性等方面比都要优于ABC,是一种有效的全局优化算法。
5 结论
将两种或数种算法结合起来产生新的混合优化算法以达到更好的优化效果日益成为当前优化研究领域的热点,本文基于PSO和ABC提出了一种混合优化算法—PSOABC,算法在解的开发和探索两个方面保持了较好的平衡,通过信息交流机制交流搜寻信息,避免各自陷入局部最优。测试函数的仿真实验表明算法在解的收敛性和稳定性等方面都优于其它两种算法。以后的工作将会考虑将ABC算法与其它智能算法如遗传算法、模拟退火算法、人工鱼群算法等结合起来提出更为优秀的新型混合算法。
参考文献
[1] Kennedy J,Eberhart R C.Particle swarm optimization.In:proceed-ings of IEEE International Conference on Neural Networks,Piscat-away,NJ:IEEEPress,1995:1942—1948
[2] Eberhart R C,Kennedy J.A new optimizer using particle swarm the-ory.In:Proc of the Sixth International Symposium on Micro Machineand Human Science,Nagoya,Japan,1995:39—43
[3] Karaboga.D.An idea based on honey bee swarm for numerical opti-mization.Technical Report-TR06,Kayseri:Erciyes University,En-gine-ering Faculty,Computer Engineering Departm-ent,2005
[4] Karaboga D,Basturk B.A powerful and efficient algorithmfor numer-ical function optimization:artificial bee colony(ABC)algo-rithm.Journal of Global Optimization,2007;39(3):459—471
[5] Karaboga D,Basturk B.Artificial bee colony(ABC)optimization al-gorithm for solving constrained optimization.Foundations of FuzzyLogic and Soft Computing,2007;4529:789—798
[6] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm.Applied Soft Computing,2008;8(1):687—697
[7] Karaboga D,Akay B.Artificial bee colony algorithm on training arti-ficial neural networks.//2007 IEEE 15th Signal Processing andCommunications Applications Conference.New York:IEEE,2007:818—821
[8] Karaboga D,Akey B,Ozturk C.Artificial bee colony(ABC)optimi-zation algorithm for training feed-forward neural networks.ModelingDecis-ions for Artificial Intelligence.Berlin:Springer-Verlag,2007;4617:318—319
[9] Karaboga N.A new design method based on artificial bee colony algo-rithm for digital IIR filters.Journal of the Franklin Institute,2009;346(4):328—348
[10]李端明,程八一.基于人工蜂群算法求解不同尺寸工件单机批调度问题.四川大学学报(自然科学版),2009;46(3):657—662
[11]胡中华,赵敏.基于人工蜂群算法的机器人路径规划.电焊机,2009;39(4):93—96
混合算法 第10篇
云计算作为一种计算、存储资源的新型商业模式而出现, 具有按需访问大量、潜在的远程数据、计算中心的功能。随着云计算的发展日趋成熟, 相关的服务和应用正在逐年递增, 云计算为之配备的服务器数量规模也在高速增长。为了达到负载均衡、降低成本以及节能的目的[1], 云计算任务分配调度已经成为当今研究的热点课题。
云计算是从网格计算的基础上发展而来, 但网格计算一般用于科学研究, 而云计算则更多的是面向广大用户, 应用场景的不同使得两者的任务分配方法存在着非常明显的差异[2]。网格计算多是针对应用与科学研究领域, 以计算密集型应用为主, 更注重的是效率, 比如最短时间完成任务, 所以传统的网格程序性能预测模型往往只考虑程序的运行时间效率, 而忽略了其他硬件方面的开销。而云计算应用范围的广泛化就决定了必须在效率和各种资源开销之间寻找一个平衡, 这些开销就包括时间开销、CPU利用率、内存使用大小、I/O使用大小, 为了降低成本就要使以上各种硬件资源得到充分的使用而减少任务所需主机的总数量, 同时为了保证Qo S (Quality of Service) 必须避免出现资源征用情况的发生。
目前, 许多云计算任务分配调度方法的目的主要为了减少任务的运行时间[3], 或者任务运行的利益最大化[4], 却较少地关注到任务运行所消耗的资源以及能耗。Pandey等[3]使用优化粒子群算法寻找出云计算环境下最优的资源分配策略, 使得任务的执行总时间以及通信量最低;徐骁勇[5]通过对云计算资源进行调度, 缩短了云计算任务的运行时间, 同时也达到了降低能耗的目的;Srikantaiah[1]发现当计算机CPU和硬盘处在某一利用率时可以达到处理平均事务所消耗的能量最少, 并通过调整硬件资源的利用率来达到节能的目的;Duy[6]将计算机状态分为运行、等待、休眠和关机, 再结合数据中心的电源管理办法, 通过将计算机在这四种状态之间互相转换来达到节能的目的, 但并没有影响到计算机内部资源的利用率, 而且也没有解决资源使用不充分的问题;已有的三种绿色任务调度算法是STF-OS、LTF-OS、和RT-OS算法[7], 这三种算法虽然能够达到节能的目的, 但却只考虑了CPU的调度, 而没有兼顾到计算机的内存、I/O和带宽等资源的整体调度, 可能导致资源的不充分利用或者资源的争用, 从而影响Qo S。
根据云计算任务调度的特点, 本文提出了一种基于混合遗传算法的云计算任务分配策略, 实验表明, 这种方法能够有效地降低任务运行的总能耗, 降低任务成本。
1 云计算任务分配模型
1.1 任务分配问题的描述
假设一个数据中心包含m台主机, n个任务等待分配, {Cj, Mj, Dj, Nj}四元组分别对应第j台主机的CPU、内存、硬盘I/O、网络带宽四种资源, {ci, mi, di, ni}为第i个任务对四种资源的需求量, 则四元组{Cj, Mj, Dj, Nj}即为背包问题中第j个背包容量, {ci, mi, di, ni}为第i个物品的大小, 由此任务分配问题就转化为四维背包问题的求解, 如何将n个任务分配到m台主机, 同时保证每台计算机的资源使用率在四元组{Cj, Mj, Dj, Nj}的限定之内, 这是对一个多维多背包问题的求解。
1.2 任务分配问题的数学模型
背包问题是一种组合优化的NP完全问题[8]。问题可以描述为:给定n个物品, 每种物品都有自己的重量和价格, 第i个物品的重量为wi, 价格为vi, 在限定的总重量c内, 应该如何选择, 才能使得物品的总价格最高。其数学模型可表示为:
其中, xi表示物品是否被选装入:
多维多背包问题是背包问题的一类子集[9], 其中表示背包容量和物品大小的变量有多维表示, 而且物品放入的背包可有多个选择[10], 在任务分配问题中可用主机的各种硬件资源{Cj, Mj, Dj, Nj}表示为背包问题中第j个背包容量, 每个任务对各种硬件资源的需求量{ci, mi, di, ni}表示为第i个物品的大小, 则任务分配问题的数学模型可表示为:
其中, {Cj, Mj, Dj, Nj}表示第{Cj, Mj, Dj, Nj}台主机的CPU、内存、硬盘I/O以及网络带宽四个维度的容量, xij表示第i个任务是否被分配至第{Cj, Mj, Dj, Nj}台主机, 用公式表示如下:
2 混合遗传算法
遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法, 是进化算法的一类分支。这种启发式的研究思路通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而衍生发展起来的, 这些现象包括遗传、突变、自然选择以及杂交等。而鉴于基本的遗传算法存在着局部搜索能力差以及容易产生早熟现象的缺点, 结合云计算任务分配问题的特点, 本文采用了遗传和贪心相结合的混合遗传算法, 该算法克服了基本遗传算法局部搜索能力差以及容易产生早熟现象的缺点[11]。
2.1 遗传算法的基因编码
传统的遗传算法基因编码方式多采用二进制编码, 考虑任务分配问题可转化为0/1规划问题的特点, 可以将问题的解直接映射成一个m×n的矩阵, 以此作为遗传算法的基因编码, 这种方法存在的缺点是基因长度为m×n, 当问题规模较大时不利于搜索问题的优化解。
因为任务分配问题中, 一个任务只能分配到一台主机, 二进制编码中将会存在大量的冗余, 所以本文中直接采用整数编码的方式, 问题的解可表示为X={x1, x2, …, xn}, (xi∈{0, 1, 2, …, n}) , 例如将第i个任务分配至第j台主机, 则xi=j, 当xi=0时, 则表示没有多余的资源可以执行第i个任务, 任务未被分配。
采用整数基因编码方式优化解的搜索空间为O (mn) , 而采用二进制编码方式的搜索空间为O (2mn) , 当问题规模较大时, 采用整数编码的遗传算法搜索空间要远小于采用二进制编码的搜索空间。
2.2 修正种群个体
种群的个体在经过交叉和变异之后都会产生新的个体, 但是这个个体不一定是可行解, 所以要将种群中的不可行解修正为可行解, 并且为了加快算法收敛的速度, 要将可以优化的可行解进一步优化。在这里采用贪心算法实现这一功能, 其算法流程如图1所示。
2.3 目标函数与适应度函数
为了达到节能的目的, 采用计算耗能作为目标函数, 主机的能耗可表示为:
其中, T为主机的运行时间, p为主机运行的实际功率, p为主机的额定功率, 一般情况下都会满足p≤P, 但在文中修正种群个体的过程中会保证各运行主机的硬件资源得到充分的利用, 在这种情况下p≈P, 所以选取目标函数为:
其中, Pj为第j台主机的额定功率, Tj为第j台主机的运行时间, 由于云计算中一台主机可以运行多个任务, 所以Tj为第j台主机上最长任务的执行时间, 当主机未被分配任何任务时, 则处于休眠状态, 休眠状态下的主机耗电量为0。个体适应度函数选取目标函数的倒数:
2.4 选择与遗传操作
遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体, 被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体, 遗传到下一代群体。本文中选择算子采用轮盘赌选择方法, 设种群中共有N个个体, 个体xi被选中遗传到下一代的概率为:
个体杂交方式采用单点杂交方式, 其主要过程如下:
(1) 在染色体上随机选择一个交换点;
(2) 确定是在交换点前面部分或者后面部分的基因进行交换;
(3) 根据上述原则将两父本的染色体基因进行交换重组, 从而形成新的个体。
2.5 算法流程
改进后的混合遗传算法流程如下:
(1) 初始化。t←0进化代数计数器;T是最大进化代数;随机生成M个个体作为初始群体Population (t) ;
(2) 修正个体。使用贪心算法对个体进行优化和修正;
(3) 个体评价。计算Population (t) 中各个个体的适应度值;
(4) 选择运算。将选择算子作用于群体;
(5) 交叉运算。将交叉算子作用于群体;
(6) 变异运算。将变异算子作用于群体, 并通过以上运算得到下一代群体Population (t+1) ;
(7) 终止条件。判断t≦T:t←t+1转到步骤 (2) ;t>T:终止输出解。
3 算法仿真与结果分析
本文使用Cloud Sim[12]模拟了大规模云计算数据中心, 并对基于混合遗传算法的任务分配策略进行了仿真和测试。实验中模拟了一个包含1 000台主机的与计算数据中心, 对1 000个任务分配问题进行了仿真。1 000台主机和1 000个任务的数据为随机生成, 为有利于仿真, 数据完全按照Cloud Sim中主机和任务的量化标准生成。
3.1 算法正确性验证
虽然任务分配问题是NP完全问题, 在问题规模较大时得到最优解是非常困难的, 但在问题规模较小时还是可以得到最优解的。为了验证算法的正确性, 选取任务和主机都较少的情况进行验证, 实验选取的3个任务、5台主机的任务分配问题进行验证, 任务数据和主机数据如表1和表2所示, 任务分配的结果如表3所示。
由表3可以看出, 所有3个任务全部分配给了第三台主机。从表2可以看出第4台主机能耗较低, 但其计算能力较弱, 如果将任务全部分配给第四台主机就会出现资源争用的情况, 降低程序运行的效率, 为避免出现这种情况就必须开启其他主机, 这样却会使能耗大大增加;第二台主机也能够完成三个任务的计算, 但其功率相比第三台主机要大, 完成任务所需的能耗更大, 所以算法将三个任务全部分配给第三台主机是能耗最优的选择。
3.2 算法收敛效果比较
为了验证改进的混合遗传算法在解决任务分配问题是否具有更好的性能, 将其与基本的遗传算法和贪心算法做了比较, 实验结果如图2所示。
图2中三条线分别为混合遗传算法、基本遗传算法和贪心算法计算所得优化解, 因为本文中目标函数为能耗最低, 所以值越低, 说明该值越接近最优解。从图2中可以看出, 混合遗传算法搜索优化解的结果要远优于贪心算法和基本的遗传算法。贪心算法虽然开始时搜索局部优化解的速度较快, 但其对全局优化解的搜索能力却比较差, 基本遗传算法搜索全局优化解的能力要比贪心算法强, 但其搜索局部优化解的能力较弱, 所以向最优解收敛的速度较慢, 而混合遗传算法则结合了基本遗传算法和贪心算法的优点, 其收敛速度较快。在实验中使用50个任务, 1 000台主机, 混合遗传算法种群进化1 000代的耗时为2.7s, 基本遗传算法耗时1.8s, 贪心算法为0.3s, 算法执行时间有所增加, 但仍在可以接受的范围内。
3.3 仿真结果分析
Cloud Sim提供了资源的监测、主机到虚拟机以及虚拟机到任务的映射功能[13], 并且提供了能耗的仿真和计算模块, 可以方便地模拟主机或者虚拟机的能耗, 而且能够根据任务运行所占的资源量和所用时间给出任务执行所耗费的成本。
实验模拟云计算数据中心包含1 000台主机, 任务数量从0到1 000不等, 分别对随机任务分配算法、Cloud Sim能量感知任务分配算法[14]及基于混合遗传算法的任务分配算法的能耗和任务执行成本做了对比。对比结果如图3和图4所示, 从图3和图4的对比结果可以看出, 基于混合遗传算法的任务分配方式能够大大降低任务执行的总能耗, 并且由于充分利用了计算机的硬件资源, 避免了运行主机的空闲资源浪费, 所以大幅降低了任务执行总成本, 在任务总量越多时节能和节约成本的效果越明显。
4 结束语
本文使用基于混合遗传算法对云计算数据中心任务分配策略进行了优化, 优化后的任务分配策略能够有效地减少任务运行的总能耗, 减少任务运行的成本。这种任务分配策略在解决云计算的任务调度、负载均衡、节能减排、成本最小化等问题时有着良好的应用价值。
摘要：云计算中主机和任务的数量都是十分庞大的, 如何通过任务分配调度来减少成本开销和降低能耗是当前云计算和绿色计算领域研究的热点问题。根据云计算任务以及运行环境的特点, 将云计算任务分配问题抽象为多维多背包求解问题, 并采用改进的混合遗传算法对该问题进行求解。实验结果表明, 改进的混合遗传算法能够在较短的时间内找到问题的优化解, 并且根据该算法实现的任务分配策略能够有效地减少任务执行的成本开销和能耗。
混合算法 第11篇
本文将遗传算法与模拟退火算法相结合，从而优化模型设计过程，提高求解效率，克服传统遗传算法的缺陷，避免陷入局部最优。
1 遗传算法与模拟退火算法的结合
1.1 遗传算法和模拟退火算法的原理
遗传算法是借鉴适者生存、优胜劣汰的生物界进化规律而演化出的随机搜索算法，是由美国密歇根大学HOLLAND教授于1975年首先提出的新型全局优化搜索算法。遗传因子经过迭代能启发式地自适应搜索具有全局最优解的较小区域，并以较大的概率趋向于全局最优解。利用该原理能够有效解决许多常规优化方法难以解决的复杂优化问题。
模拟退火算法最早于1983年由KIRKPATRICK等用于组合优化领域，是基于蒙特卡罗迭代求解策略的随机寻优算法，基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解中概率性地跳出并最终趋于全局最优解。
1.2 遗传算法和模拟退火算法的局限性
遗传算法处理的对象不是参数本身，而是对参数集进行编码后的个体。由于应用了编码技术，可直接对结果对象进行操作，不存在求导和函数连续性的限定，因此适用于各类优化问题。然而，由于遗传算法采用根据适应度值大小来决定个体是否被复制的选择机制，容易出现来源于同一种群的个体被大量繁衍的情况，形成近亲繁殖，造成算法的局部搜索和过早收敛。由此可见，遗传算法具有一定的局限性，主要表现如下：（1）遗传算法属于启发式算法，求得的是近似解，求解效率有限；（2）需针对问题设计合适的编码方式，编码方式的优劣直接影响求解质量；（3）除非模型能提供最优解参考值，否则不能确定演算结果是否最佳；（4）由于此方法为群体同步搜寻，因此会占用计算机内存空间，影响演算速度。
理论上模拟退火算法以1的概率收敛，但局限性也较明显[1]，主要表现如下：（1）实际设计算法时算法结果存在波动性；（2）为寻找最优解，通常要求较高的初温、较稳的降温速率、较低的终止温度以及各温度下足够多次的抽样，优化过程较长，受计算速度和计算时间的限制，难以保证计算结果为全局最优点，优化效果不理想；（3）由于马尔可夫链的长度不易控制，在每一温度下很难判定是否达到平衡状态，反映到计算过程中就是实现Metropolis准则的次数不易控制。
1.3 构造混合遗传—模拟退火算法
遗传算法与模拟退火算法相结合是解决两种算法各自局限性问题的有效途径，具体来说有以下四方面的结合。[2]
（1）优化结构的互补 模拟退火算法采用串行优化结构，而遗传算法采用群体并行搜索方法，两者结合能使模拟退火算法成为并行算法，在提高自身优化性能的同时作为自适应的变异操作，增强和补充遗传算法的进化能力。
（2）优化操作的结合 模拟退火算法每一时刻仅保留1个解，缺乏冗余和历史搜索信息；而遗传算法的复制操作能在下一代中保留种群的优良个体，交叉操作能使后代在一定程度上继承父代的优良模式，变异操作能增强种群中个体的多样性，这些不同作用的操作相结合，丰富了优化过程中解空间的搜索结构，增强了全空间的搜索能力。
（3）优化行为的互补 由于复制操作对当前种群外的空间无搜索能力，种群中个体分布“畸形”使交叉操作的进化能力有限，而小概率变异操作很难增加种群的多样性，因此，若收敛准则设计得不好，则会出现进化缓慢或早熟收敛的现象，结合后并行化的抽样过程可优化算法的时间性能。
（4）削弱参数选择的苛刻性 设计算法时需依靠大量的试验和经验来确定两者相结合后算法各方面的搜索能力均得到提高，因此，对算法参数的选择不必过分严格。研究表明，混合算法在采用单一算法参数时，优化性能和鲁棒性均有大幅度的提升，尤其是针对较大规模的复杂问题。
2 利用混合遗传—模拟退火算法求解班轮航线配船问题
2.1 班轮航线配船问题描述及模型建立
参考文献：
[1] 段姹莉，陈波．VB环境下的模拟退火算法求指派问题[J]．电脑知识与技术，2008，4（8）：2153-2155.
[2] 丁香乾，韩运实，张晓丽．自适应遗传算法解决集装箱装载问题的方法探讨[J]．中国海洋大学学报：自然科学版，2004，34（5）：844-848.
智能优化混合算法研究进展 第12篇
不同的优化问题要采用不同的优化算法,最理想的情况是以最快地速度得到全局的最优解。传统的优化算法在面对大型问题时,需要遍历整个搜索空间,一旦形成了搜索的组合爆炸,就无法在多项式时间内完成。那么,在复杂、广阔的搜索空间来找最优解,就成为科学工作者研究的重要课题。
智能算法在可接受的时间内对复杂大规模优化问题进行求解取得了惊人的优秀成绩。代表的智能算法有:模拟退火算法、演化算法、遗传算法、粒子群算法等。智能算法一般具有自组织性、自适应性和并行性,直接把目标函数值作为搜索信息,具有正反馈机制,可以有效地完成优化任务。面对日益复杂的大规模优化问题,尤其是多模态、高维、带约束和多目标优化问题,采用某一种智能算法,总会存在该算法本身的缺点,所以,要想取得更加令人满意的优化效果,可以将两种或多种智能算法,按照某种规则组合使用,形成混合优化算法,不同的算法扬长避短,极大地提高算法的搜索效率。
1 智能优化混合算法
智能算法在解决优化问题时,算法本身要考虑全局最优和局部最优,根本目的是以最快地速度找到全局最优解,但在搜索的过程中,太过以目标函数值为指引,很容易陷入局部最优解,而错误找到全局最优解。因此,针对不同的优化问题,如何避免陷入局部最优解,在保证速度的前提下找到全局最优解,就成为指引智能算法设计的基本原则。
智能优化混合算法设计时就是根据如何避免陷入局部最优解,快速找到全局最优解这个基本原理来设计的。一些智能算法的全局搜索能力很强,如,遗传算法、模拟退火算法和群智能算法。常见的智能优化混合算法一般会选择一种全局搜索算法,在保证全局搜索能力的基础上,采用一定的措施,融入局部搜索的策略或另外一种智能算法,以达到整体优化的高效效果,下面介绍几种常见某一种智能算法为基本,混合其他智能优化算法的混合算法。
1.1 混合遗传算法
1975年美国Michigan大学的J.Holland教授首先提出了遗传算法,它借鉴自然界自然选择和自然遗传机制进行随机搜索。
遗传算法直接把目标函数作为搜索信息,鲁棒性强,因此,在许多优化问题上都取得了很好的优化效果,但是它的局部搜索能力很弱,极易出现早熟现象,因此,改进遗传算法,提高算法的收敛效率,可以引入局部搜索能力强的其他智能算法,或者在遗传算法的选择、交叉和变异3个基本步骤中,引入其他智能算法的机制,形成混合遗传算法,以达到满意的优化效果。
(1)遗传算法和文化算法相结合。李铁克,王伟玲,张文学2010年提出将遗传算法引入文化算法,从种群中获取有用的知识,并用这些知识指导搜索过程。算法在迭代过程中利用文化算法的寻优机制,提取解的特征知识,指导遗传算法的选择操作,形成一种双层进化结果,从而提高算法的收敛速度。
(2)2009年,黄明,宫旭德,梁旭提出了改进的DNA免疫遗传算法,将遗传算法和免疫算法相融合,引入疫苗库进行群体之间的信息交互,通过两种算法的结果,提高了混合算法的收敛速度和全局搜索能力,取得了比较好的优化效果。
(3)郑世祺等人为优化永磁同步机的伺服驱动器,采用了遗传算法和小波神经网络的混合方法,使得驱动系统的精度更高,性能更好。
(4)2016年,Anupam Trivedi等人为了解决机组组合调度问题,采用了遗传算法和差分演化算法相融合的混合算法。Anupam Trivedi等人在混合框架中,二进制变量进行遗传算法优化,连续变量采用差分进化算法优化,通过实验,在机组组合调度的优化问题上,取得了非常优异的成绩。
1.2 混合模拟退火算法
模拟退火算法采用Metropolis准则,防止陷入局部最优,在搜索的过程中,不但朝着好的方向搜索,也按一定的概率往差的方向搜索,所以,要返回一个最优解或准最优解,要很长的时间,尤其是规模庞大的优化系统,更是无法承受运行时间。将模拟退火算法与其他智能算法相融合,取长补短就可以达到令人满意的优化效果了。
(1)2010年邵琳等人把模拟退火遗传算法应用于水电站调度图的优化方法上,成绩显著;2013年,白舸等人提出采用遗传模拟退火算法进行无线传感器广播路由选择,使传输功耗进一步节省。
(2)Shieh Horng-lin等人2011年提出将粒子群优化算法和模拟退火算法相结合后的算法具备两种源算法的优秀机制,对比单一的智能算法,混合算法在大部分情况下取得了更优效率;2015年Abubaker Ahmad等人把多目标混合粒子群和模拟退火算法实现一种自动聚类算法;2016年熊慧等人把混合的粒子群和模拟退火算法应用于聚焦优化上,较好地改善了聚焦线圈产生磁场的聚焦性能。
(3)2014年,杨艳霞提出了将模拟退火操作引入到差分进化算法中去,提高了一类复杂组合优化问题的求解能力,在算法初期保持了种群的多样性,而在运行的后期,又可以跳出局部最优解,有效地找到全局最优解或定位到最优解附近;2015年,张慧峰等人提出采用差分进化算法和模拟退火相结合的方法来解决动态经济排放调度问题,适当地避免早熟,取得了较好的收敛效果。
2 结语
该文针对现阶段生产生活中日益复杂和规模扩大的优化问题,研究采用智能优化混合算法解决优化问题的现状和进展,分析以某一种智能优化为基础,引入另外一种智能优化算法,使两种算法扬长避短,提高优化效率,以求在不同的优化领域中构建新的智能优化混合算法可以从该文得以借鉴。
参考文献
[1]白舸,张海涛,刘翠苹,等.基于遗传模拟退火算法的WSN广播算法研究[J].计算机测量与控制,2013,21(11):3053-3056.
[2]熊慧,胡小伟,刘近贞.基于混合粒子群和模拟退火算法的聚焦性优化[J].航天医学与医学工程,2016,29(1):34-38.
【混合算法】相关文章：
混合智能算法08-23
混合杂草优化算法08-20
混合模拟退火遗传算法05-15
RSA混合加密算法07-14
混合蚁群优化算法06-02
遗传算法求解混合流水车间调度问题09-11
基于混合遗传算法的物流路径优化方法探讨09-13
混合遗传算法和支持向量机的股票预测模型09-12