基于遗传算法的最美路径导航算法

摘要

本发明公开了一种基于遗传算法的最美路径导航算法，它采用序号编码的形式，对每个景点进行编号，路线以经过景点的编号来表示，便于编码和解码，并采用线性聚合优先权法处理多目标遗传算法（MOGA），设计由自适应概率控制的插入、删除和变异算子处理变长染色体遗传算法（Clv GA），添加排序算子缩小搜索空间，加快收敛。本发明能够达到原始设计要求，取得相应的有效解，良好的解决了获取最美路径的问题。并且用户可指定计算参数，在获得的解集中选取自身喜爱的路径。

主权项

一种基于遗传算法的最美路径导航算法，其特征在于该算法用于地图导航，其中：景点总数为n，算法中适应度函数为：$fit=\frac{1}{2}\left(\frac{1}{\pi }\right[\frac{\pi }{2}+\arctan \left(\right(\underset{i=0}{\overset{n}{\Sigma }}{p}_i-c\times p_{min})\times q+(-1\left)\right)\left]\right)+\frac{1}{2}(1-sin(\frac{\pi }{2}\times \frac{\underset{i=0}{\overset{n}{\Sigma }}{\mathrm{rank}}_i}{5\times n}\left)\right),$为n个景点的路程总长度和总评分，p_min为起点到终点的最短路程，c为用户路程额定参数；q为散列参数；采用序号编码的形式，对每个景点进行编号，则一条路线以起点编号0、途经景点的编号和终点编号n来表示，每一个基因均代表一条对应的路径；具体步骤为：1)设计起始路径作为初始基因，其中包括起点v0，终点vn，以及随机数个随机节点；每条路径中不应有重复的节点；2)设定起始最美路径为(v0，vn)，此路径不包含任何景点，只有起点和终点；设定每代种群为pop；3)设定算法最大迭代数目为maxGen，只要未达到此数目，则重复步骤4‑7；4)使用适应度函数计算pop中各基因个体g的适应度值；5)计算各基因个体的适应度值与当前代所有基因个体的适应度值总和的比值，产生一个随机数，找出适应度比值小于该随机数的基因个体，将此基因个体选出加入候选基因集；6)依次从候选基因集中选出个体g’，设定插入概率：取值范围为0.6～1、删除概率：取值范围为0.6～1和变异概率：取值范围为0～0.1，进行如下a‑d操作：a)如果满足插入概率，设定g’包含景点外的所有景点集合为候选集；从候选集中随机选取随机数个节点插入到g’中的随机位置，但插入位置不包括第一个节点的前面和最后一个节点的后面；b)如果满足删除概率，在g’中的随机位置删除随机数个景点，但删除操作后的子代中至少应包含起点和终点；c)如果满足变异概率，设定g’包含景点外的所有景点集合为候选集；从候选集中选择不包括起点和终点的随机数个节点，随机替换g’中相同数目的节点；d)对g’中的景点序列进行排序，排序规则为按照各景点到终点的距离，由远及近进行；7)将适应度值最大的基因gmax保存为最美路径；8)输出最美路径。