有关于遗传算法的教程教材课程.ppt

采用算术交叉算子： 如染色体v16”和v19”的交叉操作后产生两个后代：任取[0,1]区间随机数c 交叉后的后代10个加上未参加交叉操作的20个染色体，得到新种群 取一变异概率p2，用前面一样的方法可选择若干染色体进行变异。 如v1’’’被选来变异，先随机产生一个方向d和随机数M，若 若上述染色体不可行，则可在区间[0.M]中重新随机产生M1，然后再用M1代替原来的M值，等等。 注意事项 遗传算法的选择、交叉与变异概率不适当的话，会引起“早熟现象”。 遗传算法局部搜索能力较差，如果中间适当穿插局部搜索算法（上升法，模拟退火算法等），可以提高算法质量 个体P(t) 选择运算 交叉运算 变异运算 群体P(t+1) 解码 解集合 个体评价 局部搜索 局部最优解集合 编码变换 模拟退火算法(Simulated Annealing ) 原理：模仿金属热处理过程 算法要素： 1. 搜索空间Ω，也称状态空间，一个状态代表一个可行解。 2.能量函数E(x)。 3.状态转移规则：从一个状态xold到另一个状态xnew的转移概率，与当前温度参数T有关。 4.冷却进度表T(t) 经典降温方式 快速降温方式 常用算式还有： K为略小于1的系数 系统由状态xold变为xnew的接受概率可按照以下Meteopolis规则确定： A B C 如果搜索陷入局部最优点A，若要使搜索脱离这个局部最优点达到C，则必须使系统至少具有B点所对应的能量。 温度T减小时接受概率也随之减小，最后系统收敛于某一能量最小的状态，该状态可视作目标函数的全局最小值。 模拟退火算法计算步骤 Step1 随机产生一个初始点，计算目标函数值。 Step2 设置初始温度θ：=T0. Step3 设置循环计数器初始值t：=1 Step4 对当前最优点作一随机变动，产生一新的最优点，计算新的目标函数值，计算能量函数值增量Δ Step5 如果Δ0则接受新产生的最优点为当前最优点，否则以概率p=exp(-Δ/θ)接受该点为当前最优点。 Step6 如果t终止步数则t:=t+1转step4. Step7 如果未达到冷却状态则θ:=T(t)转步3，否则输出当前最优点，计算结束。 使用遗传算法时应该注意的问题 1. 适用性。 2. 设计遗传算法时应突出技术创新点，如独特的编码技术和交叉方法等。 3. 使用遗传算法需要自己编程。往往找不到现成的算法。很多模型在遗传算法算法设计中常会遇到技术难点。 4. 网上程序可以用作参考和借鉴的母本。 遗传算法与模拟退火算法 杭州电子科技大学 数学教研室 杭州电子科技大学 沈 灏 二00八年八月 任务一. 读阅读模型3，案例39： 血管的三维重建报告日：8月22日下午1：30负责老师：陈建兰，刘建贞 任务二. 写一篇集训心得（简明扼要），内容： 本人集训体会（真实体会，不要写套话） 本人在集训中做了哪些工作 另两名队友各自做了哪些工作 本队合作实际情况 是否希望参加全国竞赛。 集训心得8月27日12：00之前发到：qzy@hdu.edu.cn 集训心得纸质材料8月28日一早交给裘哲勇老师。 暑期集训结束前不重新组队。 希望重新组队同学说明如果留在原来的队里是否仍愿意参加全国竞赛。 遗传算法（genetic algorithm） 遗传算法是一种全局搜索优化算法，特点是仿生物进化过程，使遗传算子作用于群体P(t)，得到新群体P(t+1)。 遗传算子的基本运算有： 1.选择（selection) 根据个体适应度,按照一定规则从P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。 2.交叉（crossover）将选择出来的个体随机搭配成对，对每一对个体，以某个交叉概率交换它们之间的部分染色体。 3.变异（mutation）对P(t)中每一个个体，以某一变异概率改变某一个或某一些基因座上的基因值为其它的等位基因。 个体P(t) 选择运算 交叉运算 变异运算 群体P(t+1) 解码 解集合 个体评价 遗传算法流程图 算法步骤 Step1 初始化。设置进化代数计数器t=0,设置最大进化代数T，随机生成M个个体作为初始群体P(0). Step2 个体评价。计算P(t)中各个体的适应度。 Step3 选择运算。将选择算子作用于群体。 Step4 交叉运算。将交叉算子作用于群体。 Step5 变异运算。 将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1). Step6 t=T?是则输出整个进化过程中具有最大适应度的个体作为最优解，否则t:=t+1,返回step2. 运算过程 1. 个体编码：采用6位无符号二进制整数，如X=101110表示x=(5,6)。 2. 取