混合模拟退火遗传算法

2024-09-03

混合模拟退火遗传算法（精选八篇）

混合模拟退火遗传算法篇1

RNA分子具有三级结构,其中一级结构是由碱基A(腺嘌呤)、G(鸟嘌呤)、U(尿嘧啶)、C(胞嘧啶)所构成的线性序列;二级结构是由碱基配对与核苷酸链折叠形成的茎环结构[1]。RNA分子很多功能都需要借助其二级结构实现,准确预测其二级结构具有重要意义。

基于最小自由能模型是预测RNA二级结构最常用的方法。Tinoco等[2]于20世纪70年代提出了最小自由能模型,Nussinov针对该模型运用动态规划法寻找最优结构[3]。该模型假定真实的RNA会折叠成具有最小自由能的二级结构,分子自由能是各个配对的碱基对自由能之和。而后Zuker改进了此方法,将RNA二级结构中不配对碱基形成环区所产生的能量也考虑进去,并测定出了具体的数值[4]。为了避免动态规划算法的复杂性,近年来研究者在最小自由能量基础上运用启发式算法对RNA二级结构预测方法进行优化。常见的算法有粒子群优化算法[5]、神经网络算法[6]、遗传算法等。

遗传算法是模拟生物遗传进化中选择、交叉、变异机制而形成的一种自适应全局优化搜索算法[7]。Batenburg等[8]最早提出了利用遗传算法模拟RNA序列折叠过程并预测出其二级结构。Wiese等[9]在整数编码基础上改进算法中的选择交叉算子,有效提高了预测的准确度。遗传算法的全局搜索能力较强,但在搜索初期,优良个体急增会使得种群失去多样性,从而导致最后的解空间陷入局部而达不到全局最优解[10]。

模拟退火算法是由Metropolis等[11]于1953年提出,是一种以金属退火原理为基础的全局最优化方法,以某种概率接受劣质解获取全局最优解。文献[12]采用模拟退火算法,通过碱基配对与拆分的方式改变RNA二级结构,以热力学自由能和动力学活化自由能为目标函数,模拟RNA二级结构的形成过程。在算法实现过程中,受计算速度和时间的限制,难以保证结果为全局最优解,当问题的规模不可避免地增大时优化效果不够明显。

这两个算法都曾经被生物研究者用于预测RNA二级结构,但效率并不是特别高。本文结合遗传算法较强的全局搜索能力和模拟退火算法较强的局部搜索能力,将这两种算法相结合,设计出一种用于预测RNA二级结构的混合型算法———遗传模拟退火算法(GSA)。本文算法中,用茎序列表示个体,设计相应的交叉变异算子并进行了退火操作,最后给出PSTV病毒(Potato Spindle Tuber Viroid)的二级结构预测来验证算法的可行性。

1 相关知识

1.1 RNA二级结构

碱基是RNA二级结构的基本单元,根据碱基配对规则形成的连续3对以上的配对碱基集合形成茎区,未形成配对的碱基构成环区,相容茎区集唯一确定出RNA的二级结构[13]。由于RNA二级结构是空间结构,为便于研究,常使用一些特殊的表示方法,包括平面图表示法、点括号法和三元组法等[14]。

图1为平面图表示法,其中的每个黑点代表碱基A、U、C、G,可以直观地看出其中的配对关系。本节对RNA二级结构定义的描述中使用的是三元组表示法,该方法可以标识出配对的具体位置与长度。

RNA二级结构的相关定义如下:

定义1:长度为n的RNA序列R=r1r2r3…rn,如果其中存在有子序列R1=riri+1…ri+k-1和R2=rjrj+1…rj-k+1,且(ri,rj)∈{(A,U),(U,A),(G,C),(C,G),(G,C),(G,U),(U,G)},其中1≤i<j≤n,j-i>3,则称R1和R2构成一个茎区s,记作s(i,j,k)。其中i和j分别表示茎区在序列R中的起始位置和结束位置,k表示茎区长度。

定义2:给定两个茎区s1(i1,j1,k1)和s2(i2,j2,k2),若s1和s2既不相交也不重合,则称茎区s1和s2相容。即需要满足:

定义3:设S={s1,s2,…sm}是RNA序列R中的一个茎序列,若其中的任意两个茎区si和sj都是相容的,则该相容集合S能够唯一确定出序列R的一个二级结构[15]。

1.2 最小自由能量模型

由分子热动力学基本原理可知,RNA二级结构所含的总自由能应尽可能保持较小,才能使其处于相对较为稳定的状态[16]。根据RNA二级结构的特征,假设一个RNA二级结构S的自由能为E(S),则可以根据其中各分支结构确定图1所示结构的总自由能大小。

本文选用Turner Group所测定的自由能参数。表1为双联体碱基配对的自由能参数,可以求出Epair的数值。

同样,其它环区结构也分别有对应的参数,可以从http://rna.chem.rocher.edu/下载,最终可求出总的自由能。对于一组给定的RNA序列,设A为其所有可能的二级结构集合,S′为其中最小自由能的二级结构,则求解最小自由能二级结构的问题可以表示为:

2 遗传模拟退火算法

本文遗传模拟退火混合算法是对遗传操作所产生的一组新个体独立地进行模拟退火操作求得最优解的过程。其运行过程与遗传算法相似,以适应度函数为准则,通过选择、交叉、变异等步骤来产生一组新个体,然后再独立地对每个个体进行模拟退火过程,以其结果作为下一代群体中的个体。此运行所产生的一组新个体独立地随机选择个体中的两个基因作为扰动点,经扰动后的个体所得的适应度增强,则一定接受这个新个体,而当新个体所得的适应度减小时,以某一概率接受这个新个体。

综上所述,本文提出一种遗传模拟退火算法GSA,具体描述如下:

输入:初始种群规模N、遗传杂交概率Pc、遗传变异概率Pm、退火初始温度T0、PSTV病毒一段序列;

输出:以s(i,j,k)三元组形式表示的RNA二级结构。

步骤:

(1)构建碱基配对矩阵,根据待测RNA序列的所有茎s(i,j,k)列表,随机选取其中的N组构成种群。

(2)评价当前种群的适应度,建立适应度函数F=-E(S),作为评分标准。

(3)根据种群中所有结构的自由能大小,利用轮盘赌法选出新一代种群。

(4)由杂交概率Pc在结构中随机选择i、j位,生成变异区间长度li和lj,令a=max(0,i-li+1),b=min(j+lj-1,n)。若某个茎区包括这两个变异区间[a,i]与[j,b]中的碱基去除;

(5)将列表中的茎按照概率p=ΔG(gain)/ΔG(loop)加入形成新结构;

(6)选定二级结构S1和S2进行配对,随机产生杂交位i和j,交换S1和S2中i、j位之间的茎区。

(7)对杂交后的个体以拆分碱基对的方式产生新的个体。

(8)若新旧个体之间的自由能量差值△C<0,接收新的个体;否则,按照概率min{1,-exp(-ΔC/T)}接收新个体。

(9)按照以上的步骤得到能够使得总体自由能。

3 实验结果及分析

实验数据来源NCBI和RNase P数据库,选取PSTV病毒的其中一段序列,运用上节所提出来的算法,测定出其可能的二级结构,并与其真实二级结构相比较,得出预测碱基对位置和个数的准确性。

3.1 评价指标

本文选取了生物信息学研究中常用的两个评价指标:敏感性(Sensitivity,SE)和特异性(Specificity,SP)[17]作为评价RNA二级结构预测结果的标准。敏感性是指正确预测的碱基对个数占所有碱基对个数的百分比;特异性是指所有预测到的碱基中正确预测的百分比,如式(5)、(6)所示:

其中,TP(true positive)表示正确预测的碱基对个数;FN(false negative)表示真实结构中存在,但没有被正确预测的碱基对个数;FP(false positive)表示真实结构中不存在,但被预测出来的碱基对个数。

当FN=0时,SE=1,表明所有的碱基对都被正确预测出来,但其中可能会存在多余的碱基对;当FP=0时,SP=1,表明预测的碱基对都存在于真实结构中,但不能够确定是否全都包含。因此这两个参数的值总会有偏向性,在相关文献中常会用统计学中的马修斯系数[18](Matthews correlation coefficient,MCC)作为参考:

其中,TN(true negative)表示正确预测的不配对的碱基的个数,通常情况下TN不会为0,因此MCC的取值范围[19]是[0,1],MCC可用于平衡敏感性和特异性[20],确保结果不偏向其中某一个参数。从式(7)可以看出,预测精度的提高与正确预测的碱基对个数有关。因此,提高正确预测的碱基对个数有利于提高预测算法的正确率。

3.2 实验分析与讨论

从RNase P数据库查找出PSTVd的实际二级结构中有246对碱基对,存在茎区数量是23个,自由能是-167.9KJ/mol,通过茎区表的形式表示如图3所示。

通过本文算法所得到的碱基对一共有214对,茎区共有24个,总的自由能是-163.7KJ/mol,其中正确预测到的茎区数量为20个,按照茎区表的形式如图4所示。

图5、图6是RNAStructure绘制出来的真实的PSTVd结构和预测到的结构在部分位置的比对,可以看出通过碱基对在不同位置的配对从而形成不同的茎环区。

从表2可以看出,单独使用遗传算法的准确率略高于单独使用模拟退火算法,而本文混合算法结合了两个算法的优点,预测出来的结果在确率上都有所提高。

4 结语

混合模拟退火遗传算法篇2

一、遗传算法

遗传算法（Genetic Algorithm）是最初由美国Michigan大学J.Holland教授于1975年首先提出来的，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法包含5个要素：初始化种群，选择，交叉，变异，更新初始群体，结束条件。

