ＥＬＥＣＴＲｏＮＩＣＳ Ｗ０ＲＬＤ・苁 ｊ２ 基于遗传算法的最短路径规划 南京大学金陵学院信息科学与工程学院林煦涵 刘耀轩孙海洋 【摘要】传统遗传算法在路径规划中对路径长短、终点选择以及路径安全度等参数进行多目标选择算法时，很难找到兼顾多个问题的合适路 径。本文提出了一种改进遗传算法的思路，在遗传算法的选择、交叉、变异的基础上，增加了定代和引导收敛的方式，并加入了适应度函数 的选取和判定方法。将多个问题的解决集成到一个目标函数内，解决了高效性和安全性无法兼顾的问题。最后利用Ｍａｔｌａｂ进行仿真，证明了 该改进算法的可行性及正确性。 【关键词】遗传算法；路径规划；收敛问题 Ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ Ｌｉｎ ＸｕＨａｎ，Ｌｉｕ ＹａｏＸｕａｎ，Ｓｕｎ Ｈａｉｙａｎｇ （ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ａｃａｄｅｍｙ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ Ｊｉｎｌｉｎｇ Ｃｏｌｌｅｇｅ，Ｎａｎｊｉｎｇ ２ ｌ ００８９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｎ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｄｉｓｔａｎｃｅ，ｓｅｌｅｃｔｉｎｇ ｔｅｒｍｉｎａｌ ｐｏｉｎｔｓ ａｎｄ ｓｅ— ｃｕｒｉｔｙ．Ｗｅ ｃａｎ ｆｉｎｄ ｔｈａｔ ｉｔ’Ｓ ｈａｒｄ ｔｏ ｂａｌａｎｃｅ ｍｕｌｔｉｐｌｅ ｔａｒｇｅｔｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｕｓｅｄ ａｎ ＧＡ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｑｕｅｓｔｉｏｎ ａｓ ａ ｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓ，Ｗｅ ａｄｄ ａｎ ｉｄｅａ ｗｉｔｈ ｓｐｅｃｉｆｉｅｄ ｇｅｎｅｒａｔｉｏｎ ａｎｄ ｇｕｉｄｉｎｇ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ．Ｉｔ ｃａｎ ｈｅｌｐ ＵＳ ｔｏ ｇｉｖｅ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｔＯ ｂｏｔｈ ｓｅｃｕｒｉｔｙ ａｎｄ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ． Ｉｎ ｔｈｅ ｅｎｄ，ｕｓｉｎｇ ｔｈｅ ＭＡＴＬＡＢ ｔｏ ｓｉｍｕｌａｔｅ ｉｓ ｎｅｅｄｆｕｌ，ｉｔ ｃａｎ ａｌｓｏ ｐｒｏｖｅ ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ｏｆ ｔｈｉｓ ｉｄｅａ． Ｋｅｙｗｏｒｄｓ：Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ；Ｐａｔｈ ｐｌａｎｎｉｎｇ；ｃｏｎｖｅｒｇｅｎｃｅ 引言 机器人路径规划问题是人工智能学术里必不可少的一个研究方 向。通常我们关注两个方面：机器人如何获取最短的运行路径（高 效性），机器人如何避开已知或未知的障碍物（安全性）…。因 此，如何设计既兼顾高效性又兼顾安全性的路径规划算法就成了研 究的难点和重点。 １思路建模以及参数设置 １。１建模 将路径的起点与终点规划成一个直角坐标系。其中，起点为原 点（０，０），并以起点和终点作为矩形的两个顶点，画出一个矩形 框 作为我们的路径地图。在矩形内设置若干个大小、位置随机的 圆形作为障碍物。如图ｌ所示。 置和方向就构成了种群。而初始种群则是在算法开始运作之前，通 过随机数产生的一些运行方向和位置。该种群需要包含足够多的随 机因子（即有许多不同的运行方向和位置），因此必须让它足够大 并且能够适应遗传算法的应用要求。将２．０中所设计的编码组ｉｎ随机 的产生０个，并进行逐一记录（即有０个个体）。本文产生２００个ｉｎ 编码作为初始种群。这些个体的数值是由随机数构成的，数量也足 够多。因此，可以对它们进行遗传算法操作。 ２．３遗传算法的参数设定 初始种群中的每个个体均都有自己的特征，而每个特征的定义都 是未知的。通过一定的约束条件将它们的特征数据化，并通过数据比对 来进行保留或舍弃，而保留的个体又会经历各种不同的变化（选择： 保持不变、变异：发生定位变化、交叉：发生互相改变等），这就是遗 传算法的基本思想。而在此之上，将约束条件也进行一定规律的数据 化，使它们能够通过函数的改变来约束、引导算法达到预期的要求： 将每一步的终点数据应用在两个函数中进行比对。 ①与最终目标点的距离函数ｄ 当前这一步要运行到的位置点 ，ｙ ）到终点 ， ）的距离ｄ为： ｄ： ＝＝ ②已运行的路程函数Ｌ （１） 将每一步运行的位置点 ， ）与这一步的起点即前一个点 ， ．。） 的距离记录为，，并将每一个越行累加，即为已运行的路程函数Ｌ。 ｌ＝√（ｘ 一ｘ ，） ＋（） ．一ｙ ） ￡＝∑， （２） （３） 图１ １＿２环境参数 在Ｍａｔｌａｂ程序中，如图１，用一段程序来随机产生障碍物（以 圆形替代）。再用网格对我们的路径地图进行划分，每一个单位长 度视作一步。 有了以上参数，就可以通过算法兼顾到路径规划中的“全程最 短”和“单步最短”的问题了。 当然对于路径规划来说，还应该考虑到运行时的安全问题，可 加入一个参与判定的函数： ③判定障碍物与运行轨迹的距离函数Ｍ 将每一步的起点（ｘ ，Ｙ．－Ｉ）与终点（ …Ｙ）所连成的直线， 与圆心 ）进行判定，计算出圆心到直线的距离Ｍ。 ， （） 一ｙ １）一ｙｏ ｈ一（ｙ 一Ｉב＋１） √Ｌｙ 一ｙ“ｌ‘＋１ （４） ２基于遗传算法的路径规划基本设计思路 ２．１坐标设定及编码产生 将每一步的终点横坐标ｘ 和纵坐卡，ｊ 记录下来作为下一步的起 点。当进行到第ｎ步时，将纵坐标ｙ的数据通过一定比例转换成ｎ位 二进制数，使它能够适用于遗传算法的各项操作，这种二进制数即 为我们的编码组ｉｎ。 ，此时，通过Ｍ与半径ｒ的数值比对， 就有了判断运行轨迹是否 会撞上障碍物的办法。 ２．４适应度函数的选择条件 适应度函数决定着某个体是否会被淘汰、是否是优质个体的问题 Ｙ１） ａ２，ｎ）…－＋（ｘ ， ）】 它几乎掌握着遗传算法的“生杀大权”。因此，适应度函数的计算 十分重要，而如果适应度函数的选取不当，则更有可能影响到算法的收 敛速度以及准确地运行 Ｊ。此处，考虑到最短路径问题里要求的“全程 最短”和“单步最短”的两个参数，则有适应度函数： 。２．２初始种群的设定及产生 本文中，把每一步的目标位置都视作一个个体，许多不同的位 ，（ ）＝ｄ＋￡ （５） 由于还需要考虑障碍物的存在，因此加入判定：若直线与圆心 基金项目：南京大学金陵学院２Ｏ１４教学改革重点立项项目（编号：００１０５２１５０９）；基于遗传算法的智能小车路径规划的研究与设计（编 号２０１６１３６４６０１７Ｘ）。 电子世界・１７７・ ＥＬＥＣＴＲＯＮｌＣＳ ＷＯＲＬＤ・ 的距离Ｍ与圆半径ｒ的关系为Ｍ＜ｒ时，将该个体的适应度函数 ｘ）设 为．１，便于算法在下一次迭代时将这个个体进行舍弃或改变。而若 Ｍ＞ｒ时，则视作该条路径安全，将适应度函数的值准确的加入到个 体特征中以作参考。 …… ； ；３实例分析 流程图： 图５运行轨迹示意图 计算出起点到终点之间的线段距离Ｄ Ｄ＝ｌ８．６８ｌ５ 于是，规划出的路径Ｌ与起点到终点的线段距离Ｄ的差距为 △，＝￡一Ｄ＝１８．７５１５一Ｉ８．６８１５＝０．０７。 ５结束语 针对传统遗传算法 中无法兼顾多个目标的问题，通过对适 应度函数的适当改变（加入判定）对算法进行优化，以达到避障 的效果（安全性）。同时，兼顾到“全程最短”和“单步最短” 的两个参数，选取出了最优最简的路径，使得路径的规划办法变 得更加效率（高效性）。最后，通过Ｍａｔｌａｂ明了这一思路 的可行性及高效性。 图２路径规划流程图 图３遗传算法迭代流程图 参考文献 …张颖，昊成东，于谦．基于遗传算法的机器人路径规划ＩＪ１．沈阳建 筑工程学院学报（自然科学版），２００２（０４）． 【２１成明，唐振民，赵春霞，刘华军等．移动机器人路径规划中的图方 法应用综述［１１＿工程图学学报，２００８（４）：６～１４． 【３】张思才，张方晓．一种遗传算法适应度函数的改进方法Ｕ１＿计算 机应用与软件．２００６（０２）． 图４适应度函数选择流程图 Ｉ４１李擎，张伟，尹怡欣，王志良．一种用于最优路径规划的改进遗传 算法【Ｊ１．信息与控制，２００６（０４）． 『５１陈国良．遗传算法及其应用ＩＭ】．人民邮电出版社，１９９６． 作者简介： 林煦涵（１９９５一），男，本科，学生，主要研究方向：电子信 息科学与技术、机器人。 ４运行结果分析 使用Ｍａｔｌａｂ仿真时，将路径地图的横坐标均分为ｎ步，在每一步目 标点的选择时都进行了遗传算法，最后移动到终点，完成全程路径规 划。如图５所示，圆为设定的障碍物，实线是由改进遗传算法计算出的 最优路径，起点为（Ｏ，０），终点为（１８，５）路径总长度Ｌ为１８．７５１５。 孙海洋【通信作者】（１９８２一），男，讲师，主要研究方向： 智能控制算法 （上接第１７６页） 三、系统程序的设计 系统工作初始，需将整个程序进行初始化并清屏。系统开机 时会先显示“０８８．０”，即预制发射频率为８８ＭＨｚ，该频率将送入 ＢＨｌ４ｌ ５Ｆ，之后进入键盘扫描和显示子程序的循环。当有按键按下 时，程序将判断是哪个键被按下，然后执行相应的按键功能，并调用 ＬＣＤ显示所设置的发射频率；当没有键按下时，程序返回键盘扫描子 程序，并继续判断是否有键被按下。图４为系统主程序流程图。 软件系统中的关键部分在于码制转换与合成算法的实现。频 率数据需经码制转换程序由十进￥１］ＢＣＤ码转为十六进制，这是由 于ＢＨｌ４ｌ ５Ｆ的频率控制字为两个字节。两个字节中低ｌｌ位（ＤＯ． Ｄｌ０）为频率数据，其值乘以０．１ Ｒｐ为单位为ＭＨｚ的输出频率。高 ５位（Ｄ１ｌ—Ｄｌ ５）为控制位，Ｄ１１（ＭＯＮＯ）位为单声道／立体声控 制位，Ｄｌ １＝０时为单声道发射模式，Ｄ１ ｌ＝ｌ时为立体声发射模式。 ＤＩ２（ＰＤ０）、Ｄｌ ３（ＰＤ１）位用于相位控制，常规情况下均为０， 当Ｄｌ２Ｄｌ３＝０ｌ时，可使发射频率在最低处，Ｄｌ２Ｄｌ３＝１Ｏ时可使发射 频率在最高处。Ｄｌ４（ＴＯ）和Ｄ１５（Ｔ１）为测试模式控制，常规情 况下为０Ｏ，当ＴＯＴＩ＝１０时为测试模式。 ・１７８・屯子世界 四 结论 基于ＢＨ１４１５Ｆ的小功率无线调频发射器系统结构简单，频率设定 性较高，可用于多布点同步。在环境电磁兼容要求上，既能够有选择 地避开本地的调频电台，避免有意于扰，也能够在低功率的条件下控 制无意发射，对保障小调频同步广播技术的可靠性具有重要的意义。 参考文献 …韩雁．Ｃ５１单片机及应用系统设计ｆＭ１．电子工业出版社，２（）１６ 【２１陈帮媛．射频通信电路『Ｍ１．北京科学出版社，２（）（）２． 【３】李雪梅．无线调频功放的设计与制作…，电子世界，２０１３（６）：１２３． 【４】程俊红，戴青云由ＢＨ１４１ ５Ｆ组成的数控调频台Ｉｌ１ｌ黑龙江科技 信息，２（）１ １（１６）：５２． 。 ｌ５】燕济安．基于单片机的广播发射机监控系统设计分析【）１＿数字 技术与应用，２０１５（２）：５ 作者简介： 李晓林（１９８１一），女，吉林吉林人，硕士，长春职业技术学 院工程分院讲师。
