遗传算法的实现和应用举例

《遗传算法的实现和应用举例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六节算法实现及应用一、算法实现遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定问题编码方案确定适配值函数设计遗传算子（选择、交叉、变异）确定算法参数确定算法终止条件生成初始种群SGA实现①个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所

2、有个体的适应度必须为正数或0，不能是负数。为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：对于目标函数是求极大化，方法为：式中，为一个适当地相对比较小的数它可用下面几种方法之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。②比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(RouletteWheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；

3、其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。③单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。④基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率指定其为变异点；对每

4、一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。简单演示问题：求（1）编码：编码长度为5（2）初始群体生成：群体大小设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度函数：（4）轮盘赌选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择11000和01101交配产生下一代（5）交叉操作：发生交叉的概率取大交叉点位置的选取

5、是随机的（单点交叉）01101011001100011001（6）变异：发生变异的概率取小改变某个字节1100111101（7）新群体的产生：保留上一代最优个体，1个新个体取代旧个体11101，11000，01000，10011（8）重复上述操作20次，或许就能够得到最优解！应用实例：TSP问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学描述给定图G=(V,E),V为顶点集,E为边集，确定一条长度最短的Hamilton回路TSP问题问题复杂度:指数增长的！(

6、NP完全问题)12个城市，具有39916800条不同的路径。一条路径对应一个排列！交叉算子传统的交叉算子可能产生无效路径。交叉算子（1）基于位置的交叉把一个父代在向量上的被选元的位置强加到另一个父代。父代1：12345678910父代2：59246110738所选位置：****子代1：19236457810子代2：92345618107交叉算子（2）部分映射交叉利用父代所选段内元的对应定义子代。父代1：26438151079父代2：85110762439子代1：51437621089子代2：72610815439变异算子起双重作用：1、提

7、供和保持群体的多样性；2、搜索算子的作用。(1)基于位置的变异：随机选择两个元，然后把第二个元放在第一个元之前；(2)基于次序的变异：随机选择两个元，然后交换他们的位置；(3)打乱变异：随机选择一段，然后打乱这段内的次序。编码方案路径表达：对一个旅行最自然的表达一个旅行5—>1—>7—>8—>9—>4—>6—>2—>3的编码就是（517894623）编码空间和解空间一一对应，总量为n!个？其实一些解是相同的，因为（51789

8、4623）=（4623

9、51789）二者是同一个解(n-1)!/2应用实例1：TSP适应度函数就取为目标函数的倒数

10、，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定......p1p2pir选择操作算子:轮盘式选择首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