模拟退火算法是根据固体退火原理，将固体加热到充分高的温度，再让其徐徐冷却，加温时，固体内部的粒子随着温度上升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到到平衡态，最后在常温时达到基态，内能减为最小【1】。

由于遗传算法具有良好的全局搜索能力，但是对于局部空间搜索却不是很有效，容易产生早熟收敛现象，陷入局部最优【2】。为了解决这个问题，可以将模拟退火算法结合到遗传算法中，模拟退火算法的局部搜索能力可以解决遗传算法局部搜索能力差以及早熟现象，同时也解决了模拟退火算法全局搜索能力差和效率不高的问题。

二、软件测试

软件测试是运行程序并发现程序错误的过程。测试是为了发现程序中的错误，而不是证明程序中没有错误。而测试用例应该包括为测试某个程序路径或者确定是否满足某个特定需求而编制的一组测试输入、执行条件和与之对应的预期结果。一个好的测试用例是能够快速有效的发现程序中的错误。一般把测试分为两类：白盒测试也称为结构测试、透明盒测试、逻辑驱动测试或基于代码的测试，是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作；黑盒测试也称为功能测试或数据驱动测试，是通过测试来确认每个功能是否得到完整实现，检测每个功能是否都能正常使用。而黑盒测试的测试用例设计通常是用等价划分法。

用等价类划分法首先要划分等价类：输入规定了的取值范围或值的个数就可以确定一个有效等价类和两个无效等价类。输入规定了的输入值的集合或者一个布尔量可以确定一个有效等价类和一个无效等价类。输入规定的输入数据的一组值（假设m个）且对每一个输入值分别处理可以确定m个有效等价类和一个无效等价类。输入的数据必须遵守一定的规则可以确定一个有效等价类和若干个无效等价类。已划分的等价类中各元素处理方式不同时应将等价类再划分为更小的等价类。其次确定测试用例：给等价类编号设计一个重复使其尽可能多地覆盖尚未被覆盖过的合理等价类直到所有合理等价类被测试用例覆盖的测试用例。设计一个使其只覆盖一个不合理等价类的测试用例。

三、用模拟退火遗传算法需求最佳测试用例

（1）编码。模拟退火遗传算法需要将软件测试中的一个问题的可行解从解空间转换到遗传算法所能解决的搜索空间。初始化种群规模为100，编码方法可以选择浮点法、grey法则和二进制法，本文每个参数的编码方式采用二进制编码。

（2）选择退火算子

在软件测试中，测试的目的是发现程序中至今没有发现的错误，一个好的测试用例就相当于遗传算法中适应度值大的个体，本文将初始群体中的100个个体进行适应度评价，个体适应度值越大，该个体被遗传到下一代的概率也越大。

①随机选择初始群体两个个体A、B，计算其个体适应度值f（A）和f（B）。

②如果f（A）

③重复①、②操作直到新的一代群体中也包含100个个体。

（3）选择。染色体的选择方法可以采用锦标赛法和轮盘赌法，本文采用轮盘赌法，通常适应度大的被选择的几率较高。

（4）交叉。在遗传算法的遗传操作中，交叉运算决定了遗传算法的全局搜索能力【3】。将父代中的任意两个个体进行交叉产生最新染色体。进行退火操作，如果最佳适应度大于最新染色体适应度，就用最新染色体适应度取代之前的最佳适应度，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复操作，直至以概率0.7完成所有的交叉操作。

（5）变异。在遗传算法的遗传操作中，变异操作决定了遗传算法的局部搜索能力【3】。变异方法的选择浮点法和单点法。本文采用浮点法。随机选择一个的内部选择两个节点进行变异，如果新产生的个体适应度小于原个体适应度，就用最新个体取代原个体，否则以概率P（exp（（f（A）-f（B））/T））接受最新个体。重复此操作。直至以概率0.05完成所有的交叉操作。

（6）终止条件。当进化代数超过某个值而适应度不变时或者进化代数达到最大值时。最后留下的也即最优的软件测试用例。

四、结束语

综上所述，本文重在在软件测试中使用模拟退火遗传算法需找最好的软件测试用例。以一种高效率的方式完成软件中的黑盒测试，并找出最佳测试用例。

参考文献

[1]季海婧.基于模拟退火—量子遗传算法的路径测试数据自动生成方法研究[D].浙江：杭州师范大学，2012.

[2]杨清平.基于改进遗传算法的测试用例自动生成研究[D].广东：广东工业大学，311.

[3]李欣，基于贝叶斯网络和遗传算法的测试用例生成模型[D].重庆：重庆交通大学，2012.

混合模拟退火遗传算法篇3

电力的生产、传输和使用依赖于发电系统、输电系统和配电系统。配电系统处于电网末端,是连接输电网和用户的中间环节[1,2]。用户很多且相当分散,检修的任务重,一旦检修,很容易直接引起用户停电,而且配电网检修计划需配合上级输电网检修计划[3,4,5]。随着配电网的发展,其自身的检修及优化问题也逐渐受到重视。

配电网检修计划优化是1个多目标多约束的优化问题。许多智能算法,如遗传算法(Genetic Algorithm,GA)和模拟退火算法(Simulation Annealing Algorithm,SA)等均能应用于配电网检修优化,但在实际运用中却发现它们都存在着一定的局限性:遗传算法虽然有很强的全局寻优能力,但其精细局部寻优能力却较差。而模拟退火算法具有较强局部搜索能力,并能使搜索过程避免陷入局部最优解,但模拟退火算法却对整个搜索空间的状况了解不多,不便于使搜索过程进入最有希望的搜索区域,从而使模拟退火算法运算效率不高[6]。

本文根据配电网检修计划优化的思想,在考虑多种约束条件的基础上,建立了以降低供电企业停电损失为目标的优化模型。利用Lin Feng-tse等提出的混合遗传-模拟退火算法[7](Hybrid Genetic/SimulationAnnealing Algorithm,HGSA)对配网检修计划进行优化调整,并与遗传算法和模拟退火算法的优化结果进行比较,证明了所提出HGSA算法的有效性。

1 配电网检修计划优化模型

结合实际工作,综合考虑系统安全和协调检修等多种约束条件,建立以降低供电企业停电损失为目标的优化模型。

1.1 目标函数

配电网检修计划优化的目标:在满足各种约束条件下,尽量减少停电损失。数学描述为:

式中:Pt为第t时段的单位电价;Uti为第t时段停电第i个负荷的容量(以配电变压器为负荷点);为变压器的容载比;T为检修的所有时间段;N为第t个时间段停电的所有变压器数量。

1.2 约束条件

约束条件包括协同约束和互斥约束,主要体现在目标函数的第t个时间段的N中。

(1)协同约束:当停运某台设备,其他设备将跟着停运时,这些设备应该同时检修。

式中:Xi为第i个设备的开始检修时间;Xj为第j个设备的开始检修时间。

(2)互斥约束:当2台设备互为备用时,在1个时间段内只能检修1台。

式中:Dj为第j台设备检修的持续时间。

(3)检修资源约束:检修的设备总数应该少于等于拥有的资源数。

(4)潮流约束:。

式中:Si为通过设备i的潮流值;为设备i允许通过的潮流限制。

(5)电压约束:。

式中:Vi为第i个节点电压;和为节点i允许的最低及最高电压。

由上述数学模型可见,配电网检修优化是1个复杂的离散非线性优化问题,也可以看作是大规模的组合优化问题[8],若用传统的优化方法求解存在很大的困难。研究人员大多数都开始采用现代的智能优化方法求解,这些智能方法大体包括遗传算法以及模拟退火法等。但配电网设备众多检修优化又存在大量约束条件,所以即使现代的智能优化方法运用到配电网检修优化时也存在大量问题。所以本文采取了遗传与模拟退火结合的混合算法。

2 混合遗传-模拟退火优化算法

与传统的遗传算法和模拟退火算法相比,混合遗传-模拟退火算法主要有以下特点:

(1) HGSA在遗传算法中引入模拟退火思想,有效缓解了遗传算法的选择压力,并对基因操作产生的新个体实施概率接受策略,不但增强了算法的全局收敛性,并且使算法在优化后期有较强的爬山性能,加快了进化后期的收敛速度。

(2) HGSA在模拟退火算法中引入遗传算法的群体操作思想,使算法在解空间展开多处的局部搜索,既加快了算法的搜索速度,又能有效地提高模拟退火算法处理局部收敛问题的能力。

(3) HGSA以遗传算法控制寻优方向,从而加快搜索进程,用模拟退火算法解决局部收敛问题,以提高搜索精度。充分发挥了遗传算法的快速全局搜索性能和模拟退火算法的局部搜索能力,具有较高的效率和广泛的适用性。

遗传-模拟退火混合算法的流程如图1所示。

在优化检修计划时,HGSA可能会产生一些适用性问题,如寻优速度较慢、运算时间较长和收敛精度较差等,针对这些问题,本文采取了如下改进措施:1)在编码方式上改进了传统的二进制编码,直接采用整实数编码,且直接反映检修计划,大大减少了搜索空间;2)构造适应度函数时,加入了反映约束条件的惩罚项;3)在选择方式上,除采用按比例的适应度分配法分配个体的选择概率外,还采用稳态繁殖的选择方法,即在每次迭代中,父种群中2个个体繁殖的新个体直接替代父种群中适应度较差的个体,并与父个体一起参与繁殖下一代,加快寻优速度;4)交叉算子采用一点交叉,为避免杂交后得到的解超出起始时间的上下限范围,杂交的位置必须是介于2个相邻的子分量之间;5)变异算子以一定的概率采用实值变异。因为用的是十进制编码,所以变异不能和二进制编码一样直接将某位或某些位的状态取反,而是按随机方式进行变异;6)为了兼顾计算时间和精度要求,群规模取60,并通过HGSA的概率接受准则解决可能出现的局部收敛问题;7)以最优个体最少保留代数与最大遗传代数相结合作为终止进化的判据,从而避免单因素控制准则的缺陷。

