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

摘要

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

说明书

技术领域

本发明涉及智能优化算法领域，具体地说是一种基于遗传算法的最美路径导航算法，应用于地图导航中获取最美路径。

背景技术

使用地图导航已经变得越来越普及，普通导航通常选取两地之间最短或最方便的线路，但路途枯燥乏味。能否让导航获得的路线变得精彩起来已逐渐成为研究热点。雅虎实验室于2014年8月在ACM会议上提出了最美路线的问题，即旅途过程中不仅仅关注于最短路线，同时也关注于路线经过的地方风景是否优美。传统的GPS地图程序，用户只需要输入起始点和终点，就可以得到一个最短的行进路径。但这通常仅适合赶时间的用户而非游客。游客通常希望从起点到终点的路途中，能沿途看到美丽的景色。但此类问题目前还处于理论研究阶段，实验数据也多为小范围地图，当前并未投入到实际应用中。由于采集景点数据量大，制定标准复杂，因此开发全自动高性能的算法具有一定难度。

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化算法，它借鉴了达尔文的进化论和孟德尔的遗传学说。它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。

遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、变异、自然选择以及杂交等。

遗传算法通常实现方式为一种计算机模拟。在算法中，优化问题的解被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。

下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的，其中繁殖包括交叉(crossover)和变异(mutation)。

选择则是根据新个体的适应度进行的，但同时并不意味着完全的以适应度高低作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。

之后，被选择的个体进入交叉过程。一般的遗传算法都有一个交叉概率，范围一般是0.6～1，这个交叉概率反映两个被选中的个体进行交叉的概率。每两个个体通过交叉产生两个新个体，代替原来的“老”个体，而不交叉的个体则保持不变。交叉父母的染色体相互交换，从而产生两个新的染色体。

下一步是变异，通过变异产生新的“子”个体。一般遗传算法都有一个固定的变异概率，通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的变异，通常就是改变染色体的一个字节(0变到1，或者1变到0)。

经过这一系列的过程(选择、交叉和变异)，产生的新一代个体不同于初始的一代，并迭代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交叉，然后突变，产生第三代。周而复始，直到终止条件满足为止。

生物的进化过程主要是通过染色体之间的交叉和变异来完成的。基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。

针对最美路径导航问题的分析，采用遗传算法进行求解存在两方面问题：

问题1：变长染色体的处理问题。不同于传统遗传算法中定长染色体序列，路径导航结果路线应为变长序列。

问题2：途经路线长度和沿途景点选取两者的平衡选择问题。不同于传统遗传算法中单目标优化问题，路径导航涉及多目标优化问题。

相较于传统的遗传算法采用定长的染色体，获取最美路径问题中路径节点为变化的，即染色体为变长。为了保持在进化过程中，染色体的长度是可变的，传统的交叉和变异算子将不再适用。其次，并不是一个随机的节点序列就可以表示为一条有用路径，还需要考虑到是否有节点重复等问题。另外，为简化问题描述和编解码，采用序号编码相较于二进制编码更有优势。

适应度函数在遗传算法中的作用举足轻重。适应度函数设计应满足以下条件：规范性、合理性、单值、连续、计算量小、通用性。另外，设计适应度函数应注意两个遗传算法的欺骗问题：算法初期，种群中出现的少数适应度较高的个体会充斥整个种群，使产生新个体的操作失去作用，算法迅速收敛到一个局部最优解；算法后期，种群中个体之间差异缩小，算法失去竞争性，退化成随机选择过程。设计适应度函数时，需要对函数式进行优化。优化目标为保证适应度值不局限于一个很小的子区间；越靠近最优解，适应度值变化越灵敏；在平均适应度值以下的个体，适应度值下降更快。

发明内容

本发明的目的是提供一种基于遗传算法的最美路径导航算法，该算法能够达到原始设计要求，取得相应的有效解，良好的解决了获取最美路径的问题。

本发明的目的是这样实现的：

一种基于遗传算法的最美路径导航算法，该算法用于地图导航，其中：景点总数为n，算法中适应度函数为：

$>\mathrm{fit}=\frac{1}{2}\left(\frac{1}{\pi }\right[\frac{\pi }{2}+\arctan ((\underset{i=0}{\overset{n}{\Sigma }}{p}_i-c\times p_{\min })\times q+(-1))\left]\right)+\frac{1}{2}(1-\sin (\frac{\pi }{2}\times \frac{\underset{i=0}{\overset{n}{\Sigma }}{\mathrm{rank}}_i}{5\times n}))$>

