遗传算法学习心得体会 13页

‎　　遗传算法 概念 ‎　　遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它既能在搜索中自动获取和积累有关空间知识，并自适应地控制搜索过程以求得最优解遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近视最优方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近视解。这个过程导致种群中个体的进化，得到的新个体比原个体更适应 ‎　　环境，就像自然界中的改造一样。 应用 ‎　　遗传算法在人工智能的众多领域具有广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如tsp、背包问题）、函数的最大值以及图像处理和信号处理等等。遗传算法多用应与复杂函数的优化问题中。 原理 ‎　　遗传算法模拟了自然选择和遗传中发生的复制、交叉、和变异等现象，从任一初始种群出发，通过随机选择、交叉、变异操作，产生一群更适合环境的个体，使群体进行到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体求得问题的最优解。‎ ‎　　算法流程 1. 编码：解空间中的解数据x，作为作为遗传算法的表现型形式。从表现 型到基本型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传 ‎　　空间的基本型串结构数据，这些串结构数据的不同的组合就构成了不同的点。 2. 初始种群的形成：随机产生n个初始串数据，每个串数据称为一个个体， n个串数据构成了一个群体。遗传算法以这n个串结构作为初始点开始迭代。设置进化 ‎　　代数计数器t 0;设置最大进行代数t；随机生成m个个体作为初始群体p(0)。 3. 适应度检测：适应度就是借鉴生物个体对环境的适应程度,适应度函数 就是对问题中的个体对象所设计的表征其优劣的一种测度。根据具体问题计算p(t)的适应度。‎ ‎　　4.‎ ‎ 选择：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到 下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的 ‎　　适应度评估基础上的。‎ ‎　　5. 交叉：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结 构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 6. 变异：将变异算子作用于群体。即是对群体中的个体串的某些基因座上 的基因值作变动。‎ ‎　　群体p(t)经过选择、交叉、变异运算之后得到下一代群体p(t+1)。 7. 终止条件判断:若t<=t,则t=t+1，转到第3步，否则以进化过程中所得 到的具有最大适应度个体作为最优解输出，终止计算。 遗传算法流程图如下图所示： 遗传算法 ‎　　下几种：适应度比例方法、随机遍历抽样法、局部选择法。 其中轮盘赌选择法是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法 ‎　　2、交叉：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分 ‎　　结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。 交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，‎ ‎　　期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法： b)二进制交叉（binary valued crossover） 1)单点交叉（single-point crossover） 2)多点交叉（multiple-point crossover） 3)均匀交叉（uniform crossover） 4)洗牌交叉（shuffle crossover） 5)缩小代理交叉（crossover with reduced surrogate）。 3、变异 ‎　　变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编 ‎　　码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异。‎ ‎　　一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。 例：简单一元函数优化 求下面函数的最大值：‎ ‎　　f(x)=xsin(10*pi*x)+2.0, -1<=x<=2; 程序： figure(1);‎ ‎　　fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]); %画出函数曲线 %定义遗传算法参数 ‎　　nind=40; %个体数目(number of individuals) maxgen=25; %最大遗传代数(maximum number of generations) preci=20; %‎ ‎　　变量的二进制位数(precision of variables) ggap=0.9; %代沟(generation gap) trace=zeros(2, maxgen); %寻优结果的初始值 fieldd=[20;-1;2;1;0;1;1]; %区域描述器(build field descriptor) chrom=crtbp(nind, preci); %初始种群 gen=0; %代计数器 variable=bs2rv(chrom, fieldd); %计算初始种群的十进制转换 ‎　　objv=variable.*sin(10*pi*variable)+2.0; %计算目标函数值 while gen５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143‎ ‎　　子代ｂ：986 | 130 | 5427‎ ‎　　6. 顺序交叉法(ox) （用于互换编码） 从父代ａ随机选一个编码子串，放到子代ａ的对应位置；子代ａ空余的位置从父代ｂ中按ｂ的顺序选取（与己有编码不重复）。同理可得子代ｂ。 父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：‎ ‎　　子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904‎ ‎　　7. 循环交叉（cx）法（用于互换编码） cx同ox交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：ox中来自第一个亲代的编码子串是随机产生的，而cx却不是，它是根据两 ‎　　个双亲相应位置的编码而确定的。 父代ａ：1 2 3 4 5 6 7 8 9 | | | | |‎ ‎　　父代ａ：5 4 6 9 2 3 7 8 1 可得循环基因：1->5->2->4->9->1 用循环的基因构成子代ａ，顺序与父代ａ一样 1 2 4 5 9‎ ‎　　用父代ｂ剩余的基因填满子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的编码同理。（循环基因 5->1->9->4->2->5） 遗传算子——变异 变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。ga中的变异运算是产生新个体的辅助方法，它决定了ga的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。‎ ‎　　注：变异概率pm不能太小，这样降低全局搜索能力；也不能太大，pm > 0.5，这时