3 算例分析

广灵供电支公司隶属于山西省电力公司,辖有广灵110 kV变电站、东台110 kV变电站、罗疃35 kV变电站和南村35 kV变电站。其中广灵110 kV变电站出线有10 kV加斗线、10 kV宜兴线、10 kV斗泉线、10 kV作疃线、10 kV广百线、10 kV城水线、10 kV广疃线、10 kV微波线、10 kV城一线、10 kV城二线;东台110 kV变电站出线有10 kV东城一线、10 kV东城二线、10 kV东纸线、10 kV东王线、10 kV东蕉线;罗疃35 kV变电站出线10kV罗蕉线、10 kV罗水一线、10 kV罗水二线、10 kV罗一线、10 kV罗锰线10 kV罗化一线、10 kV罗化二线;南村35 kV变电站出线10 kV南村线、10 kV南海线、10 kV南梁线、10 kV南望线。

用本文建立的配电网检修优化模型,分别用遗传算法、模拟退火算法和遗传-模拟退火混合算法对广灵供电公司2009年3月份的检修计划进行优化。其中遗传算法的种群规模为60,交叉率为0.6,变异率为0.01,最大迭代次数为300。模拟退火算法的初始温度t0=K(fmax-fmin),K为初始温度系数取100,fmax为初始种群最大适应度值,fmin为初始种群最小适应度值,退温函数为tk-1=αtk,α为退温系数取0.8。

3 种算法的迭代收敛过程如图2所示。由图2可看出,模拟退火算法在迭代一定次数之后能够到达较优的解,遗传算法因局部参数空间内集中搜索机制薄弱,最优解的更新缓慢,HGSA方法的收敛速度相对最快、寻优结果相对最优。

检修计划优化之前的负荷损失为20.304 MW,各算法优化后的负荷损失及减少的负荷损失如表1所示。

4 结论

本文采用遗传-模拟退火混合算法,通过算法的匹配克服了各自的缺陷,综合了两者的优点,使算法既具有遗传算法的全局性和并行性,又具有模拟退火算法的局部搜索能力和退火特征。计算结果表明该混合算法既加快了收敛速度又减少了负荷损失,最大限度地避免重复停电,更适合配电网检修优化问题。

摘要：从配电网设备检修计划编制的实际需要出发,在考虑多种约束条件的基础上,建立了以配电网经济性最好为目标的优化模型。针对该模型的特点,采用1种新型混合遗传-模拟退火算法(HGSA)对配电网检修计划进行优化调整。该算法综合了遗传算法和模拟退火算法的优点,使其既具有遗传算法的全局性和并行性,又具有模拟退火算法的局部搜索能力和退火特征。通过遗传算法、模拟退火算法对实际检修计划优化结果的比较,证明了所提出HGSA算法的有效性。

关键词：电力系统,配电网检修计划,遗传算法,模拟退火算法,混合遗传模拟算法

参考文献

[1]朱新菊,王毅,万明明.配电网检修计划优化问题的研究[J].陕西电力,2009,37(1):28-31.

[2]李红蕾,戚伟,陈昌伟.智能电网模式下的配网调控一体化研究[J].陕西电力,2010,38(5):91-93.

[3]董雷,鲍海,齐郑,等.一种供电系统检修计划自动制定系统的设计方法[J].现代电力,2001,18(3):58-60.

[4]于尔铿,刘广一,周京阳.能量管理系统[M].北京:科学出版社,2001.

[5]左郑敏,吴耀武,熊信艮.机组检修计划问题的GA&SA组合算法[J].水电能源科学,2001,19(4):64-66.

[6]陈少华,杨澎.遗传算法在火力发电机组计划检修中的应用[J].武汉水利电力大学学报,1999 32(5):23-28.

[7]王凌,郑大钟.一种GASA混合优化策略[J].控制理论与应用,2001,18(4):552-554.

混合模拟退火遗传算法篇4

纸箱包装行业是一个传统的制造行业, 随着社会经济的发展和物质文化的进步, 对于纸箱的需求越来越大, 因此对纸箱生产的要求也越来越高, 这就对纸箱制造企业提出了更高的要求。因此纸箱制造企业迫切需要降低生产成本, 提高生产效率。企业在生产中的损耗是影响成本的一大因素, 但是损耗是不可能被消灭的, 我们能做到的是尽可能的通过各种方式、技巧来将损耗降低到最低。本文讨论的问题是如何降低纸箱企业生产上的损耗, 并用遗传模拟退火算法来求得问题的近似最优解。

装箱问题属于NP难题.这里采用遗传算法来解决这个问题, 但是遗传算法的局部搜索能力不强, 引起这个问题的主要原因是新一代群体的产生主要是依赖上一代群体的随机交叉重组来完成的, 这样即使搜索到最优解附近, 而要达到这个最优解, 仍然需要费很多功夫。另外对于已经编码的个体, 再进行变异操作的时候, 虽然只是对一个基因座进行操作, 但是染色体值会发生很大变化。遗传算法的全局搜索性能较强, 但是其容易过早收敛, 而且在进化后期搜索效率较低, 种群的进化缓慢;模拟退火算法具有较强的局部搜索能力, 并且能使搜索过程避免陷入局部最优解, 但是把握搜索过程的能力不强, 运行效率不高。本文通过将模拟退火的思想引入遗传算法, 使两者有效地结合, 缓解了遗传算法的选择压力, 增强了遗传算法的全局收敛性, 避免在搜索过程中陷入局部最优。

1 纸箱生产损耗问题的提出

有一个宽度为S (S>0) 的生产线, 有各个宽度不同的纸箱订单, 各个订单所对应的纸板宽度是a $_{1}^{}$ , a $_{2}^{}$ , ..., a $_{n}^{}$ , a $_{n}^{}$ ∈Z $_{}^{+}$ , 假设需要m次换纸, 有一批原纸, 原纸的宽度各不相同, 分别为:w $_{1}^{}$ , w $_{2}^{}$ , ..., w $_{m}^{}$ , 对应的成本分别是c $_{1}^{}$ , c $_{2}^{}$ , ..., c $_{m}^{}$ , 需要将这些订单进行排程合并生产。

目标: (1) 是生产线上的修边损耗最小; (2) 在满足所有订单都投入生产的情况下, 每次生产的用纸利用率要高。显然第一个目标的重要性要比第二个目标的重要性大。

并满足以下约束条件:

1) 每次换纸后生产的订单的宽度和不能大于原纸的宽度和边幅的差;

2) 因为后道工序的原因, 每个订单只能一次生产, 不能分批生产。就是说订单所对应的纸板的用纸必须一致, 不存在换纸的情况;

3) 所有的订单的宽度不能超过原纸的宽度。

2 算法设计

2.1 算法步骤

STEP1 初始化种群T, 种群数量为num1, 产生一组随机的染色体。

STEP2 判断是否满足结束条件, 若满足结束条件则停止计算输出最优染色体i $_{}^{*}$ 和最优解f $_{}^{*}$ 。否则保存这些染色体作为模拟退火算法的初始解。然后将T中最好的1/5直接复制到新的种群中, 剩余的计算适应度函数, 由适应度函数决定的概率分布选取一组染色体形成种群tmp1。

STEP3 以概率Pcross种群tmp1进行交叉操作, 得到种群tmp2。

STEP4 以概率Pmute种群tmp2进行交叉操作, 得到种群tmp3。

STEP5 用模拟退火算法进行处理, k=0;初始温度tk=t0;对初始种群计算适应度函数值fi (tk) , 其中, fi (tk) 为第i个染色体在温度为tk时的适应度值。i ∈tmp3 , 即当代种群中的一个染色体。任意选择一个染色体, 按模拟退火算法的接受准则接受或拒绝该染色体, 执行times1次, 得到种群tmp4。接受准则为:

$A_{i} (t_{k}) = \min {1, \exp (- \frac{f_{i} (t_{k}) - f_{i} (t_{k - 1})}{t_{k}})}$

STEP6 找出使函数fi (tk) 最小的染色体i和这个函数值f, 如果f<f*, 那么记i*= i, f*= f。tk+1=α×tk, α∈ (0, 1) 。种群tmp4的数量为num4, 随机产生 (num1- num4) 个染色体, 得到种群pop (k+1) , 并使k=k+1, 返回STEP2。

2.2 遗传编码

可以将所有的订单全部排开, 每个订单都包含一定的信息, 将原纸看成是容器, 订单包含在原纸中。每种原纸都包含一定的信息, 将这些信息改造成一个数据结构, 这些数据结构与遗传算法中的0/1编码没有实质的区别。不同的只是各个等位基因包含的是0/1值, 还是订单的信息。编码如图1所示。

2.3 选择、交叉和变异算子

根据事先确定的种群数量resultNum和排序的结果, 可以计算出某个体ansi的相对适应值f (ansi) 。对于基于适应值的概率分布选择新群体的选择过程, 通常使用一个根据适应值调节刻度宽距的轮盘。将这样的选择方式称为轮盘赌方式。可由如下方式构造这样一个轮盘:

$Ρ {a n s_{i}} = \frac{f^{} k_{} (a n s_{i})}{\sum_{j = 1}^{r e s u l t Ν u m} f^{} k_{} (a n s_{j})}$

交叉算子使用两个父代 (P1, P2) 产生一个子代C。两个父代中, 一个通过轮盘赌方式, 根据其选择概率选定, 另一个随机选定。由一个父代P产生一个子代C。首先通过轮盘赌方式, 根据其选择概率选定父代P。

2.4 自适应的交叉算子和变异算子概率

