遗传模拟退火（精选9篇）
遗传模拟退火 篇1
1 引言
本文在分析遗传算法和模拟退火的基础之上求解TSP问题, 针对遗传算法的不足, 结合模拟退火思想对遗传算法进行改进, 并将传统遗传算法与改进后的遗传算法所得结果进行比较, 表明了改进后遗传算法在求解此问题上的优越性, 取得了理想的试验结果。
2 遗传算法设计
遗传算法基本结构可概括为:1初始化种群;2对种群每个个体进行评估;3选择 (竞争生存机会) ;4变化 (重组、杂交与变异) ;5如不满足终止条件, 转2;否则结束[1,2]。
2.1 种群初始化
种群的规模选择应适当, 盲目的增大种群规模不能使算法得到改进, 反而大大增加了计算的开销。以20个城市为例, 种群初始化时, 先产生1, 2, ……, 20的一条规则路径, 然后在这条路径中随机选两个数, 将它们交换位置, 这样做若干次保证这条路变成了一条随机的路径。以这条随机路径为基础, 对一些随机的位, 做两两交换, 这样产生了一个个体;同样地产生种群里其它的个体[3,4]。
2.2 适应度函数与最优解的保存
用个体 (一条闭合路径) 的周长 (平面欧氏距离) 作为该个体的适应值。求得种群中所有个体的适应值后, 将适应值最大的个体保存起来, 到演化完毕时, 这个个体就是最后要求的解。
2.3 选择 (竞争) 策略
这里采用了轮盘选择策略。可以采用一个映射对适应值进行规范:
其中, F是适应度函数求出的适应值, Fmax为其中的最大值, F′是规范后的适应值。然后, 用F′来构造轮盘, 概率为:
表示了某一个体被选入下一代的概率。
2.4 杂交算子
在遗传算法里面, 可以用单体杂交, 双体杂交和多体杂交。但要保证种群的规模不变, 须保证n个个体杂交产生n个后代, 后代产生之后要代替其父体的位置[5,6]。
2.5 变异算子
变异可以看作是外界对种群的影响。变异是为了引入新的因素, 希望个体在外界的作用下, 能够自我优化, 产生好的基因[7,8]。变异算子采用了简单的倒序变换, 以8个城市为例, 随机的产生两个小于8的整数, 对某个个体进行分割, 将分割段倒序并放回原来的位置即可。
3 模拟退火算法设计
在演化的前期, 种群的质量较差, 因此给变异产生的后代较多的生存机会, 而随着演化向末期推进, 将他们的生存机会减到平衡状态。针对传统模拟退火算法存在的问题, 主要在新解的生成, 当前解的改良方面进行改进。
3.1 新解的生成
改进模拟退火算法中新解的生成是通过在闭合的路径中随机选择3条边进行断裂, 这样将生成3个路径段, 对这3个路径段进行倒置操作, 在满足路径原则的前提条件下, 对以上6个路径段进行重新组
F福建电脑UJIAN COMPUTER
合, 选择最优的一条作为新解。以9个城市为例: (1, 2, 3, 4, 5, 6, 7, 8, 9) 假设断点为1, 4, 7 (8, 9, 1, 丨2, 3, 4, 丨5, 6, 7) ——— (1) (1, 9, 8, 丨4, 3, 2, 丨7, 6, 5) ——— (2) 将 (1) 与 (2) 重新组合得到新路径 (1) (8, 9, 1, 丨2, 3, 4.丨7, 6, 5) 得到新路径 (2) (8, 9, 1, 丨4, 3, 2.丨5, 6, 7) 得到新路径 (3) (8, 9, 1, 丨2, 3, 4.丨5, 6, 7) 得到新路径 (4) (1, 9, 8, 丨4, 3, 2.丨5, 6, 7) 得到新路径 (5) (1, 9, 8, 丨2, 3, 4.丨7, 6, 5) 得到新路径 (6) (1, 9, 8, 丨2, 3, 4.丨5, 6, 7)
在新产生的6个新路径中选择最优路径作为新路径。
3.2 解的改良
改良过程采用的是局部最优化和单点最优位置两种方法。局部最优化是在当前解中随机选取小段路径, 对该小段路径进行重新排列组合。选择最优局部路径代替原来的路径段。单点最优位置就是, 在当前染色体中对每一个基因在染色体中的位置进行遍历, 选择最佳位置。
3.3 总体算法的流程
算法流程如图1所示。
4 实验分析
为了检验算法的性能, 本文做了两组实验, 第一组采用kroc100进行验证, 第二组采用了tsp255进行验证。算法的路径图如图2-3所示。
从实验的效果图来看, 改进后的算法针对TSP问题求解具有较好的效果。通过表1可以看出改进后算法求得的最优解基本接近当前的最优解, 可见算法具有较好的稳定性。
5 结语
本文提出了改进的模拟退火和遗传算法求解TSP问题。设计的改进算法在初始解的选择、新解的生成、当前解的改良及交叉方式等方面提出了新的观点, 提高了最优解的搜索速度。
摘要：本文提出了一个用于求解TSP问题的改进模拟退火的遗传算法, 利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。用100个城市和255个城市的TSP问题验证算法, 实验测试的结果表明该方法具有较好的收敛效果和可靠的稳定性。
关键词：遗传算法,旅行商问题,模拟退火算法
参考文献
[1]张盛意.基于改进模拟退火的遗传算法求解背包问题[J].微电子学与计算机, 2011, 28 (2)
[2]郭晓利.电网知识协同发现策略研究[J].东北电力大学学报, 2014, 34 (1) :94-98
[3]王建忠.TSP问题的一种快速求解算法[J].微电子学与计算机, 2011, 28 (1)
[4]曲朝阳.基于本体语言OWL的电网领域知识表示方法[J].东北电力大学学报, 2012, 32 (4) :30-34
[5]孟凡奇.不依赖字符集的数据库非标字段检测方法[J].东北电力大学学报, 2012, 32 (4) :4-7
[6]曲朝阳.基于双层次分析的智能变电站数据分类方法[J].东北电力大学学报, 2014, 34 (2) :61-65
[7]曲楠.XEN虚拟机动态增量迁移的设计与实现[J].东北电力大学学报, 2014, 34 (3)
[8]滕志军.基于矩阵旋转的改进STBC码[J].东北电力大学学报, 2012, 32 (4)
遗传模拟退火 篇2
线性最小二乘估计在对非线性函数进行线性近似的.过程中会产生模型误差,而一些非线性参数估计方法可能因为函数复杂而难以求导,法方程系数矩阵秩亏或呈病态矩阵时难以求解,非线性迭代解法有时对初始值的选择存在依赖性,不恰当的初始值会导致迭代无法收敛.针对这些问题,引入了模拟退火算法,介绍了该算法的基本原理、计算步骤和收敛性,并以3个控制网平差应用为例,说明该算法具有无需求导求逆,简洁实用,易于编程等优势,并能实现全局优化,获得高精度的平差结果.
作 者：邓兴升 王新洲 DENG Xing-sheng WANG Xin-zhou 作者单位：邓兴升,DENG Xing-sheng(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079)
王新洲,WANG Xin-zhou(武汉大学,测绘学院,湖北,武汉,430079;武汉大学,灾害监测与防治研究中心,湖北,武汉,430079;山东科技大学,地球信息科学与工程学院,山东,青岛,266510)
基于模拟退火算法的中继器分布 篇3
关键词中继器；模拟退火算法；MATLAB
中图分类号TM文献标识码A文章编号1673-9671-(2011)051-0114-02
在当今的信息时代，中继器无疑在无线传播领域扮演着举足轻重的角色。然而，中继器自身仍然存在着一些局限，比如欲使两中继器相互通信，必须使它们位于对方的覆盖范围之内，这样才能实现更大范围的远距通信。鉴于此，在研究中继器的分布时就很有必要需找一种优化的分布方式，以期达到使用最少的中继器覆盖该地区所有用户的目的。
1中继器
中继器（Repeater）属于同频放大设备，是指在无线通信传输过程中起到信号增强的一种无线电发射中转设备。中继器的基本功能就是一个射频信号功率增强器。中继器在下行链路中，由施主天线现有的覆盖区域中拾取信号，通过带通滤波器对带通外的信号进行极好的隔离，将滤波的信号经功放放大后再次发射到待覆盖区域。在上行链接路径中，覆盖区域内的移动台手机的信号以同样的工作方式由上行放大链路处理后发射到相应基站，从而达到基地站与手机的信号传递。
但是中继器所服务的移动台（即用户）有一定的数量限制。一旦超过该额定数量，超过的用户将不能实现传输信号的放大，从而不能实现所有用户的远距通信。同时，中继器的额定功率还决定了中继器的覆盖范围，其他的中继器必须在某一中继器的覆盖范围内才能实现放大信号的传递，进而通过相邻中继器的信号传递实现远距通信。
2模拟退火算法
模拟退火算法（Simulate Anneal Algorithm）提出于本世纪80年代初，其思想源于固体退火过程：将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
2.1算法原理
模拟退火算法的基本思想是从一个给定解开始，从邻域中随机产生另一个解，接受Metropolis准则允许目标函数在有限范围内变坏，它由一个控制参数t决定，其作用类似于物理过程中的温度T，对于控制参数的每一取值，算法持续进行“产生——判断——接受或舍去”的迭代过程，对应着固体在某一恒定温度下的趋于热平衡的过程。当控制参数逐渐减小并趋于0时，系统越来越趋于平衡态，最后系统状态对应于优化问题的全局最优解，该过程也称为冷却过程。由于固体退火必须缓慢降温才能使固体在每一温度下都达到热平衡，最终趋于平衡状态，因此控制参数t必须经过缓慢衰减，才能确保模拟退火算法最终能够得到该优化问题的整体最优解。
2.2算法具体步骤
1）给定模型每一个参数变化范围，在这个范围内随机选择一个初始模型m0，并计算相应的目标函数值E(m0)。
2）对当前模型进行扰动产生一个新模型m，计算相应的目标函数值E(m)，得到ΔE=E(m)-E(m0)。
3）若ΔE<0，则新模型被接受；若ΔE>0，则新模型m按概率P=exp(-ΔE/T )进行接受，T为温度。当模型被接受时，置m0=m，E(m0)=E(m)。
4）在温度T下，重复一定次数的扰动和接受过程， 即重复步骤2）、3）。
5）缓慢降低温度T。
6）重复步骤2）、5），直至收敛条件满足为止。
算法的实质分两次循环，随机扰动产生新模型并计算目标函数值（或称能量）的变化，决定是否被接受。由于算法初始温度设计在高温条件，这使得E增大的模型可能被接受， 因而能舍去局部极小值，通过缓慢地降低温度，算法最终能收敛到全局最优点。
应当指出的是，模拟退火算法是一种处理全局最优解的启发式算法。特别是在计算机计算速度不断提高的条件下，具有不可低估的发展潜力和重要的研究价值。
3仿真过程
在此，本文以半径为64km的圆形区域、其间随机分布200位用户为例，说明模拟退火算法在中继器优化分布问题上的应用。同时由于中继器规格不同，其覆盖范围、额定功率都不尽相同。在此，仅以覆盖范围为20km、额定用户为10位的中继器为例予以分析说明。
3.1仿真思想
宏观上来说，本文的程序仿真思想借鉴了Dijkstra最短路径算法的核心。
首先，随机产生第一个中继器的位置，之后进行模拟退火算法找到最优解；由于要实现中继器之间的顺利通信，因此将第一个中继器的覆盖范围作为下一个中继器位置的产生范围，在此范围内再进行模拟退火算法，确定第二个中继器位置之后，再将前两个中继器覆盖范围视作一个整体以作为第三个中继器位置的产生范围，以此方法迭代下去……本文称此思想为“辐射式思想”，即，以之前确定位置的中继器的覆盖范围为源，在此基础上向外“辐射”，通过模拟退火算法的迭代找到最优解，进而得到在整个区域内使用最少中继器覆盖所有用户的目标。
3.2模拟退火算法流程
1）随机产生一个中继器位置(x1，y1)，并记(xbest，ybest)=(x1，y1)并计算目标函数值max(xbest，ybest)，此目标函数值max(x，y)即为该中继器半径范围内所覆盖的用户数量；
2）设置初始温度，k为当前确定位置的中
继器个数，Tusers为当前所有中继器覆盖用户数之和，一旦该数量达到总用户数200，则以下循环停止；
3）do while Tusers!=200
①for j=1~n；尽可能多的循环次数以确保能够找到全局最优解；
②对当前最优解按照某一邻域函数，产生一新的解(xnew，ynew)。计算新的目标函数值max(xnew，ynew)，并计算目标函数值的增量Δmax=max(xnew，ynew)-(xbest-ybest)。
③如果Δmax<0，则(xbest，ybest)=(xnew，ynew)；
④如果Δmax>0，则P=exp(-Δmax/users(k))；
a）如果c = random[0，1] < p，则(xbest，ybest)=(xnew，ynew)；
b）否则不做改变；
⑤end for；
⑥确定当前最优点(xbest，ybest)，本次计算结束；
4）k= k＋ 1；
5）end do；
6）找到该区域中继器的最优分布，算法结束。
3.3仿真结果
下图即为程序运行中（图1、图2）和运行结束后（图3）中继器的分布情况。图中，“△”为已确定位置的中继器，“○”为当前正在执行模拟退火算法的中继器，整个圆形区域内部的“*”为区域内随机分布的用户。
4结果讨论
在实际运行过程中，由于笔者计算机配置有限，将每个中继器寻找最优分布点的迭代次数设定为20次。理论上迭代次数越大，得到的分布点越优化、越能满足实际优化问题的要求。此外，由于仿真过程中计算量过大，本文将时间间隔定为1s，这样势必增加了模拟的时间，如何提高算法的运行效率还是值得进一步研究的。同时需要指出的是，上述过程是动态仿真过程，对于同样的用户分布来说，执行仿真的时候有可能出现不同的中继器分布情况。本文所提供的方法也可以运用于比如搜索问题等类似的最优化问题的求解上。
参考文献
[1]Al Duncan- VE3RRD.Amateur Radio FM Repeater Basics,Updated October,2007.
[2]谢云.模拟退火算法的原理及实现[J].高等学校计算数学报,1999,3:212.
[3]许小勇.模拟退火算法在指数曲线拟合中的应用[J].四川工程职业技术学院学报,2006,4:35.
[4]项宝卫,余雪芬,骆兆文.模拟退火算法在优化中的研究进展[J].台州学院学报,2005,(27)6:6.
[5]严蔚敏,吴伟民.数据结构(第1版).北京:清华大学出版社,1997,
遗传模拟退火 篇4
遗传算法(GA)与模拟退火法(SAA)是近年来优化领域的研究热点,与传统的优化方法相比,具有算法简单、使用灵活、寻优效高、算法“健壮”、适合并行计算、不需要梯度信息等优点,目前已在组合优化、管理决策、工程领域得到一些应用。鉴于这两种算法在寻优方面的优越性,特将其算法思想以及寻优特点作一归纳,使之在工程优化设计领域中能得到广泛应用。
1 两种算法的基本思想
1.1 遗传算法
遗传算法是根据达尔文的生物进化中的“优胜劣汰”原则建立的一种优化算法。20世纪60年代首先由美国Michigan大学的J. Holland教授提出。该算法模拟了自然界中生物自然选择、适者生存的进化过程,从而达到搜索最优解的目的,标准遗传算法主要由以下基本步骤组成:
a) 对设计向量编码:遗传算法不直接处理解空间数据,需通过编码将解空间中的设计向量转化为遗传空间中的基因串,通过遗传算法改变基因串的结构以达到搜索解空间最优解的目的,常用的编码形式为二进制编码、浮点编码等。
b) 生成初始母体群:遗传算法是群体操作算法,随机生成n个基因串(每个基因串对应解空间的一个设计向量),以此作为迭代搜索的初始点。
c) 适应度计算:适应度是反应基因串对环境的适应能力,遗传算法一般不需要其他信息,仅通过适应度来评价群体中的两个体的优劣,适应度越大,个体的遗传基因越优,反之遣传基因较劣。
d) 对群体基因串进行遗传算子操作,产生新一代群体基因串遗传算法,主要有选择、交叉、变异三种算子组成,选择的目的是从群体基因串中选择遗传基因优良的基因串作为遗传父代,交叉运算的目的是产生子代基因串,变异的目的是为产生新的基因串提供机会。
通过上述三种遗传运算操作形成新一代(子代)群体基因串,如此反复迭代遗传直到搜索到最优解。
1.2 模拟退火法
模拟退火法是模拟固体退火过程而设计的一种寻优算法。20世纪80年代首先由Kirkpatrilk等人提出,在模拟退火法中,解向量X和目标函数F(X)分别对应退火过程一个固体微观状态i和相应的能量E,随着算法进程递减其值的控制参数C对应于退火过程的温度T,在某一控制参数C值下,算法所进行的“产生新解→判断→接受或放弃”的迭代过程,相对应固体在某一恒温下趋于热平衡的过程。通过若干次迭代变换后算法求出的最优解x*和目标函数F(X*)分别对应固体的基态和最小能量。
模拟退火法的求解步骤如下:1) 设定初始解X=X0和初始控制参数C=Co;2) 随机产生新X′;3) 计算转移概率p;
P(X′=>X)=
undefined
4) 判断接受或放弃新解X′,当p(X′=>X)>r,接受X′为新解,否则,放弃为X′新解;5) 判断终止条件,满足条件则停止迭代,否则转向2)。
2 两种算法的寻优能力比较
2.1 测试函数算例
为了考察两种算法的寻优能力,曾经测试了几个具有典型“欺骗”性质的函数的优化,这种具有“欺骗”性的函数全局最优点往往是孤立的并被全局最优点包围,或是多峰值函数。
f1=100(x2-xundefined)2+(x2-1)2,Ω=(-200,200)2;
f2=undefined100(x1+1-xundefined)2+(x1-1)2,Ω=(-200,200)1;
f3=xundefined+2xundefined-0.3cos3πx1-0.4cos4πx2+0.7,Ω=(-100,200)2。
f1为二维Rosenbrock函数,最小值为0,全局最优点(1,1),是一个具有曲型“狭长深谷”的函数;f2为四维Rosenbrock函数,最小值为0,全局最优点为(1,1,1,1);f3为一个多峰值函数。上述函数用传统方法很难搜索到全局最优点,具体测试结果见表1:
遗传算法与模拟退火法均为随机搜索算法,与传统优化方法相比,两种算法在寻优方面各有特点。
2.2 遗传算法的寻优特点
a) 寻优过程不需梯梯信息,特别适用复杂目标函数的优化;
b) 不是从一个单点而是从多点(群体)开始搜索;
c) 利用概率转移规则,而非确定规则;
d) 由于引入了交叉与变异算子,使遗传算法搜索到全局最优解的能力增强,理论上遗传算法搜索到全局最优的概率为1;
e) 遗传算法对初始解没有苛刻要求是一种“健壮”的算法;
f) 由于遗传算法是在遗传空间中通过操作n个基因编码串进行寻优,而n个基因串能反映O(n3)阶个基因串模式,因而遗传算法隐含并行性,这一优点特别适用于并行计算机处理,除上述优点外,遗传算法也有其缺陷,其中最突出的是“早熟现象”特别是对多峰值目标函数的优化中表现的较明显,所谓“早熟现象”是过早收剑到某一局部最优解,目前国内外学者也提出了一些解决方法,如引入共享函数、学编码等。
2.3 遗传算法的寻优算例
例:已知20t/25m门座起重机变幅齿条最大切向力F1=344kN
常规计算过程如下:
a) 初选小齿轮模数m=25,Z=14,材料40Cr,变位系数ξ=0.177,根据齿变典强度条件,求得齿宽b=200mm。
选取齿轮轴材料45号钢,根据结构和齿宽b定轮轴支承情况和支承距离L,进行齿轮轴弯曲疲劳强度校核得到轴直径d=168mm。
b) 校核齿体强度:根据齿轮计算得齿根圆直径df=296.3mm,而齿体强度要求齿根圆直径不小于302.4mm。上述计算结果不满足要求,这时必须凭经验调整有关几何尺寸参数再进行齿轮、齿轮轴和齿体的强度校核直到满足为止。而通过遗传算法可得到下面一组解(见表2),其中第一组解为全局最优解,其他若干组次优解,设计人员可以根据实际情况从中任选一组解。必定优于常规计算所得的结果。
2.4 模拟退火算法的特点
a) 寻优过程不需要梯度信息,适合复杂目标函数优化;
b) 算法简单,易程序化;
c) 与局部搜索法相比,模拟退火法能以一定概率接受恶化解从而扩大了搜索空间,使迭代过程易跳出局部最优“陷井”,增大了搜索到全局最优解的机会;
d) 最终优化解的质量不依赖初始解,因而模拟退火法是一种“健壮”的算法;
e) 理论上模拟退火法搜索到全局最优解的概率为1;
f) 如冷却进度表选取合理,模拟退火法能在较短的CPU时间内获得者高质量的全局最优解。
由于模拟退火法是对固体退火过程的简单模拟,因而不可避免的存在一些不足,主要表现为合理选取初始温度T较为困难:1) 随着控制参数T的逐渐衰减,接受恶化解的概率逐渐减小,从而使算法停留在局部最优的“陷井”中无法跳出;2) 目前,已有学者提出了一些改进的模拟退火法来解决上述问题,如加温退火法、记忆退火法、回火退火法等,均取得了较好的效果。
2.5 模拟退火算法的寻优算例
算例:16t带载变幅直臂架起重机。有关技术性能参数如表3:起重质量16t,最大幅度Rmax=16m,最小幅度Rmin=7m,臂架端点至臂架铰点的垂直距离Hmin=14m。臂架自重Gb=5×104kN,臂架重心位置l1=8m。
计算结果列于表3:
根据计算结果绘制了落差曲线图(图1)和不平衡力矩曲线图(图2)。
3 总结
遗传算法与模拟退火法在优化领域有着非常广泛的应用前景,目前对这两种算法的数学理论、性能分析、并行性计算,在神经网络中的应用等方面均是国内外学者的研究热点,本文的目的就是希望通过对这两种算法的寻优特点进行一些归纳,使之能更好的用于工程优化设计领域,以提供有价值的帮助。
摘要：介绍了遗传算法与模拟退火算法的基本思想,综述归纳了两种算法的寻优特点,使之在工程优化设计领域得到更广泛的应用。
关键词：遗传算法,模拟退火法,优化设计
参考文献
[1]刘勇.非数值并行算法——遗传算法[M].北京:科学出版社,1994.
[2]康立山.非数值并行算法——模拟退火法[M].北京:科技出版社,1995.
[3]柳卫东,等.遗传算法优能力研究[J].武汉交通科技大学学报,1998.
[4]孙艳丰,王众托.遗传算法在优化问题中的应用进展[J].控制与决策,1996(4).
[5]vas Lasrhovon P J M,Asrts E H L.Simulated annealing[M].Theory and Applications.D Reidel,1997.
[6]胡琉达.实用多目标最优化[M].上海:上海科学技术出版社,1990.
[7]刘惟信.机械最优化设计[M].北京:清华大学出版社,1994.
[8]van laarhoven P J M,Aarts E H L:Simulated annealing[M].Theory Applitions D Reidel,1947.
遗传模拟退火 篇5
网络重构是配网自动化的一个重要组成部分,其实质是在满足系统电压、电流、电源容量等约束前提下,通过调整网络中分段开关和联络开关的状态组合来寻找一条最优的供电路径,以达到降低网损、消除过载、改善电压分布、提高供电可靠性的目的。
配电网络重构是一个大规模非线性组合优化问题。从数学角度分析,配电网络重构是一个多约束、高度非线性的NP综合优化问题。目前,解决网络重构算法有:各类改进遗传算法[1,2,3,4]、粒子群算法[5,6,7]、模拟植物生长算法[8]、模拟退火算法[9]、混合算法[10]等。由于单一算法各自具有天生的缺陷,使得不同算法之间的优化组合成为了探寻最优算法的一种方向。
本文将食物链生态进化算法(EEAFC)和模拟退火算法(SA)两种思想有机结合,提出链式遗传—模拟退火混合算法(CAGSAH)。该算法将环境压力映射为待优化问题,进化链(食物链)上每条染色体(个体)则对应于问题的一个候选解。进化链上采用不同进化机制的多种群协同搜索,而种群间则采用横向进化策略,使低级模式种群沿进化链逐步向高级模式迁移,实现算法从一个局部最优状态向更高一级的局部最优状态定向移动。通过模拟退火Metropolis取舍准则来控制算法搜索最优方案的进程,使算法以更大的概率收敛于全局最优解。最后,将所提方法应用于配电网络重构中,并通过与模糊自适应遗传算法进行比较,以验证本文所提算法的优越性。
1 数学模型
以系统网络有功损耗最小为目标函数的配电网络重构数学模型可表示如下:
(1)目标函数:
式(1)中,Ri为支路i的阻抗;ki为开关i的状态,0表示断开,1表示闭合;Ui是支路i的电压;Pi、Qi是支路i末端的有功和无功。
(2)约束条件:
式(2)中,Vi,min、Vi,max是节点i的电压上限值和下限值;Si、Si,max是支路i流过的功率计算值及其最大允许值;St、St,max是第i条线路提供的功率及其最大容许值。除上述几个约束条件外还应包括重构后的配电网络必须是连通和网络拓朴必须呈辐射形结构的约束。所有上述约束条件通过惩罚函数的形式加入到目标函数中。
适应度函数用以评价食物链上个体适应性能的指标,由上式的目标函数为最小化问题,根据目标函数构造以下适应度函数,即:
式(3)中,ω适应度函数值调节系数,它的引入是使适应度函数值处于正常大小,避免计算机处理过大或过小数据时出现数值问题。
2 链式遗传——模拟退火混合算法
本文所提算法充分发挥食物链生态进化算法高效全局搜索性能和模拟退火的局部细化搜索能力,为解决优化问题提供可行的新思路。
基于链式遗传—模拟退火混合算法的电网扩展规划包含两个循环过程,其一为EEAFC主优化过程,其功能是提高个体进化的多层次性;其二是SA子优化过程,主要是提高个体多样性,解决局部收敛问题。链式遗传—模拟退火混合算法计算流程图如图一所示:
2.1 食物链编码及初始化
根据优化问题的决策变量,模拟生物在生态环境中的能量传递方式,构造搜索空间为NPOP×L的进化初始食物链,食物链上种群个体适应性能从高到低逐级递减。NPOP×L为食物链种群规模,为提高食物链上种群进化层次性,预防“未成熟收敛”,将食物链划分为高级(M3)、中级(M2)、低级(M1)三级子种群,即NPOP=M1+M2+M3,L为决策变量维数。Ag=[0,0…0]为决策变量的下限取值,Bg=[b1,b2,…,bg,…,bL]为决策变量的上限取值,各级种群个体的决策变量M(i,k,g)∈Z且满足Ag≤M(i,k,g)≤Bg,食物链上各级种群个体序号k=1,2…Mi,个体基因位g=1,2…L。
食物链上高、中、低三级子种群规模满足:
式(4)中,∂i+1i食物链上种群Mi向种群Mi+1的能量传递效率,一般取0.005~0.5。
2.2 纵向进化搜索机制
食物链进化算法为扩大解的搜索范围,各级种群引入遗传机制纵向进化,确保食物链上种群的多样性和新特性。基于低级种群到高级种群逐渐减少而种群的质量逐步提高特点,各级种群选用不同的遗传进化策略(交叉率Pc、变异率Pm不同)在解空间并行协同进化搜索,具体步骤为:
(1)实数交叉:按一定的交叉率Pc对随机选定参与交叉的一对染色体在[1,L-1]区间内随机确定交叉位进行一点交叉。
(2)实数变异:以一定的变异率Pm选定染色体变异位M(i,k,g),若M(i,k,g)=0,则取[0,n]范围随机整数变异,其中n为变异位所对应决策变量的取值上限;若M(i,k,g)>0,则该变异位值进行自减1操作。
为避免遗传算法选择算子造成适应性强的个体大量繁殖,使算法陷入局部最优现象,结合模拟退火算法的概率突跳性质的Metropolis准则邻域移动方法,对交叉、变异操作产生的新解实施概率性“双向”接收,以有效缓解食物链生态进化算法的选择压力,使得算法在优化后期具有较强的爬山性能,加快算法进化后期的全局收敛速度。
设P为当代进化前食物链,P'为当代进化后食物链,则进化前后个体目标函数适应度函数值的增量可表示为△Fn=F(P'n)-F(Pn),式中(n=1,2,…NPOP),p=exp(-△Fn/T),取当前温度T=αT,α为降温系数,一般取1/3<α<1/2。若满足min(1,p)>rand(0,1),则新个体P'n被接受;否则,新生个体P'n被父代种群中所对应个体Pn所取代。如此新解接受机制为全局范围搜索提供了理论保证:当T较大时,P较大,即接受“劣化”方案的概率较大,算法进行广域搜索;随温度的下降,接受劣解的概率逐渐减小,算法朝“优化”方向搜索,即转入局域细化搜索。
2.3 局部最优种群保留
局部最优种群产生的规则与进化成熟收敛的效率密切相关,为保持每一代出现的若干最优个体免遭破坏,高级种群实施“局部最优种群保存”策略。具体步骤为:选取食物链顶端与高级种群规模一致的若干个体作为“最优种群”暂存,当代纵向进化后的高级种群M'3i与进化前记忆的“最优种群”(即进化前高级种群M3)个体逐一进行适应性能比较。若F[M'(3,k)]
2.4 横向进化策略
根据进化情况,引入环境“弱肉强食”的生存压力,高一级种群对低一级种群相应个体模式采取横向进化策略,实现低一级种群品质向更高一级种群迁移。横向进化策略为:若调整度T(M(i,k),M(i+1,k))<1,则高一级种群个体M(i+1,k)将取代低一级种群个体M(i,k),低一级种群引入高品质个体有利于促进低级种群“寻优”进化,加快进化速度。横向进化策略避免了单种群进化陷入未成熟收敛的缺陷。调整度定义详见文献[10]。
2.5 收敛判据
智能算法停止的条件一般有:(1)完成预先给定的进化代数作为进化迭代结束条件;(2)种群平均适应度在连续若干代没有改进作为进化迭代结束条件[11]。这2种准则不适合作为链式遗传—模拟退火混合算法的收敛判据。本文选取食物链进化在一定的迭代次数内搜索不到比当前已寻优到的最小局部最优解(目标函数值最小)更优的解时,则将搜索到的最小局部最优解(目标函数值最小)作为全局最优解,认为算法全局成熟收敛,算法停止迭代计算。
3 应用算例分析
以IEEE16节点系统为算例验证所提方法的有效性[9]。该系统总负荷为28.7MW+j17.3Mvar,具有16条支路和3个联络开关,分别采用本文所提的混合算法CAGSAH对系统进行网络重构,重构结果如表一所示,迭代次数和寻优效果如图二所示。由图二可知,链式遗传—模拟退火混合算法通过概率突调机制改善了算法收敛性能,只需迭代到13代就可全局收敛,显示了链式遗传—模拟退火混合算法较食物链生态进化算法具有更好的优化性能,而且用混合算法所得重构结果网损比文献[3]要小。
4 结束语
提出了一种链式遗传——模拟退火混合算法。该法采用基于食物链多种群并存竞争的协同进化机理进行寻优,并结合模拟退火算法的概率性突调搜索机制,既提高了搜索的效率,又避免了陷入局部最优解的问题。将所提方法应用到IEEE16节点系统上,并通过与文献[3]中的方法进行比较,结果表明所提方法不仅可以有效降低网损,而且迭代次数也大大减少。
摘要：以网损最小为目标函数,节点电压、网络辐射性和电源容量的限制为约束条件,建立了配电网络重构优化数学模型。针对各种单一算法的局限性,提出了一种基于链式遗传-模拟退火算法。该算法将环境压力映射为待优化问题,进化链(食物链)上每条染色体(个体)则对应问题的一个候选解,通过模拟退火Metropolis取舍准则控制算法搜索最优方案的进程。最后,在IEEE16节点系统上验证了所提方法的有效性。
关键词：链式遗传算法,模拟退火算法,网络重构,链式遗传—模拟退火混合算法,配电网络
参考文献
[1]]邹风桥.基于免疫克隆遗传算法的配电网络重构研究[D].广州:广东工业大学,2004.
[2]杨滨,刘东,等.网络重构中基于配电网拓扑特征的改进遗传算法[J].华东电力,2009,(5).
[3]张忠城,王淳.模糊自适应遗传算法在配电网重构中的应用研究[J].江西电力,2006,(2).
[4]刘莉,陈学允.基于模糊自适应遗传算法的配电网络重构[J].中国电机工程学报,2000,20(2):66-69.
[5]王韶,马晶晶,等.配电网重构的蜜蜂进化型遗传算法[J].电力系统保护与控制,2010,(16).
[6]彭先胜,姚李孝,伍利,等.基于改进粒子群算法的配电网多目标重构[J].西安理工大学学报,2010,2.
[7]肖鲲,黄挚雄.多智能体粒子群算法在配电网络重构中的应用[J].计算机工程与应用,2010,(8).
[8]于永哲,黄家栋.基于模拟植物生长法的配电网络重构[J].电力系统保护与控制,2010,(2).
[9]陈章潮,顾洁,孙纯军.改进的混合模拟退火—遗传算法应用于电网规划[J].电力系统自动化,1999,23(10):28-31,40.
[10]李德华,王韶,等.模糊遗传算法和蚁群算法相结合的配电网络重构[J].电力系统保护与控制,2009,(7).
遗传模拟退火 篇6
1 指派问题数学模型
为方便研究将平衡与非平衡两种指派问题归纳为如下两种形式研究:
设有n项任务,要派m个人去完成,Cij表示第i个人完成第j项任务要付出的代价,tij表示第i个人完成第j项任务所需时间,则如何分派会使整体效益最好,即用时少费用低。
为建立模型引入0-1变量:
1.1 人数大于或等于工作项目时m≥≥n≥
1.2 人数小于工作项目时m<n
式中b———每人限制的最大工作量
2 指派问题的模拟退火遗传混合算法实现
2.1 模拟退火遗传混合算法思想
Step1:选定初始温度t=t0
利用模拟退火算法的温度控制方法选定较合适的初始温度。如果初始温度选择过高会导致计算时间较长,从而降低计算效率。如果初始温度选择过低又有可能使最终收敛得不到最优解。因此根据(14)式的条件来确定初始温度t0。
式中Δfij———任意两个相邻的温度差
Step2:确定初始群体initpop
首先,用实数编码方法对任务数n进行编码且不变;
其次,用实数编码方法对人数m进行编码且可以随机抽取;
最后,利用随机生成法对l!l=m-1个解中随机选取一个解为初始群体initpop。
Step3:构造适应函数f0=fitfun1,ft=fitfun1
Step4:利用遗传算法对初始群体initpop进行优化,产生种群seedpop1
(1)确定评价函数eval Vi
取一个小于1的实数α=0.9,fie是随着i的增大而不断减小的基于序的评价函数,则评价函数eva Vi是随i的增加(fie的减小)而缓慢减小的。
(2)利用评价函数可以确定进入种群的个体
当qi-1≤γ≤qi时(γ为(0～1)的伪随机数),第i个染色体进入种群,从而形成种群seedpop1。
Step5:利用模拟退火算法对种群seedpop1进行训练,产生更优的新种群seedpop2
(1)对seedpop1中1～m个体的适应值与初始群体中f0的值进行比较,满足条件的进入seedpop2;
(2)否则,根据评价函数来判断进入seedpop2的个体。当个体的适应值满足时,则选择进入seedpop2;
(3)经过优化训练,产生新种群seedpop2。
Step6:对新种群seedpop2进行交叉、变异,产生子代children
(1)对新种群seedpop2进行双亲双子法交叉,交叉率β,生成crosspop;
(2)再进行变异,交叉率ε,生成mutpop;
(3)生成子代children。
Step7:返回Step4,直到满足终止条件
Step8:得到最优解
3 算例演示
某大型生产企业为生产和人员安全每年都要定期对生产设备进行检修,检修分为平时检修和7月分大检修。现取其中一个车间来做算例,该车间只有3个维修工,平时每次平均会有2个地方出现故障,到7月大检修时该车间5个检修点都要停止运作重新进行检查和修理。已知工人维修故障所需时间Pij见表1,每个维修工的基本维修费用Cij见表2,注:在7月份大检修时天气比较炎热为保证维修工安全要求每个工人至多维修两个故障点。
单位:小时
单位:百元
混合算法相关参数选择α、初始时间t0=6、交叉率β=0.2、变异率=0.05。利用前面设计的混合算法进行运算得到结果及比较结果见表3,运行次数都为10次。按照该方案进行分配所得到的完成任务的花费时间大约要比单一使用模拟退火或遗传算法获得最优解短五分之二。
4 结论
本文结合模拟退火算法和遗传算法的优点,提出模拟退火遗传混合算法来解决实际中的指派问题。指派问题属于组合优化问题,很适合用本文研究的算法来实现。这种混合算法能够准确快速地求解最优结果或分配方案,针对较大规模的指派问题,能够缩短搜索时间,取得良好的效果。
参考文献
[1]贺国先.现代物流系统仿真[M].北京:中国铁道出版社,2008.
[2]焦永兰.管理运筹学[M].北京:中国铁道出版社,2000.
[3]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[4]谢凡荣.求解指派问题的一个算法[J].运筹与管理,2004(6):24-26.
[5]张新辉.任务数多于人数的指派问题[J].运筹与管理,1997(3):15-18.
[6]Cattrysse D G,Van Wassenhove L N.A survey of algoirths for the generalized assignment problem[J].Europena Joumla ofOperationla Research,1992,60(3):260-272.
遗传模拟退火 篇7
关键词：关联规则,遗传算法,模拟退火算法,Web挖掘,自适应
1 关联规则挖掘模型
在关联规则系统中,规则本身是“如果条件怎么样、怎么样,那么结果或者情况就怎么样”的形式。可表示为“A⇒B”关联规则,它包括两个部分:左部A称为前件,右部称为后件。前件可以包括一个或多个条件,在某个给定的正确率中,要使后件为真,前件中的所有条件必须同时为真。后件一般只包括一种情况。如:购买计算机有购买财务软件趋向的关联规则、年龄在30至40岁之间并且年收入在4200元至5000元之间的客户购买高清晰度彩色电视机趋向的关联规则可分别表示为:
undefined
数据项集合A和B由一项或多项属性组成,分别为决策属性和任务属性。通过对问题的分析,可以发现,决策属性相互间是无序的。因此可以将决策属性一次性排定顺序组成属性串,且在挖掘过程中不变其顺序。为了便于问题的分析,作以下形式定义。
定义1( Web事务。)在事务文件中出现的所有页面集合表示为P={p1,p2,…,pn}。其中每个页面pi(i=1,2,…,n)通过其URL地址唯一表示。事务集合U表示为U={u1,u2,…,un},每个事务ui={i=1,2,…,m}均为页面集合P的子集。
定义2 (页面权值。)假定将用户访问页面的平均停留时间作为该页面的权值。整个事务的权值为
undefined
定义3 (向量空间。)事务集合中的每一个事务ui(i=1,2,…,m)可以转换为页面空间上的n维向量,u=
定义4 (支持度s(pi)。)页面pi∈p的支持度为
undefined
定义5 (可信度。)规则pi⇒pj的可信度为C(pi⇒pj)=s(pi∪pj)/s(pi)。
定义6 (支持度 s(pi∪pj)。)页面 pi∪pj支持度为S(pi∪pj)=∑u∈U&pi∈uw(pi,u)×w(pj,u)/|{u∈U|pi∈u∧pj∈u }|
定义7 (AGSAA算法。)AGSAA=(Ω,f,P0,N,T0,Φ,Γ,Ψ)。其中,Ω为个体的编码方法;f为适应度函数;P0为初始种群;N为群体规模;TO为初始温度;Φ为遗传选择;Γ为交叉算子;Ψ为退火变异。
2自适应遗传退火算法的设计
2.1染色体编码
本文采用二进制编码来表示关联规则。对所有的特征属性和类别属性取离散值,且对连续型的值先作离散化处理。已知取值范围,对每个属性的每一个取值用一个合适长度的二进制串来表示,每个二进制串代表一个基因。将所有属性值的二进制串连接在一起得到一个二进制串作为一个染色体。一个染色体就代表一个关联规则,染色体的基因对应于事务中的页面权值。
2.2适应度函数
适应度函数评估是选择操作的依据,它的设计对遗传算法的收敛速度及能否找到最优解至关重要。本文考虑到在遗传算法中适应函数通常是最大值的形式,设计的适应函数为fitness=1/F。且采用适应度拉伸方法:
i=1其中,fi为第i个个体的适应度;g为遗传代数;T为温度;T0为初始温度
2.3遗传选择
遗传选择是将父代的个体信息传递到子代,每代中的每一个个体按照适应度函数的大小决定它能够复制到下一代的概率。AGSAA算法采用“轮盘赌”式的选择策略,随机生成一个数r=random[0,1],若(p0+p1+…+pi-1),则第i个个体被选择到下一代。算法采用的选择概率为:
2.4自适应遗传交叉、变异
IAGA算法为了保证每一代的优良个体不被破坏,采用了精英保留策略。即如果下一代种群的最优个体适应度值小于当前种群最优个体适应度值,则将当前种群最优个体或者适应度值大于下一代最优个体适应度值的个体直接复制到下一代,随机替代或替代最差的下一代种群中的相应数量的个体。此策略保证了当前的最优个体不被交叉、变异。但当适应度值等于最大适应度值的时候,交叉概率和变异概率的值为零,此时易产生局部最优解,出现停滞现象。为了避免此现象的发生,AGSAA算法根据适应度值来动态调整交叉概率和变异概率。
其中,fmax为种群最大适应度,favg为每代种群的平均适应度值,fmin为种群最小适应度值,f′为要交叉的两个个体中较大的适应度值,f为要变异个体的适应度值。Pc1>Pc2>Pc3,Pm1>Pm2>Pm3取(0,1)区间的值,可在优化过程中调整。
2.5个体模拟退火过程
用适应度作为模拟退火遗传算法中的能量,对算法中的近邻子集采用动态调节的方式选取:M=λ×(fmaxfavg)。当适应度值增加时,接受该解作为下一个当前解,否则,以一定的概率p=exp(-△fitness/T)接受该解。即
其中,fi+1为子个体的适应度值,fi为父个体的适应度值,温度T由随着算法进程递减其值的控制参数担当。
2.6并行模式
AGSAA算法采用主从式的并行遗传算法模型,该模型在不改变遗传算法结构的基础上,将一个群体的选择、交叉和变异等全局操作由主处理器串行进行,而适应度的评价和计算由各个从处理器并行执行。
2.7结束条件
如果经过若干代计算后,仍然没有满足用户给定阈值的规则,则终止并输出结果。
3实验及分析
3.1实验环境
为验证本文所提出方法的有效性,采用天网2001年用户查询与点击日志。其中,用户查询日志记录了用户查询时提交的关键词、提交时间、用户ip、页号及是否在cache中命中等信息。天网点击日志记录了用户的点击时间、查询串、点击的URL、点击页面的编号、点击URL的序号等信息。系统数据共维护了100多万个有效页面,被点击的URL只有16万多。经过数据净化处理,从中识别出2019条事务和317个页面。实验过程中所使用到得参数初始化定义为:种群规模150、交叉概率0.8、变异概率0.15、初始温度1、最大迭代次数genmax=220、支持度阈值10%、置信度阈值80%。实验环境为Intelc2.0GHZ、2GB内存、Windows xp和MATLAB7.0。分别对SA、AGA和AGSAA算法进行对比试验。
3.2 AGSAA算法流程
AGSAA算法流程如图1所示:
3.3实验结果及分析
图2描述的是在同迭代次数下SA、AGA和AGSAA三种算法产生的关联规则数的比较。从图2可看出,AG-SAA算法能够有效地进行关联规则挖掘,具有较快的收敛速度。图3描述的是3种算法在同迭代次数下关联规则准确率的比较。图3表明AGSAA算法挖掘出的规则的准确率比SA和AGA算法要高。表1描述的是SA、AGA和AGSAA算法在同计算时间下关联规则提取量的比较。从表1可看出,在初始阶段,AGA算法挖掘的规则数要高于AGSAA算法,但是在中后期阶段,AGSAA算法的挖掘效果要优于SA和AGA算法。这主要是因为通过引入自适应的交叉概率和变异概率,有利于AGSAA算法跳出局部最优解,增强了较差个体的变异能力,克服了早熟的现象。
4结束语
针对Web日志关联规则挖掘,本文在模拟退火遗传算法基础上,引入自适应的交叉概率和变异概率,且采用并行处理技术保持和丰富种群的多样性。通过对Web日志数据进行关联规则的实验和分析得出,该算法具有较强全局搜索能力,有效避免了早熟现象。表明该算法能有效地应用于Web日志关联规则挖掘中。
参考文献
[1]忠植.知识发现[M].北京:清华大学出版社,2002.
[2]阮光栅.基于兴趣度策略的启发式web挖掘算法[J].计算机工程与应用,2009(5).
[3]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009(6).
[4]GALE D.The game of Hex and the Brouwer fixed point theorem[J].American Mat-Hematical Monthly,1979(10).
[5]李凤营,赵连朋,王红雨.一种基于遗传算法的关联规则改进方法[J].计算机工程与应用,2008(10).
[6]武兆慧,张桂娟,刘希玉.基于模拟退火遗传算法的关联规则挖掘[J].计算机应用,2005(5).
[7]SRINIVAS M,PA TNAIL K L M.Adaptive probabilities of cross-over and mutation in genetic algorithms[J].IEEE Transaction onsystem,Man and Cybernetics,1994(4).
[8]任子武,伞治.自适应遗传算法的改进及在系统识别中应用研究[J].系统仿真学报,2006(1).
[9]许国艳,史清宇.遗传算法在关联规则挖掘中的应用[J].计算机工程,2002(7).
[10]刘若,孙杨军.基于多克隆选择的多维关联规则挖掘算法[J].复旦学报,2004(5).
遗传模拟退火 篇8
新形势下, 随着现代化科技的蓬勃发展, 以及计算机技术在教学内容、教学手段和教学方法中的结合使用日趋紧密, 促使基于遗传模拟退火算法的智能组卷系统的研究工作越来越受到人们的普遍关注和重视。一般来说, 智能组卷系统可以采取的算法主要包括了随机抽取算法、模拟退火算法、遗传算法, 以及遗传模拟退火算法等几种。其中, 遗传模拟退火算法在智能组卷系统当中的应用, 相对于其他算法来说, 其组卷成功率和收敛速度更为有效, 具有极为重要的研究意义。为此, 本文主要通过结合遗传模拟退火算法及其在在智能组卷系统当中的应用的仿真实验所涉及的一些知识内容展开讨论, 现具体分析如下。
智能组卷系统的数学模型构建
优化带约束条件的组合是智能组卷系统构建的核心内容。具体可以从模型构建的约束条件和目标函数进行分析。
1模型构建的约束条件
从智能组卷系统的模型来看, 智能组卷系统当中的一份试卷, 一般相当于一个m×n型的目标矩阵。其中, m为约束条件, n为题目总数。主要的约束条件包括试卷总分约束、试卷难度约束、试卷题型约束、试卷知识范围约束和答题时间约束等几种。
在试卷总分约束中, 假设试卷中的所有题型的分值构成m×n矩阵的第一列, 则其分值需要同时满足于公式:
其中, S为试卷总分, 最终数值主要由用户决定。
在试卷难度约束中, 假设试卷难度包括了容易、中等和困难等三个等级, 构成m×n矩阵的第二列, 那么, 试卷难度约束需要同时满足于条件:
其中, Sj为第j个难度级别所对应的总分, 通常由用户决定。当xi, 2=j时, y1=1, 否则yj=0。
在试卷题型约束中, 假设试卷共有选择题、填空题和简答题等三类题型, 构成m×n矩阵的第三列, 那么, 规定试卷题型约束为:
其中, 不同题型的总分由用户决定, Ti为第j种试卷题型的试题总分, 在xi, 3=j的情况下, yj为1, 否则则为0。
在知识范围约束中, 通常各章节内容编制的试题所占的分数比例可通过教学大纲规定, 假设其构成了m×n矩阵的第四列, 同时需要满足以下约束:
其中, Wj表示第j章节的试题分数, 通常由用户确定。在在xi, 4=j的情况下, yj为1, 否则则为0。
在答题时间约束中, 假设其答题时间构成了m×n矩阵的第五列, 那么, 答题时间需同时符合以下约束条件:
其中, xi, 5为完成第i道试题的预计时间, Q为预计总答题时间。
2模型构建的目标函数
在满足或基本满足用户的要求的情况下, 将试卷的总分、题型、难度、选题知识范围和答题时间等通过m×n矩阵进行表示, 能够有效实现试卷误差的正常反应。可按照试题是否重要为出发点, 确定试卷总误差 (用f表示) 需要为m个约束的加权和。具体目标函数为:
其中, fi为第i个约束和用户要求之间的误差绝对值, wi为第i个约束的权重。
智能组卷系统中遗传模拟退火算法的相关内容
1遗传模拟退火算法的基因库构造
在充分考虑试卷题型比例、总分等要求的基础上, 遗传模拟退火算法的基因库构造需要实现以下步骤, 包括: (1) 构造包括试题知识点、难易度等属性的子集, 并将属性相类似的划分为一个子集; (2) 对试卷题型的试题数量, 以及其在试卷当中所占分数比例加以计算, 并且试题数量需要符合用户所要求在试卷的覆盖情况; (3) 对试卷中同种难度的试题及其数量 (用R表示) 加以计算, 确定是否需要; (4) 通过消除早已存在试卷中的题目, 为数据存储对象保持低冗余性提供保障; (5) 对从各子集中随机抽取的试题加以检查, 确定是否符合规定, 并对不符合限制条件的试题进行删除, 对符合限制条件的试题划分到同类子集中; (6) 对各章节试题进行分析, 判断是否可以加入试卷当中。若可以, 则表明当前知识点在数据对象中有相同试题, 需要执行全部删除命令, 并回到第5步继续;若不可以, 则表示试卷中本章节的试题量符合试卷要求的最大值, 只需删除相应试题即可, 再回到第6步继续; (7) 若满足R=0的条件, 则说明试卷已经生成, 可以退出循环。或是试题数量无法满足要求, 则执行退出命令。
通过以上步骤, 能够确保生成的初始试题数量适中、分布均匀, 且增加了试题的明显差异性和丰富性。
2遗传模拟退火算法的编码
假设1道试题为试题库中的1条染色体, 那么用户可以用染色体基因的长度来形容知识点总量。
3退火变异算子
退火变异算子, 作为遗传模拟退火算法的主要集合, 具体可以从以下步骤加以分析, 包括: (1) 若是变异概率Pm要高于退火变异算子所形成的随机数因子, 则执行f评估值的计算, 反之, 则不执行任何操作; (2) 新的个体可以通过基因的任意改变而形成; (3) 由以上步骤得到新的f (x') 评估值, 并根据公式△f=f (x') -f (x) 计算差异; (4) 比较差异, 若是f (x') >f (x) , 则新产生的个体要比原个体优异, 替代原个体;若f (x') ≤f (x) , 则表示新产生的个体没有原个体优异, 此时可能取代原个体的概率在△f/T。
基于遗传模拟退火算法的智能组卷系统的模拟分析
1模拟参数分析
本研究需要用到的设备主要是Math Lab7.0模拟器、奔腾四2.8G/512 M计算机等。将最大遗传代数设定为50, 交叉概率采用0.85, 变异概率采用0.005, 惩罚因子采用1.2, 并将退火初始温度和温度系数K分别设定为1和0.95。
2模拟数据分析
通过对群体规模与最佳适应、平均适应和算法平均耗时等之间的关系研究, 可以看出, 在遗传模拟退火算法中, 解决问题的精度越高, 染色体的长度也会相应变长, 致使搜索空间变得越大。不过随着问题数量的增加和搜索空间的增大, 采用遗传模拟退火算法需要消耗的时间同样有限, 可见算法具备收敛性快的特点, 适合于智能组卷系统的应用。
结束语
遗传模拟退火 篇9
在四杆机构设计中,经常遇到已知连杆上某点的轨迹进行机构优化设计,即轨迹再现型曲柄连杆机构的设计。对这类问题,传统的方法是用解析法列方程组来求解,所得结果具有很大局部性。本文采用遗传模拟退火算法对其进行优化设计。
1 解析法求解
如图1所示,在平面坐标系xoy中,确定曲柄连杆机构尺寸及连杆上M点的位置,使M点的轨迹与给定轨迹yg=f(xg)相符。表1为给定轨迹yg=f(xg)上主要点的坐标。
取参考坐标系x′Ay′,设M点的坐标为(xM,yM),参考坐标为(xM′,yM′),其方程为:
undefined
。 (1)
经推导得M点的位置方程为:
U2+V2=W2 。 (2)
其中:
U=e[(xM′-dcosφ)cosθ+(dsinφ-yM′)sinθ]·(xM′2+yM′2+k2+a2)-kxM′[(xM′-dcosφ)2+yM′2+e2-c2] ;
V=e[(xM′-dcosφ)cosθ+(dsinφ-yM′)sinθ]·(xM′2+yM′2+k2+a2)-[(xM′-dcosφ)2+yM′2+e2-c2] ;
W=2kesinθ[xM′(xM′-dcosφ)+yM′2+dcosφ·(dsinφ-yM′)cosθ] 。
在xoy坐标系,M点的坐标为:
undefined
。 (3)
在上述方程组中,待定尺寸参数为a、c、d、e、k、xA、yA、φ、θ,可任选轨迹上9个点的坐标值代入式(2)、式(3)即可求得待定参数。但根据上述方法所求得的结果只能实现给定轨迹中这9个点的位置,其它位置就不一定能实现,即解析法所求得的结果具有很大的局部性[1]。
2 遗传模拟退火算法原理
2.1 遗传模拟退火算法思想
遗传模拟退火算法(Genetic Simulated Annealing,简称GSA)是将遗传算法与模拟退火算法相结合而成的一种优化算法。遗传算法(Genetic Algorithms,GA)[2]是一种全局优化算法,其仅以目标函数值为搜索依据,通过群体优化搜索和随机执行基本遗传运算来实现遗传群体的不断进化[3],但该算法在实际应用中会产生早熟现象和局部寻优能力差的问题。模拟退火算法是1982年由Kirkpatrick等提出的,算法的核心[4]是模仿力学中固体的退火过程,在算法中采用Metropolis接受准则,模拟退火算法的局部搜优能力较强,并可使搜索过程避免陷入局部最优解,但模拟退火算法不便于搜索过程进入最有希望的搜索区域,因而模拟退火算法的运算效率并不高。GSA是遗传算法与模拟退火算法的结合,对它们取长补短,是一种性能优良的全局搜索算法。
2.2 GSA基本流程
GSA算法的总体运行过程与基本的GA算法相类似,首先从随机产生的一组初始解(初始群体)出发,然后通过选择、交叉、变异等遗传操作来产生一组新个体,再独立地对所产生的各个个体进行模拟退火过程操作,并以其结果作为下一代群体中的个体。将上述迭代过程反复进行,直至满足终止条件,得到全局最优解,算法结束[5]。其算法流程见图2。
3 遗传模拟退火优化设计过程
3.1 建立数学模型
(1)建立目标函数:
undefined。 (4)
其中:xMi、yMi由式(3)代入;xi、yi是轨迹上已知点的坐标。
(2)确定设计变量:
X=[x1,x2,x3,x4,x5,x6,x7,x8,x9]T=[a,c,d,e,k,xA,yA,φ,θ]T 。 (5)
(3)建立约束函数:
根据曲柄连杆机构特性及最小传动角的要求:①四杆机构中的最长杆与最短杆之和应小于另两杆之和;②曲柄必须是最短杆;③最小传动角大于30o。建立的约束函数为:
undefined
。 (6)
其中:undefined;undefined。
3.2 遗传模拟退火算法求解
3.2.1 染色体的编码
在采用遗传模拟退火算法进行搜索之前,先将变量编码成一个定长的编码。根据问题特征,本例采用浮点数编码,即直接采用十进制的实数编码。用浮点数编码不但可以消除因二进制编码精度不够而造成的搜索空间中具有较优适应值的可能解未能表示出来的隐患,而且可以消除“Hamming悬崖”。
3.2.2 随机生成初始群体
遗传模拟退火算法是对群体进行操作的,通过随机方法生成一个初始群体,其数量称为群体规模N。在选择N时,要结合具体问题合理选择,一般N取10～160。本例中选择N=100。
3.2.3 适应函数值的计算
对种群规模为N的染色体群进行性能分析,需将目标函数f(X)转化为适应度函数f*(X),对于带约束的优化问题可用惩罚函数将其转化为无约束问题:
undefined。 (7)
式中:gi(x)——约束函数,i=1,2,3,4;
C ——罚函数,C>0。
适应度函数:
f*(X)=1/(F(X)+R) 。 (8)
式中:R——足够大的正数。
这样就将式(4)转化为求无约束的极大适应函数值问题。
3.2.4 遗传算子
在上一代染色体的基础上,运用选择、交叉和变异等遗传算子作用于种群,产生适应函数值f*(X)更高的新一代种群,即产生N个满足约束条件的目标函数值f(X)越来越小的设计点。
(1)选择:
选择过程是根据N个染色体的适应函数值的大小来选择染色体进行复制,并将其拷贝到下一代。常用的选择方法为轮赌法,适应函数值越高的染色体被选择的机会就越大。
(2)交叉:
交叉操作是遗传算法产生新个体的主要方法,在算法中起关键作用。染色体是否发生交叉由交叉概率Pc决定。本例中取Pc=0.6。
(3)变异:
变异操作是模拟自然界生物体上某位基因发生的突变现象,从而改变染色体的结构和物理形状。在遗传算法中,变异过程是以较小的概率Pm随机地改变染色体串上的某一位。本例采用十进制编码,个体Si的第j个基因发生变异的操作ΨD定义为:ΨD(Si,j)=Sji+N(0,σ),其中N(0,σ)是均值为0、方差为σ的高斯噪音[6]。变异过程包含于交叉过程。本例中取变异概率Pm=0.02。
3.2.5 个体模拟退火操作
GSA引入了Metropolis接受准则,且具有摆脱局部最优陷阱的能力。假设遗传到第k代后,第i个设计矢量Xundefined所对应的无约束罚函数值为Fundefined,通过遗传运算之后,Xki演化为的Xundefined′所对应的无约束罚函数值为Fundefined′,其接受准则为:
undefined
。 (9)
其中:Pi=exp(ΔF/T),ΔF=Fundefined-Fi′,T为退火温度;Pi为接受概率;r为[0,1]中的随机数。
本例采用了C++6.0编程,按连续20代历史最好解X不变作为终止条件,经过数代的遗传,再将所得到的染色体还原就可得到原问题的最优设计点X。其计算结果对比见表2。通过f(X)值可发现基于GSA优化的结果是更优解。
4 结语
本文建立了曲柄连杆机构的优化模型,并给出了传统解析法思路和遗传模拟退火算法求解的具体算法。通过具体实例运算结果对比分析,说明GSA提高了GA算法避免陷入局部最优解的能力,使算法搜索到全局最优解的概率和效率大大提高,较好地解决了轨迹再现型曲柄连杆机构的优化设计问题,所得结果是令人满意的。因此遗传模拟退火算法是机械优化设计的较好算法。
摘要：采用遗传模拟退火算法对轨迹再现型四杆机构进行优化设计,结果表明,该优化算法把模拟退火算法结合进遗传算法中,这样在保证获得较好的全局搜索能力的同时,又加快了遗传算法在最优值附近的收敛,提高了遗传算法的效率。
关键词：四杆机构,模拟退火算法,遗传模拟退火算法,优化设计
参考文献
[1]陶贵春.机械原理[M].北京:航空工业出版社,1990.
[2]David B Fogel.An introduction to simulated evolutionaryoptimization[J].IEEE Trans Neural Networks,1994,5(1):21-25.
[3]陈国良.遗传算法及应用[M].北京:人民邮电出版社,1996.
[4]Kirkpatrick S.Optimization by simulated annealing[J].Science,1983,220:671-679.
[5]陈伦军.机械优化设计遗传算法[M].北京:机械工业出版社,2005.
[6]张晓缋.遗传算法的编码机制研究[J].信息与控制,1997,26(2):9-11.