遗传算法与禁忌搜索算法的混合策略_李大卫
1998年9月 JOURNALOFSYSTEMSENGINEERING Sep.1998
遗传算法与禁忌搜索算法的混合策略
李大卫①
(鞍山钢铁学院,鞍山王 莉 114002)(鞍山师范学院,鞍山王梦光 114005)(东北大学,沈阳110006)
摘要 遗传算法与禁忌搜索算法的出现为解决高维组合优化问题提供了强有力工具.二
者既有共性,又有个性.通过对遗传算法与禁忌搜索算法的分析,提出了一种遗传算法与禁忌搜
索算法的混合策略,把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中,构造了新
的重组算子,并把禁忌搜索算法作为遗传算法的变异算子,对旅行商问题的求解表明:混合策略
在许多方面优于遗传算法.
关键词:遗传算法,禁忌搜索,混合策略,旅行商问题
分类号:N94
GENETICALGORITHMANDTABUSEARCH:AHYBRIDSTRATEGY
LiDaweiWangLiWangMengguang
(AnshanInstituteofIronand(AnshanNormalCollege,(NortheasternUniversity,SteelTechnology,Anshan114002)Anshan114005)Shenyang110006)
Abstract Theappearanceofgeneticalgorithmsandtabusearchprovide
powerfultoolsforsolvingcombinatorialoptimizationproblemsinhighdimen-sions.Thetwomethodseitherhavesomecommonbonds,orsignificantdiffer-ences.Throughanalysing,weproposeahybridstrategyofgeneticalgorithmand
tabusearch.Thememoryfunctionoftabusearchisintroducedintoprocedureof
geneticalgorithms.Anewrecombinationoperatorisconstructed,whilemutation
operatorisreplacedbytabusearch.Geneticalgorithmandhybridstrategyareusedseparatelytosolvetravelingsalesmanproblem.Theexperimentresults
showthatthehybridstrategyissuperiortothestandardgeneticalgorithmin
manyaspects.
Keywords:geneticalgorithm,tabusearch,hybridstrategy
0 引 言
在过去的20年里,由美国学者Holland和他的同事、学生们提出的遗传算法(geneticalgorithms,GA)成为求解任意函数优化问题的强有力的工具[1].GA是一种进化搜索算法,它的基本思想是基于Darwin的进化论和Mendel的遗传学说.其中重组和变异算子是GA①36岁,男,博士,讲师.36,male,Dr.,lecturer.11.
1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略·29·的两个最重要的组成部分,它们被重复地应用到对问题的解进行编码而构成的染色体上.在许多优化问题和工业实际应用上,GA已经得到了成功的应用[2].禁忌搜索(TabuSearch,TS)是另一个著名的启发式搜索算法,最早由Glover提出[3].具有记忆功能是TS独创的特点之一.许多研究人员对TS的理论和应用作了研究,使得TS在调度领域,运输问题,专家系统和神经网络等方面得到了广泛的应用[5].
GA开创了在解空间中从多出发点搜索问题最优解的先河,而TS是在搜索过程中使用记忆功能的先驱者.它们在解决各种实际应用问题所取得的成功表明,使用二者解决复杂的问题是有价值的.尽管GA和TS的适用范围很广,但由于某些条件约束,所以GA和TS并不是对所有的问题都是万能的算法,或多或少存在着某些缺陷.因此有必要对GA和TS作进一步的研究.本文对此作些尝试性的工作,在对GA与TS算法进行分析的基础上,提出了一种GA与TS的混合策略(GATS),把TS独有的记忆功能引入到GA搜索过程之中,构造了新的重组算子,并把TS作为GA的变异算子.
1 GA与TS的比较
1.1 GA简介
GA可用如下的五维向量组形式描述
GA=(Npop,Ngen,K,feval,fsel)
其中Npop为群体规模;Ngen为迭代代数;K为遗传算子(重组和变异)及它们的概率集合;feval为评价函数,或称作适应值;fsel表示再生选择规则.这里并不关心染色体的具体编码的形式,因此假设GA和TS可以使用同样的编码.
GA的特点可以概括成下面的4点[2]:
1)利用变量的编码方式,而不使用变量本身;
2)在解空间中从多出发点搜索问题的解,而不像某些传统的搜索方法从一点出发搜索问题的解;
3)直接利用目标函数的函数值信息,而不使用函数的导数或其它的辅助信息;
4)使用概率转移规则,而不采用确定性的转移规则.
GA的求解过程如图1所示:
begin
t=0;initializeP(t);
evaluatestructuresinP(t);
whileterminationconditionnotsatisfieddo
t=t+1;
selectP(t)fromP(t-1);
recombinestructuresinP(t);
evaluatestructuresinP(t);
end(其中P(t)表示第t代群体)
图1 GA的求解过程
1.2 TS简介,
·30·系 统 工 程 学 报 第13卷 第3期 TS=(Npop,Ngen,Λ,fmove,tabulist)
其中Npop表示一个初始解;Ngen为迭代代数;Λ表示移动的构成方式;fmove为移动值;tabulist是长度为T的禁忌表,其中T可以是定长的,也可以是变长的.TS求解过程可以表示成如图2的形式:
begin
t=0;generateNpop;setT;
setthebestandpresentsolutionsx=x0=Npop;
whileterminationconditionnotsatisfieddo
t=t+1;
movextox′;
update(x;x0;tabulist);
end
图2 TS的求解过程
TS也是一种迭代搜索算法.由于TS使用了记忆功能,在搜索过程中可以接受劣解,所以TS具有强的“爬山”能力(相对于全局最小值问题),这样使得TS在搜索过程中能够跳出局部最优解,进而转向其它区域进行搜索,从而获得更好的解或全局最优解的概率也大大增加.
2 GA的局限性和TS的缺陷
2.1 GA的局限性
尽管GA能够胜任任意函数,高维空间的组合优化问题,但是对于像优化大规模神经元网络的权系数,优化网络的结构等超大规模的优化问题,GA的应用就受到了限制.究其原因,主要在于GA在进化搜索过程中,每代总是要维持一个较大的群体规模,从而使计算次数呈非多项式时间增加,限制了GA的使用.
GA的另一个不足之处是“早熟”.造成这种成熟前收敛的原因,一方面是GA中最重要的遗传算子——交叉算子使群体中的染色体具有局部相似性,从而使搜索停滞不前;另一方面是变异概率又太小,以至于不能使搜索转向其它的解空间进行搜索.
此外,GA还有爬山能力差的弱点.这也是由于变异概率低造成的.因此,如何提高GA的爬山能力成为一个重要的研究方向,为了提高GA的爬山能力,Ackley开发了一个具有随机爬山功能的称作SIGH的算法[6].他的分析表明,随机爬山能够促进GA的搜索速度和解的准确性.
2.2 TS的缺陷
TS的搜索速度比GA的搜索速度快,但TS对于初始解具有较强的依赖性.一个较好的初始解可使TS在解空间中搜索到更好的解,而一个较差的初始解则会降低TS的收敛速度.为此人们往往使用启发式算法来获得一个较好的初始解,提高TS的性能.
TS的另一缺陷是在搜索过程中初始解只能有一个,在每代也只是把一个解移动到另一解,而不像GA那样每代都是对解集(群体)进行操作.
1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略·31·3 GA与TS的混合策略GATS
开发混合算法的目的是使原算法的优点被保持,弱点被克服或者被削弱,提高算法的力度.Mǜhlenbein最早把记忆功能引入到GA中[6],而TS的创始人Glover对混合GA与TS的必要性和可行性进行了理论上的分析和论述[7],被公认为混合GA与TS的理论基础.通过上面对GA和TS的分析,在Glover理论的基础上,本文提出一种GA与TS的混合策略GATS.把TS独有的记忆功能引入到GA进化搜索过程之中,构造了新的重组算子TSR,针对GA爬山能力差的缺陷,利用TS爬山能力强的优点,使用TS算法改进GA的爬山能力,即把TS作为GA的变异算子TSM.GATS综合了GA具有多出发点和TS的记忆功能和爬山能力强的特点,克服了GA爬山能力差的弱点,并保持了GA具有多出发点的优势.
设x是一个解(染色体),则TSM的操作过程如图3所示:
begin
t=0;setthebestsolutionx0=x;setT;
whileterminationconditionnotsatisfieddo
t=t+1;
movextox′;
update(x;x0;tabulist);
end
图3 TSM的操作过程
TSM与标准变异算子极为类似.首先,TSM把一个解(染色体)作为输入(初始解),经TSM作用,返回一个解作为输出.不同之处在于TSM是一个搜索过程,因此需要调用评价函数来确定移动值,并根据移动值和禁忌表决定接受哪个移动(输出).同样由于TSM是一个TS搜索过程,在搜索过程中可以接受劣解,因此TSM具有强于其它变异算子(例如倒位和部分倒位变异算子)的爬山能力.
TSR算子作为重组算子,使用一个长度为T的禁忌表,表中记录染色体的适应值,渴望水平取作父代群体适应值的平均值.进行TSR操作时,首先把子代的适应值同渴望水平相比较,如果比渴望水平好,则破禁,即这个子代染色体进入到下一代之中;如果子代比渴望水平差,但不属于禁忌,也接受这个子代;若是属于禁忌,则选择最好的那个父代进入到下一代中,具体过程如图4所示:
begin
iffitnessofx>averagevalueofpopulation,thenacceptx
else
ifoffspringxisnotintabulist
acceptx
else
choosethebetteroftwoparentstothenextgeneration;
updatetabulist;
end图T
·32·系 统 工 程 学 报 第13卷 第3期从TSR的重组过程可以看出,具有高适应值的子代进入到下一代的机会是很大的,但是并不是所有的高适应值的子代一定都进入到下一代,因为TSR使用了禁忌表,它可以限制适应值相同的子代出现的次数,因此可使群体中尽可能保持染色体结构的多样性,从而避免算法早熟.
下面给出GA与TS的混合策略GATS:
GATS的求解步骤:
Step0参数设置(最大代数Ngen,群体规模Npop,重组概率pc,变异概率pm)
Step1令t=0;生成初始群体;
Step2计算当前代群体中染色体的适应值;
Step3选择:按滚轮方式选出Npop个染色体,放入交配池中;
Step4重组
step4.1生成0,1之间的随机数ri,i=1,2,…,Npop;如果ri
step4.2对每对双亲进行交叉操作,产生两个子代;
step4.3调用TSR对交叉后得到的子代进行重组;
Stpe5变异
step5.1生成0,1之间的随机数ri,i=1,2,…,Npop;如果有ri
step5.2t=t+1;如果t
4 GATS的性能分析
在这一节中,分别用GA及GATS算法求解具体的TSP问题,对n=10,67的TSP问题分别进行求解,所用的数据分别来自文[8,9].为了比较两个算法的性能,使用本单位独自开发的求解线性规划的软件包求得最优解.此外,关心引入TSM/TSR算子是否能提高GA的性能,所以并不是让GA和GATS都收敛.相反,算法在一个预先给定的代数上停止.
4.1染色体的编码
应用GA解决TSP问题时,通常使用自然数编码构造染色体,而不使用二进制编码[2].使用自然数编码的优点在于染色体比较直观,并且无论是进行交叉操作还是进行变异操作,染色体总是能够满足TSP问题的约束条件,即总保持染色体对应的解是可行解.因此也使用自然数对染色体进行编码.例如:
P={8,2,4,6,1,5,7,3}
P为一个染色体,表示访问顺序依次为8,2,4,…,3,8.需要注意的是,因为访问路径是一个闭合的回路,所以两个不同染色体所表示的路径可能是相等的,因此适应值也应相等.例如:
Q={2,4,6,1,5,7,3,8}
尽管Q与P是完全不同的染色体,但是两者所表示的是相同的路径,故P与Q的适应值也是相等的.
4.2适应值:
1998年9月 李大卫等:遗传算法与禁忌搜索算法的混合策略·33· f(P)=Cmax-问题的目标值
其中Cmax是一个较大的正数,它保证适应值非负.
4.3遗传算子
在标准GA中,交叉算子分别取PMX,CX和OX算子,变异算子为部分倒位操作,在GATS中,利用TSR进行重组,其中交叉算子也分别取PMX,CX和OX算子,变异算子为TSM.
4.4初始群体
采用随机生成的办法,随机地排列自然数1,2,…,nNpop次,构成初始群体.
在实验中,GA及GATS使用的参数为:群体规模取为30,交叉概率和变异概率分别为0.8和0.03.对于n=10,算法在搜索100代后停止.对于n=67,算法在搜索1000代终止.表1和表2给出了实验结果,图5和图6给出了使用PMX时GA和GATS的搜索过程.
表1 10个城市TSP问题的实验结果(单位:km)GA交叉算子
最好值
最优值PMX83CX95OX8073PMX73GATSCX73OX73[2]
表2 67个城市TSP问题的实验结果(单位:km)GA
交叉算子最好值
最优值PMX1753CX1795OX17801615PMX1653GATSCX1679OX1672
图5中的目标值指的是每代群
体中染色体对应目标值的平均值.从
图5可以看出,GA在40代之后才达
到稳态,而GATS在6到10代为平
稳的搜索过程,从第11代开始爬山,
并在
13代搜索到最优解.
对于67个城市TSP问题,GA
在400代搜索到的解为2875,600
代为2217,800代为1753,而GATS图5 10个城市TSP问题的GA和GATS的搜索过程(PMX)
在400代的解为1737,600代为1
653,这个值与最优解比较接近.
下面讨论不使用TSR作为重组
算子时对GATS算法(即在GA中只
使用TSM作为变异算子)的影响.
图7是对于67个城市的TSP问题的
搜索过程.
在这种情况下,GATS的搜索
图6 67个城市TSP问题的GA和GATS的搜索过程(PMX)曲线变化不大,仍然能够搜索到接近
最优解的近优解,但是在700代之后
才搜索到,因此可以说明TSR的引入的确能够改善GATS的搜索效率.
·34·系 统 工 程 学 报 第13卷 第3期最后再讨论GATS的计算量问
题.GATS的计算量由GA和TS的
计算量构成.当群体规模为N时,
GA的计算量是O(N).但在实验
中发现在相同代数下GATS的执行
时间略大于GA的执行时间.如对
67城市的TSP问题,GATS所用的
时间约是GA所用时间的1.2倍.多
出的部分主要是因为在GATS中变
异算子TSM是一个搜索过程,所以
要占用一部分时间.图7 未使用TSR的GATS搜索过程(PMX)3[2]
5 结 论
用重组算子TSR和变异算子TSM取代标准GA中的重组算子和变异算子,提出了GA算法与TS算法的混合策略GATS,使得GATS混合策略在许多方面优于标准GA算法.通过求解TSP问题,可以看出GATS既保持了GA具有多个解(染色体)的优点,又提高了GA的爬山能力.
参考文献
1 HollandJ.Adaptioninnaturalandartificialsystems.TheUniversityofMichiganPress,AnnArbor,1975
2 GoldbergD.Geneticalgorithminsearch,optimizationandmachinelearning.Addison-WesleyPublish-ing,1989
3 GloverF.FuturePathsforintegerprogrammingandlinkstoartificialintelligence.ComputersOps
Res.,1986;5:533～549
4 GloverF,LagunaM.Tabusearch.InModernHeuristicTechniquesforCombinatorialProblems(Edit-edbyC.Reeves),Oxford:BlackwellScientific,1993
5 AckleyD.Stochasticiteratedgenetichillclimbing.Ph.D.Diss.,Dept.Comp.Sci.CMU-CS-87-107,
CarnegieMellonUniversity,March1987
6 MǜhlenbeinH.Parallelgeneticalgorithmsincombinatorialoptimization.ComputerScienceandOpera-
:PergamonPress,1995tionsResearch(EditedbyOsmanBalci),Oxford
7 GloverF,KellyJ,LagunaM.Geneticalgorithmsandtabusearch:hybridsforoptimizations.Comput-ersOps.Res.,1995,22(1):111～134
8 FouldsL.Combinatorialforundergraduates.Spring-VerlagNewYorkInc.,1984
9 NemhanserG,WolseyL.Integerandcombinatorialoptimization.Wiley-InterScience,1986