董素媛遗传算法

《董素媛遗传算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法简介GeneticAlgorithm(GA)-----AnBriefIntroduction-----一、遗传算法的概述起源和特点：遗传算法是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，是由美国Michigan（密西根）大学的J.Holland教授于1975年首先提出的，是搜索最优解的一种随机化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，是近十多年来备受关注的一种算法。搜索机制：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代

2、中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。群体竞争种群婚配子群变异淘汰生物进化循环图构造初始种群计算个体（染色体）的适应值选择交叉变异遗传算法基本流程遗传算法概要：对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数学规划模型：maxf(X)(1-1)s.t.X属于R(1-2)R属于U(1-3)其中：X＝[x1,x2,…,xn]T为决策变量，f(X)为目标函数，

3、(1-2)、(1-3)为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解；集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。总的来说，求最优解或近似最优解的方法主要有三种：枚举法、启发式

4、算法和搜索算法。随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。遗传算法中：将n维决策向量X＝[xl,x2,…,xn]T用n个记号Xi(i=1,2,…,n))所组成的符号串X来表示：X＝xlx2…xnTX＝[x1，x2，…,xn]T•把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。•这里的等位基因可以是一组整数。也可

5、以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。•这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。•对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，适应度越小。•遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空

6、间。•生物的进化是以集团为主体的。与此对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程：•第t代群体记做P(t)，•经过一代遗传和进化后，得到t+1代群体，记做P(t+1),这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。二、遗传算法的基本流程：Step1给出一个

7、有N个染色体的初始群体pop(1),t=1；Step2若停止规则满足，则算法停止；否则，对群体pop(t)中每一个染色体popi(t)计算其适应值；Step3从群体pop(t)中随机选一些染色体构成一个种群newpop(t+1)={popj(t)

8、j=1,2,…,N};Step4通过交叉，交叉概率为Pc,得到有N个染色体的crosspop(t+1)Step5对每个新个体依变异概率Pm进行变异，形成mutpop(t+1);t=t+1,新的群体pop(t)=mutpop(t);返回Step2注意：1）ne

9、wpop(t+1)集中可能重复选pop(t)中的某个元素2）最好的染色体不一定出现在最后一代，所以在进化开始，必须把最好的染色体保留下来，记为V0，如果在新的种群中又发现了更好的染色体，则用它代替原来的染色体V0,在进化完成之后，这个染色体就可以看作是最优问题的解。三、遗传算法实现的技术问题：解的编码；初始群体的设定；适应值函数的设计；遗传算子(选择规则；交叉规则；变异规则；)约束条件的处理；结束准则；运行参数的选择；GA的流程框图编码的主要方法：常规码