混合遗传算法GASA

基于模拟退火的混合遗传算法混合遗传算法我们知道，梯度法、爬山法、模拟退火法等一些优化算法具有很强的局部搜索能力，而另一些含有问题相关的启发知识的启发式算法的运行效率也比较高。如果融合这些优化方法的思想，够成一种新的混合遗传算法(hybridgeneticalgorithm)，是提高遗传算法运行效率和求解质量的一个有效手段。目前，混合遗传算法实现方法体现在两个方面，一是引入局部搜索过程，二是增加编码变换操作过程。在构成混合遗传算法时，DeJong提出下面三个基本原则：①尽量采用原有算法的编码；②利用原有算法全局搜索的优点；③改进遗传算子。一种混合遗传算法构成的示意图种群P(t)种群P(t＋1)解集合选择交叉变异局部搜索个体评价编码变换局部最优解解码遗传空间解空间混合处理模拟退火遗传算法(SimulatedAnnealingGeneticAlgorithm,SAGA)。模拟退火算法是1982年Kirkpartick等将固体退火思想引入组合优化领域，提出了一种解大规模组合优化问题，特别是NP完全组合优化的有效近似算法。固体退火过程的物理图像和统计性质是模拟退火算法的物理背景，Metrolpis接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。固体退火是先将固体加热至融化，然后徐徐冷却使之凝固成规整晶体的热力学过程。从统计物理学的观点看，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。固体温度参数T，反复进行状态转移过程，新状态的接受概率P(x)服从Gibbs分布:式中，z为概率正则化系数，E(x)为状态x的能量。由上式可知，随着温度参数的减小，接受概率也随着减小，即能量函数增大的可能性也逐渐减小，最后系统会收敛于某一能量最小的状态。显然模拟这样的固体退火过程，应用于函数优化中是可行的。))(exp(1)(TxEzxP设组合优化问题的一个解i及其目标函数分别与固体的微观状态i及其能量Ei等价。令随着算法进程递减其值的控制参数t担当团体退火过程中的温度T的角色，则对于控制参数t的每一个取值，算法持续进行“产生新解→判断→接受／舍弃”的迭代过程就对应于固体在某一恒定温度下趋于热平衡的过程。从统计物理学获得的Metrolpis接受准则应用于确定从当前解i到新解j转移的概率Pk：否则，当),)()(exp()()(1)(tjfifjfifjiPk开始时让t取较大的值．在进行足够多的状态转移后，缓慢减小t的值，如此反复，直至满足某个停止准则时算法终止。因此，模拟退火算法可视为递减控制参数时Metrolis算法的迭代。下面是模拟退火法的伪代码描述：Procedure模拟退火算法beginS＝初始解S0；T＝初始温度T0；while(某种条件未满足时)beginwhile(未达到平衡时)S’=S的邻解;A＝f(S’)一f(S)；Prob=min(1．e-△/T)ifProb＞random(0,1)thenS=S';endupdateT;end模拟退火遗传算法(SAGA)遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法。遗传算法的局部搜索能力较差，但把握搜索过程总体的能力较强；而模拟退火并法具有较强的局部搜索能力、并能使按索过程避免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。但如果将遗传算法与模拟退火算法相结合，互相取长补短，则有可能开发出性能优良的新的全局搜索算法，这就是遗传模拟退火算法的基本思想。与基本遗传算法的总体运行过程相类似，遗传模拟退火算法也是从一组随机产生的初始解(初始群体)开始全局最优解的搜索过程，它先通过选择、交叉、变异等遗传操作来产生一组新的个体．然后再独立地对所产生出的各个个体进行模拟迟火过程，以其结果作为下一代群体中的个体。这个运行过程反复迭代地进行．直到满足某个终止条件为止。GASA混合优化策略的构造出发点1.优化机制的融合。2.优化结构的互补。3.优化操作的结合。4.优化行为的互补。5.削弱参数选择的苛刻性。……遗传模拟退火算法可描述如下算法GeneticSimulatedAnnealing(1)进化代数计数器初始化t:=0。(2)随机产生初始群体P(t)。(3)评价群体P(t)的适应度。(4)个体交叉噪作P'(t):=Crossover[P(t)]。(5)个体变异操P''(t):=Mutation[P'(t)]。(6)个体模拟退火操作P'''(t):=SimulatedAnnealing[P''(t)]。(7)评价群体P'''(t)的适应度。(8)个体选择、复制操作P(t+1):=Reproduction[P(t)∪P'''(t)](9)终止条件判断。若不满足终止条件，则：t:=t+1，转到第④步，继续进化过程；若满足终止条件，则输出当前最优个体，算法结束。NYYNGASA混合策略流程图给定算法参数初始化种群，确定初温评价当前种群中各个体执行GA的选择复制操作执行GA的交叉操作（附带保优操作）执行GA的变异操作（附带保优操作）得到GA的初始种群，对群体中个体进行SA搜索由SA状态产生函数产生新个体以概率接受新个体输出优化结果退温操作算法收敛准则满足否？SA抽样稳定否？遗传算法在运行早期个体差异较大，当采用经典的轮盘赌方式选择，后代产生个数与父个体适应度大小成正比，因此在早期容易使个别好的个体的后代充斥整个种群，造成早熟(pre-mature)；在遗传算法后期，适应度趋向一致，优秀的个体在产生后代时，优势不明显，从而使整个种群进化停滞不前(stalling)。因此对适应度适当地拉伸(scalingorstretching)是必要的。这样在温度高时(遗传算法的前期)，适应度相近的个体产生的后代概率相近；而当温度不断下降后，拉伸作用加强，使适应度相近的个体适应度差异放大．从而使得优秀的个体优势更明显。一种改进的适应度函数PaulL.Stoffa借鉴模拟退火思想，提出了模拟退火遗传算法(SAGA)，该算法采用如下的适应度拉伸方法：式中，fi为第i个个体的适应度，M为种群大小，g为遗传代数，T为温度，T0为初始温度。)99.0()(101//gMiTfTfTTeeifii混合遗传算法中除了上述将遗传算法与模拟退火法结合起来之外，还可以与启发式搜索算法结合起来构成一种新的混合算法；禁忌搜索(TabuSearch，TS)是一种著名的智能启发式搜索算法，由于TS具有记忆功能，将之引入到遗传算法的搜索过程中，构造新的重组策略，并把TS作为遗传算法的变异算子，这样可以综合两者的优点，并可以克服遗传算法爬山能力差的弱点。AGSA算法的应用示例弹药装载问题（AmmunitionLoadingProblem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。AGSA的基本原理在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSA），从而综合了全局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。AGSA的编码方式AGSA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为１，表示该弹药箱装入运输工具，为０则不装。AGSA的解码和适应度函数AGSA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。弹药装载的启发式算法（1）定位规则（Locatingrule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Orderingrule）定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。遗传算子的选择AGSA的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。交叉算子的选择由于AGSA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSA采用的是部分映射交叉算子。部分映射交叉算子交叉前：87|43|126512|57|8346交叉后：83|67|124517|62|8345至此，可以结合上面的GASA流程图写出相应的AGSA程序。