遗传算法的研究与应用
- 格式：pdf
- 大小：244.43 KB
- 文档页数：4
维普资讯
研 究 与 开 发
圈圆圈画 圜国国
徐 清振 ， 肖成林
（， 南师范 大学计 算机学 院 。 １华 广州 ５０ ３ ； ． １６ ｌ ２ 华南 理工 大学应用 数学 系 ， 广州 ５０４ ） １６０
摘 要 ： 据遗传 算法 的一 些基本概 念以度 遗传 算法的操 作 流程 ， 遗传算 法的繁 殖算 子从数 学上给 出 根 对
体 的选 择 、 叉和变 异 ， 中编码 是最重 要的环 节。 交 其
Ａ筹 ． 『’ 。 Ｉ ＝ －２ ｎ １． …
唯一对 应着一个 实数 葺， 可按式 （ ） ２ 计算 ：
Ｘ＝０１ ＝ ｌ －（
，
（ １ 】
现 代 （） ２ 计
于是对 任何 研 长 的 ０ ｌ 符 串 Ａ ＝ ｉ －— ｌ －字 ｂ ｒ ｂ， ｎ
设 （ ｌ …， ， ［ 蜘， １２ … ，， ｘ ，２ ）鹭苣 日 ＝ ， 。 ｎ 给 Ｘ， ｎ 定 精度 为 ８则取 ｍ 是满 足式 （） ， １ 的最小整数 。
几位 的组 合称 为一个基 因 。 叉称染 色体 。然后 再对这
些染 色体 进行某 些操作 实现参数 寻优 。 遗传算 法 中的 基本概 念包括染 色体 的编码 、 数 、 应度 函数 、 色 参 适 染
维普资讯
研究与 开发
其 中 ｅ Ａ） （ 为一 实数 。
因此 ， 编码 ｅ 是一种有效的编码 ， 但它不是正则
编码 ．因为对 ｎ 空 间里 的不 同 向量可 以对应着 相 同
的编 码 串 。
被选中的概率就越大 ， 其子孙在下一代产生的个数就 越多。 选择 的方法 根据不 同的 问题 ， 用不 同的方案 。 采 最常见的方法有比ቤተ መጻሕፍቲ ባይዱ法 、 排列法和比率排列法 。比侧
定叉， 刻划 了繁 殖 算子的 本质 。遗 传算 法是一 种基 于概 率意 义上 的随机搜 索算法 ， 它是从 空 但
同上 的一组 点而 不是一 个点 出发 。 因此 遗传 算法 的搜 索能 力比其他 随机 搜 索算 法更 强 ． 以找 可
到 全局 范围 内的 最优 解。但是 。 应该 注意在 遗传 算法的 应用 中． 避免 其过早 的收 敛 ． 止陷入 要 防
赖性 很小 ． 用范 围广 应
遗 传算法 的编码种类 很多 ． 常见的是 二进 制编 最 码 和实数编码 。
③ 全局性 和稳健性 。 传算法是 一种求解 全局最 遗
①二进制编码就是以二进制字符 Ｏ和 １ 为等位
基 因的定长字符 串编码 ， 目前遗 传算法采 用最 广泛 是 的编码方 式 。 例：
个 体 编码 ｅ 是从 到 ｎ 的一 个 映射 ， 得 对 就 使
ＶＡ∈凰 ， 了唯 一 的 ｘ＝ （ ∈ｎ 与 之对 应 ， 里 Ｘ ｅ Ａ） 这 称 为 的解码 。这里 玩 ＝ ＝ ｌ ， 毗： ｉ ＝ ， ｛ 日 ２ ， ａ∈Ｆ， １２， ａｏ
…
，
ｌ 是个体 空间 ， ｛ （ １ ２… 。 ｌ ｎ＝ ｘ ， ， ％）∈ 是待求 Ｘ
优解 的有效算 法 ， 它使用概 率搜索 机制。 ④ 简单和 可操作性 。
遗传 算法 的 基本思 想 是先将 优 化 问题 的一组 基
本可 行解（， ｉ ｉ ｘ ｙ ｚ 编码 为一组 二进 制 的字符 串 。 ｉ ，） 每个
字符 串包含 多个子 字符串 ， 每个 子字符 串 的某 一位 或
型和排序 型选 择算子 是 目前 使用 最多 的选择算子 ， 因 此 这里 只介绍 这两类选 择算 子 。 ① 比例型
比例 型选 择算子 有很 多种 ， 择算 子轮 盘赌转 盘 选
二 进制 编码 虽 然具有 形 式 直观 ， 简单 ， 易操 作 等 适 合遗传操 作 的特 点 ， 但有一 个突 出 的问题是 它破 坏 了解空 间的拓扑连 续性 。 如整数 ７和 ８在整数 空间 例
・ 本课 题得到 国 家 自然科 学基金 （０ ７ ０ ３ 资助 。 ６２３ ６ ）
令 Ｌ＝ Ｉ …＋ ，则对任 何 Ｌ 的 ０ １ ｍ＋ 啦＋ ％ 长 － 字符
串 Ａ∈｛， ｝ 可按式 （ ） 示 ： Ｏ ｌ， ３表
Ａ－ ， Ｖ … ＶＡ ＝ Ｖ Ａ
算
机
＾
总
… … －・ ｚ （ ） ｒ・ １ ３
＝ 乜ｍ １ ｌ 乜 ． １ － １ …厶
第
二
＝
一
解 码 见 式 （ ） ４：
日 （ ＝ 日 （ ）日 ’ ） ・ ｅ ） 一 ） （ 一 １ 。 Ｉ ． （ 一． （ ） （） ４
五
期
ＭＤＲ Ｃ ＰＴ ０ ｏ ＯＥＮ Ｏ Ｕ Ｒ ６ Ｍ Ｅ２ ． ０５
岛 ） ／￣ －ｉ ｂ． １
ｌ 编 码
编码就是把 一个问题 的可行 解从 其解空间转换 到 遗传算法能处理的搜索空间的转化方法 。 遗传算法不是 对待求解 问题 的实际优化变量直接操作 ． 而是对 编码后 的个体做选择与繁殖运算 。 通过这些反复运算达到优 化 目标。 因此 ， 是遗传算法解决问题的先决条件 ， 编码 一个 好 的个体编码往往是算法性能的重要条件 。
局部 最优 解。
关键 词 ： 传算 法； 遗 编码 ； 选择 （ｅ ｃｏ ） Ｓ ｌ ｔ ｎ 算子 ；交叉算子 ｅｉ
引 言
遗 传算 法本 质上 是 一种基 于 概率 的随机 搜 索 算 法， 总结 起来 ， 它具有 如下特点 【 ｌ １ ：
④并 行性 。遗传算 法是从 多个 点出发并 行操 作 ．
采用群体搜索策略 ． 可以有效地防止搜索过程收敛于
局 部最优解 。
解 问题 的可行解 空间 。
如 果对 Ｖ ∈ ｎ，都有 唯一 的一个个 体 Ａ∈日 与
之对应 ， 称编码 ｅ 正则 的。 则 是
②通 用性 。 传算法通 过 目标 函数计算个 体适 应 遗 度值， 而不 需要 其他 的 推导 和附 加信 息 。 问题 的依 对
研 究 与 开 发
圈圆圈画 圜国国
徐 清振 ， 肖成林
（， 南师范 大学计 算机学 院 。 １华 广州 ５０ ３ ； ． １６ ｌ ２ 华南 理工 大学应用 数学 系 ， 广州 ５０４ ） １６０
摘 要 ： 据遗传 算法 的一 些基本概 念以度 遗传 算法的操 作 流程 ， 遗传算 法的繁 殖算 子从数 学上给 出 根 对
体 的选 择 、 叉和变 异 ， 中编码 是最重 要的环 节。 交 其
Ａ筹 ． 『’ 。 Ｉ ＝ －２ ｎ １． …
唯一对 应着一个 实数 葺， 可按式 （ ） ２ 计算 ：
Ｘ＝０１ ＝ ｌ －（
，
（ １ 】
现 代 （） ２ 计
于是对 任何 研 长 的 ０ ｌ 符 串 Ａ ＝ ｉ －— ｌ －字 ｂ ｒ ｂ， ｎ
设 （ ｌ …， ， ［ 蜘， １２ … ，， ｘ ，２ ）鹭苣 日 ＝ ， 。 ｎ 给 Ｘ， ｎ 定 精度 为 ８则取 ｍ 是满 足式 （） ， １ 的最小整数 。
几位 的组 合称 为一个基 因 。 叉称染 色体 。然后 再对这
些染 色体 进行某 些操作 实现参数 寻优 。 遗传算 法 中的 基本概 念包括染 色体 的编码 、 数 、 应度 函数 、 色 参 适 染
维普资讯
研究与 开发
其 中 ｅ Ａ） （ 为一 实数 。
因此 ， 编码 ｅ 是一种有效的编码 ， 但它不是正则
编码 ．因为对 ｎ 空 间里 的不 同 向量可 以对应着 相 同
的编 码 串 。
被选中的概率就越大 ， 其子孙在下一代产生的个数就 越多。 选择 的方法 根据不 同的 问题 ， 用不 同的方案 。 采 最常见的方法有比ቤተ መጻሕፍቲ ባይዱ法 、 排列法和比率排列法 。比侧
定叉， 刻划 了繁 殖 算子的 本质 。遗 传算 法是一 种基 于概 率意 义上 的随机搜 索算法 ， 它是从 空 但
同上 的一组 点而 不是一 个点 出发 。 因此 遗传 算法 的搜 索能 力比其他 随机 搜 索算 法更 强 ． 以找 可
到 全局 范围 内的 最优 解。但是 。 应该 注意在 遗传 算法的 应用 中． 避免 其过早 的收 敛 ． 止陷入 要 防
赖性 很小 ． 用范 围广 应
遗 传算法 的编码种类 很多 ． 常见的是 二进 制编 最 码 和实数编码 。
③ 全局性 和稳健性 。 传算法是 一种求解 全局最 遗
①二进制编码就是以二进制字符 Ｏ和 １ 为等位
基 因的定长字符 串编码 ， 目前遗 传算法采 用最 广泛 是 的编码方 式 。 例：
个 体 编码 ｅ 是从 到 ｎ 的一 个 映射 ， 得 对 就 使
ＶＡ∈凰 ， 了唯 一 的 ｘ＝ （ ∈ｎ 与 之对 应 ， 里 Ｘ ｅ Ａ） 这 称 为 的解码 。这里 玩 ＝ ＝ ｌ ， 毗： ｉ ＝ ， ｛ 日 ２ ， ａ∈Ｆ， １２， ａｏ
…
，
ｌ 是个体 空间 ， ｛ （ １ ２… 。 ｌ ｎ＝ ｘ ， ， ％）∈ 是待求 Ｘ
优解 的有效算 法 ， 它使用概 率搜索 机制。 ④ 简单和 可操作性 。
遗传 算法 的 基本思 想 是先将 优 化 问题 的一组 基
本可 行解（， ｉ ｉ ｘ ｙ ｚ 编码 为一组 二进 制 的字符 串 。 ｉ ，） 每个
字符 串包含 多个子 字符串 ， 每个 子字符 串 的某 一位 或
型和排序 型选 择算子 是 目前 使用 最多 的选择算子 ， 因 此 这里 只介绍 这两类选 择算 子 。 ① 比例型
比例 型选 择算子 有很 多种 ， 择算 子轮 盘赌转 盘 选
二 进制 编码 虽 然具有 形 式 直观 ， 简单 ， 易操 作 等 适 合遗传操 作 的特 点 ， 但有一 个突 出 的问题是 它破 坏 了解空 间的拓扑连 续性 。 如整数 ７和 ８在整数 空间 例
・ 本课 题得到 国 家 自然科 学基金 （０ ７ ０ ３ 资助 。 ６２３ ６ ）
令 Ｌ＝ Ｉ …＋ ，则对任 何 Ｌ 的 ０ １ ｍ＋ 啦＋ ％ 长 － 字符
串 Ａ∈｛， ｝ 可按式 （ ） 示 ： Ｏ ｌ， ３表
Ａ－ ， Ｖ … ＶＡ ＝ Ｖ Ａ
算
机
＾
总
… … －・ ｚ （ ） ｒ・ １ ３
＝ 乜ｍ １ ｌ 乜 ． １ － １ …厶
第
二
＝
一
解 码 见 式 （ ） ４：
日 （ ＝ 日 （ ）日 ’ ） ・ ｅ ） 一 ） （ 一 １ 。 Ｉ ． （ 一． （ ） （） ４
五
期
ＭＤＲ Ｃ ＰＴ ０ ｏ ＯＥＮ Ｏ Ｕ Ｒ ６ Ｍ Ｅ２ ． ０５
岛 ） ／￣ －ｉ ｂ． １
ｌ 编 码
编码就是把 一个问题 的可行 解从 其解空间转换 到 遗传算法能处理的搜索空间的转化方法 。 遗传算法不是 对待求解 问题 的实际优化变量直接操作 ． 而是对 编码后 的个体做选择与繁殖运算 。 通过这些反复运算达到优 化 目标。 因此 ， 是遗传算法解决问题的先决条件 ， 编码 一个 好 的个体编码往往是算法性能的重要条件 。
局部 最优 解。
关键 词 ： 传算 法； 遗 编码 ； 选择 （ｅ ｃｏ ） Ｓ ｌ ｔ ｎ 算子 ；交叉算子 ｅｉ
引 言
遗 传算 法本 质上 是 一种基 于 概率 的随机 搜 索 算 法， 总结 起来 ， 它具有 如下特点 【 ｌ １ ：
④并 行性 。遗传算 法是从 多个 点出发并 行操 作 ．
采用群体搜索策略 ． 可以有效地防止搜索过程收敛于
局 部最优解 。
解 问题 的可行解 空间 。
如 果对 Ｖ ∈ ｎ，都有 唯一 的一个个 体 Ａ∈日 与
之对应 ， 称编码 ｅ 正则 的。 则 是
②通 用性 。 传算法通 过 目标 函数计算个 体适 应 遗 度值， 而不 需要 其他 的 推导 和附 加信 息 。 问题 的依 对
