文档介绍：遗传算法
1 .基本概念
2 .应用举例
1基本概念
遗传算法:模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律,是具有“生存+检测”的迭代过程的搜索算法。
本质特征:与传统的启发式优化搜索算法(爬山算法、模拟退火算法)相比,遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子。
1基本概念
理论基础:主要以收敛性分析为主,即群体收敛到优化问题的全局最优解的概率。
分类:从整体上讲,可分为给予随机过程的收敛性研究(随机模型理论)和基于模式理论的收敛性分析(进化动力学理论)
1基本概念
遗传算法的优点:
以目标函数值作为搜索信息,提高了搜索效率;
以决策变量的编码作为运算对象,这种编码处理方式可以更方便的操作算子;
使用自适应概率搜索技术,增加了搜索过程的灵活性。
1基本概念
遗传算法的构成要素:
①参数编码(一般二进制)
②初始群体的设定N
③适应度函数
④遗传算子(包括选择算子、交叉算子、突变算子)
⑤基本遗传算法运行参数(N、T/Pc/Pm/Pr)
1基本概念
遗传算法的一般框架:
①编码设置初始群体     
②对群体迭代的执行下面的两个步骤,直到满足停止
准则:
(i).计算群体中每个个体的适应值
(ii).应用选择、交叉和突变算子产生下一代群体
③把在任一代中出现的最好的个体串指定为遗传算法的
执行结果,此结果可以表示问题的一个解(或近似解)
算法流程图:
2遗传算法应用案例
例:利用遗传算法求解区间[0,31]上二次函数y=x2的最大值。
分析:原问题可转化为在区间[0,31]中搜索能使y取最大值的点x的问题。那么,[0,31]中的点x就是个体,函数值f(x)恰好就可以作为x的适应度,区间[0,31]就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。
解:
设定种群规模,编码染色体,产生初始种群。
将种群规模设定为4,用5位二进制数编码染色体,取下列个体组
成初始种群S1;
s1=13(01101), s2=24(11000)
s3=8(01000), s4=19(10011)
定义适应度函数,取适应度函数:f(x)=x2
计算各代种群中的各个体的适应度,并对其染色体进
行遗传操作,直到适应度最高的个体(即31(11111))出
现为止
首先计算种群S1中各个体的适应度f(si):
s1=13(01101) ,s2=24(11000)
s3=8(01000) , s4=19(10011)
容易求得:
f(s1)=f(13)=132=169
f(s2)=f(24)=242=576
f(s3)=f(8)=82=64
f(s4)=f(19)=192=361