本文采用根据适应度集中程度, 自适应地变化整个群体的Pcross和Pmute的方法, 并采用群体的最大适应度fmax、最小适应度fmin和适应度平均值favg, 这三个变量来衡量群体适应度的集中程度。

fmax与fmin的接近程度反映了整个群体的集中程度, 二者越接近, 遗传算法越可能陷于局部最优解, 也就是适应度越“集中, $\frac{f_{\min}}{f_{\max}}$ >b时, 认为个体集中, 0<b<1。b越接近于1, 该式就越容易满足, 从而越容易判断为“集中”。

fmax与favg的接近程度反映了群体内部适应度的分布情况, 二者越接近, 表明该代个体越集中。当 $\frac{f_{a v g}}{f_{\max}}$ >a时, 认为个体集中, 0.5<a<1。a越接近于1, 该式就越容易满足, 从而越容易判断为“集中”。

当 $\frac{f_{\min}}{f_{\max}} > b$ 和 $\frac{f_{a v g}}{f_{\max}} > a$ 时, 判断为群体“集中”, 此时, 使Pcross和Pmute根据群体的集中程度自适应变化;不满足该条件时, 判断为群体“分散”, Pcross和Pmute保持最初的较小的初值。

$Ρ_{c r o s s} = {\begin{cases} Ρ_{c r o s s} \times \frac{1}{1 - \frac{f_{\min}}{f_{\max}}} 当 \frac{f_{\min}}{f_{\max}} > b 和 \frac{f_{a v g}}{f_{\max}} > a \\ Ρ_{c r o s s} 其他 \end{cases}$

$Ρ_{m u t e} = {\begin{cases} Ρ_{m u t e} \times \frac{1}{1 - \frac{f_{\min}}{f_{\max}}} 当 \frac{f_{\min}}{f_{\max}} > b 和 \frac{f_{a v g}}{f_{\max}} > a \\ Ρ_{m u t e} 其他 \end{cases}$

2.5 群体评价

决定某个解是否可行或是好坏的因素有三个:

(1) 所有的订单是否都在生产线上生产;

(2) 总的损耗最少;

(3) 每次换纸后生产用纸的损耗能够相对均匀。

设最后得到的问题的个体解集为ansi, 需要对解集做一个筛选, 得到最优解。即要根据这三个因素作一些处理。

因素 (1) 的量化指标可以通过检测当前解没有放入原纸的订单宽度之和, 即 $\sum_{t = 1}^{k} a_{t}$ 。

因素 (2) 的量化指标即在所有个体解ansi中寻找损耗的数目最小的一个, 即:

因素 (3) 的量化指标为所有过程的损耗率的偏差平方和, 群体中第i个解的损耗率的偏差平方和lossStai为:

$l o s s S t a_{i} = \sum_{j = 1}^{m} (l o s s R a t e_{i j} - a v g L o s s R a t e_{i j})^{2}$

因此, 根据惩罚函数法和处理多目标优化的加权系数法, 定义适应值函数为:

F () =k1A+k2B+k3C

其中, k1, k2, k3为权重, 可以根据经验需要来选择, 且满足k1, k2, k3>0, k1+k2+k3=0。

3 总结及展望

本文主要针对纸箱软件的排单功能, 考虑了纸箱厂的实际情况, 根据纸箱厂的实际工艺和工序完成的。除了物流行业, 装箱算法在工业生产中有比较多的应用, 尤其是各种行业的排单功能。对于纸箱包装行业, 本文对此行业软件的开发提供了一些经验。文章将将遗传算法和模拟退火算法结合, 防止了遗传算法的收敛过快以及局部搜索能力不强的缺点。在遗传算法的选择操作中直接保存优秀个体, 来增强算法的收敛性。在变异和交叉操作中采用自适应的变异和交叉概率, 增强了搜索解空间的均匀性, 并引入了记忆功能, 最终获得问题的近似最优解。

参考文献

[1]胡瑞, 丁香乾.复杂集装箱装载问题法研究.中国海洋大学, 2006:45- 48.

[2]马广馄, 黄有群.集装箱装入新算法的研究与软件实现.沈阳工业大学, 2004:47- 49.

[3]江娜, 丁香乾.混合遗传算法在装箱问题中的研究.中国海洋大学, 2006:34- 50.

[4]黄川, 杨慰民, 吴子文.集装箱装载优化算法研究.福建师范大学, 2005:50.

[5]翟钰, 孙小明.三维装箱问题的混合遗传算法研究.上海交通大学, 2007:23 -42.

[6]阎庆, 鲍远律.物流配送中心管理信息系统.中国科学技术大学, 2006:41 -45.

[7]武晓金, 朱仲英.二维装箱问题的一种实现方法.微型电脑应用, 2003 (4) .

[8]周明, 孙树栋.遗传算法原理及应用.国防工业出版社, 1999, 6.

[9]张辰, 张艳群.基于遗传和模拟退火算法的自动组卷系统设计与实现.计算机工程与科学, 2004, 26 (11) .

[10]张智海, 吴星玮, 郑力.并行遗传模拟退火算法求解带容量限制的车辆调度问题.清华大学出版社, 2006.

[11]姚庆祝.配送中心选址问题的温度并行模拟退火算法.南开大学出版社, 2006.

混合模拟退火遗传算法篇5

关键词：协商,遗传算法,模拟退火算法,实数编码

0 引言

随着电子商务的不断发展，企业和消费者都希望获得一种更加主动化、智能化的服务，从而基于Agent的电子商务诞生了。由于Agent所代表个人的偏好、目的和知识的不同，两个Agent要达到一致，就必须经过一个协商的过程。而当参与协商的Agent数目和所需协商的属性较多，且范围比较大的时候，协商问题就变成了一个大规模的非线性优化问题，采用传统的方法比较难解决。

解决此类问题目前比较多的是使用遗传算法[1]，比如文献[2,3,4]，遗传算法能从概率意义上以随机的方式寻求到全局最优解，但是遗传算法的局部搜索能力较差，实际应用搜索过程中比较容易产生过早地收敛即“早熟”现象[2,3]，然而遗传算法尚能在一个可以接受的时间内求得问题的最优解。

模拟退火最早是由N.Metropolis[5]等人于1953年提出的，S.Kirkpatrick[6]等人和V.Cerny在1983年成功地把它应用于VLSI设计等优化问题。它是一种解决非线性优化问题的有效算法，能够克服局部极值而求解全局最优解，但存在一个很大的缺点是其计算量过大，收敛速度较慢。因此将遗传算法和模拟退火算法结合使用是目前解决这类非线性优化问题的一种有效方法。

在基于Agent的电子商务系统中如何提高协商效率，减少协商时间，是Agent协商研究中的一个重要课题。本文提出一种加速遗传模拟退火算法，通过在遗传算法中引入模拟退火算法和加速机制，避免了遗传算法和模拟退火算法的自身缺陷，并且能大幅度提升收敛速度，从而使协商过程更加高效准确。仿真试验表明，该算法比遗传算法、模拟退火算法以及一般的遗传模拟退火算法都具有优越性。

1 加速遗传模拟退火算法

根据上面所述，模拟退火算法克服了遗传算法局部寻优能力差的缺点，增强了遗传算法的全局收敛性，而遗传算法能有效地加快模拟退火算法的收敛，减少了算法的运算时间，两者互相取长补短，弥补对方的不足，因此将此两种算法结合使用，是解决多约束优化问题的一个很好方法。

本文算法以遗传算法为基础，将模拟退火算法引入到遗传算法的若干步骤中，在避免陷入到局部最优解和产生“早熟”现象的同时，在算法中加入加速机制，使算法能较快地收敛，并且根据协商问题的具体情况采用特定的编码形式，令算法有一个较稳定的收敛速度。

1.1 加速机制原理

在GA中，随着演化进程的发展，群体在其搜索范围内逐步向其真值附近集中，最后，种群中的值绝大部分都是分布在其真值附近的一个小的范围之内。根据这个结果以及协商问题的特点即协商属性值与满意度值的一一对应性，保证真值若存在则必唯一的特点，可以在种群的演化过程中逐步缩小搜索范围，来压缩解空间，使算法不必每次都在整个初始变量约束范围内进行搜索，这样就可以在保证算法精度的条件下，加速算法的收敛。

定义1以真值为中心，以真值到搜索范围最近的端点之间距离L为半径的区域，叫作真值的领域。

设算法在第k次迭代以后等到当前最优的可行解为F(k)=(p1(k)，p2(k)，…，pn(k))，pi的搜索范围为(pimin,pimax)。

当真值p≤(pimax+pimin)/2时，图1中L1为真值的领域，半径为l,L2=pk-pimin,L3=pimax-pk,L4就是新范围(p′imin,p′imax)，从图1中可得，设真值为p,pk∈(pimin,pimin+2l)，当D=2时p′imin=pimin+(pk-pimin)/2∈(pimin,pimin+l)p′imax=pimax-(pimax-pk)/2∈((pimax+pimin)/2,(pimax+pimin)/2+l)。

所以p∈(p′imin,p′imax)，而pk必然属于p∈(p′imin,p′imax)，因此新的范围包含真值p和当前最优解pk，当p>(pimax+pimin)/2时也可同样证明。所以当当前最优解在真值领域内的时候，其真值和最优解必然也在范围(p′imin,p′imax)内，其中p′imin=pimin+(pk-pimin)/D,p′imax=pimax-(pimax-pk)/D,D≥2,pk为当前最优解，D越大，空间压缩的速度就越慢。

因此可将k+1次的范围确定为(pimin,pimax)k+1=(p′imin,p′imax)，那么实际上算法得到了k个区间(pimin,pimax)t,i=1,2，…，n;t=1,2，…，k;且:

同时最优解p*∈(pimin,pimax)k，算法以概率1收敛到全局最优解。

1.2 编码方式

一般遗传算法采用的是二进制编码。而本模型根据计算结果的精度要求以及根据协商问题的具体情况，采用实数编码方法，每个协商属性对应一个基因。

设若协商属性的变化范围为pi∈(Mi,Ni)，si=Mi+ai(Ni-Mi)，ai∈(0,1)，即可将此协商属性的范围统一转换为0到1之间，可将此范围作为基因值的变化范围。当协商属性范围比较大的时候，初始种群不能充分占据所有约束空间，可能会导致每次计算在收敛速度上差异很大，而转化以后，基因范围一定，增强了算法收敛的稳定性。

2 Agent的协商模型

Agent协商问题描述协商是一种决定形式，决定两个或多个参与者达到一个一致的目标来搜索可能的解空间。文献[7]提出了一种协商模型的形式化描述，即一个协商过程可以用一个10元组来描述-<N,M，△，A,H,Q，Ω，P,C,E>。根据Bazaar模型将协商过程简化为以下描述形式-<N,M,C>，在这里N表示参与者的集合，M表示协商中属性的集合，N中的任一元素i对M中的任一元素j都有满意程度Cij,Cij为正值表示同意，否则表示对此属性不同意。因此，协商问题的最终结果可以描述为获得的N对M的所得所有Cij的最优解。

2.1 协商模型建立

假设本文讨论的协商问题只有两个Agent，即Agent1和Agent2，参与对一个商品采购的协商，假设Agent1代表买家，Agent2代表卖家。

定义2 Pi表示需要协商的属性，i=1,2，…，n。

定义3 S1i(k)表示买家在第k次协商时根据所得Pi值对协商第i个属性的满意度，S2i表示卖家在第k次协商时对协商第i个属性的满意度。

定义4 F1i表示买家对协商属性Pi的偏好，F2i表示卖方对协商属性Pi的偏好，即各个属性的权值，权值可根据协商双方的偏好来设定，只要保证公式(1)成立即可:

若属性Pi不在约束范围内，则定义Fji为一个很大的负数，记F′。

定义5买方的第k次协商的满意度函数为:

卖方的第k次协商的满意度函数为:

由于买卖双方都对协商属性有自己的范围，对属性I，若Agent1要求p1i∈(min1＿pi,max1＿pi)，Agent2要求p2i∈(min2＿pi,max2＿pi)，从而属性的约束变化范围为pi∈{p1i∪p2i};从而目标函数即为在约束条件pi下，求。若min f(k)存在，则判定协商成功，对应的各项属性的最优解即为所求。

本文仅对商品价格、保修时间和送货时间这三个属性进行协商，设P1为商品价格调整幅度，P2为保修时间，P3为送货时间。

2.2 模型的算法设计

2.2.1 AGASA算法过程

算法以遗传算法的过程为主体，加入模拟退火操作和加速机制，从而形成本文的加速模拟退火算法，也可以称为AGASA，算法步骤如下:

1)确定初始种群pop0，初始温度T=T0，降温比率a;

2)判断如果每个属性pimax-pimin≤θi,i=1,2，…，n，θi为很小的正数，算法停止，输出最优解;