为n个景点的路程总长度和总评分，p_min为起点到终点的最短路程，c为用户路程额定参数；q为散列参数；采用序号编码的形式，对每个景点进行编号，则一条路线以起点编号0、途经景点的编号和终点编号n来表示，每一个基因均代表一条对应的路径；具体步骤为：

1)设计起始路径作为初始基因，其中包括起点v₀，终点v_n，以及随机数个随机节点；每条路径中不应有重复的节点；

2)设定起始最美路径为(v₀，v_n)，此路径不包含任何景点，只有起点和终点；设定每代种群为pop；

3)设定算法最大迭代数目为maxGen，只要未达到此数目，则重复步骤4-7；

4)使用适应度函数计算pop中各基因个体g的适应度值；

5)计算各基因个体的适应度值与当前代所有基因个体的适应度值总和的比值，产生一个随机数，找出适应度比值劣于该随机数的基因个体，将此基因个体选出加入候选基因集；

6)依次从候选基因集中选出个体g’，进行如下a-d操作：

a)如果满足插入概率，设定g’包含景点外的所有景点集合为候选集；从候选集中随机选取随机数个节点插入到g’中的随机位置，但插入位置不包括第一个节点的前面和最后一个节点的后面；

b)如果满足删除概率，在g’中的随机位置删除随机数个景点，但删除操作后的子代中至少应包含起点和终点；

c)如果满足变异概率，设定g’包含景点外的所有景点集合为候选集；从候选集中选择不包括起点和终点的随机数个节点，随机替换g’中相同数目的节点；

d)对g’中的景点序列进行排序，排序规则为按照各景点到终点的距离，由远及近进行；

7)将适应度值最大的基因g_max保存为最美路径；

8)输出最美路径。

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

附图说明

图1为本发明中的插入算子示意图；

图2为本发明中的删除算子示意图；

图3为本发明中的变异算子示意图；

图4为本发明中的排序算子示意图；

图5为本发明的流程图；

图6为本发明实施例算得的十个结果示意图；

图7为本发明实施例的路径在地图上的示意图。

具体实施方式

以下结合附图对本发明进行详细描述。

本发明是一种基于遗传算法的最美路径导航算法，该算法用于地图导航。

假设有一个无向图M＝(V,R,E)，其中节点集V＝{v_i}(i＝1,2,…N)表示各节点，评分集R＝{r_i}(i＝1,2,…N)表示每个节点的优美度评分，以及边集E∈V*V表示联结节点的边。两个节点之间的开销和优美度评分均是非负的整数。路径表示为一个节点序列(v_i,v_k,v_l,…,v_m,v_j)，且路径中相同的节点不能出现两次。此路径的优美度总评分为最美路径则为总路径长度最小且优美度总评分最高。

景点总数为n，算法中适应度函数为：

$>\mathrm{fit}=\frac{1}{2}\left(\frac{1}{\pi }\right[\frac{\pi }{2}+\arctan ((\underset{i=0}{\overset{n}{\Sigma }}{p}_i-c\times p_{\min })\times q+(-1))\left]\right)+\frac{1}{2}(1-\sin (\frac{\pi }{2}\times \frac{\underset{i=0}{\overset{n}{\Sigma }}{\mathrm{rank}}_i}{5\times n}))$>

为n个景点的路程总长度和总评分，p_min为起点到终点的最短路程，c为用户路程额定参数；q为散列参数。

依据现实意义，设定路径距离和优美度评分在适应度函数中的权重比例为1:1；使用三角函数的图形特点来规避遗传算法的两个欺骗性问题；添加参数将数据归一化，并均匀散列在函数作用范围内。这样设计的意义在于：1.算法初期能够尽快淘汰适应度值较低的个体；2.算法后期能够有效拉开最优解附近点的适应度值，作为一种鼓励手段便于做出敏感选择，避免陷入次优解。

采用序号编码的形式，对每个景点进行编号，则一条路线以起点编号0、途经景点的编号和终点编号n来表示，每一个基因均代表一条对应的路径；具体步骤为：

1)设计起始路径作为初始基因，其中包括起点v₀，终点v_n，以及随机数个随机节点；每条路径中不应有重复的节点；

2)设定起始最美路径为(v₀，v_n)，此路径不包含任何景点，只有起点和终点；设定每代种群为pop；

3)设定算法最大迭代数目为maxGen，只要未达到此数目，则重复步骤4-7；

