遗传算法与模拟退火算法比较

1、一、遗传算法与模拟退火算法比较分析模拟退火算法的基本原理可以看出，模拟退火算法是 通过温度的不断下降渐进产生出最优解的过程，是一个列马尔科 夫链序列，在一定温度下不断重复Metropolis H程，目标函数值 满足Boltzmann概率分布。在温度下降足够慢的条件下，Boltzmann分布收敛于全局最小状态的均匀分布，从而保证模拟 退火算法以概率为1收敛到全局最优。另外，不难看出，模拟退 火算法还存在计算结构简单、通用性好以及鲁棒性强等优点。但 是，模拟退火算法存在如下缺陷：1.尽管温度参数下降缓慢时理论上可以保证算法以概率为1地收敛到最优值，但是需要的时间过长加之误差积累与时间长 度的限制，

2、难以保证计算结果为最优；2.如果降温过程加快，很可能得不到全局最优解，因此，温 度的控制是一个需要解决的问题；3.在每一种温度下什么时候系统达到平衡状态，即需要多少 次Metropolis程不易把握，从而影响模拟退火算法的最终结果。与模拟退火算法相比较，遗传算法具有如下典型特征：这两种算法的相同点是都采用进化控制优化的过程。主要不 同点是模拟退火是采用单个个体进行进化，遗传算法是采用种群 进行进化。模拟退火一般新解优于当前解才接受新解，并且还需 要通过温度参数进行选择，并通过变异操作产生新个体。而遗传 算法新解是通过选择操作进行选择个体，并通过交叉和变异产生 新个体。具体说来，遗传算法具有如下

3、特点：（1）与自然界相似，遗传算法对求解问题的本身一无所知,对搜索空间没有任何要求（如函数可导、光滑性、连通性等）， 只以决策编码变量作为运算对象并对算法所产生的染色体进行 评价，可用于求解无数值概念或很难有数值概念的优化问题，应 用范围广泛；（2）搜索过程不直接作用到变量上，直接对参数集进行编码操作，操作对象可以是集合、序列、矩阵、树、图、链和表等;（3）搜索过程是一组解迭代到另一组解，采用同时处理群体屮多个个体的方法，因此，算法具有并行特性；（4）遗传算法利用概率转移规则，可以在一个具有不确定性的空间寻优，与一般的随机性优化方法相比，它不是从一点出 发按照一条固定路线寻优，而是在整个可行解

4、空间同时搜索，可 以有效避免陷入局部极值点，具有全局最优特性；（5）遗传算法有很强的容错能力.由于遗传算法初始解是一 个种群， 通过选择、 交叉、 变异等操作能够迅速排除与最优解相 差较大的劣解.与模拟退火算法相比，遗传算法存在局部搜索能力差、容易 陷入过早收敛等缺陷，因此，人们将模拟退火算法与遗传算法相 结合得到的混合算法可以避免两种算法的缺陷，有利于丰富优化 过程的搜索行为，增强全局和局部意义下的搜索能力和效率。二、混合遗传算法举例遗传算法的不足：如求解精度不尽如意、难以控制、局部搜 索能力较差，随Z而来的问题就是算法的稳定性较差、算法的收 敛速度较慢这些不足都妨碍了它的进一步推广.因此，

5、如何提高 算法的精度、稳定性以及算法摆脱局部最优的能力，成了当前遗 传算法研究的难点与热点.另一方面，在一些实际应用屮，存在许多含有针对该问题的 有效知识型启发式算法，这些算法可以克服遗传算法局部搜索能 力弱的缺陷，通常具有局部搜索能力强、计算效率较高的优点（例 如，神经网络算法、模拟退火算法、共觇梯度法等），因此，在 遗传算法的搜索过程中融入这些专门领域知识或高效局部算法 的思想，构成一种混合遗传算法（hybrid genetic algorithm,简记 为Hybrid GA）,从而达到提高遗传算法效率和算法质量的一种 行之有效的手段.混合遗传算法的主要特点体现在下面两个方面：（1）在遗传

