一种用于求解TSP问题的遗传交换操作

计算机研究与发展 年第 期 一种用于求解 问题的遗传 交换操作 尚 奕 唐志敏 中国科学院计算技未研究所国家智能机研究开发中心 , 北京 , 。。。 。, 摘要 遗传葬法作为一种通 用随机搜索葬法 , 在函数优化 、 机器学习等许多方 面获 得 了很好的结果 。 但是 , 常规的遗传操作对于有序问题效果不理想 。 本文分析 了一种典 型的有序问题 —旅行售货员问题 , 根据其特 点并结合遗传葬法的模式理论 , 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出一 个新的启发式遗传交换操作 。 理论分析和实验结果显示这种文换操作的效果大大好于较 通用的有序交换操作 , 也优于 的贪心方法 关键词 遗传算法 , 问题 , 交换操作 。 去 已 遗传算法是一种通用的自适应随机搜索算法 , 在函数优化 、 神经网络 、 自适应控制和机器学 习等许多领域得到了研究与应用 。 遗传算法适宜于搜索高维 、 多局部极值 、 不连续及含噪音的复 杂问题空间 。 在〔 〕中给出了遗传算法的理论基础 , 指出许多复杂结构可以用简单 的位串形式编码表示 , 而且通过一些简单的变换能够逐步改进这些位串结构 , 使之向所需要的形 式转变 。 遗传算法就是实现结构的进化 。 它先将问题的解表示成字符串形式 , 然后通过不断修改 字符串结构 , 来试验不同的解 , 搜索解空间 , 最终得到满足需要的解 只要搜索空间存在某种规律性 , 遗传算法就能在较有限的搜索中去寻找规律 , 一 利用搜索中获 得的信息进行明智的搜索 。 复杂结构中的规律较难被发现 。 将复杂结构表示成简单的 位 串 形 式 后 , 往往就容易发现规律了 。 评价函数是遗传算法与间题的接口 , 对遗传算法的收敛速度和结果 影响很大 。 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化方法是根据搜素空间中点的原始优劣情况计算评价函数值的方法 , 因而遗传算 法的性能对规范化方法的优劣很敏感 。 如果规范化方法过分强调当前的较优点 , 就会很快降低集 合中点的多样性 , 使算法过早收敛 而如果对当前较优点强调不够 , 算法就很容易丢失已找到的 较优点的信息 , 从而不能在合理的时间内收敛到较好的点 。 遗传操作是实现算法的信息遗传 、 优 胜劣汰思想的关键 对于不同类型的问题 , 同样的遗传操作的效果不同 。 通用遗传操作是以效率 换取通用性 , 对特定问题的效率往往不高 。 有效地利用了问题域知识的启发式遗传操作能大大改 善搜索效率 〔名 , 。, 。, ·, 遗传算法求解的问题可分为两类 一类是值问题 。 这种问题的解表示为字符串形式后 , 串中 各位置的取值互不影响 , 解空间 即字符串空间 是串中各位置取值范围的笛卡尔积 。 另一类是有 序问题 。 这种间题解的字符串表示中 , 各位置取值互相影响 。 值向题已经得到较深人的研究 , 得 出了效果较好的遗传操作 。 对有序问题的研究开展不久 , 遗传算法的应用效果不太理想 。 旅行售 文于 , 年 月收到 。 本项研究得到国家 高技术 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 的支持 。 尚 鹅 , 了年生 , 牟毕业于中国科技大学少年 班 份算机蕊 〕, , 年在中国科学 院 计算技术研究所获硕士学位 。 研究兴肠集中于人工智能 、 井行处理和体系结构 。 右志位 , 年生 , , 年毕业于南京大学计算机系 , 。年在中国科学院计算技术研究所获博士单位 。 目前研究兴幼包括并行计算 、 体系给构 、 设计和神经网络 。 货员问题 是典型的有序问题 。 很容易描述 在有 个点的完全图中找出最短的哈密顿 回路 。 是 一 问题 , 很可能没有多项式时间的求解算法 。 人们设计了多种遗传交换操 作来求解之 〔 , ”’ ’, 效果均不太好 。 本文设计了一种新的启发式遗传交换操作 , 效果优于已有类 似的遗传交换操作 〔‘ ’。 二 、 问 题 表 示 遗传算法先将问题的解表示成字符串形式 , 在运算过程中保持一个集合的解 。 算法典型执行 过程是 二 。, 选取 个解构成初始解集 。 , 。, · · 二 , 。子。 计算解集里每个解的评价函数 , , ‘ 二 也 。 ‘ 当不满足算法终止条件时 依选择概率 ‘ , 二 二 , 从解集 产生解集 幻 对 十 中的解进行遗传重组操作 比如交换 , 突变 。 什算 中的解的评价函数值 。 二 提出了“模式 ” 概念 , 对算法的本质和性能进行了较精确的刻划 。 每个模 式是解空间的一个子集 , 每个解又是许多模式的实例 。 遗传算祛在一次试脸 对一个解进行遗传 操作 中 , 就对许多模式进行了操作 , 这就是遗传算法的“ 内在并行性 ” 。 解集里的解以正比于其 优劣的速度产生后代 , 各个模式在解集里的实例个数按照其所观察到的性能成指数关系地增加或 减少 , 使解集中解的结构逐渐接近最优 。 我们用排列法表示 的解 , 即 · 个城市代号的任意一种排列就表示 的一个解 。 所考 虑的模式是有序模式 ’。 , 。 定义一阶棋式为固定回路的一边的模式 , 形如 ⋯ ⋯ , 即只 有两个连续位置不是不关心字符 固定多条边的模式称为高阶模式 。 好的与差的模式的选 择 概 率的差别应较大 , 亦即其所观察到的评价函数值应有明显的相对差 , 算法的性能才好 。 下面的定 理表明 , 如果直接便用回路的长度 作为评价函数值 , 即对于解 一 , ⋯ 。 , ‘ 十 十 ⋯ 卜 , 其中 表示 与 之间的路径长度 , 那么不同的一阶模式的评价函数值 差别很小 。 此定理是对【 〕中定理的推广 。 定理 对于欧几里德平面上的 问题 , 、 和 。 是两个一阶模式 , 那么 、 一 其中 和 分别表示边 和 的长度 , 表示 · 的性能 , 且所有边的 长度是对称的 , 即 一 证明 如能设计从 、 中的囿路到 ‘ 。 中的回路的一一 映 射 , 使得 任 、 , 中 〔 “ , 且 一 ‘ 魂 , 则定理得证 。 下面构造映射 。 卜 二 ⋯ , 一 一 ‘ 一 ⋯ 二 甲 ⋯ ⋯ , 。 ⋯里 。卜 二 是通过互换 中的 与 。、 与 得到的 。 一 二 “ 。 ‘ 一 比 翔 “ 。 由三角不等式 , 得 一 , , 一 成 , , 一 蕊 。 , ‘一 。蕊 , 一 簇 , 。一 簇 ’ 」 一 《 一 而 毛 簇 一卜 一 蕊 十 同法可得 一 蕊 ’ 工 一 】簇 口 回路的长度一般说来比定理中的界限 十 大得多 , 远大于这一界限 , 因而所观 察到的一阶模式的性能无 明显不同 , 遗传选择概率没什么差别 。 所以 , 简单地把回路的长度作为 评价函数值会使算法收敛极慢 。 实验也 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 了这一点 。 因而有必要采用规范化方法来计算合适的 评价函数值 。 下面是两种规范化方法 。 最大值规范 用当前解集中的最大回路长度 减去每个解的回路长度 , 得到每个解的评价函数值 一 , 即 一 遗传选择概率 , 二 艺界 , 。 表 是用此方法求解 个城市 的 的结果 这问题的最优解是 ‘。 。 解集的大小是 。 采用有序遗传交换操作 。 , 这是 目前对于有序问题效果较好的一种通用交换操作 。 投有使用突变操作 。 算法终 止标谁是解集中的最小回路长度 与平均回路长度 的比 簇 。 。 算法 的收敛时 间比较长 。 当解集更大时 , 收敛时间会更长 。 原因之一是这种规范化方法仍不能使优 、 劣模式的 评价函数值有较大的相对差别 , 不能给较优模式以足够偏置 。 平方最大值规范 加强对解集中较优解的偏置 , 能加速算法的收敛 。 此方法计算评价函数值的方法是 一 ’。 此法的收敛速度较快 , 但收敛值较差 。 算法搜索过程中发生了过早收敛 ’ 用 于 计算前面 个城市的问题 , 解集的大小是 , 结果见表 。 表 收敛时间 收 敛 值 收敛时间 收 敛 值 自,工,曰,翻沪匀,住协﹃﹄。 。 代 代 代 扣一一⋯ 三 、 启发式遗传交换操作 对于 , 使用有序交换操作的遗传算法收敛较慢 从前 面例子也可看出 , 是因为遗传选 择阶段不能使较好的模式有合适的 、 较大的选择概率 。 这时 , 可以设计启发式遗砖重组操作 , 在 遗传操作中适当增加对较优模式的偏置 。 遗传重组操作在遗传算法中是很关键的 , 对算法收敛速 度及收敛值影响很大 。 为设计启发式交换操作 , 先研究一阶模式的性舱 。 假设城市数是 , 城市之间的路径长度是 私 , 二 ⋯ , , 为对称连接 , 私‘二 。 对于一阶模式 二 卜 二 ⋯ , 的性能就是固定 连接后 , 所有不同回路长度的平均 值 。 经过 边的不同回路有 一 里条 , 每条回路包括 边 。 两 条 边 和 , 。, 〔 一 , 。一 是除 和 两点外 一 个点的集合 。 一 条边 , , 〔 , 一 。 对于 〔 。一 , 经过 边的不同回路数是 一 。 同样 , 对 〔 一 , 经过 的不同回路 数 也 是 一 。 对于 , 〔 一 , , 尹 , 经过边 的不同回路数是 一 。 这样 , 经过 边的 一 条不同回路的长度总和是 甘 一 , 二 、一 一 · 艺 一 。曲 一 通一 一 一 乙 , , , 几 , 一 一 其 中 。 表示 卜 中的点构成的所有不同边的 一 长度和 。 、 吧 一 平均回路长度 , 一 一 条不同回路之和 一 洛 ‘ 丫 于二 十 —一 朴 一 艺 兄 叭 十 兄 ‘ 一 者 飞十 — ’一 ’ 称 一 , 元 , 亏‘ 一吕 对此式略作变换 儿 一 、 钾 , 、 , 口’“ 一 火不二厄 ,‘ 一百二万念 、 ’‘十 “ , ’卞 下二厄七 ” · 最后一项对于所有的一阶模式是一样的 , 选择前两项作为判别项 臼 。 , 一 、 二 , 一 一 , , 。 任‘ 。 较优的模式具有较小的 值 , 有较大的口值 。 通过比较口值的大小就可以得出一阶模式 的 优 劣 。 以此为基础设计了增加较优模式实例数 目的启发式遗传交换操作 — 。 一 。 。 这个交换操 作从两个父本构造后代的方法是 随机选择一个城市作为后代的起始城市 比较两父本中与此城 市相连的四条路 , 选择有最大 口 值的路 , 且路的另一端城市未在后代中出现过 , 则另一 端 的 城 市作为后代中的下一城市 。 如果父本中的相关的四个城市都在后代中出现过 , 则随机选择一个未 在后代中出现过的城市作为后代的下一城市 然后以下个城市作为出发点 , 继续扩展 , 直至产生 经过所有城市的回路 。 一 与 的贪心交换操作 下面简称为 〔“ ’类似 , 不同在于 是 在父本的四条路径中选择最短的路 , 而 一 。 是选择 口 值最大的路 这两种启发式交换操作 的计量相似 , 进行一次交换操作的计算量都是 , 是城市数 目 。 对于 个城市的 , 一阶模式的数 目是 君。 一个解里能表示的一阶模式的 数 目是 。 要 使解集中包含所有一阶模式 , 解集的大小至少是 一 邝 。 在下面的实验 实验一 中 , 解 集 的 大小选择为城市数的 、 、 倍 。 算法都采用最大值规范化方法 , 但分别使用启发 式 交 换 操作 一 。 和 , 而不用有序交换操作 。 求解前面的 个城市的 , 典型实验结果见表 。 这两种启发式交换操作效果都较好 。 算法收敛逮度大大快于使用有序交换操作 , 并能收敛到较好 的近似最优解 , 收敛值通常在最优值的 以内 。 解集太小 , 如为 时 , 解集中的模式 很 容 易 丢失 , ‘ 使得算法的收敛值不太好 。 解集大小为城市数的两倍 时 , 结果就较好了 。 一 。 的效果比 更好些 相同解集大小的情况下 , 当解案较小时 , “ 一 。 的收敛时间与 吠 差不多 , 但收敛值要好 , 当解集较大时 , 一。 的收敛值与 差不多 , 但收教时间要少 。 上述实验中的遗传算法是无记忆的 , 即时刻 时的解集仅由时刻 一 时的解集产生 。 在实验 · 二中使用的遗传算法略有不同 时刻 时的解集由 一 时的解集产生后 , 将 一 时刻以 前 所 找 到的最好的解加人 时刻的解集中 , 随机替换掉解集中的一个解 , 、 这样 , 当前解集里总含到 目前 为止找到的最好的解 。 同样将算法应用于前面的 个城市的问题 。 典型实验结 果 见表 。 卜 和 的结果都比实验一有所改善 , 。 仍优于 。 表 表 一 收收敛时间间 收敛道道 收敛时间间 收敛值值 代代 代代 代代 代代 代代 代代 代代 。 代代 亡亡 代代 加加加代代 代代 。 代代 。 代代 。 执执代代 。 七七 代代 。 代代 解解集大小小 一 收收收敛时间间 收敛涟涟 收敛时间间 没敛值值 代代 代代 。 代代 , 代代 峨 代代 代代 。 代代 七七 。 代代 代代 。 代代 于七七 。 代代 。 代代 。 干七七 代代 。 代代 。 代代 峨 实验三是解一个 个城市的欧基里德平面 表 一 解集大小 收敛时间 代 代 代 收敛值 。 。 。 收敛时间 代 代 代 代 代 代 七 代 代 收敛值 。 代 代 代 。 。 。 代 代 代 。 。 。 问题 。 这 个城市随机分布在平面上 。 已知 的最优解是 。 采用如实 验二那样保持所 找到的最优解的方法 。 典型实验结果见表 。 无论是收敛速度 , 还是收敛结果 , 一 。 都 明显地优于 。 当 解集 较 大 时 , , 一 。 收敛的最优值 通 常在问题的 最优值的 之内 。 当解集变大时 , “一 。 的收敛值变好 , 收敛所需的代 数基本上不变 , 而 的收敛代数变多 , 且 不稳定 。 的解空间非 常 大 。 城市 的 的 解有 一 个 。 遗传算法 只 考虑 了其中 个解 是代数 , 是解集的大小 。 本文 中的算法的 约为 , 为 的 一 倍 。 可见 , 遗传算法只考察了解空间 很小 的一部分就找到 了较优的解 , 这其中启发式交换操作起了很大作用 。 四 、 结 论 遗传算法的很多方面可以利用问题域的知识赛使得算法更有效 。 采用规范化方法设计合适的 评价函数往往是必要的 。 遗传爆作是算法的关键 , 设计启发式的遗传操作能使算法对 伺 题 更 有 效 。 对于有序问题 , 还没有很有效的通用的遗传交换操作 。 本文针对一种典型的有序问题 —旅行售货员问题 , 从遗传算法的原理出发 , 设计了一个新的启发式遗传交换操作 。 实验结果显示 , 此启发式交换操作比 “ ‘ ‘ 设计的类似的启发式卒换操作效果要好 。 采用此启发式交换操 作的遗传算法的收敛速度很快 , 且计算结果通常在最馋值的 以内 。 、 致谢 作者在工作中得到了李国杰研究员的指导和帮助 , 特表示感谢 。 参 考 文 献 〕 , 名, , , 〕 , , 比 , , 五 一 , 一 〕 七 , , , 、 , , 一。 , 〕 , 一 , , 一 , 〕 圣 , 以 , ’ , , 〕 · ‘ 。‘ , 七 王 , 产 ‘ 主五 , , , , 〕 , , , 〕 , , , 奋 , , 」 、 , , 尹 , 二 , 。 一 , 比 户。 , , , , 。 ‘ 二 , 口。 , , , 。名 艺 。尹 ￡。 ‘ , 拜 “‘、‘。 夕“ 云九 、 夕 , 。葱 月玄。葱 , 艺云。 , , , ’ 七 竹 , 份 , , ’ , —加, 往 元 , , 幼 , 枕 《上接 页 胜 。尹 , 幸 犷 刀 云 ” , 刃 “ 落妞 ”‘, , “‘, , , 韶 吐。一 一 一 而 一 玩 几 一 一 , , , 一 一