3)用遗传算法的选择、交叉和变异操作产生新的群体为popk;

4)对产生的新个体j和其父代i进行模拟退火操作,若f=f(i)-f(j)<0,则接受子代i,否则以概率exp(-f/t)[8]接受i,从而形成新的种群popk+1;

5)在种群popk+1中选择l个适应度最高的个体，计算它们各个属性的平均值作为当前范围压缩所使用的最优解的值，即:

6)确定新的搜索范围(p′imin,p′imax)，其中:

7)降温Tk+1=a Tk，跳转到步骤2)。

2.2.2 初始种群及范围压缩方向

本文的算法无需考虑遗传算法会导致局部最优解的可能，因此根据约束范围及初始群体的数量来随机生成初始群体。

设初始种群数为n，选择的高适应度个体数为l，若n过小，令种群无法分布于整个约束空间，无法有效快速地寻找到全局最优解，而若n过大，则会让优秀个体在群体中所占比例较小，使优秀群体包围真值的几率大大减小，所以，本文选择初始群体数n为300，优秀群体数l为20。

2.2.3 确定初始计算范围

由于压缩范围的前提为当前最优解处于真值领域内，为了避免真值处于边界而导致真值领域为0，从而使算法失效，因此需要将各个基因的变化范围适当扩大。本文取pi∈(min＿pi-1,max＿pi+1)，即每个基因变化范围为(-1,2)。

2.2.4 适应度函数

为适应度函数，

其中:

3 仿真实验

例子:Agent1(买家):降价幅度p1∈(2,10)，保修时间p2(3,12)，送货时间p3(1,7)，权值F(0.7,0.2,0.1);Agent2(卖家):降价幅度p1∈(0,5)，保修时间p2(1,12)，送货时间p3(3,9)，权值F(0.8,0.1,0.1)，边界外权值F′为-100，压缩比D为3，使用的时间结果如表1所示(为20次平均结果)。

从表1中可以看出，本文算法相比一般的遗传算法，加速模拟退火算法[9]有更快的速度得到最优解。

而当协商属性范围有所变化时，本文算法的稳定性也不会发生太大变化，当协商范围分别是例子中5,10,100倍时，算法所用时间的方差如图2所示。

可以从图2中看出，当约束范围越大，没有经过编码处理的遗传算法和加速模拟退火算法的收敛速度的增幅比较大，而本文算法的收敛速度却没有很大的变化，因此具有较强的稳定性。

4 小结

本文首先结合了遗传算法和模拟退火算法两种求优化问题比较常用算法的长处，根据目前协商需要解决的问题，采用了压缩搜索范围机制，来加速遗传模拟退火算法。并且根据协商问题的具体情况，对基因编码作了适当的转换，使算法能在各种不同大小约束范围内有比较稳定的收敛速度，从而能在保证精确度的情况下迅速达成协商一致。

参考文献

[1]Michael C C,McGraw G,Schatz M A.Generating Software Test Data by Evolution[J].IEEE Trans.on Software Engineering.2001,27(12):1085-1110.

[2]Chen Z Z,Zheng J H,Cai Z X.Solving proble,of Agent negotiation by using Genetic algorithm[J].Computer engineer and applications,2001,37(15):113-145.

[3]陈振洲,郑金华,蔡自兴.用遗传算法解决智能体协商问题[J].计算机工程与应用,2001,15:113-145.

[4]Shao-Mei Wang,Wen-Bin Hu.Research on the bilateral negotiation al-gorithms of cooperative design system based on genetic algorithm[C].Computer Supported Cooperative Work in Design,2005.Proceedings of the Ninth International Conference on2005,5:39-43.

[5]Metropolis N,Rosenbluth A,Rosenbluth Metal.Equation of state calcu-lations by fast computing machines,Journal of Chemical Physics,1953,21:1087-1092.

[6]Kirkpatrick S,Gelatt.Jr C D,Vecchi M P.Optimization by simulated annealing,Science,1983,220:671-675.

[7]Dajun Zeng,Katia Syeara.Benefits of Learning in Negotiation[M].

[8]Entropy-Boltzmann.selection in the genetic algorithms.Systems,Man and Cybernetics.IEEE Tran on Chang-Yong Lee.2003:138-149.

混合模拟退火遗传算法篇6

无线传感器网络(WSN)作为上世纪新兴的一种技术,在工农业、城市管理、抢险救灾等许多领域都有重要的科研价值和应用前景。WSN由大量的无线传感器节点组成,每个节点随机布置,因此很难得知其具体位置。虽然运用GPS可以精确得到每个节点的位置,但它高昂的成本和使用环境的限制使它不能广泛应用于WSN。目前,应用定位算法来估算节点位置已经成为一个热点。现有的WSN定位算法是根据少量的位置已知的节点(锚节点)以及它们与其它节点的通信信息来估算整个网络中每个节点的位置。这些算法大部分由两个阶段组成。第一阶段,测量未知节点和锚节点之间的距离或角度,这一阶段称为测距阶段。第二阶段,利用前一阶段的距离或角度测量值得到未知节点的位置,这一阶段称为定位阶段。由于设备的硬件代价和使用限制条件,并且粗精度的定位对于绝大多数应用来说已经足够,许多研究者认为跳段距离是估计未知节点和锚节点距离的一种有效途径。DV-Hop是利用跳段距离的定位算法中最受关注的一个。

定位问题已经被证明是一个NP难解的问题[1],要想在多项式时间内解决这个问题必须使用启发式方法。本文提出使用遗传模拟退火算法作为DV-Hop的后期优化,即使用DV-Hop计算基于跳段的距离,使用遗传模拟退火算法计算节点的位置。仿真结果表明,这种新的定位方法比目前提出的其他几个定位算法的性能要好。

1 相关工作

目前许多定位算法相继被提出[2,3]。本文仅详细介绍利用跳段数来计算距离的方法,因为本文的距离估计就是采用该方法。

1.1 DV-Hop的基本机制

DV-Hop[4,5,6]是一种基于跳段的定位算法。它主要由三个阶段组成。

