引入模拟退火机制的新型遗传算法

引入模拟退火机制的新型遗传算法

第32卷 第1期 电 子 科 技 大 学 学 报 Vol.32 No.1 2003年2月 Journal of UEST of China Feb. 2003

引入模拟退火机制的新型遗传算法

张　　晖* 　　吴　　斌　　　　余张国　

(西南科技大学计算机学院 四川绵阳 621002)

【摘要】提出了一种将遗传算法与模拟退火算法相结合的新搜索算法。该算法以遗传算法运算流程作为主体流程，并把模拟退火机制融入其中，用以调整优化群体。在进化过程中使用了保留策略，以保存适应度较好的个体。在模拟退火算法的跳变操作过程中使用类似遗传算法变异来实现，先作置反操作，再作前后等长交换操作，以防止陷入局部最优。实验表明，该算法与传统遗传算法相比，提高了进化速度和全局寻优能力。

关 键 词 遗传算法; 模拟退火算法; 进化速度; 全局搜索 中图分类号 TP301.6 文献标识码 A

Research of New Genetic Algorithms Involving

Mechanism of Simulated Annealing

Zhang Hui Wu Bin Yu Zhangguo

(School of Computer Science, Southwest University of Science and Technology Sichuan Mianyang 621002)

Abstract The new global search algorithms result from the combination of the genetic algorithms and simulated annealing algorithms. The genetic algorithms are served as the main flow of the new algorithms which involve the mechanism of simulated annealing to adjust the optimization population. Reservation strategy is used in evolution process to reserve the individuals which have good fitness. To avoid trapping in local optimum, two steps similar to mutation including inverse operation and exchanging operation were adopted during the flipping operation of simulated annealing. The experiments indicate that the new algorithms can improve the evolution speed and the abilities of seeking the global excellent result.

Key words genetic algorithms; simulated annealing; evolution speed; global search

遗传算法能从概率意义上以随机的方式寻求到最优解，但在实际应用中会出现一些问题，主要是容易产生早熟现象、局部寻优能力较差等，而基于遗传算法的求解效果往往不是解决这个问题最有效的方法。

遗传算法的局部搜索能力较差，但把握搜索过程的能力较强；模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但模拟退火算法不适合整个搜索空间，不能使搜索过程进入最有希望的搜索区域，从而使模拟退火算法的运行效率不高。本文在遗传算法的搜索过程中融合退火算法的思想，提高了遗传算法运行效率和求解质量。

1 实现方法

本文提出的新型遗传算法是以遗传算法运算流程作为主体流程，把模拟退火机制融入其中，用以进一步调整优化群体。其基本的执行过程是先随机产生初始群体，开始随机搜索，通过选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地通过对所产生出的各个个体分别进行模拟退火，以其结果作为下一代群体中的个体。即整个算法的执行过程由两部分组成，首先通过遗传算法的进化操作(侧重全局搜索) 2002年8月28日收稿

* 男 30岁 硕士 讲师 主要从事图像处理和人工智能方面的研究

引入模拟退火机制的新型遗传算法

电 子 科 技 大 学 学 报 第32卷 40

产生出较优良的一个群体，再利用模拟退火算法的退火操作(侧重局部搜索)来进行进一步基因个体的优化调整。其中模拟退火操作设计针对一定规模群体中的每个基因个体，对每个基因个体实施一定演变而产生恶化解的设计引用了遗传算法中的变异和倒位思想。这种算法思想策略，从对全局最优解的搜索角度和算法的进化速度上来提高遗传算法的性能。运行过程反复迭代，直到满足某个终止条件为止，其流程如图1所示。

算法设计如下：

1) 初始化运行参数，将运行代数t置为0； 2) 随机产生初始群体P(0)；

3) 群体复制操作P1(t)←Selestion[P(t)]；

4) 使用单点交叉算子进行交叉运算P2(t)←Crossover [P1(t)]；

5) 使用均匀变异算子进行变异运算P3(t)←Mutation [P2(t)]；

