遗传算法原理

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

1、遗传算法原理算法简介定义：模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率算法。最早由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出。算法简介理论基础：模式定理（SchemaTheorem）模式定理揭示了群体中的优良个体（较好的模式）的样本数将以指数级规律增长，从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。算法简介一遗传算法的生物学基础遗传算法所借鉴的生物学基础就是生物的遗传和进化。根据达尔文的自然选择和现代遗传学理论，生物在其延续生存

2、的过程中，子代从其亲代继承了遗传基因，并通过基因重组和基因突变，使其品质不断得到改良，以适应于其生存境。算法简介核心：优胜劣汰生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。组成群体的单个生物称为个体(Individual)，每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。算法简介二基本概念1.个体与种群个体：就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群：就是模拟生

3、物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。算法简介适应度(fitness)：就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数(fitnessfunction)：就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。算法简介3染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体等位基因：{0,1}9----10

4、01（2，5，6）----010101110遗传算法要素及其实现技术编码个体适应度评价遗传算子运行参数原则：1低阶，短定义精度（易于生成适应度较高的个体）染2最小字符集（在确定规模的种群中能处理最多的模式）色二进制编码方法：最常用，使用由二进制符号0和1组体成的二值符号集{0,1}，所构成的个体基因型是一个二编进制编码符号串。假定某参数取值范围[U1,U2],用长度为l的二进制符码号串来表示：方000….0000=0U1l法111….1111=2-1U2U2U1精度：l21li1U2U1解码：blb

5、l1bl2b2b1xU1(bi2)li121二进制编码对于一些连续函数的优化问题，由于随机性使其局部搜索能力差；精度和编码串长度问题。染色格雷码：连续的两个整数所对应的编码值之间仅有体一个码位不同。编十进制数二进制码格雷码码000000000方100010001法200100011300110010401000110501010111转换：二进制编码Bbmbm1b2b1染格雷码：Ggmgm1g2g1色体二进制到格雷：gmbmgibi1bi,im1,m2,,1编码格

6、雷到二进制：bmgm方bibi1gi,im1,m2,,1法其他编码方法：浮点数编码方法，符号编码方法十进制编码方法适应度不能为负；适函数值最大，最小。应度适应度尺度变换：在遗传算法运行的初级阶段，群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若用比例选择算函子来确定个体的遗传数量时，这几个相对较好的个体将在下一代中有很高的比例，当群体规模较小时，新的群体可能完全由这样的少数数几个个体所组成。这时就会导致交叉算子起不了什么作用，这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象，

7、使遗传算法所求到的解停留在某一局部最优点上。在遗传算法运行的后期阶段群体中所有个体的平均适应度可能会接近群体中个体的最佳适应度，使得进化过程无竞争可言，从而影响遗传算法的运行效率。为了克服这种现象，需在遗传算法运行初期阶段对适应度较高的个体做缩小变换，对适应度较低的个体做扩大变换，进而维护群体的多样性。适应度尺度变换较常用的方法是线性尺度变换。现行尺度变换的公式如下：F’=aF+b，式中F-原适应度；F’-变换后的适应度；适a和b-系数。系数a、b直接影响到这个尺度变换的大小一般希望它们满足两个条件：应条件一：

8、尺度变换后全部个体的新适应度的平均值F’要avg等于其原适应度平均值F，即：F’=F。这条要求是为了度avgavgavg保证群体中适应度接近于平均适应度的个体能够有期待的数量函被遗传到下一代中。条件二：尺度变换后群体中新的最大适应度F’要等于其max原平均适应度F的指定倍数，即：F’=C*F.式中C为最数avgmaxavg佳个体的期望复制数量，对于群体大小为50~100的情况，一般取C