第一阶段,网络中所有的节点计算其到每一个锚节点的最短路径,该路径是跳段数的形式。具体执行过程如下:每个节点都需要一个表来记录锚节点的信息,该表类似于路由表,我们称之为“锚节点列表”。每个“锚节点列表”的形式为{IDi,xi,yi,hi},其中IDi是锚节点的标识符,xi和yi分别是该锚节点的横坐标和纵坐标,hi是节点到该锚节点的跳数值。开始时,每个锚节点都广播一个消息,其中包含它的IDi、(xi,yi)和hi(hi被初始化为0)。一旦接收到此消息,接收节点会检查它的“锚节点列表”中是否含有相同IDi的锚节点信息。如果没有,接收节点就把到该锚节点的跳数值增加1,并将该锚节点的IDi记录到其自身的“锚节点列表”中,然后将此消息广播给它的邻居节点;如果有,则接收节点会将本次接收到的消息中的hi与它“锚节点列表”中的hi进行比较。如果本次消息的跳数值hi小于原来的,则表明了本次的跳数值hi是到那个锚节点的较短跳数值hi,于是该接收节点就更新其“锚节点列表”中的跳数值为此较小者,并将跳数值加1后广播给其邻居节点;若以上两种情况都不是,该消息就被抛弃,既不被更新也不被广播。更新和广播一直继续,直到找到所有的最短路径。

第二阶段:一旦一个锚节点得到了到其他所有锚节点的信息,该锚节点就会计算平均每跳距离Hopsizei,它是该锚节点到所有锚节点的距离之和与所有跳数值之和的比值。锚节点计算出Hopsizei后,会将该值广播给邻居未知节点。Hopsizei被未知节点用来粗略估算到每个锚节点的欧式距离,即将未知节点到每个锚节点的跳数乘以Hopsizei。

每个锚节点计算Hopsizei的公式为:

$Η o p s i z e_{i} = \frac{\sum_{j \neq i} \sqrt{(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}}}{\sum_{j \neq i} h_{j}} (1)$

式中,hj是当前位于(xi,yi)的锚节点与位于(xj,yj)的锚节点之间的跳数值。

由经验可知,一个锚节点在整个定位过程中至少需要计算一次Hopsizei。Hopsizei的更新和广播在文献[7]中被第一次陈述。

第三阶段:在二维空间中,一旦一个未知节点至少知道了它到三个锚节点的估计距离,该未知节点就会执行三边方法来估算自身的位置。每当有了新的信息时,该估计值将会被更新。这些新的信息可以是新的锚节点信息、到锚节点的更短路径、新的Hopsizei等。当不再有更新并且整个网络变得稳定时,定位估计停止,即定位过程完成。

1.2 基于优化算法的定位算法

定位问题在本质上是一个基于不同距离或路径测量值的优化问题。大部分工作都是致力于利用不同的启发式或者数学方法来提高定位估计的精度。目前遗传算法、模拟退火算法、差分进化算法成功地解决了许多复杂的优化问题。这些方法都是基于全局误差函数的最小化。近年来,有学者提出了利用这些优化算法来改善定位算法的性能。

V.Tam[8,9,10]提出了利用微种群遗传算法改进APS。文献[11]解决了同时定位和映射问题。该问题被定义为一个全局优化问题,并用遗传算法来解决。基于模拟退火算法的定位算法在文献[12]中被提出,模拟退火算法的主要特征是可以尽量避免陷入局部最小值。文献[13]提出了一种基于差分进化算法的复杂度较低的定位算法。

2 基于遗传模拟退火算法的定位算法

2.1 遗传模拟退火算法

遗传算法(GA)和模拟退火算法(SA)是使用范围较广泛的优化算法,它们各有优缺点。GA可以从一个初始种群并行开始,但它却容易陷入局部最小解。相反,如果初始温度较高,降温速率较低,SA可以克服局部最小解。但是较高的初始温度和较低的降温速率影响了SA的性能。并且SA的并行性不易实施。本文提出的GASA将全局搜索的GA和局部搜索的SA相结合,是性能更好的优化方法。

一对个体进行交叉和变异操作后会有四个染色体:两个父代个体和两个子代个体。在传统的GA中,父代个体会被它们的子代个体代替。但是在GASA中,组成下一代的两个染色体是从这四个染色体中选择出来的。选择的标准是它们的适应度值。适应度值较高的染色体保留到下一代的概率较大;适应度值较小的个体不一定被抛弃,利用作为局部选择策略的模拟退火算法进行概率性的选择,该概率与当前的控制温度有关。该选择过程涉及四个参数,他们是fbest、fworst、fi和Tt。其中fbest是父代个体中适应度值最好的个体,fworst是父代个体中适应度值最差的个体,fi是子代个体的适应度值,Tt是控制温度。在每个温度Tt,试验染色体的适应度函数值fi(i=1,2)与fworst进行比较。如果下面的条件满足,染色体i就被接受。

min[1,exp(fi-fworst)/Tt]>r (2)

其中,r是介于0到1之间的随机数。如果染色体i被接受,则最坏和最好染色体将会被更新。

开始时,GASA的变异概率Pm被设置成一个较大的数值,并用SA对其进行调整。每10代以后,Pm被更新为α*Pm,直至Pm达到一个特定值,其中α是SA的降温速率。因此,在初始化阶段,如果SA的降温机制操作正确的话,初始化的高温可以确保父代个体能够被子代个体代替,不管子代个体是不是更适合。更重要的是,初始的高变异率可以改进种群的多样性,从而避免传统GA早熟收敛的问题。另一方面,在后期,变异概率和温度逐渐变小,因此子代替换更适合父代的可能性大大降低。这种方式可以使当前最好的个体始终进入下一代种群。由于变异概率的减小,在最后的种群中移除有用个体的可能性就减少。

算法1 GASA的伪代码,其中P(t)是第t代种群,Tt是控制温度,n是染色体的长度。

1. t=0

2. 初始化种群P(t)和温度Tt

3. 评价种群P(t)

4. while(终止条件不满足)do

5. t=t+1

6. 从P(t-1)选择P(t)

7. 重复

8. 选择两个未用过的个体P1,P2

9. 交叉和变异,产生两个子个体C1和C2

10. 评价C1和C2

11. for i=1 to 2 do

12. if min[1,exp(fi-fworst)/Tt]>random(0,1) then

13. 接受Ci并且替换相应的父代个体

14. 更新父代个体中的最优个体和最差个体

15. end if

16. end for

17. until所有被选择的个体完成繁殖

18. Tt+1=α*Tt

19. if mod(t,10)==0&&Pm>1/n then

20. Pm=α*Pm

21. end if

22. end while

GASA可以增加种群的多样性,加速种群的进化过程,并且可以避免传统GA陷入局部最优解。所以本文第一次提出利用GASA作为DV-Hop的后期优化。

2.2 定位问题描述

假设网络中含有M个锚节点,N个未知节点。使用向量θ=[z1,z2,…,zM+N]代表传感器节点的初始位置,其中zi=[xi,yi]T。M个锚节点位于(x1,y1),(x2,y2),…,(xM,yM)。定位问题就是给定以上M个锚节点的位置,求解未知节点的位置θ=[θx,θy],其中θx=[xM+1,xM+2,...,xN],θy=[yM+1,yM+2,...,yN]。由于测距误差的存在,定位问题的实质用下面的公式定义如下:

$f_{i} (\hat{x}, \hat{y}) = d_{i} - \sqrt{(x_{i} - \hat{x})^{2} + (y_{i} - \hat{y})^{2}} (2)$

其中( $\hat{x}$ , $\hat{y}$ )是未知节点的估计位置,(xi,yi) (i=1,2,…,M)是第i个锚节点的实际位置,di 是第i个锚节点与未知节点的测量距离(本文中该测量值是由DV-Hop的测距阶段得到的), $\sqrt{(x_{i} - \hat{x})^{2} + (y_{i} - \hat{y})^{2}}$ 是第i个锚节点与该未知节点的估计距离。因此,fi( $\hat{x}$ , $\hat{y}$ )是未知节点到第i个锚节点的测量距离与估计距离的误差估计。定位问题的实质就是求解该定位误差的最小值。

2.3 基于遗传模拟退火算法的定位算法

(1) GASA的个体编码

针对WSN节点数目较多,计算量大,且二进制编码不能直接反映所求问题的结构特征,本文的定位算法采用实数编码,这便于与模拟退火算法的结合,并且可以改善算法的计算复杂度,提高运算效率。

(2) GASA的适应度函数

本文中,遗传模拟退火算法的适应度函数采用启发式方法,将其定义为:

$f i t n e s s (\hat{x}, \hat{y}) = \sum_{i = 1}^{Μ} α_{i}^{2} f_{i}^{2} (\hat{x}, \hat{y}) (3)$

式中,αi是反映未知节点与第i个锚节点之间距离测量值精度的权值,该权值与节点到锚节点的跳数成反比,该跳数是由DV-Hop的测距阶段得到的。当节点与锚节点的跳数值大时,就惩罚它们之间的距离测量值。未知节点的估计位置是通过最小化(3)式中给出的适应度函数取得的。

(3) 遗传算子设计

遗传算子主要包括选择、交叉和变异。本文中,选择采用轮盘赌算子和最优保存策略相结合。交叉采用算术交叉。变异采用离散单点变异。

(4) GASA定位算法的终止条件

当迭代次数达到预定条件,或者种群的成熟度满足一定条件,停止迭代。

算法2 本文提出的定位算法伪代码如下:

% 初始化参数

1: noOfNodes,noOfAnchors,R,PZ,T

2. for all unknown nodes noOfNodes do

3. (xn,yn )=random( )

4. end for

%将锚节点均匀的置于边界处([14])

5. for all anchors noOfAnchors do

6. (xm,ym)=unibound()

7. end for

% 使用改进后的DV-hop算法Near-3 ([15])

8. Input:hop count (αi) to nearest three anchors

9. for i=1 to noOfNodes do

10. for Anchors j to three nearest Anchors of

$\begin{array}{l} i (Μ = 3) \\ 11 . f_{i} (\hat{x}, \hat{y}) = d_{i} - \sqrt{(x_{i} - \hat{x})^{2} + (y_{i} - \hat{y})^{2}} \end{array}$

