毕业论文普通遗传算法与佳点集遗传算法的研究.doc

目目 录录 摘要 1 关键词 1 引言 1 1 遗传算法概论 1 1 1 遗传算法的历史和研究现状 1 1 2 遗传算法的基本原理 3 1 2 1 遗传算法基本概念 3 1 2 2 遗传算法基本原理 3 1 2 3 遗传算法的特点 3 2 普通遗传算法 4 2 1 普通遗传遗传算法思想 4 2 2 普通遗传算法的遗传操作 4 2 2 1 选择 selection 操作 4 2 2 2 交叉 crossover 操作 4 2 2 3 变异 mutation 操作 5 4 遗传算法在 TSP 问题上的应用 8 4 1 TSP 问题概述 8 4 2 遗传算法求解 TSP 问题 8 4 2 1 编码与解码 8 4 2 2 初始化种群 9 4 2 3 适应度函数 9 4 2 4 选择算子 10 4 2 5 交叉算子 10 4 2 6 变异算子 15 4 2 7 停止准则 15 5 TSP 问题的实验结果及分析 15 5 1 普通遗传算法与佳点集遗传算法的比较与分析 15 5 1 1 最优解分析 15 5 1 2 算法收敛速度分析 17 5 1 3 算法运行时间分析 18 总 结 18 致 谢 18 参考文献 19 ABSTRACT 19 KEY WORDS 19 遗传算法在遗传算法在 TSP 问题上的应用问题上的应用 摘要摘要 遗传算法 GA 模拟自然进化机制 在搜索优化问题全局或全局附近的最优解上具有较好的 鲁棒性 内在的并行性和较优越的稳定性 因而在诸如组合优化 图像处理等方面有着广泛的应用 但是传统的遗传算法性能很大程度上依赖于相关参数的取值与算子的作用方式 佳点集遗传算法利 用数论中的佳点集理论和方法 来改进普通遗传算法中的各相关算子 以期克服普通遗传算法收敛 速度慢 易陷入局部最优的弱点 本文在分析普通遗传算法和佳点集遗传算法机理上 利用 JAVA 语言实现了佳点集算法演示系统 通过选取不同的遗传算子来对标准 TSP 的数据集中的大量数据 进行了对比分析和验证 我们的实验结果表明对于较大规模的 TSP 组合问题佳点集的优势是非常 明显的 关键词关键词 Tsp 问题 普通遗传算法 佳点集遗传算法 单切点交叉算子 双切点交叉算子 循环交叉算子 佳点集交叉算子 引言引言 遗传算法 Genetic Algorithm GA 是由美国密歇根大学的 John H Holland 教授及 其学生于 20 世纪 60 年代末到 70 年代初提出的 它是以达尔文的自然进化论 适者生 存 优胜劣汰 和孟德尔遗传变异理论为基础 模拟生物进化过程 它具有大范围快 速全局搜索能力 能在搜索过程中自动获取和积累有关搜索空间的知识 并自适应地 控制搜索过程以求的最优解 正是遗传算法的诸多特点 使得它在求解组合优化 机 器学习 并行处理等问题上得到了广泛的应用 普通遗传算法是通过模拟染色体群的 选择 交叉和变异等操作 不断迭代 最终收敛到高适应度值的染色体 从而求得问 题的最优解 但是随着问题规模的扩大 组合优化问题的搜索空间急剧扩大 普通遗 传算法的收敛速度慢 易陷入局部最优的缺点就暴露了 而佳点集遗传算法正是通过 佳点集的方法改进交叉算子 加快算法收敛到全局最优解的速度 降低发生早熟的概 率 提高整个算法的计算效率 1 1 遗传算法概论遗传算法概论 1 1 1 1 遗传算法的历史和研究现状遗传算法的历史和研究现状 早在 1967 年 Bagley 和 Rosenberg 就提出了生物遗传算法 GA 的初步思想 1975 年由美国 Michigan 大学的 John Holland 的出色工作奠定了遗传学算法的理论基础 遗 传变异和优胜劣汰现象的优化搜索算法付诸了实际应用 这也标志着遗传算法的诞生 到了 80 年代初期 Holland 的一些学生的毕业论文中对遗传算法的应用以及在应 用中遇到的问题进行了研究 其中有 Delong 1975 对 GA 的各种策略的性能和机理进 行了大量的细致分析与实验 与此同时 Holland 还给出了一个自适应的规则学习系统 并于 1980 年成功地实现了这一学习系统 Holland 及其学生的研究成果使得人们开始 看到了 GA 的应用价值 1981 年 Betake 的博士论文中提出了用 Walsh 函数来研究遗传 算法的方法 Alberta 大学的 Brindle 在其博士论文中开始对选择策略进行了研究 这 一时期的研究回答了 GA 算法的到底有何意义 有何价值 也正是他们的研究使得更 多的人把目光投向了遗传算法 1985 年召开了第一届 GA 国际会议 至此以后每两年 召开一次 80 年代中期 遗传算法广泛的应用于许多的应用领域 如 TSP 问题 调度问题 机器学习 模式分类问题 囚徒困境问题以及多关节机械手轨迹规划问题 1989 年 D J Goldberg 总结了遗传算法的主要成果 全面论述了遗传学的基本原理极其应用 奠定了现代 GA 的科学基础 进入 90 年代 遗传算法迎来了兴盛发展时期 无论是理论研究还是应用研究都成 了十分热门的课题 尤其是遗传算法的应用研究显得格外活跃 不仅它的应用领域扩 大 而且利用遗传算法进行优化和规则学习的能力也显著提高 同时产业应用方面的 研究也在摸索之中 此外一些新的理论和方法在应用研究中亦得到了迅速的发展 这 些无疑均给遗传算法增添了新的活力 遗传算法的应用研究已从初期的组合优化求解 扩展到了许多更新 更工程化的应用方面 1991 年 D Whitey 在他的论文中提出了基于领域交叉的交叉算子 Adjacency based crossover 这个算子是特别针对用序号表示基因的个体的交叉 并将其应用到了 TSP 问题中 通过实验对其进行了验证 D H Ackley 等提出了随机迭代遗传爬山法 Stochastic Iterated Genetic Hill climbing SIGH 采用了一种复杂的概率选举机制 此机制中由 m 个 投票者 来共同决定新个体的值 m 表示群体的大小 实验结果表明 SIGH 与单点交叉 均匀交叉的神经遗传算法相比 所测试的六个函数中有四个表现出 更好的性能 而且总体来讲 SIGH 比现存的许多算法在求解速度方面更有竞争力 H Bersini 和 G Seront 将遗传算法与单一方法 simplex method 结合起来 形成了一种 叫单一操作的多亲交叉算子 simplex crossover 该算子在根据两个母体以及一个额外 的个体产生新个体 事实上他的交叉结果与对三个个体用选举交叉产生的结果一致 同时 文献还将三者交叉算子与点交叉 均匀交叉做了比较 结果表明 三者交叉算 子比其余两个有更好的性能 近年来 国内也有不少的专家和学者对遗传算法的交叉算子进行改进 2002 年 戴晓明等应用多种群遗传并行进化的思想 对不同种群基于不同的遗传策略 如变异 概率 不同的变异算子等来搜索变量空间 并利用种群间迁移算子来进行遗传信息交 流 以解决经典遗传算法的收敛到局部最优解问题 2004 年 赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的 现象 提出了一种用基因块编码的并行遗传算法 Building block Coded Parallel GA BCPGA 该方法以粗粒度并行遗传算法为基本框架 在染色体群体中识别出可 能的基因块 然后用基因块作为新的基因单位对染色体重新编码 产生长度较短的染 色体 在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体 2005 年 江雷等针对并行遗传算法求解 TSP 问题 探讨了使用弹性策略来维持群体 的多样性 使得算法跨过局部收敛的障碍 向全局最优解方向进化 总之人们对遗传算法的研究主要可以概括为以下三个方面 1 遗传算法搜索在进化到一定的程度就往往会使得种群的适应度趋向于相 同 这样似的种群间的概率变的非常接近 这时的选择和复制策略接近 于纯随机的抽样过程 使得搜索的收敛速度比较慢 针对这一问题 人 们提出了不同的选择和复制策略 2 遗传算法的收敛性研究 主要结果是典型的 GA 不会收敛到全局最优 对于保留精英 elitism selection 的选择策略 GA 能收敛到全局最优 尽 管这一结论说明了改进的 GA 最终能收敛到全局最优解 但收敛到最优 解的时间可能很长 3 遗传算法收敛性能的研究 普通的遗传算法搜索的局部性而往往不能全 局最优 针对这一问题人们采用设计合适的交叉算子和变异算子来解决 而本文要实现的基于佳点集的遗传算法就是通过设计合适的交叉算子来 解决收敛速度和收敛性能的问题的 关于遗传算法收敛性能的研究 到 目前为止还没有肯定的结论哪一种方法的遗传算法性能绝对最优 对于 遗传算法的性能往往是问题不同 得到的结论也不同 1 1 2 2 遗传算法的基本原理遗传算法的基本原理 1 1 2 2 1 1 遗传算法基本概念遗传算法基本概念 种群种群 population 染色体带有特征的个体的集合称为种群 该集合内个体数称为 群体的大小 个体个体 individual 指染色体带有特征的实体 种群大小种群大小 population size 种群中个体数目称为群体大小 适应度适应度 fitness 各个个体对环境的适应程度叫做适应度 fitness 适应度函数 适应度函数 fitness function 为了体现染色体的适应能力 引入了对问题中的 每一个染色体都能进行度量的函数 叫适应度函数 适应度函数是计算个体在群体 中被使用的概率 遗传操作 遗传操作 genetic operator 遗传算法中有三种关于染色体的运算 选择 交叉 和变异 这三种运算被称为遗传操作 交叉率 交叉率 交叉运算的染色体个数占全体染色体总数的比例 取值范围一般为 0 4 0 99 变异率 变异率 参加发生变异的基因位数所占全体染色体的基因总位数的比例 取值范围 一般为 0 0001 0 1 这里主要是参考了计算机毕业设计网 上的 文章 1 1 2 2 2 2 遗传算法基本原理遗传算法基本原理 遗传算法 10 GA 把问题的解表示成 染色体 在算法中也即是以二进制编码或实数 编码的串 并且 在执行遗传算法之前 给出一群 染色体 也即是假设解 然后 把这些假设解置于问题的 环境 中 设定相应的适应度函数 并按适者生存的原则 从中选择出较适应环境的 染色体 进行复制 再通过交叉 变异过程产生更适应环境 的新一代 染色体 群 这样 一代一代地进化 最后就会收敛到最适应环境的一个 染色体 上 得到问题的最优解 1 1 2 2 3 3 遗传算法的特点遗传算法的特点 遗传算法 GA 利用了生物进化和遗传的思想 所以它有许多与传统的优化方法不 同的特点 1 GA 遗传算法是对问题参数集的编码 染色体群 作为运算对象 使得我们可以借 鉴生物学中的染色体和基因的概念 模仿自然界生物的遗传和进化机理对问题参数集 的编码 染色体群 进行进化 而不是象传统优化方法对参数本身进行优化 2 GA 是从问题的集合开始进行群体搜索 而不是从某个解开始进行单点搜索 形 象地说 GA 是并行地爬多个峰 这一特点使 GA 具有较好的全局搜索性能 大大减少 了陷入局部最优解的可能性 3 GA 的适应性强 仅用适应度函数值来引导搜索 而不需要问题领域的先验知识 或其它辅助信息 从而对问题的依赖性较小 4 GA 使的选择 交叉 变异三个算子都是随机操作 具有不确定性 采用概率的 变迁规则来指导搜索方向 引导搜索过程朝着搜索空间的更优化的解区域移动 因此 它是一种启发式搜索 2 2 普通遗传算普通遗传算法法 2 2 1 1 普通遗传遗传算法思想普通遗传遗传算法思想 1 初始化群体 2 计算群体上每个个体的适应度值 3 按由个体适应度值所决定的某个 规则选择将进入下一代的个体 4 按概率 Pc进行交叉操作 5 按概率 Pm进行变异操作 6 没有满足某种停止条件 则转第 2 步 否则进入 7 7 输出种群中适应度值最优的染色体作 为问题的满意解或最优解 算法简单流程图如右图所示 图 1 遗传算法简单流程图 2 2 2 2 普通遗传算法普通遗传算法的遗传操作的遗传操作 2 2 2 2 1 1 选择 选择 selectionselection 操作 操作 选择 selection 操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算 就是从种群中选择适应度较高的染色体进行复制 以生成下一代种群 最常用的选择 策略是赌轮选择策略 赌轮选择的基本思想 做一个轮盘 然后按照各个染色体的个 体适应度比例转化为选中概率 选择概率 将轮盘分成若干个扇区 随机地产生 0 1 之间的随机数 这样就相当于转动轮盘 获得转盘停止时指针位置 指针停止在某一 扇区 该扇区代表的个体即被选中 这里选择概率的计算公式 P xi 其中 f 为适应度函数 f xi 为的适应度 N j j i xf xf 1 2 2 2 2 2 2 交叉交叉 crossover crossover 操作操作 交叉就是互换两个染色体某些位上的基因以产生新的个体 普通遗传算法中常用的 交叉算子有单切点交叉 双切点交叉 循环交叉 下面我们来进行依次介绍 1 单切点交叉 single point crossover 单切点交叉的思想是从种群中选出两个个体 P1 和 P2 随机地选择一个切点 cutting 将切点两侧分别看成一个子串 将右侧的子串分别进行交换 这样就得到 了两个新的个体 C1 和 C2 P1 和 P2 其中称为父代染色体 C1 和 C2 称为子代染色体 初始化群体 计算适应度 交叉操作 变异操作 条件终止 结束 选择操作 适合度最优群体 切点 切点 图 2 单切点交叉示意图 单切点交叉操作的信息量比较小 交叉位置的选择可能带来较大的偏差 并且染 色体末尾的基因总是被交换 2 双切点交叉 double point crossover 双切点交叉的思想是从种群中选出两个个体 P1 和 P2 随机地选择两个切点 cutting 交换两个切点之间的子串 从而得到了新一代的染色体 切点 切点 切点 切点 图 3 双切点交叉示意图 3 循环交叉 cycle crossover 循环交叉 12 的基本思想是子串位置上的值必须与父母相同位置上的值相等 循环 交叉操作的具体步骤如下 a 选 P1 的第一个元素作为 C1 的第一个元素 选 P2 的第一个元素作为 C2 的第一 个元素 b 在 P1 中找 P2 的第一个元素赋给 C1 的相对位置 重复此过程 直到 P2 上得 到 P1 的第一个元素为止 称为一个循环 c 对最前的基因按 P1 P2 基因轮替原则重复以上过程 d 重复以上过程 直至所有位已完成 图 4 循环交叉示意图 P1 A1 A2 P2 B1 B2 C1 A1 B2 C2 B1 A2 P1 A1 A2 A3 P2 B1 B2 B3 P1 A1 B2 A3 P2 B1 A2 B3 C1 2 9 5 3 8 4 6 7 1 C2 3 4 8 6 5 9 2 1 7 C1 C2 3 循环 C1 9 5 8 4 C2 3 4 8 5 9 循环 4 7 1 C1 9 4 C2 3 4 9 循环 3 5 8 P1 P1 循环 2 2 2 2 3 3 变异变异 mutation mutation 操作操作 变异本身是一种局部随机搜索 与选择 交叉算子结合在一起 保证了遗传算法的 有效性 使遗传算法具有局部的随机搜索能力 同时使得遗传算法保持种群的多样性 以防止出现非成熟收敛 在变异操作中 变异率不能取得太大 如果变异率大于 0 5 遗传算法就退化为随机搜索 而遗传算法的一些重要的数学特性和搜索能力也不复存 在了 最常用的变异操作是按位交换变异 它的基本思想 对于同一个个体的基因如 果发生变异 则随机与同一个个体的另一个基因交换位置 4 4 遗传算法在遗传算法在 TSPTSP 问题上的应用问题上的应用 4 4 1 1 TSPTSP 问题概述问题概述 TSP 问题就是已知个城市各城市间的距离 一旅行商从某一城市出发访问每个城 市一次且仅一次 最后回到出发城市 如何安排才能使其所走路程最短 问题的数学模型可以描述为 对于 n 个城市 V v1 v2 vn 的一访问次序为 T t1 t2 tn tiVi i 1 2 n tn 1 t1 则问题即要求 min 其中 n i tt ii d 1 1 表示城市 i 与城市 i 1 之间的距离 1 i tti d 对于 TSP 这样的一个典型的组合优化问题 最为普通的一种解决办法就是穷举出 所有可能的合法序列 然后比较距离函数 得出最优的城市序列 这就是穷举搜索法 的思想 理论上它可以解决任何组合优化问题 但是对于 n 个城市的 TSP 问题来说 可能的合法回路有条 计算每一条路径需求 n 个距离之和 因此计算量正比于 2 1 n 即使使用运算速度为 105亿次每秒的巨型计算机按穷举搜索法计算 100 个城市的 2 n TSP 问题也需要 1 48 10136年的时间 在这里还没有考虑算法所需的巨大的存储空间 由此可见 TSP 问题的时空复杂度之高 这就为遗传算法的应用提供了机会 下面我们 就来看一求解 TSP 问题的遗传算法 4 4 2 2 遗传算法求解遗传算法求解 TSPTSP 问题问题 4 4 2 2 1 1 编码与解码编码与解码 在遗传算法中每一个个体表示成一个染色体 每一个染色体又是由一个个基因位 所构成的 这样每一个个体对象相当于生物体的表现型 而染色体就相当于生物体的 基因型 从表现型到基因型的映射称为编码 在遗传算法中最初使用的编码方法是二 进制编码 每个染色体使用固定长度的 0 1 字符串表示 如 X 0110010 表示一个染色体 该个体的染色体长度为 7 二进制编码具有易于 位值计算 包括的实数范围大的优点 适合于背包问题 实优化问题和指派问题 但 是在另外的一些实际问题如 TSP 问题 二进制编码编码长 不易计算同时不易进行变 异交叉操作 易产生大量非可行解 所以针对特殊的问题 可以采用不同的编码方法 本文在 TSP 求解中 采用基于城市序号的顺序实数编码 它是用 的自然数来编 码 这种编码不允许重复 即 xi1 2 3 n 且当 ij 时 xixj 如 X 2 3 1 5 4 7 6 表示一个染色体长度为 7 的顺序实数编码 对于 7 个城市的旅 行商问题 上述编码表示 2 3 1 5 4 7 6 2 的一条行走路线 这种编码虽然方便 但是 要注意编码的合法性检查 并对不合法的个体进行合法性修复 解码就是求出一条染色体所对应的路径长度的过程 如 一染色体 X 的顺序实数编码为 2 3 1 5 4 7 6 解码就是要把相邻两点的距离进行 求和 具体地说就是要把 2 与 3 3 与 1 1 与 5 5 与 4 4 与 7 7 与 6 6 与 2 之间 的距离相加 相加的结果就是由解码得到的路径长度 d 4 4 2 2 2 2 初始化种群初始化种群 遗传算法是一种既有群体寻优的方法算法运行时是一个群体在搜索空间进行搜索 一般采用随机方法产生一个初始种群 本文就是采用是一种经典的洗牌随机生成的方 法生成初始种群 设表示编码的一维数组为 P1 n 和 P2 n 先把 P1 n 和 P2 n 按城市序号 初始化为 0 1 n 1 令 i 0 产生一个 n 1 i 范围内的整数 r 然后将 P1 n 1 i 赋值于 P2 i P1 n 1 i 赋值给 P1 r i 增加 1 后 进入下一轮循环 如此循环直至达 到所需的群体规模为止 P2 n 即为洗牌随机生成后的序列 其算法 JAVA 实现如下 public void init List list int popSize int cityNum String fileName initDistance list fileName cityNum for int i 0 i popSize i this citys add i new GenoType this copy list 0 0 0 0 初始化种群数组 int num new int cityNum for int j 0 j cityNum j num j j int temp cityNum 随机地初始化城市序列 for int j 0 j cityNum j int r int Math random temp this citys get i get j setSequece num r num r num temp 1 temp this citys get i setFitness 0 this citys get i setSelectP 0 this citys get i setExceptp 0 this citys get i setIsSelected 0 4 4 2 2 3 3 适应度函数适应度函数 适应度函数一般根据目标函数来进行设计 目标函数一般表示为 f x 适应度函数 一般表示为 F x 对优化问题 适应度函数就是目标函数 TSP 的目标是路径总长度 为最短 路径总长度可作为 TSP 问题的适应度函数 F x f x 其中 x n 1 x1 n j jj xxD 1 1 计算种群适应度的函数 JAVA 实现 private void CalFitness int popSize int cityNum for int i 0 i popSize i double len2 this citys get i getFitness for int j 0 j cityNum 1 j len2 this distance this citys get i get j getSequece this citys get i get j 1 getSequece len2 this distance this citys get i get 0 getSequece this citys get i get cityNum 1 getSequece this citys get i setFitness len2 4 4 2 2 4 4 选择算子选择算子 在每一代的运算过程中 个体被选中的概率与其在群体中的相对适应度成正比 即采用赌轮选择机制 计算选择算子的 JAVA 实现 private void CalSelectP int popSize double sum 0 for int i 0 i popSize i 计算所有种群的适应度之和 sum this citys get i getFitness for int i 0 i 0 x int Math random popSize y int Math random popSize int location int Math random cityNum SiglePointPTexecuteCrossover x y location cityNum x y 两个体执行普通遗传算法的单切点交叉 pop public void SiglePointPTexecuteCrossover int x int y int location int cityNum for int i location i cityNum i 交换两个体的序列 int temp this citys get x get i getSequece this citys get x get i setSequece this citys get y get i getSequece this citys get y get i setSequece temp int j 0 个体修复 while j cityNum if j i j int k 0 while k 0 x int Math random popSize y int Math random popSize CyclePTexecuteCrossover x y cityNum x y 两个体执行交叉 pop public void CyclePTexecuteCrossover int x int y int cityNum int arr1 new int cityNum int arr2 new int cityNum for int i 0 i cityNum i arr1 i this citys get x get i getSequece arr2 i this citys get y get i getSequece Cross util new Cross arr1 arr2 实现循环交叉的主体类对象 int result1 util getResult1 int result2 util getResult2 for int i 0 i cityNum i this citys get x get i setSequece result1 i this citys get y get i setSequece result2 i 3 佳点集交叉算子 根据佳点集的理论 结合 TSP 问题的实际意义我们给出 TSP 问题的佳点集交叉算 子 随机选取个体 A1 A2 的前 t 位不同 后 L t 位相同 取 t 维单位立方体 在 t 维 单位立方体中任取一点 P p1 p2 pt 将个体 A1 A2 中相同的基因位去掉 设余下的基因编码位 S s1 s2 st 其中 s1 s2 st 将 P 进行从小到大排序得到 T t1 t2 tt 则 T 相对于 S 得到一个新的 S 排列 这个新的 S 排列于 A1 和 A2 个体 中的相同部分合在一起就得到了佳点集交叉后的新个体 例如 A1 7 2 0 1 8 5 9 4 3 6 A2 1 2 4 0 5 6 9 3 7 6 相同部分 2 9 6 不同部分 S 0 1 3 4 5 7 8 取佳点 P 0 2 0 12 0 81 0 73 0 5 0 4 0 83 从小到大排序得到 T 0 12 0 2 0 4 0 5 0 73 0 81 0 83 T 相对于 S 得到一个新的 S 排列 S 1 0 7 5 4 3 8 与 A1 和 A2 相同部分合并得交叉后的新个体 1 2 0 7 5 4 9 3 8 6 佳点集交叉操作有效的避免了普通交叉算子因交叉产生的非法个体 又避免了因 问题规模的扩大 使算法性能的下降 佳点集交叉算子的 JAVA 实现 private void executeCrossover int x int y int cityNum int dimension 0 for int i 0 i cityNum i if this citys get x get i getSequece this citys get y get i getSequece 个体x和个体y中对应位基因不同 dimension int diffItem 0 double diff new double dimension 用于存储不同的基因片段 for int i 0 i cityNum i if this citys get x get i getSequece this citys get y get i getSequece diff diffItem this citys get x get i getSequece this citys get x get i setSequece 1 this citys get y get i setSequece 1 diffItem Arrays sort diff 将不同的基因片段进行排序 double temp new double dimension temp gp x dimension 用于交叉函数的交叉点 运用佳点集交叉 for int k 0 k dimension k 通过temp 交换数组temp中的值 for int j 0 j 0 if this citys get x get tempi getSequece 1 当为不同的 基因片段时 this citys get x get tempi setSequece int diff dimension tempDimension tempDimension tempi Arrays sort diff temp gp y dimension for int k 0 k dimension k for int j 0 j 0 if this citys get y get tempi getSequece 1 this citys get y get tempi setSequece int diff dimension tempDimension tempDimension tempi private double gp int individual int dimension double temp new double dimension double temp1 new double dimension int p 2 dimension 3 while isSushu p p for int i 0 i dimension i temp i 2 Math cos 2 Math PI i 1 p individual 1 temp i temp i int temp i if temp i 0 temp i 1 temp i for int i 0 i dimension i temp1 i temp i Arrays sort temp1 排序 for int i 0 i dimension i for int j 0 j dimension j if temp j temp1 i temp j i return temp 4 4 2 2 6 6 变异算子变异算子 变异是在种群中按照变异概率任选若干个基因位改变其位值 对于二进制编码来 说 就是反转位值 而对于顺序实数编码 就是在同一个个体的基因中 随机选取另 一个基因交换位置 如 变异算子的 JAVA 实现 public void mutate int popSize int cityNum double pmultation double random int temp int temp1 int temp2 for int i 0 i popSize i random Math random if random pmultation temp1 int Math random cityNum temp2 int Math random cityNum temp this citys get i get temp1 getSequece this citys get i get temp1 setSequece this citys get i get temp2 getSequece this citys get i get temp2 setSequece temp 4 4 2 2 7 7 停止准则停止准则 遗传算法中的停止准则一般是设定最大代数的方式 最大代数常设为 popsize 本 文采用 最大代数与收敛情况相结合的方式来设计停止准则 判断停止准则的 JAVA 代码 if tsp isSame result 判断2000代内的最优解是否相同 相同则结束 不同则看下一 代 break index if index range 重新计数 index 0 5 5 TSPTSP 问题的实验结果及分析问题的实验结果及分析 5 5 1 1 普通遗传算法与佳点集遗传算法的比较与分析普通遗传算法与佳点集遗传算法的比较与分析 5 5 1 1 1 1 最优解分析最优解分析 我们分别用佳点集遗传算法和普通遗传算法 单切点 双切点 循环交叉 对 Bayg29 个城市进行求解 取交叉概率为 0 9 变异概率为 0 04 群体规模为 50 最大 迭代代数 8000 将算法各执行 30 次 实验结果如下 遗传算法各交叉算子比较 0 2000 4000 6000 8000 10000 12000 14000 16000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 平均值 执行次数 最优解 单切点 循环交叉 双切点 佳点集 图 6 遗传算法各交叉算子比较 1 对各最优解数据作统计学处理得到下表 遗传算法各交叉算子比较 0 100000 200000 300000 400000 500000 600000 700000 800000 单切点循环交叉双切点佳点集 交叉算子 方差 系列1 图 7 遗传算法各交叉算子比较 2 由实验结果可以看出普通单切点和双切点交叉操作的交叉位置的选择随机性比较 大 因此每次执行的最优解的偏差也比较大 相比较而言 佳点集交叉和循环交叉的 随机性较小 因此算法每次执行得到的最优解偏差较小 更稳定 佳点集的遗传算法 较普通遗传算法不仅更稳定 而且所得到的解更接近于最优解 执行各算法 并得到各代的最优解如下 遗传算法各交叉算子比较 0 5000 10000 15000 20000 25000 1 90 180 270 360 450 540 630 720 810 900 990 1800 2700 迭代代数 当前最优解 佳点集交叉 单切点交叉 双切点交叉 循环交叉 图 8 遗传算法各交叉算子比较 3 通过比较实验结果可以看出由于普通单切点交叉操作的信息量比较小 较双切点 交叉更容易陷入局部最优 佳点集交叉和循环交叉都较好的保留了父代的优良基因 但是循环交叉操作生成子代的多样性较小 因此更容易陷入局部最优 佳点集的交叉 操作 按照佳点集的方法生成子代个体 使得子代个体的多样性得到了保证 因此它 有效的避免了 早熟 现象 5 5 1 1 2 2 算法收敛速度分析算法收敛速度分析 参数设置同上 各算法各执行 20 次 所得结果如下 遗传算法各交叉算子比较 0 2000 4000 6000 8000 10000 1 3 5 7 9 11 13 15 17 19 算法执行次数 算法收敛时代数 佳点集交叉 单切点交叉 双切点交叉 循环交叉 图 9 遗传算法各交叉算子比较 4 由实验结果可知 佳点集交叉操作收敛的速度远不如普通交叉算子 这也是它为 了避免算法收敛到局部最优所造成的 任何解决组合优化问题的算法要想收敛到全局 最优 就必须使其生成的子代更具有多样性 但是这样就会使得算法的收敛的速度下 降 佳点集遗传算法虽然收敛速度较普通算法慢 但是其运行时间比普通遗传算法要 快的多 下面我们来分析一下算法的运行时间 5 5 1 1 3 3 算法运行时间分析算法运行时间分析 参数设置同上 分别用各算法对 burma14 ulysses16 ulysses22 baygs29 att48 st70 rat99 a280 城市进行测试得到 遗传算法各交叉算子比较 0 1000000 2000000 3000000 4000000 5000000 14162229487099128 城市数 算法运行时间 ms 佳点集交叉 单切点交叉 双切点交叉 循环交叉 图 10 遗传算法各交叉算子比较 5 由实验结果可以看到佳点集遗传算法运行时间远小于普通遗传算法 特别是当城市 数很大的时候表现的更加明显 总总 结结 本文对佳点集遗传算法和普通遗传算法最经常使用的三种交叉算子进行了详尽的 分析并予以实现 说明了佳点集遗传算法较普通遗传算法不仅提高了求解的速度 而且 有效的避免了 早熟 现象 经过一段时间的学习和努力 终于将毕业设计和论文完成了 在设计期间我在赵 老师的指导下克服了一个又一个难关 赵老师的谆谆教诲使我明白了做任何事情都要 全力以赴 遇到任何困难都要有信心 学会坚持 只有坚持到最后 才有可能取得成 功 致致 谢谢 本课题的研究和论文撰写得到了我的导师赵靖的精心指导和帮助 在此谨对赵老 师表示由衷的感谢和深深的敬意 赵老师开阔的眼界 敏捷的思维 好学的精神 以 及严谨的治学态度和一丝不苟的工作作风 而更为重要的是 在做毕业设计的学习生 活中 我向老师学到了认真 诚实 谦虚的做人品格 它将成为我一生享之不尽 用 之不竭的精神财富 感谢我的室友和同学 在我四年大学的学习和生活中 朝夕相处 相互帮助 给 我留下了最为美好的回忆 感谢安徽科技学院提供的舒适的学习环境 优良的教学设备 感谢理学院的各位老 师的指导和帮助 参考文献参考文献 1 Holland J H Outline for logical Theory of Adaptive Systems theory J Journal of the Association for computing Machinery 3 297 314 1962 2 Holland J H Adaptation in Natural and Artificial Systems Ann Arbor J University of Michigan press 1975 3 Goldberg D E Computer aided Gas pipeline operation using Genetic Algorithms and Rule learning D Doctoral dissertation university of Michigan 4 张铃 张钹 统计遗传算法 J 软件学报 vol 8 No 5 1997 335 344 5 赵春英 张铃 佳点集遗传算法的理论及应用 D 安徽大学人工智能所 合肥 230039 6 张铃 张钹 遗传算法机理的研究 J 软件学报 vol 11 No 7 2000 945 952 7 华罗庚 王元 数论在近似分析中的应用 M 科学出版社 1979 8 张铃 张钹 佳点集遗传算法 J 计算机学报 9 计算机毕业论文辅导网 遗传算法解析 J 10 吴少岩 张青富 陈火旺 基于家族优生学的进化算法 J 软件学报 vol 8 No 2 1997 137 144 11 赵春英 张铃 求解货郎担问题 TSP 的佳点集遗传算法 J 计算机工程与应用 vol 37 No 3 2001 12 廉师友 人工智能技术导论 第三版 M 西安电子科技大学出版社 13 汪定伟 智能优化方法 M 高等教育出版社 2006 10袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁 蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃 肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