遗传算法GeneticAlgorithm(matlabGAtool用法打印了,和实验指导书放在一起)

遗传算法

GA(GeneticAlgorithm)遗传算法JohnHolland美国密歇根大学教授于1970s提出基本思想：模拟生物群体的进化(自然选择naturalselection、适者生存survivalofthefittest)和优化问题的基本联系：生物进化和遗传算法的对应关系生物学中的概念遗传算法适者生存在算法停止时，最优目标函数值的解有最大的可能性保留下来个体individual解染色体chromosome解的编码（字符串、向量等）基因gene编码位或分量适应性fitness适应度函数的值群体population(种群)选定的一组解(其中解的个数为群体的规模)(自然)选择根据适应度函数选取的一组解交配crossover通过交配操作产生的一组新解的过程变异mutation编码的某一位或分量发生变化的过程最后三个在遗传算法中称为遗传操作求解优化问题最大化目标函数也可以有约束。可行解。遗传算法的基本步骤选择一个问题的解的编码方案产生一个有N个染色体的初始群体对群体中的每一个染色体计算其适应度(目标函数值)在当代群体上重复如下步骤，直至停止条件满足。选择：根据染色体的适应度，按一个规则从当前群体中选择一些个体组成一个新群体(配对库)在该群体上，通过交配操作产生后代。在该群体上，通过变异操作产生后代。这时已得到下一代群体。计算新一代群体中各个染色体的适应度。简单遗传算法选择问题的解的编码为二进制编码随机产生一个有N个染色体的初始群体，迭代时N不改变对群体中的每一个染色体计算其适应度//目标函数值在当代群体上重复如下步骤，直至停止条件满足。比例选择：从当代群体中选择一些个体组成新群体，每个个体被选中的概率与其适应度成比例。比例选择也叫轮盘赌，一个个体可能被选中多次。在该群体上，通过交配操作产生后代。//一对染色体,单点交叉(pc经常=0.6-1.0)在该群体上，通过变异操作产生后代。//

每个编码位是等概率变异的，小概率变异(pm经常=0.01-0.1)这时已得到全新的群体。计算在新群体中各个染色体的适应度。例子maxf(x)=x2,0≤x≤31,x为整数。（迭代1步）例子：TSPTSP(TravelingSalesmanProblem)

旅行商或货郎担问题：设有n个城市，货郎担从其中的一个城市出发，每个城市必须访问一次、而且只能访问一次，最终回到开始的城市。两个城市之间的旅费是已知的，他应该选择什么样的路线才能使花费达到最小？GA求解：设有10个城市：A,B,C,D,E,F,G,H,I,J解的编码：城市的一个排列（二进制位串不行）初始种群：随机生成排列交叉操作：原来的也不适用（解会变的不可行，可行解要求排列中每个城市都出现且只出现一次）。两个旅程：JHDEFIGCBA—旅程1HGEBCJIADF—旅程2部分匹配交叉(PMX)：取两个截点：如DE间，IG间：旅程1→

JHDBCJGCBA→

IHDBCJGFEA—旅程1‘旅程2→HGEEFIIADF

→HGBEFIJADC—旅程2‘中间部分交换，外围部分中重复的城市用旅程之间对应的替换。这样，每一个都满足可行解的条件变异操作：随机选择一个城市并插入到随机位置(或随机选择两个城市并互换位置)用GA求解TSP，有很多研究(编码、遗传操作等的形式多样)

参看：米凯利维茨写的《演化程序》。还可网上搜)。GA的特点与以前讲过的算法比较多个解vs一个解；随机性vs确定性。不用求导数。在编码(而不是可行点)上进行操作。(有实数编码的GA)优点：它是一个全局优化算法万能算法缺点：需要设计(针对具体问题、设计具体的编码和遗传操作)可能会收敛速度慢：但它本质上是并行的，并行计算时效率很高。Matlab中有遗传算法工具箱(ga和gatool)1.：13、14周停课做实验：14周周一下午、工程实训楼实验内容：见实验指导书