6) 对个体进行模拟退火运算P4(t)←SimulatedAnnealing [P3(t)]；

7) 评价群体P4(t)的适应度P4(t)←Evaluation [P4(t)]； 8) 保留适应度较高的个体P4(t)←Reservation [P4(t)]； 9) 终止条件判断，若不满足终止条件，则t←t+1，转到第3)步进行下一步遗传进化过程，否则输出当前最优个体，算法

图1 算法流程图

结束。

在遗传算法的进化过程中，由于选择、交叉、变异等遗传操作的随机性，有可能破坏当前群体中适应度最好的个体。为此使用保留策略，即当前群体中适应度最高的个体不参与交叉操作和变异操作，而是用其来替换本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体[1~3]。

2 实验方法

为评价新型遗传算法的性能，考虑Rosenbrock函数的全局最大值计算问题

f(x1,x2)=100(x12 x22)2+(1 x1)2 s.t. 2.048≤xi≤2.048 i=1,2

该函数有两个局部极大点，即f(2.048, 2.048)=3897.734 2和f( 2.048, 2.048)=3905.926 2，其中后者为 全局最大点，解决该问题的构造步骤如下：

1) 确定决策变量和约束条件

2.048≤xi≤2.048 i=1,2

2) 依据所给的数学模型确定编码方案

用长度为10位的二进制编码串表示两个决策变量x1和x2。10位二进制编码可以表示从0～1 023之间的 1 024个不同的数，故将x1和x2的定义域离散化为1 023个均等的区域，包括两个端点在内共1 024个不同的 离散点。从离散点 2.048到离散点2.048，依次让其对应于从0000000000(0)到1111111111(1 023)之间的二进制编码。再将x1和x2两个10位长的二进制编码串连接在一起，组成一个20位长二进制编码串，即构成了Rosenbrock 函数优化问题的染色体编码方法。使用这种编码方法，解空间和算法搜索空间具有一一对应的关系。

3) 确定解码方法

解码时需要先将20位长的二进制编码串切断为两个10位长的二进制编码串，然后将其转换成对应的十进制整数代码，记为y1和y2。依据前述编码方法和对定义域的离散化方法可知，将代码yi转化成xi的解码公式为

xi=

4.096yi

2.048 i=1,2

1 023

引入模拟退火机制的新型遗传算法

第1期 张 晖 等: 引入模拟退火机制的新型遗传算法 41

4) 确定个体评价方法

Rosenbrock 函数的值域总是非负的，并且优化目标是求函数的最大值，故这里将个体的适应度直接取为对应的目标函数值，并且不再对其作其他变换处理，即有F(x)=f(x1,x2)。

5) 设计遗传算子

选择运算使用比例选择算子、交叉运算使用单点交叉算子和变异运算使用均匀变异算子。 6) 确定遗传算法运行参数

根据本文的程序设计，所选参数如下： 群体大小：M=80 终止代数：T=180 交叉概率：Pc=0.6 变异概率：Pm=0.001

7) 确定模拟退火算法的运行参数

本文对模拟退火算法运行参数的确定是依据基本理论，并通过实验的方式来确定。即按有利于提高整个算法进化速度的方向，经过多次的尝试来决定模拟退火算法运行所需的各个参数值。

(1) 应选取充分大的控制参数初值T0，即可达到准平衡的论证。实际上，为使算法进程一开始就达到准平衡，应让初始接受率r接近于1，由Metropolis 准则exp( f/T0)≈1可推知T0值很大。通过实验选取的经验法则是：要求算法进程在合理的时间里搜索尽可能大的解空间，只有足够大的T0才能满足这个要求，本文选T0=9 000.0。

(2) 控制参数终值Tf选取：由于算法收敛于最优解集是随控制参数T值的缓慢减小逐渐进行，只有在控制参数终值Tf充分小时，才有可能得出高质最终解。本文是每进行一轮后，用T(t)=kT(t 1)(k为一略小于1的系数)来实现T的缓慢减小过程，用循环参数t来控制算法的停止，k=0.95, t<200。