4)使用适应度函数计算pop中各基因个体g的适应度值；

5)计算各基因个体的适应度值与当前代所有基因个体的适应度值总和的比值，产生一个随机数，找出适应度比值劣于该随机数的基因个体，将此基因个体选出加入候选基因集；

6)依次从候选基因集中选出个体g’，进行如下a-d操作：

a)如果满足插入概率，设定g’包含景点外的所有景点集合为候选集；从候选集中随机选取随机数个节点插入到g’中的随机位置，但插入位置不包括第一个节点的前面和最后一个节点的后面；

b)如果满足删除概率，在g’中的随机位置删除随机数个景点，但删除操作后的子代中至少应包含起点和终点；

c)如果满足变异概率，设定g’包含景点外的所有景点集合为候选集；从候选集中选择不包括起点和终点的随机数个节点，随机替换g’中相同数目的节点；

d)对g’中的景点序列进行排序，排序规则为按照各景点到终点的距离，由远及近进行；

7)将适应度值最大的基因g_max保存为最美路径；

8)输出最美路径。

实施例

以上海为起点，成都为终点。采用雅虎地图导航两地间的路线，在路线周边选取48个城市作为景点，对包含起止点的每个城市编号，其中起点为0，终点为49。

景点评分按照百度百科信息打分，分数等级为1-5分，五个等级，起点和终点的评分均为0，分数等级5为最优。

具体步骤：

1)设定起始路径，其中包括起点上海，终点成都，以及随机数个随机景点。将起始路径作为初始基因；

2)设定起始最美路径为(上海，成都)，此路径不包含任何景点，只有起点和终点；设定每代种群数量为50000；

3)设定算法最大迭代数目为100000，只要未达到此数目，则重复步骤4)-7)；

4)适应度函数：

$>\mathrm{fit}=\frac{1}{2}\left(\frac{1}{\pi }\right[\frac{\pi }{2}+\arctan ((\underset{i=0}{\overset{n}{\Sigma }}{p}_i-c\times p_{\min })\times q+(-1))\left]\right)+\frac{1}{2}(1-\sin (\frac{\pi }{2}\times \frac{\underset{i=0}{\overset{n}{\Sigma }}{\mathrm{rank}}_i}{5\times n}))$>

其中p_min为上海到成都的路径长度1963.2，c设定为1.5；

使用适应度函数计算每代种群中各基因个体g的适应度值；

5)计算各基因个体的适应度值与当前代所有基因个体的适应度值总和的比值，产生一个随机数，找出适应度比值劣于该随机数的基因个体，将此基因个体选出加入候选基因集；

6)依次从候选基因集中选出个体g’，进行如下a)-d)操作：

a)如果满足插入概率，设定g’包含景点外的所有景点集合为候选集；从候选集中随机选取随机数个节点插入到g’中的随机位置，但插入位置不包括第一个节点的前面和最后一个节点的后面；如附图1中，若父代染色体为(0,5,2,49)，经过插入算子操作后一种可能的结果为(0,3,5,2,7,49)；

b)如果满足删除概率，在g’中的随机位置删除随机数个景点，但删除操作后的子代中至少应包含起点和终点；如附图2中，若父代染色体为(0,3,5,2,7,49)，经过删除算子操作后一种可能的结果为(0,5,2,49)；

c)如果满足变异概率，设定g’包含景点外的所有景点集合为候选集；从候选集中选择随机数个节点(不包括起点和终点)，随机替换染色体中相同数目的节点；如附图3中，若父代染色体为(0,3,5,2,7,49)，经过变异操作后一种可能的结果为(0,8,5,2,4,49)；

d)对g’中的景点序列进行排序，排序规则为按照各景点到终点的距离，由远及近进行；如附图4中，若父代染色体为(0,6,4,3,49)，经过排序算子操作后得到(0,4,3,6,49)，经过排序的路径要明显好于未排序的路径；

7)将适应度值最大的基因g_max保存为最美路径；

8)输出最美路径。

算法运行获得的十组结果如图6中所示。由图中可知，在获取的多组解中，路程长景点多的路线以及路程稍短景点较少的路线，随着路程数增加，相应的评分也会增加，用户可以根据自身喜爱选取最偏爱的路径。

图7中显示了图6中路线(0,3,5,2,15,17,33,37,49)在地图上的真实路径：上海、嘉兴、苏州、杭州、黄山、武汉、重庆、乐山、成都。可以看出在路径上的城市均为国内有名的旅游城市，符合现实情况，亦达到设计要求。