12. $f i t n e s s (\hat{x}, \hat{y}) = \sum_{i = 1}^{Μ} α_{i}^{2} f_{i}^{2} (\hat{x}, \hat{y})$

$13 . [\hat{x}, \hat{y}] = \arg \min (f i t n e s s_{i} (\hat{x}, \hat{y})) %$ GASA algorithm

14. end for

15. end for

上述代码中,PZ是GA的种群大小,T是SA的初始温度,noOfNodes是未知节点的个数,noOfAnchors是锚节点的个数,R是节点的无线射程距离。

3 仿真结果

为了评价GASA-Hop定位算法的性能,本文将此算法与其他几个与之相关的算法用Matlab仿真进行了比较。仿真中,将未知节点随机部署到一个100×100的规则正方形区域内。根据文献[14],定位算法中将锚节点均匀放置于区域的边界比将其随机布置性能要好。因此,本文将锚节点均匀布置于规则正方形的边界处。无线射程R设为10。定位中最主要的评价标准是平均定位误差,为了便于广泛应用,将此误差进行规范化处理,即将其除以R。因此,平均定位误差可以定义为:

$e r r = \frac{100}{Ν \times R} \sum_{i = 1}^{Ν} \sqrt{(x_{i} - \hat{x}_{i})^{2} + (y_{i} - \hat{y}_{i})^{2}} % (4)$

其中,N是未知节点的个数,( $\hat{x}$ i, $\hat{y}$ i)是未知节点i的估计位置,(xi,yi) (i=1,2,…,M)是未知节点的实际位置,R是节点的无线射频距离。

将基于GASA的定位算法与基于GA、SA的定位算法等分别进行了仿真比较,仿真结果如下所示。通过改变未知节点总数、锚节点所占比率和节点无线射程R来比较各个定位算法的定位误差。

(1) 将一定数量的未知节点随机布置在仿真区域内,12个锚节点均匀地布置于网络的边界。由图1可看出,当增大未知节点个数的时候,三者的平均定位误差都会减小。这是由于当未知节点增多时,网络的连通度增大,这就使跳段距离估计方法更精确。因此,平均定位误差减小。但是,在相同条件下GASA-Hop性能更好。

(2) 将200个未知节点随机布置在仿真区域中,通过改变锚节点所占的比率来比较这几个定位算法的性能。由图2可知,当锚节点比率增加的时候,这几个算法的平均定位误差都会减小。但是,相同条件下,GASA-Hop性能更好。

(3) 将200个未知节点随机布置在仿真区域中,锚节点个数固定为16。通过改变节点的无线射程R来比较这几个定位算法的性能。由图3可知,当R增加的时候,这几个算法的平均定位误差都会减小。这是因为R增大导致了网络连通度的增大。但是,相同条件下,GASA-Hop性能更好。

4 结论与未来研究方向

目前,WSN的定位算法已经引起了许多研究者的兴趣。本文提出了一种新的WSN定位算法GASA-Hop。这种定位算法以GASA作为DV-Hop的后期优化,进一步提高DV-Hop的定位精度。其中,DV-Hop用来计算未知节点与锚节点的测量距离,GASA用来最小化与DV-Hop相关的适应度函数。仿真结果表明GASA可有效地应用于定位算法中。

这项工作为以后的研究开辟了方向。首先,现实中的网络很可能是不规则网络拓补,因此分析该算法在不规则网络中的性能很重要。其次,该算法是一个集中式算法,因此在可扩展性方面会受到限制。今后还要进一步研究将此算法改进为分布式算法。这在能量有限的传感器网络中尤为重要。最后,将GASA与其他定位算法结合也将是一个有趣的研究方向。

混合模拟退火遗传算法篇7

目前对于主题爬虫搜索策略的方法集中于基于内容评价的搜索策略, 基于链接结构评价的搜索策略, 基于未来回报价值评价的搜索策略及基于自动分类的搜索算法和启发式搜索算法。

基于内容评价的主题爬虫, 其中最具有代表性的是Best First Search, FishSearch, SharkSearch三种算法, 都是根据语义相似度的高低决定链接的访问顺序。这类方法起源于文本检索中对文本相似度的评价, 优点是计算简单。但是却忽略了web网页是一种半结构化文档, 包含了许多结构信息, 页面之间也不是单独存在的, 页面中的链接指示了他们之间的相互关系。

基于链接结构评价的搜索策略, 代表有Page Rank和Hits算法, 考虑了链接的结构和页面之间的引用关系, 但忽略了页面与主题的相关性, 容易出现“主题漂移”问题。

基于未来回报价值评价的搜索策略, 它是通过训练获得用于预测未来回报的经验信息, 使网络爬虫的搜索具有一定的“倾向性”。代表有基于巩固学习的方法和基于“语境图”的方法。由于需要对已有的信息进行训练或者借助搜索引擎构建语境图, 而这些初期的操作都是建立在已有的信息结构上的 (例如搜索引擎) , 而其本身就具有局限性, 影响算法的效果。基于自动分类的搜索算法。此算法是把网络爬虫看成Agent, 使其具有一定的自主性, 可以学习互联网上的知识并具备一定的经验信息, 然后可以计算网页是否属于所需要的主题类型, 从而得到正确的下载方向。

启发式搜索算法, 用在线获得的知识评价待访问链接的价值, 按照一定的原则选择价值最大的链接进行下一步的搜索, 找出到达目标节点的最佳路径, 删除不好的, 保留好的节点。但它是一种局部最优搜索算法, 搜索过程中会丢失掉许多相关的网页, 因此需根据实际的应用进行改进从而跳出局部最优点。鉴于此本文提出了下文的算法。

1 基于模拟退火遗传算法的主题搜索策略

1.1 遗传算法

遗传算法 (Genetic Algorithms, GA) 是一种模拟生物进化的智能优化算法, 根据生物优胜劣汰适者生存的原则, 借助交叉、变异、选择等操作, 使所要解决的问题在竞争中得以进化, 从而求得问题的最优解。遗传算法的特点是一种高效的全局搜索算法。

遗传算法的特性决定了其在网络爬虫搜索策略中应用的可能性。由通用搜索引擎产生一定数目的初始种群;选择由交叉概率所求个数的链接作为交叉的结果;通过变异操作, 引入一些目录型网页, 扩大搜索范围;然后通过选择操作, 从第一轮结果中选出相关度高的个体作为新一代的种子进入新一轮的遗传。具体实现如下:

1) 初始种群:在google或者百度进行主题和主题的一个同义词进行检索获得相关的URL, 然后各选取前n个作为初始化种子集S。对所选的2n个URL进行权威值 (Authority) 排名A, 再结合Alexa中文官方网查询这些URL对应网站的访问排名L, 得到他们的综合排名AL。AL=Am+Ln (其中m=0.8, n=0.2) , 选择排名靠前的80%的网页构成集合S11作为第一代遗传种群。

用HITS算法来计算Authority, 计算公式如下:

其中ap为网页p的Authority值, hp为p的Hub值。

2) 交叉:提取初始种群S11中的所有链接对应的网页中包含的链接URL, 用VSM算法计算锚文本及其上下文与主题的相关度, 提取相关度高的一部分作为交叉结果。

3) 变异:将初始化种群中的集合S中的2n个URL按照Hub和Alexa综合排名值从大到小排列 (仿照权威页和Alexa综合排名计算方法) , 组合成集合H, 然后通过变异操作根据设定的变异概率引入Hub网页, 适当地增加URL。设变异概率为Pm, 则从集合H中选取前H*Pm个URL作为变异结果, 记为集合S13。

至此, 交叉、变异操作都已完成所得到的S1=S11∪S12∪S13, 即为第一代遗传所得的种子群体。虽然此时爬虫已经抓取了许多与主题相关的网页但是由于互联网上的网页的错综复杂性, 也只是抓了一少部分而已。故, 还需要爬虫继续不断的循环地对互联网上的信息进行抓取工作。

4) 选择:在进入遗传算法第二代交叉变异之前, 还得对第一代遗传产生的种子群体S1进行选择操作, 以选出相关度高的, 适应性强的URL还产生新一代种子群体。

1.2 模拟退火算法 (SA)

模拟退火算法起源于统计物理学中对固体退火过程的模拟。它采用随机接受准则接收新解, 用一个称为冷却系数的参数控制算法进程, 这使得算法可能跳出局部最优解。SA一般采用Metropolis准则来确定由i'来替换i的概率:

在这里f (i) 为适应度值, 即主题相关度值。根据Metropolis准则, 当新解更忧时接受新解作为当前解, 否则以概率P接受其作为当前解。

该方式能够使得SA收敛于全局最优解, 具有良好的局部寻优能力, 可以很好的避免陷入局部最优解, 但SA收敛速度相当慢, 全局搜索能力不强, 影响网络爬虫的效率。

1.3 模拟退火遗传算法的搜索策略

GA全局搜索能力强, 而局部搜索能力较差;SA局部搜索能力强, 却对整个搜索空间的状况了解不多, 搜索效率不高。SA-GA将SA嵌入到自适应GA的循环体中, 互相取长补短, 形成一种新的优化算法。

将SA-GA算法应用于主题爬虫的搜索策略, 具体的实现步骤如下:

1) 设置初始参数, 主要包括遗传算法种群规模大小 (S1) 、最大进化代数 (Tmax) 、模拟退火算法的初始温度 (T0) 、温度下降系数0≤k≤1、最大内循环次数 (tmax) 。

2) 采用1.1 (1) 所述方法产生初始种群S1。

3) 对种群中各个个体适应度值即URL所对应的主题相关度进行计算, 并按照高低顺序排列。按照1.1 (1) 所述方式进行交叉, 变异操作产生新的个体, 即第一代遗传结果。

4) 根据选择操作, 产生新一代遗传种群S2。