6、算法的执行步骤屮增加局部搜索过程.基于种群 文屮各个个体的表现形态， 进行局部搜索， 从而接受为新一代 个体的是无屮个体所对应在当前环境下的局部最优解.（2）在遗传算法的设计（如编、解码过程、交叉与变异操作）中融入与问题相关的启发式信息.下面通过两个个例子说明混合遗传算法的应用.首先考虑添 加局部搜索的混合遗传算法.例1（函数优化问题的混合遗传算法）考虑下列多元函数优 化问题加（X）其屮X=GV1,X2,.,XW）7,F = F1XE2X.XE,I,为某个定义区间，/（X）为多 元函数.求解例1的混合遗传算法与传统遗传算法相比较，其特点 是在每一代找到最优个体后并不立即进行下一代操作，而是以当

7、 代最优个体为屮心的一个固定区域（如半径为。的圆）进行局部 搜索.以便找到更好的个体.算法描述（冷昆合遗传算法）第一步：初始化种群；第二步：计算种群中个体适应值，选择最优个体；第三步：以种群中适应值最大的个体为中心，在s为半径的 圆内进行最优寻优（可以采用神经网络或梯度类算法），进入循 环过程，直到满足循环停止条件；第四步：将当代最优个体用局部寻优得到的最优值代替；第五步：种群内部进行选择、交叉、变异；第六步：转入第二步继续算法，直到满足进化条件. 利用上面描述的屛昆合遗传算法，下面具几个具体案例.例2分別用下面的两个测试函数验证冷昆合遗传算法的性 能.案例1性能测试函数F2/（X） = 10

8、0 x（和一#）2+（兀1）2xiw -5.12,5.12F2函数是一个单峰函数,极小值点为1丄,1丁， 最小值为0,极小值点的位置既不位于定义域的中心，也不位于定义域边界, 是一种有一定难度的优化问题.将标准遗传算法和訂昆合遗传算 法分别运行100次，其屮混合遗传策略编码长度为10,局部搜 索半径e取值为1,标准遗传算法的编码长度为80,两种算法的 种群规模和最大进化代数都为200,它们每次运行的最优值的折 线图分别如图1与图2所示：8.00E-02图2标准遗传算法搜索效果图从上面的图1与图2可以看出，混合遗传算法的最好的绝对 误差可达到103其屮95%的求解精度达到10以上，只有5次 的求

