遗传算法的研究与优化

来源:用户上传      作者:

　　摘要：针对遗传算法具有全局搜索和收敛速度快的特点，在机器人控制器中实现遗传算法，使机器人自主学习，不断进化，最后成功通过一个随机的迷宫。在遗传算法中引入精英个体，在每次进化逐渐降低变异率与交叉率实现二次启发，实验结果表明，改进后的算法与传统遗传算法相比具有更快的寻优速度。
　　关键词：遗传算法；二次启发式；机器人控制器
　　引言
　　90年代，学术界出现了很多以复杂问题为对象的新范畴，如NPC类型的组合优化问题与非线性多模型，遗传算法是求解多目标函数的优化问题的最佳工具之一[1]。遗传算法的搜索空间可以涵盖解空间的许多点并能快速收敛，它的这种特点使得它在智能领域中占有越来越重要的地位。通过在真实世界应用程序中实现遗传算法，人们有可能解决传统计算方法几乎不能解决的问题[2]。
　　1机器人控制器的设计原理
　　机器人控制器通过传感器的指令去导航机器人，本文设计的机器人控制器有6个传感器，两个在两侧，三个在前面，一个在后面，当传感器检测到墙时会激活，它可以执行四种动作，向前一步，左转，右转，或者什么也不做。
　　物理上评估上图所示的机器人控制器很难，并且所需的時间非常长，评估规模比较大的种群中每个个体任务异常艰巨[3]。因此本文对机器人控制器的评估方法是，建立物理机器人和环境（迷宫）的模拟模型，这样就能在软件上快速评估每个控制器。用迷宫作为一个复杂的环境去测试机器人控制器，该迷宫由墙构成，机器人不能穿墙，这是希望机器人遵循的[4，5]。
　　在机器人每次穿行中，由于迷宫中的“墙”是固定的，6个传感器在机器人下次穿行中通过相同位置的状态是不变的。本文要解决的问题是当机器人在某个位置时，如何基于传感器的指令做出正确的动作。由于机器人穿过的迷宫不同，传感器的指令也不同，针对所有可能的指令对动作进行编码，利用遗传算法得出的结果去设计机器人控制器，并将其应用于真实环境中的物理机器人。
　　2二次启发式遗传算法的实现
　　2.1编码
　　首先对机器人所做出的四个动作用二进制表示。“00”表示什么也不做，“01”表示前进，“10”表示左转，“11”表示右转。用二进制表示机器人控制器的指令集，用“1”表示传感器激活，“0”表示传感器未激活。若只有前传感器和左传感器被激活，那么控制器的指令集为000011，从左到右依次为后传感器，右传感器，左传感器，右前传感器，左前传感器，前传感器的状态。64个二进制指令集转换成十进制对应着0到63中的某一位数，因此基于传感器的指令集按“位”对动作进行编码。编码的染色体一共有64组“动作”，每一组代表着机器人控制器基于某个传感器指令所做出的动作。
　　2.2初始化种群
　　本文采用随机的方法初始化种群，种群中每个个体将被随机初始化，每个染色体由随机产生1或0的128个基因构成。
　　2.3评估并保留精英个体
　　在Java语言里，Maze类中的scoreRoute方法来对机器人的行走路线创建适应度函数，机器人每经过一次“3”位置，就可以增加个体的适应度。calcfitness方法将Individual类（操作个体的类），Maze类，与Robot类联系在一起，对机器人的行走路线进行评分，并保存为个体的适应度，并对种群中每个个体基于适应度进行排序，选出“精英个体”。
　　2.4 终止检查
　　本文中的二次启发式遗传算法的终止条件有两个。其一是迷宫中机器人最佳的行走路线被完全探索后终止，输出最优个体。另一个终止条件为允许算法运行的最大世代数。
　　2.5 选择
　　采用“轮盘赌”的方法选择亲代参与交叉。根据种群中每个个体的适应度值，将他们放置在一个假想的轮盘上，个体的适应度值越高它在轮盘所占的空间越多。本文采用反向实现轮盘赌的选择方法，我们在轮盘上“标记”一个位置，然后旋转轮盘等待“个体”落入。
　　2.6 交叉
　　在交叉过程中，种群的个体交换他们的遗传信息创建一个新的个体，包含亲代基因中最好的部分。本文采用的交叉方式为两点交叉，在这种方法中，随机选取基因组的两个位置，确定哪些基因来自哪个亲代。
　　2.7 变异
　　变异算子在二次启发式遗传算法中起到逃离局部最优和取得接近最优解的作用。本文采用“位翻转”的变异方法完成对个体的变异，根据位的初始值，将1翻转为0，将0翻转为1。
　　2.2.6 二次启发
　　在算法中更新变异率与交叉率实现二次启发。从较高的比率开始，随着算法的进行，逐渐降低变异率和交叉率[8]。
　　3 实验调试与结果分析
　　基于二次启发式遗传算法设计机器人控制器的原理，采用Java语言对算法进行设计与实现。
　　3.1算法参数
　　Input：，迷宫实例，种群规模populationSize，变异率mutationRate，交叉率crossoverRate，精英个体的数量elitismCount，冷却率coolingRate。
　　Output：每代种群中最优个体的遗传信息及适应度值，完成进化经过的世代数，最优个体的遗传信息及其适应度值。
　　initializeMaze；
　　3.2实验结果分析
　　参数设置：
　　种群规模：150，交叉率：0.85，变异率：0.04，精英个体数量：2，冷却率：0.005，染色体长度：128。
　　迷宫对象：10*10d的矩阵
　　程序代码在idea软件上运行。输入相应的参数，多次运行程序，。
　　3.2.1实验结果分析
　　取得或胜的染色体，将它编程写入一个物理机器人，该传感器控制器会做出适当的动作，在迷宫中穿行，并且在任何迷宫中，都不会撞墙，成功通过迷宫。 　　在本次实验的迷宫中，正确的位置“3”一共有34处，因此，最优个体的适应度应为“34”，采用二次启发的遗传算法会加快寻优速度，可以在更快更少的时间里找到最好的解。
　　4.结论
　　本文利用软件模拟机器人及其环境，从而节省时间，也避免了人工设计的困难。利用改进后的遗传算法对机器人控制器进行设计，引入“精英个体”的概念，在每次进化中保留最适合的个体，直接加入到下一代种群中，使种群中最优秀的遗传信息不会在交叉与变异中丢失，同时在每次进化中降低种群中两个重要参数（交叉率和变异率）实现二次启发，最初值较高的两个参数，使得算法始终搜索解空间的大块区域，随着参数值降低，算法开始专注搜索解空间中适应度较高的区域。实验对比结果表明，改进后的算法具有较快的寻优速度。当机器人传感器数量增多，编码任务会变得艰巨，种群规模变大，会使得进化代数较多，运行时间较长，在今后的工作中应加以改进。
　　参考文献
　　[1]刘曙光，费佩燕，侯志敏.生物进化论与人工智能中的遗传算法[J].自然辩证法研究，1999
　　[2]David A.Grossman，Ophir Frieder.最新算法与启发式算法[M].北京：人民邮电出版社，2010
　　[3]Lee Jacobson，Burak Kanber.Java遗传算法编程[M]. 北京：人民邮电出版社，2016
　　[4]周明，孙树栋，彭炎午. 使用遗传算法规划移动机器人路径[ J ]. 西北工业大学学报，1998
　　[5]孟庆鑫，王晓东.机器人技术基础[M].哈尔滨：哈尔滨工业大学出版社，2006（9）：52-66
　　[6]孙树栋，林茂.基于遗传算法的多移动机器人协调路径规 划[J].自动化学报，2000，26（5）：672-676.
　　[7]唐飞，滕弘飞.一种改进的遗传算法及其在布局优化中的应用 [ J ] .软件学报，1999，10（10）：1096-1102.
　　[8]周明，孫树栋，彭炎午，基于遗传模拟退火算法的机器人路径规划[J].航空学报，1998，19（1）：115-120.
　　作者简介：王迪，男，1994年8月5日，吉林省白山市，研究方向：物联网。
　　（作者单位：西南民族大学电气信息工程学院）
转载注明来源:https://www.xzbu.com/1/view-14738018.htm