5) 为了避免遗传算法的过早收敛, 用模拟退火机制对新一代种群中的个体即链接进行选择:设置内循环次数t初值为0, 从D中随机抽出一个链接i', 再从新一代种群S2中任选出一个链接i, 根据M etropolis准则来确定是否用i'来代替i。如果f (i') ≥f (i) , 则用i'来代替i;如果f (i') n (n为一随机数) , 则亦用i'来代替i。重复抽取直至t>tmax为止。

6) 如果当前进化代数T

2 结语

GA全局搜索能力强局部搜索能力差, SA局部搜索能力强但在后期收敛速度慢。将两种方法结合, 可以融合两者的优势克服单一算法的不足, 从而使主题爬虫搜索信息在内容和速度上都高于传统的方法及单个方法的应用。由于网络的复杂性及所用排名网站的局限性都会对结果产生影响, 所以GASA算法也存在一定的局限性, 需要作出进一步的努力和改进。

摘要：以何种策略访问网络, 提高搜索效率, 是近年来主题搜索引擎研究的主要问题之一。本文对主题爬虫常用搜索策略进行了简单分析, 提出了实用性较强的基于SAGA的主题爬虫搜索策略。

关键词：主题搜索策略,遗传算法,模拟退火算法,基于模拟退火遗传算法的搜索策略

参考文献

[1]Sutton R S, Barto A G.R einforcement Learning:an introduction[M].MA:MIT Press, 1998.

[2]Diligenti M, Coetzee F M, Lawrence S et al.Focused crawling using context graphs[C].In:Proc of the International Conference on Very Large Database (VLDB'00) , 2000.

[3]梁云静.基于遗传算法的主题爬虫搜索策略的研究[D].湖北工业大学, 2010.

[4]王海鹰, 魏颖.基于蚁群算法的多目标网页综合评价策略[J].计算机工程与应用, 2011.

[5]贺晟, 程家兴, 蔡欣宝.基于模拟退火算法的主题爬虫[J].计算机技术与发展, 2009.

混合模拟退火遗传算法篇8

遗传算法是仿真生物遗传学和自然选择机理, 通过人工方式所构造的搜索算法, 可用来求解优化问题。它的最大的特点是通用性, 可用来解决很多复杂问题, 只要将复杂问题转换为位串形式的编码, 然后对编码进行操作, 一代一代地繁衍, 优胜劣汰, 求得所求问题的最优解。

模拟退火算法也是一种启发式搜索算法, 其原理来源于固体退火的过程, 将固体加热熔化, 然后逐渐冷却, 在一个相当大的空间里搜索全局最优解。

遗传算法具有隐并行性, 算法效率高, 对全局的搜索掌控较好, 但局部搜索能力较弱, 但容易陷入局部最优解。模拟退火算法局部搜索能力较强, 但对全局的把握能力却较差。因此可以将两者相结合, 取长补短, 结合成新的算法———遗传模拟退火算法 (SGA) 。这一算法可以发挥遗传算法的全局掌控优势, 又能结合模拟退火算法的局部搜索较强的优势, 使得能较好较快地搜索到全局最优解[1]。

2 遗传模拟退火算法 (SGA)

遗传模拟退火算法首先产生初始种群, 然后对种群使用交叉算子和变异算子, 接着对种群使用模拟退火操作, 采用Metropolis接受准则的复制策略来产生下一代种群。这一接受准则使得种群中的最优个体进入下一代, 并在一定概率下接受不太好的解, 保证了种群的多样性, 有利于种群的繁衍, 找到全局最优解[2]。遗传模拟退火算法步骤如下:

(1) 初始化:设置种群大小s, 初始温度T, 进化代数t, Pb等。

(2) 初始化种群S (t) 。

(3) 计算种群个体S (t) 的适应度。

(4) 运用交叉算子产生种群S’ (t) 。

(5) 运用变异算子产生种群S” (t) 。

(6) 种群个体模拟退火产生种群S”’ (t) 。

(7) 计算群体S”’ (t) 的适应度。

(8) 选择操作产生下一代新的种群。

(9) 终止条件判断。如果满足终止条件, 则转向10, 算法结束;如果不满足终止条件, 则t←t+1, 转到步骤3。

终止条件为:大于预先设定的进化代数或连续若干代最优个体没有变化。

(10) 输出当前最优个体作为问题的最优解

3 GSA算法的编程实现及仿真实例

以推销员旅行问题 (TSP) 为例, 采用MATLAB语言来编程实现, 可以方便用户使用MATLAB强大的数值计算和符号计算功能, 并能进行图形输出。设有n个城市, 城市i和城市j之间的距离为d (i, j) , 且i, j=1, …, n。要求找到一条遍访每个城市一次而且恰好一次的旅行线路, 使其路径总长度最短。遗传模拟退火算法 (SGA) 设计如下:

(1) 编码。对TSP可以按一条回路城市的次序进行编码, 用w1, w2, …, wn表示, w1, w2, …, wn互不相同。初始群体的产生如下:

for i=1:pop Size

gena (i, :) =randperm (City Num) ;

end

(2) 交叉操作。交叉操作是从种群中取出要交配的一对个体, 即从染色体数组gena (pop Size, :) 中取出两个染色体gena (i, :) 和gena (j, :) ;在交叉概率的控制下, 两个个体在选定的位置交换染色体的内容。这里使用部分匹配法, 例如:对于gena (i, :) =[1 34 5 2 6], gena (j, :) =[1 5 6 3 4 2], 如随机选择两个交叉点, 第一个位置随机选在第三位, 第二个位置随机选在第四位, 则交叉后为gena (i, :) =[1 5 6 3 2 4], gena (j, :) =[1 3 4 5 6 2]。

(3) 变异操作。采用随机产生1和City Num之间的两相异整数k和m, 若k<m, 则将 (w1, w2, …, wk, wk+1, …, wm, …, wn) 变为 (w1, w2, …, wm, wm+1, …, wk, …, wn) 。若k>m, 则变为 (wm, wm-1, …, w1, wm+1, …, wk-1, wn, w, n-1, ..., wk) [3]。变异操作也是在gena (pop Size, :) 上进行的, 采用变异的概率Pb, 当rand<Pb时发生变异, 得到新的种群个体。

(4) 选择操作。选择操作就是根据适应度的值, 选择优良的个体, 繁殖到下一代。选择哪些个体遗传到下一代, 需要对染色体个体gena (pop Size, i) 进行解码, 通过解码公式计算目标问题的值, 再将所计算出的值转换为适应度fit (pop Size) 。根据适应度的大小来选择遗传的个体。TSP的目标是路径总长度最短, 所以适应度函数可设为:

(5) 模拟退火过程。设置初始温度T0、终止温度Tm和温度衰减系数。T0可根据具体问题来选择, 没有模拟退火算法要求那么高[4], 终止温度接近0, 温度的衰减函数T (t) =k·T (t-1) , 每一步以相同比率降温, 衰减量随算法进程递减, k选取0.6到0.9之间的值。

模拟退火算法首先随机扰动得到新个体, 计算gena SA () 的适应度与原来种群个体之间的差值Δ, 采用Metropolis接受准则来判断接受还是放弃。如果Δ<0, 则接受该个体, 如果Δ≥0, 则以概率p=exp (-Δ/θ) 接受该个体。

下面通过标准测试数据eil51, 来说明遗传模拟退火算法优于单一的遗传算法。城市坐标[37 52;49 49;52 64;20 26;40 30;21 47;17 63;31 62;52 33;51 21;42 41;31 32;5 25;12 42;36 16;5241;27 23;17 33;13 13;57 58;62 42;42 57;16 57;8 52;7 38;27 68;30 48;43 67;58 48;58 27;37 69;38 46;46 10;61 33;62 63;63 69;3222;45 35;59 15;5 6;10 17;21 10;5 64;30 15;39 10;32 39;25 32;2555;48 28;56 37;30 40];算法的相关参数为:群体规模pop Size为150, 交叉概率Pc为0.8, 变异概率为0.02, 起始温度T0为500, 温度衰减函数中k为0.8。种群进化到800代的路径图如下。

分别使用GA和GSA来求解上述51个城市的TSP问题, 各自独立测试20次, 将20次的结果求平均值和方差, 结果比较如下表:

4 结论

本文采用的遗传算法和模拟退火算法相结合的遗传模拟退火算法来解决TSP问题, 该算法结合了两者的优点, 既有较好的总体搜索能力, 又有较好的局部爬山能力, 算法的性能得到提高。最后, 使用MATLAB编程实现该算法解决TSP问题, 实例验证了该算法的有效性和实用性。

摘要：遗传算法和模拟退火算法均为启发式搜索算法, 结构互补, 可将两者结合, 使用遗传模拟退火算法来求解最优化问题。使用MATLAB语言来编程实现该算法, 将遗传模拟退火算法与MATLAB强大的数据处理相结合, 方便用户在MATLAB上建立模型, 解决最优化问题。最后给出一个实例, 运行结果证实了遗传模拟退火算法在求解最优化问题上优于单一的遗传算法。

关键词：遗传算法,遗传模拟退火算法,TSP,Matlab

参考文献

[1]武兆慧, 张桂娟, 刘希玉.基于模拟退火遗传算法的关联规则挖掘[J].计算机应用, 2005, 25 (5) :1010~1011.

[2]康立山.非数值并行算法[M].科学出版社, 2003.

[3]蔡自兴, 蒙祖强.人工智能基础[M].高等教育出版社, 2010.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【混合模拟退火遗传算法】相关文章：

遗传模拟退火算法08-27

混合自适应遗传算法08-12

混合遗传算法及应用09-03

用自适应多点变异混合遗传算法实现智能组卷09-11

浅谈雨课堂对《模拟电子技术》混合式教学的启示09-10