混合遗传算法GASA

基于模拟退火的混合遗传算法混合遗传算法我们知道，梯度法、爬山法、模拟退火法等一些优化算法具有很强的局部搜索能力，而另一些含有问题相关的启发知识的启发式算法的运行效率也比较高。如果融合这些优化方法的思想，够成一种新的混合遗传算法(hybridgeneticalgorithm)，是提高遗传算法运行效率和求解质量的一个有效手段。目前，混合遗传算法实现方法体现在两个方面，一是引入局部搜索过程，二是增加编码变换操作过程。在构成混合遗传算法时，DeJong提出下面三个基本原则：①尽量采用原有算法的编码；②利用原有算法全局搜索的优点；③改进遗传算子。一种混合遗传算法构成的示意图种群P(t)种群P(t＋1)解集合选择交叉变异局部搜索个体评价编码变换局部最优解解码遗传空间解空间混合处理模拟退火遗传算法(SimulatedAnnealingGeneticAlgorithm,SAGA)。模拟退火算法是1982年Kirkpartick等将固体退火思想引入组合优化领域，提出了一种解大规模组合优化问题，特别是NP完全组合优化的有效近似算法。固体退火过程的物理图像和统计性质是模拟退火算法的物理背景，Metrolpis接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。固体退火是先将固体加热至融化，然后徐徐冷却使之凝固成规整晶体的热力学过程。从统计物理学的观点看，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。固体温度参数T，反复进行状态转移过程，新状态的接受概率P(x)服从Gibbs分布:式中，z为概率正则化系数，E(x)为状态x的能量。由上式可知，随着温度参数的减小，接受概率也随着减小，即能量函数增大的可能性也逐渐减小，最后系统会收敛于某一能量最小的状态。显然模拟这样的固体退火过程，应用于函数优化中是可行的。设组合优化问题的一个解i及其目标函数分别与固体的微观状态i及其能量Ei等价。令随着算法进程递减其值的控制参数t担当团体退火过程中的温度T的角色，则对于控制参数t的每一个取值，算法持续进行“产生新解→判断→接受／舍弃”的迭代过程就对应于固体在某一恒定温度下趋于热平衡的过程。从统计物理学获得的Metrolpis接受准则应用于确定从当前解i到新解j转移的概率Pk：开始时让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为初始温度。混合遗传算法中除了