遗传算法的电子地图研究范文

本站小编为你精心准备了遗传算法的电子地图研究参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

1遗传算法原理及基本特点

1.1算法原理

遗传算法最早是由美国Michigan大学的Holland教授于1969年提出的，它主要是通过模拟大自然的淘汰生产法则和生物的进化过程形成的计算模型，在后期经过Dejong、Gol-dberg等学科专家归纳总结，形成一种全新的全局的优化搜索算法。在使用遗传算法的过程中，问题的每个可能的解都会被编码成一个“染色体”，称为染色体或者个体，若干个个体构成了种群。在初始种群产生后，通过适度函数给每个个体一个数值评价，按照适者生存和优胜劣汰的原理，淘汰适应度低的个体，并选择适应度较高的个体参加遗传操作。在遗传操作中，部分个体经过交叉和变异进行再组合生成新一代的种群。这个种群就像自然界进化一样，越往后的子代相对于初始种群能够更加适应新的环境，这样朝着最优解的方向不断进化最终得到更优解。

1.2遗传算法的优点

遗传算法充分运用大自然的遗传和进化的思想，完全不同于其他搜索方式，其明显的优点如下：

（1）快速随机的搜索能力。遗传算法本身具有很强的自适应和智能性。在搜索过程中，消除了基本的障碍，即需要能够先对问题的全部特点进行描述。搜索使用概率机制进行迭代，具有很高的随机性。同时，它不受优化函数的约束，也没有对优化函数的依赖性。

（2）搜索技术从群体出发，具有很好的并行性，可以同时进行多个个体的比较，可以降低对硬件的要求，从而减少巨额开支。

（3）搜索使用评价函数启发，过程相对简单。算法具有很好的扩展性，在实际应用过程中，容易与其他算法结合提升效率。算法简单易懂，能够较好地应用到实际操作中。

2路面特性与油耗关系

2.1汽车油耗影响因素

汽车在行驶过程中的油耗不仅关系到成本，同时也关系到绿色出行。汽车燃油经济性指标，是指汽车在一定标准的情况下，以最低能耗完成行驶定量路程的能力。在汽车的行驶过程中，能够影响汽车油耗的因素相对较多，主要有以下几类：汽车本身的性能，如汽车动力和传动系统，包括发动机、变速箱、车型、车重、轮胎等多种汽车内在因素，往往汽车越重，排量越大的汽车相对耗油量较高。驾驶技术的因素，作为司机在行车过程中，能否在合适的时候换挡（以手动挡为例），或者在行车过程中的一些良好的操作如红灯前空挡滑行、轻踩油门启动等，会直接影响汽车油耗。路面环境对汽车行驶影响。在道路上由于多种因素造成汽车在道路上缓慢行驶，如：堵车、路面情况复杂、发生交通事故等，这些会直接影响汽车在行进中燃油是否能够充分燃烧，燃油不能重复燃烧的后果是不仅耗油还会污染环境。从全局来看，提高燃油的经济性无外乎就是：一是提升燃油燃烧效率，二是降低负荷。而本文所研究的是在汽车重量一定的情况下，如何降低油耗，所以接下来会重点分析速度与燃油效率的关系。

2.2速度与油耗的关系

世界银行的HDM-3研究表明，在外国，部分公路在反复维修后，道路表面平整度减小，但是汽车的油耗反而更低。其重要原因是，在公路维修过后，道路的平整度相对减小，司机通过减速的方法来提升适应度，最终因车速的降低而使得在行驶过程中的空气阻力减小，进而减少耗油量。通过实践证明，汽车在行驶过程中，速度与油耗之间的关系呈U字形抛物线。即在起步阶段，油耗随着速度的提升不断下降，当速度提升到一定值后，汽车遇到的空气阻力不断增大，油耗随着速度的提升不断上升。

3基于遗传算法的最低油耗电子地图寻径

3.1个体编码及初始化

个体主要用于表示汽车在行进过程中的一条路线。小汽车由起点A经过途中所示范路线前行最终到达位置B，即为一个个体。个体以坐标的形式可以表现为：{（0，0，x）（0,1,x）（0,2,x）（0,3,x）（2,2,x）（3,3,x）（3,4,x）（3,0,x）（5,5,x）（6,7,x）}。其中前两位数分表代表横向和纵向值，第三位数代表着这段路程所能行驶的最大速度。初始化种群是由一定数目的个体组成，在小汽车运行的区间即A到B点之间，用随机选择、自由、不定的连续路径链接A和B。在初始化的时候，要确保选择进来的路径是能够通行的道路，且无死胡同，并且每个个体的长度尽可能地大于全路径的30%，再经过一系列的插入、删除操作，最终得到最低油耗路径。

3.2适应函数

个体的自适应函数直接关系到遗传算法的计算时间和工作效率。在设计过程中，要尽可能确保能够找到一条最低油耗路径，且该路线不会进入死胡同或者死循环。

3.3遗传算子

（1）繁殖算子。根据适应函数和个体适应度大小，使个体能够按照一定的概率向下繁殖。

（2）交叉变异算子。交叉指的是将两个父代的部分结构进行替换重组的操作，在这里主要选择重合点混合交叉的方式。即随机选取两个个体，在两个个体中，选择序号相同的道路进行交叉操作。变异则为在起点A和终点B之间随机选择一个序号作为变异点进行变异操作。

（3）删除、插入算子。定义汽车的运行方向时，主要是四个方向，分别是：前，后，左，右。为了尽可能地保证路径选择的合理性，以向前的方向及最低油耗值作为最优路线。所以汽车在行进过程中，反方向或者油耗过高的路线都会被删除，从而确保最低油耗路径的生成。插入算子主要是为了保持种群个体所对应路径的连续性。

3.4汽车前进路径规划算法路程

（1）个体编码，对所涉及问题的可能解进行染色体编码。选择操作主要使用选择重合点混合交叉的方式。即随机选取两个个体，在两个个体中，选择序号相同的道路进行交叉操作；

（2）计算种群上每个个体的适应度；

（3）按由个体适应值所制定的规则选择进入下一代的个体；

（4）按概率PC和Pm进行交叉操作和突变操作，生成新鲜的群体；

（5）若经过交叉及突变并没有生产某种停止条件，则转入到2），否则继续进入下一步；

（6）输出种群适应度最优的染色体作为问题最优解或最终解。

作者：周文彬罗莹单位：江西师范大学软件学院江西中医药大学现代中药制剂教育部重点实验室