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

1、遗传算法GA (Genetic Algorithm)遗传算法 John Holland 美国密歇根大学教授于1970s提出 基本思想：模拟生物群体的进化(自然选择natural selection、适者生存survival of the fittest) 和优化问题的基本联系：生物进化和遗传算法的对应关系生物学中的概念生物学中的概念遗传算法遗传算法适者生存适者生存在算法停止时，最优目标函数值的解在算法停止时，最优目标函数值的解有最大的可能性保留下来有最大的可能性保留下来个体个体individual解解染色体染色体chromosome解的编码（字符串、向量等）解的编码（字符串、向量等）基因基因g

2、ene编码位或分量编码位或分量适应性适应性fitness适应度函数的值适应度函数的值群体群体population(种群种群) 选定的一组解选定的一组解(其中解的个数为群体的规模其中解的个数为群体的规模)(自然自然)选择选择根据适应度函数选取的一组解根据适应度函数选取的一组解交配交配crossover通过交配操作产生的一组新解的过程通过交配操作产生的一组新解的过程变异变异mutation编码的某一位或分量发生变化的过程编码的某一位或分量发生变化的过程最后三个在遗传算法中称为最后三个在遗传算法中称为遗传操作遗传操作求解优化问题 最大化 目标函数 也可以有约束。 可行解。遗传算法的基本步骤选择一个

3、问题的解的编码编码方案产生一个有N个染色体的初始群体初始群体对群体中的每一个染色体计算其适应度计算其适应度(目标函数值目标函数值)在当代群体上重复如下步骤，直至停止条件满足。 选择选择：根据染色体的适应度，按一个规则从当前群体中选择一些个体组成一个新群体(配对库)在该群体上，通过交配操作交配操作产生后代。在该群体上，通过变异操作变异操作产生后代。这时已得到下一代群体。计算新一代群体中各个染色体的适应度。简单遗传算法选择问题的解的编码为二进制编码二进制编码随机随机产生一个有N个染色体的初始群体，迭代时迭代时N不改变不改变对群体中的每一个染色体计算其适应度 / 目标函数值在当代群体上重复如下步骤，

4、直至停止条件满足。 比例比例选择：从当代群体中选择一些个体组成新群体， 每个个体被选中的概率与其适应度成比例。比例选择比例选择也叫轮盘赌，一个个体可能被选中多次。也叫轮盘赌，一个个体可能被选中多次。在该群体上，通过交配操作产生后代。/ 一对染色体一对染色体,单点交叉单点交叉(pc经常经常=0.6-1.0)在该群体上，通过变异操作产生后代。/ 每个编码位每个编码位是等概率变异的，小概率变异是等概率变异的，小概率变异(pm经常经常=0.01 - 0.1)这时已得到全新的群体。计算在新群体中各个染色体的适应度。例子 max f(x)=x2, 0 x 31, x为整数。（迭代1步）例子：TSP TSP

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

6、交叉(PMX)：取两个截点：如DE间，IG间： 旅程1 J H D B C J G C B A I H D B C J G F E A 旅程1 旅程2 H G E E F I I A D F H G B E F I J A D C 旅程2中间部分交换，外围部分中重复的城市用旅程之间对应的替换中间部分交换，外围部分中重复的城市用旅程之间对应的替换。这样，每一个都满足可行解的条件 变异操作：随机选择一个城市并插入到随机位置(或随机选择两个城市并互换位置) 用GA求解TSP，有很多研究 (编码、遗传操作等的形式多样) 参看：米凯利维茨 写的 演化程序。还可网上搜)。GA的特点的特点 与以前讲过的算法

7、比较与以前讲过的算法比较 多个解多个解 vs 一个解；一个解； 随机性随机性 vs 确定性。确定性。 不用求导数。不用求导数。 在编码在编码(而不是可行点而不是可行点)上进行操作。上进行操作。(有实数编码的有实数编码的GA) 优点：优点： 它是一个全局优化算法它是一个全局优化算法 万能算法万能算法 缺点：缺点： 需要设计需要设计(针对具体问题、设计具体的编码和遗传操作针对具体问题、设计具体的编码和遗传操作) 可能会收敛速度慢：但它本质上是并行的，并行计算可能会收敛速度慢：但它本质上是并行的，并行计算时效率很高。时效率很高。 Matlab中有遗传算法工具箱 (ga 和 gatool)1. ：13、14周停课 做实验：14周周一下午、工程实训楼 实验内容：见实验指导书请课代表通知自己班的同学，请课代表通知自己班的同学，并互相转告。（并互相转告。（15分）分）2. 交作业，15周讲作业的问题。16周随堂考。3. 公邮 : ，密码: 123qwe以后的安排以后的安排人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中