(3) 程序中对群体中的个体执行个体跳变操作的思想基于遗传算法的“变异”操作思想设计，通过两步实现：第一是对个体中的基因按一定的概率进行随机单点置反操作；第二是把个体基因串按较小的概率p(p<0.01)进行前后等长交换操作。这样的演变操作对维持群体中个体的多样性，防止算法陷入局部最优有着重要作用。对按以上步骤设计的模拟退火遗传程序进行调试运行，并对基本遗传算法和模拟退火遗传算法对Rosenbrock函数进行最大值寻优的实验结果进行分析。

3 实验结果

数据的采集采用算法程序连续运行25次(为一组)，记录搜索到最优解所需的进化代数，在到终止代数(180代)还不能搜索到最优解的以180计。对4个被测算法程序随机进行7组采样，先对实验的采集数据每组分别求进化次数平均值，然后再把前后实验所得的7组数据总体求平均值，再连同所有单个数据一起作为算法评价的依据，即算法在所测过程中陷入局部最优解的次数和进化平均速度。实验结果如表1所示，其中无最解率是指在规定的进化代数(180)内没有搜索到全局最优解的比例。

表1 实验结果表

比较项目 平均进化代数 总体无最解率/(％)

不带保留策略 基本遗传算法

148 77

带保留策略基 本遗传算法

99 46

不带保留策略 新型遗传算法

55 6

带保留策略新 型遗传算法

21 0

引入模拟退火机制的新型遗传算法

电 子 科 技 大 学 学 报 第32卷 42

4 结 束 语

本文通过对传统遗传算法和模拟退火算法基本原理的研究，从对其各自的优缺点作了分析，提出了一个把模拟退火算法和传统遗传算法相结合的实现方案。在实验过程中发现，基本遗传算法很容易陷入局部最优，而在不带保留策略的新型遗传算法中虽没有搜索到全局最优解，但在陷入次优解时，在算法运行中出现从次优解中跳出的现象，而这种跳变在基本遗传算法的运行过程中几乎不会出现。实验结果表明，新型遗传算法比传统的基本遗传算法在进化速度和全局搜索能力上均有较大提高，而且还有效地克服了传统遗传算法可能出现的不收敛现象。

参 考 文 献

1 Man K F, Tang K S, Kwong S. Genetic Algorithms[M]. London：Springer, 1999

2 刘 勇, 康立山, 陈毓屏. 非数值并行算法(第二册)——遗传算法[M]．北京：科学出版社，1995 3 康立山, 谢 云, 尤矢勇, 等. 非数值并行算法(第一册)——模拟退火算法[M]. 北京：科学出版社，1995

编 辑 徐培红

------------------------------------------------------------------------------------------------------------------------------------------- 成果与专利

正交电极体外射频前列腺治疗仪

正交电极体外射频前列腺治疗仪给出了一种体外射频前列腺治疗仪，由于它具有正交放置的两对电极，患者的前列腺部位比已有的单容性电极的场强增加了1.4倍，提高了治疗部位的温度，从而提高了治疗效果，但非治疗部位的温度并不增加；再加上增加了一套皮肤降温装置，从而消除了治疗者皮肤灼伤及皮下脂肪结块现象；其射频产生控制系统采用它激工作方式，比已有的自激工作方式更稳定，没有间隙振荡和停振现象产生，提高了疗效且使用方便，是一台疗效显著、实用化的体外射频前列腺治疗仪。

近贴式透明全息防伪膜及其制造方法

近贴式透明全息防伪膜及其制造方法是属于全息防伪薄膜技术。产品是由具有全息图案的有机薄膜层、点阵状的金属箔镜面层和粘结层构成。其产品具有既能看到防伪标志的全处民图案，又能通过透明防伪薄膜观察到被防伪物的表面细节，它适用有效的各种专用证、卡、券，有利于识别假冒伪造的网点印刷工艺和化学镀工艺、或真空蒸镀工艺，生产成本低、技术易掌握，利于厂家成批生产。

文 争

本文来源：https://www.bwwdw.com/article/fq0j.html