一种模拟进化计算的遗传算法方案.docxVIP

一种模拟进化计算的遗传算法方案 一、 自然法系的模拟 遗传算法：ga发表于美国mipigan大学的约翰霍拉德教授在20世纪60年代提出。这是一种自然适应优化方法。该算法是基于自然遗传和自然优化机制的最佳方法。所谓自然遗传和自然优选来自于达尔文的进化论学说,该学说认为在生物进化过程中,任一动植物经过若干代的遗传和变异,使之能够适应新的环境,是优胜劣汰的结果,这种自然遗传思想也适用于求解优化问题。GA采用选择(selection)、交叉(crossover)和变异(mutation)运算来实现“物竞天择,适者生存”这一自然法则的模拟。遗传算法的一般框架: 输入参数:染色体个数N,交叉概率Pc,变异概率Pm; 通过初始化过程产生N个染色体; 计算所有染色体的评价函数; 根据评价函数抽样选择染色体; 对染色体进行交叉和变异操作; 重复若干次(下一代的代数)计算评价函数、选择、交叉和变异。 由于最好的染色体不一定出现在最后一代,开始时保留最好的染色体,如果在新的种群又发现更好的染色体,则用它代替原来的染色体,进化完成后,这个染色体可以看作最优化的结果。 遗传算法几乎渗透到从工程到社会科学的诸多领域,必须要编制遗传算法的程序进行计算,作为使用者希望找一个现成的程序,而MATLAB的遗传算法工具箱正好满足要求。我们主要对遗传算法工具箱的用法和技巧作一点探讨。 二、 类型清系统岩型线ade输出 其主程序是ga.m,其用法如下: function[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps) 输出部分: 输入参数: 三、 in5x+7cos4xgao 以一个简单地连续性优化例子来说明,例如求maxf = x +10 sin(5x) +7 cos(4x) 采用GAOT的步骤如下: 运行结果如图1和图2所示,图1中标有“+”记号的点为初始值,标有“0”的点为最优值。最优解为x* = 7.8564, fmax = 24.8553。 四、 城市距离的距离问题 旅行商问题(Traveling Salesman Problem:TSP)是一个典型的组合优化问题,设有n个城市和各城市距离dij(i,j= 1,2,…,n),dij表示城市i到城市j的距离,问题是找遍访每个城市恰好一次的一条回路,且其路径长度为最短。目前解决此问题的方法较多,遗传算法是其中一种方法,下面用遗传算法工具箱编制的程序如下: 上面的程序是解决中国31个直辖市和省会城市的CTSP问题,t矩阵记录各城市的相对坐标。运行的结果如图4和图5所示。图3是中国31个城市的CTSP目前最好的解,它通过复杂的改进的模拟退火算法得来的,本程序的结果与接近,但程序编程简单。 五、 遗传算法工具 通过两个实例说明了遗传算法工具箱的强大的功能,是学习和利用遗传算法的好工具。其用法比较灵活,对其有关模块作适当修改,可解决许多实际问题。 (1)首先编制目标函数文件,如gaDemolEval.m (2)调用主程序ga.m,程序如下: