《基本遗传算法讲的很好很透彻学习亲测 资料》由会员分享，可在线阅读，更多相关《基本遗传算法讲的很好很透彻学习亲测 资料（56页珍藏版）》请在金锄头文库上搜索。
1、基本遗传算法 基本遗传算法 GA 1 基本遗传算法描述基本遗传算法描述 遗传算法在自然与社会现象模拟 工程计算等方面得到了广泛应用 在各个遗传算法在自然与社会现象模拟 工程计算等方面得到了广泛应用 在各个 不同的应用领域 为了取得更好的结果 人们对不同的应用领域 为了取得更好的结果 人们对GA进行了大量改进 为了不至进行了大量改进 为了不至 于混淆 我们把于混淆 我们把Holland提出的算法称为基本遗传算法 简称提出的算法称为基本遗传算法 简称 GA SGA Simple Genetic Algorithm CGA Canonical Genetic Algorithm 将其它 将其它 的
2、的 GA类 算法称为类 算法称为GAs Genetic Algorithms 可以把可以把GA看作是看作是GAs的一种特的一种特 例 例 1 1 基本遗传算法的构成要素基本遗传算法的构成要素 1 染色体编码方法染色体编码方法 基本遗传算法使用基本遗传算法使用固定长度的二进制符号串固定长度的二进制符号串来表示群体中的个体 其等位基来表示群体中的个体 其等位基 因由二值符号集因由二值符号集 0 1 组成 组成 初始群体中各个个体的基因值用均匀分布的随机数来生成 如 初始群体中各个个体的基因值用均匀分布的随机数来生成 如 x 100111001000101101 就可表示一个个体 该个体的染色体长度
3、是就可表示一个个体 该个体的染色体长度是 l 18 2 个体适应度评价个体适应度评价 基本遗传算法基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传按与个体适应度成正比的概率来决定当前群体中每个个体遗传 到下一代群体中的机会多少 到下一代群体中的机会多少 为正确计算这个概率 这里要求所有个体的适应为正确计算这个概率 这里要求所有个体的适应 度必须为正数或零 这样 根据不同种类的问题 必须预先确定好由目标函数度必须为正数或零 这样 根据不同种类的问题 必须预先确定好由目标函数 值到个体适应度之间的转换规则 特别是要预先确定好当目标函数值为负数时值到个体适应度之间的转换规则 特别是
4、要预先确定好当目标函数值为负数时 的处理方法 的处理方法 3 遗传算子遗传算子 基本遗传算法使用下述三种遗传算子 基本遗传算法使用下述三种遗传算子 选择运算 使用选择运算 使用比例选择算子比例选择算子 交叉运算 使用交叉运算 使用单点交叉算子单点交叉算子 变异运算 使用变异运算 使用基本位变异算子基本位变异算子 4 基本遗传算法的运行参数基本遗传算法的运行参数 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定 个运行参数需要提前设定 M 群体大小 即群体中所含个体的数量 一般取为 群体大小 即群体中所含个体的数量 一般取为20 100 T 遗传运算的终止进化代数 一般取为 遗传运算
5、的终止进化代数 一般取为100 500 pc 交叉概率 一般取为 交叉概率 一般取为0 4 0 99 pm 变异概率 一般取为 变异概率 一般取为 0 0001 0 1 说明说明 这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响 但目前个运行参数对遗传算法的求解结果和求解效率都有一定的影响 但目前 尚无合理选择它们的理论依据 在遗传算法的实际应用中 往往需要经过多次试尚无合理选择它们的理论依据 在遗传算法的实际应用中 往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围 算后才能确定出这些参数合理的取值大小或取值范围 1 2 基本遗传算法的形式化定义基本遗传算法的形式
6、化定义 基本遗传算法可定义为一个基本遗传算法可定义为一个7元组 元组 GA M F s c m pc pm M 群体大小 群体大小 F 个体适应度评价函数 个体适应度评价函数 s 选择操作算于 选择操作算于 c 交叉操作算子 交叉操作算子 m 变异操作算于 变异操作算于 pc 交叉概率 交叉概率 pm 变异概率 变异概率 1 3 基本遗传算法描述基本遗传算法描述 Procedure GA Begin initialize P 0 t 0 while t T do for i 1 to M do Evaluate fitness of P t end for for i 1 to M do Se
7、lect operation to P t end for for i 1 to M 2 do Crossover operation to P t end for for i 1 to M do Mutation operation to P t end for for i 1 to M do P t 1 P t end for t t 1 end while end 2 基本遗传算法的实现基本遗传算法的实现 根据上面对基本遗传算法构成要素的分析和算法描述 我们可以很方便地用计根据上面对基本遗传算法构成要素的分析和算法描述 我们可以很方便地用计 算机语言来实现这个基本遗传算法 算机语言来实现
8、这个基本遗传算法 现对具体实现过程中的问题作以下说明 现对具体实现过程中的问题作以下说明 2 1 编码与解码编码与解码 1 编码编码 假设某一参数的取值范围是假设某一参数的取值范围是 umin umax 用长度为 用长度为l的二进制编码符号串来表的二进制编码符号串来表 示该参数 则它总共能够产生示该参数 则它总共能够产生 2l种不同的编码 参数编码时的对应关系如下 种不同的编码 参数编码时的对应关系如下 00000000 00000000 0 umin 00000000 00000001 1 umin 00000000 00000010 2 umin 2 11111111 11111111 2
9、l 1 umax x umin bi 2i 1 1 1 i l Umax umin 2l 1 其中 其中 为二进制编码的编码精度 其公式为 为二进制编码的编码精度 其公式为 Umax umin 2l 1 2 解码解码 假设某一个体的编码是 假设某一个体的编码是 x bl lbl l 1 bl l 2 b2b1 则对应的解码公式为 则对应的解码公式为 例例 设设 3 0 x 12 1 精度要求精度要求 1 10000 由公式 由公式 Umax umin 2l 1 1 10000 12 1 3 0 1 151001151001 即 即 217 151001 0 0 if f X Cmin 0 F
10、X Cmax f X if f X Cmax 0 if f X Cmax 2 3 比例选择算子比例选择算子 1 选择算子或复制算子的作用 选择算子或复制算子的作用 从当前代群体中选择出一些比较优良的个体 并将其复制到下一代群体中 从当前代群体中选择出一些比较优良的个体 并将其复制到下一代群体中 2 最常用和最基本的选择算子最常用和最基本的选择算子 比例选择算子 比例选择算子 3 比例选择算子 比例选择算子 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比 4 执行比例选择的手段是轮盘选择 执行比例选择的手段是轮盘
11、选择 轮盘法的基本精神是 个体被选中的概率取决于个体的相对适应度 轮盘法的基本精神是 个体被选中的概率取决于个体的相对适应度 pi fi fi i 1 2 M 式中式中 pi 个体个体i被选中的概率 被选中的概率 fi 个体个体i的适应度 的适应度 fi 群体的累加适应度 群体的累加适应度 显然 个体适应度愈高 被选中的概率愈大 但是 适应度小的个体也有可显然 个体适应度愈高 被选中的概率愈大 但是 适应度小的个体也有可 能被选中 以便增加下一代群体的多样性 能被选中 以便增加下一代群体的多样性 轮盘选择的原理 轮盘选择的原理 图中指针固定不动 外圈的圆环可以图中指针固定不动 外圈的圆环可以
12、自由转动 自由转动 圆环上的刻度代表各个个圆环上的刻度代表各个个 体的适应度 当圆环旋转若干圈后停止 体的适应度 当圆环旋转若干圈后停止 指针指定的位置便是被选中的个体 指针指定的位置便是被选中的个体 从统计意义讲 适应度大的个体 其从统计意义讲 适应度大的个体 其 刻度长 被选中的可能性大 反之 适刻度长 被选中的可能性大 反之 适 应度小的个体被选中的可能性小 但有应度小的个体被选中的可能性小 但有 时也会被 破格 选中 时也会被 破格 选中 上述轮盘选择过程 可描述如下 上述轮盘选择过程 可描述如下 顺序累计群体内各个体的适应度 得相应的累计值顺序累计群体内各个体的适应度 得相应的累计值
13、Si 最后一个累计值为 最后一个累计值为Sn 在在 0 Sn 区间内产生均匀分布的随机数区间内产生均匀分布的随机数r 依次用依次用Si与与r比较 第一个出现比较 第一个出现Si大于或等于大于或等于r的个体的个体j被选为复制对象 被选为复制对象 重复重复 项 直至新群体的个体数目等于父代群体的规模 项 直至新群体的个体数目等于父代群体的规模 轮盘选择示例轮盘选择示例 2 4 单点交叉算子单点交叉算子 1 交叉算子作用交叉算子作用 通过交叉 子代的基因值不同于父代 交换是遗传算法产生新个体的主要手段 通过交叉 子代的基因值不同于父代 交换是遗传算法产生新个体的主要手段 正是有了交换操作 群体的性态
14、才多种多样 正是有了交换操作 群体的性态才多种多样 2 最常用和最基本最常用和最基本 单点交叉算子 单点交叉算子 3 单点交叉算子的具体计算过程如下 单点交叉算子的具体计算过程如下 对群体中的个体进行两两对群体中的个体进行两两随机随机配对 配对 若群体大小为若群体大小为M 则共有 则共有 M 2 对相互对相互 配对的个体组 配对的个体组 每一对相互配对的个体 每一对相互配对的个体 随机随机设置某一基因座之后的位置为交叉点 设置某一基因座之后的位置为交叉点 若染色体的长度为若染色体的长度为l 则共有 则共有 l 1 个可能的交个可能的交叉点位置 叉点位置 对每一对相互配对的个体 依设定的交叉概率
15、对每一对相互配对的个体 依设定的交叉概率pc在其在其交交叉点处相互交换两个个叉点处相互交换两个个 体的部分染色体 从而产生出两个新的个体 体的部分染色体 从而产生出两个新的个体 单点交叉运算的示单点交叉运算的示例例如下所示如下所示 单点交叉单点交叉A 10110111 00 A 10110111 11 B 00011100 11 B 00011100 00 交叉概率交叉概率 pc Mc M 式中式中 M 群体中个体的数目 群体中个体的数目 Mc 群体中被交换个体的数目 群体中被交换个体的数目 交叉操作示例交叉操作示例 交叉的个体是随机确定的 如下表所示 某群体有交叉的个体是随机确定的 如下表所
16、示 某群体有n个个体 每个个体含个个体 每个个体含8 个等位基因 针对每个个体产生一个个等位基因 针对每个个体产生一个 0 1 区间的均匀随机数 假设交叉概率区间的均匀随机数 假设交叉概率 pc 0 6 则随机数小于 则随机数小于0 6的对应个体与其随机确定的另一个个体交叉 交叉的对应个体与其随机确定的另一个个体交叉 交叉 点随机确定 点随机确定 个体编号个体编号个体个体随机数随机数交叉操作交叉操作新个体新个体 1110110000 72811011000 2101010110 589101010 11101010 01 3001011000 67800101100 4100011010 801100011 01100011 11 2 5 基本位变异算子基本位变异算子 基本位变异算子是最简单和最基本的变异操作算子 基本位变异算子是最简单和最基本的变异操作算子 对于基本遗传算法中用二进制编码符号串所表示的个体 若需要进行变异操作对于基本遗传算法中用二进制编码符号串所表示的个体 若需要进行变异操作 的某一基因座上的原有基因值为的某一基因座上的原有基因值为0 则变异操作将该基因值变为 则变异