9、解精度比10低，最差的结果为103而标准遗传算法的最好 结果为10，而且只岀现三次，其一般的求解精度为10，因此， 求解精度以及算法稳定性等方面，混合遗传算法比标准遗传算法 有显著提咼.案例2对大海捞针Nih问题(NcdleinaHaystack)进行对 比实验，其中，大海捞针函数的表达式如下：)2+ x2+ y2, x, y e -5.12,5.12求函数的最小值.为简单计，取“3.0,0.05进行计算,min/(0,0) = L ,四个局部极值点为(5.12,5.，局部极小值为360012748.48 分别对两种算法实验100次，最大进化代数均取为300,种 群规模设定为400,标准遗传算

10、法的编码长度为120,混合遗传 算法的编码长度为20,试验结果如下表所示：表1冷昆合遗传算法与标准遗传算法求解效果对照表b + (x2+ y2)6D0E-024.00E-022.00E-02O.OOEI 13 25 37 49 61 73 85 97运行次数运行次数图1屛昆合遗传算法搜索效果图12 rt tl 21 31 41 51 61 71 81 91运行次数运行次数函数问题GANih问题找到最优解的 次数（精确到0.1）最优值平均值 找到最优值的 平均代数60（准确找到3 600）3 323 93770-2 557.24182从表1的结果可以看出，屛昆合遗传算法比标准遗传算法性 能要好.

11、对于大海捞针问题，屛昆合遗传算法有60次准确找到了 最优值补，而标准遗传算法没有一次找到最优值，而从平均值3600的角度来看，标准遗传算法明显陷入局部最优的陷阱.综上所述，将局部搜索策略引入遗传算法可以大大提升算法 的性能，性能的提升主要体现在两个方面：一是算法的精度大大 得到提高；另一方面，算法的稳定性得到极大增强，因此，算法 的可靠性随之得以提高.下面讨论的例子则通过在遗传算子的设计中溶入与问题相 关的启发式信息从而建立一种混合遗传算法。例3（背包问题（ZOKP）的混合遗传算法）求解ZOKP的贪婪算法（Greedy algorithm）常采用下面的 启发式策略：首先将物品按照价值密度卩产2

12、,心,2,从大到小 进行排列，依次将物品装入背包，直到背包容量达到最大为止. 采取该贪婪策略可以求得ZOKP的近似较好解，但是有可能得 不到最优解.采用标准遗传算法求解，当问题规模不大时，可以 求出近似最优或最优解，但当问题规模变得较大时，由于标准遗 传算法在较大的搜索空间屮搜索能力较差，从而很难得到该质量 的解，因此，为了提高标准遗传算法的搜索能力，将求解背包问 题的贪婪算法溶入到遗传算法屮，得到一种混合遗传算法，其思 想描述为：（1）编码格式： 采用01字符串进行编码， 一个字符串代 表一种编码策略，例如，个体以0，1“与装包策略的关系为:g =0，1分别对应于将第件物品不装入（或者装入）

13、袋屮;（2）混合繁殖算子： 对于选取的选择算子S,交叉算子C和 变异算子M,引进背包问题已有的贪婪算法以改进繁殖算子，具 体做法是：首先引进贪婪变换G:0,1T0,1,对于任意的X=粘. ,G（X） = y2儿，其屮X，j = l,2,.,由下列贪婪算法得 到：贪婪算法：第一步（排序）：对所有兀=1的物品，物品按照价值密度 ,山1,2,.v从大到小进行排列,形成队列奶；第二步（赋值）：1 .心1；2.计算=XHaj）；3.如果wkw,则将第仮）号物品装入袋中,即畑=1,赋值Ejk + i并回到2.否则转下一步4 ylD=O,J = Ar + l,/该贪婪变换把任意一个个体变换成可行解，此时，我

14、们把贪婪变 换与所选定的交叉与变异算子分别作复合运算，从而形成新的混 合交叉与混合遗传算子：Ch=GoCM =GM（ 1 ）（3）适应度度量：丿（X） = /V“2,=按照上面描述的编码格式、混合的交叉耸变异算子以及适应 度度量，即可建立一种求解背包问题的混合遗传算法.例如，考 虑由5 0件物品组成的背包问题，其屮物品价值匕、容积叩和 背包容量w分别为c. = 220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,10098,96,95,90,88,82,80,77,75,73,7

15、2,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1w. = 80,82,85,70,72,70,66,50,55,25,5055,40,4& 50,32,22,60,30,32,40,3835,32,25,2& 30,22,50,30,45,30,6050,20,65,20,25,30,10,20,25,15,10 10,10,4,4,2,1W = 1000分别采用贪婪算法、标准的遗传算法（含比例选择、单点交叉和 点变异）和上述构造混合遗传算法进行求解，其中运行参数取为第一组：M,7 ，匕 =80,500,0.6,0.1;第二组：M

16、,7巳，化 =50,500,0.6,0.5其中分别代表种群规模和终止进化代数，各算法独立运行1000次，然后对结果进行统计，其统计结果如表2所示，而最 好结果如表3所示.表2求背包问题的贪婪算法、 标准遗传算法与混合遗传算法的 比较（100次实验）结果超过贪结果超过贪婪最好求解结果算法及参数婪算法的解算法解时的进（总价值/总的次数化代数重量）标准遗传算法1 71 3 23 0 4 4 /980,500,0.6,0.1丄1丄u乙9 9混合遗传算法QQA4 53 0 9 4 /980,500,0.6,0.1DU9 9标准遗传算法2 0 62 3 83 0 7 7 /950,500,0.6,0.59 9混合遗传算法1 0 03 53 10 3/950,500,0.6,0.59 9贪婪算法3 0 3 6 / 9 99表3标准遗传算法、混合遗传算法与贪婪算法 求解50个物品背包问题的最好解比较算法个体X110110111110100110111求解结果