一种基于鸟类物种进化机制的路径优化方法

摘要

本发明公开一种基于鸟类物种进化机制的路径优化方法，包括：随机生成若干条可行路径，每一条路径对应一只鸟类的染色体，每一个节点对应染色体上的一个基因，基因长度为路径长度，基因顺序为路径节点顺序；确定经过可行路径所需的花费作为适应性函数；根据经过每条可行路径花费的多少对可行路径进行排序，并对其进行分类；计算利用多夫多妻制类的可行路径的数目，并重新随机生成一定比例的新可行路径，替代属于多夫多妻制类的可行路径；各条可行路径按照其所属鸟类物种进化方式进行繁殖重构，完成繁殖重构后，比较父代个体与子代个体的路径长度，保留花费少的可行路径；重复迭代到达设定的迭代次数阈值，获取若干条可行路径；对获取的可行路径中选取花费最少的路径作为优选路径。

说明书

技术领域

本发明涉及网络路径优化领域，更具体地，涉及一种基于鸟类物种进化机 制的路径优化方法。

背景技术

最短路径问题是网络优化中最基本的问题，在多跳网络的路由分配以及在 事故抢修、交通指挥、GPS导航等行业应用中使用的非常广泛，快速的路径寻 优算法能使系统可以充分的利用网络资源，满足客户需求。

(1)求解单源最短路径的取值非负问题，最经典的方法为Dijkstra算法， Dijkstra算法又称为单源最短路径，它能求从一个顶点出发，到所有可到达顶点 的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法的优点是100％能得出最短路径的最优解，但由于它遍历计算的节 点很多，所以有效率低的缺点。

(2)Chang Wook Ahn等提出利用遗传算法求解最短路径问题，该方法把 可行路径分解成若干段，在保证路段拓扑连通性的前提下，利用交叉算子交互 可变路段，利用变异算子引入新的路段，不断迭代直到算法收敛得到最短路径。 该法的主要缺点有两个：一是算法对新空间的探索能力是有限的，容易收敛到 局部最优解。二是算法属于随机类算法，需要多次运算，结果的可靠性差，不 能稳定的得到解。

鸟类是世界上最大的四足类脊椎动物，鸟类繁殖进化的过程与优化问题有 很多共通之处，鸟类共有5种繁殖方式，包括单性生殖，单配制，一夫多妻制， 一妻多夫制度，多夫多妻制，每只鸟类将按照其自身的方式繁衍后代。

发明内容

为了克服上述现有路径寻找方法存在的不足，本发明提出一种基于鸟类物 种进化机制的路径优化方法，寻找出最短的路径，该方法模仿了鸟类物种特有 的衍化后代的方式，通过模仿鸟类的繁殖进化方式来求解图论中的最短路径问 题，能够提高寻优效率和收敛速度。

为了解决上述的不足，本发明的技术方案为：

一种基于鸟类物种进化机制的路径优化方法，包括：

S1.随机生成若干条可行路径，每一条路径对应一只鸟类的染色体，每一个 节点对应染色体上的一个基因，基因长度为路径长度，基因顺序为路径节点顺 序；

S2.确定经过可行路径所需的花费作为适应性函数；

S3.根据经过每条可行路径花费的多少对可行路径进行排序，并对其进行分 类，其具体分类方式如下：

1)根据花费的多少将可行路径分为雌性类和雄性类，其中，花费小于等于 阈值A时，则对应的可行路径属于雌性类，否则属于雄性类；

2)对属于雌性类的可行路径进行分类，根据花费将其分为单性生殖类和一 妻多夫制类，其中，花费小于等于阈值B时，则对应的可行路径属于单性生殖 类，否则属于一妻多夫制类；

对属于雄性类的可行路径进行分类，根据花费将其分为单配制类、一夫多 妻制类和多夫多妻制类，其中，花费小于等于阈值C时，则对应的可行路径属 于单配制类，花费大于阈值C且小于等于阈值D时，则属于一夫多妻制类，花 费大于阈值D时，则属于多夫多妻制类；

其中A>B，D>C>A；

S4.计算属于多夫多妻制类的可行路径的数目为E，并重新随机生成αE个 新可行路径，0<α<1，替代属于多夫多妻制类的αE个可行路径；

S5.对各条可行路径按照其所属鸟类物种进化方式进行繁殖重构，完成繁殖 重构后，比较父代个体与子代个体的路径长度，保留花费少的可行路径；

S6.重复步骤S3到S5直到到达设定的迭代次数阈值，获取若干条可行路径；

S7.对步骤S6获取的可行路径中选取花费最少的路径作为优选路径。

优选的，所述步骤S5中所述的各条可行路径按照其所属鸟类物种进化方式 进行繁殖重构的具体方式如下：

当可行路径属于单性生殖类时，其繁殖重构方式为：

101)为每个节点生成一个节点变异概率rn_i，当rn_i大于节点变异概率阈值 时，则该节点发生变异，两个变异节点间的基因片段为待变异基因片段；

102)为每个待变异基因片段生成一个基因变异概率rpv_j，当rpv_j大于基 因片段变异概率阈值时，该基因片段发生变异，根据该段基因的首尾节点重新 生成一条可行路径替换掉对应的待变异基因片段；

当可行路径属于单配制类时，则与属于单性生殖类或一妻多夫制类的可行 路径进行繁殖重构获取子代个体，其具体方式为：

201)搜索两条可行路径间相同的节点，并以首尾节点相同的部分路段集作 为待交换基因片段；

202)当待交换基因片段交换概率rpc_j大于交换阈值时，则基因片段交换；

当可行路径属于一夫多妻制类时，则与雌性类的可行路径进行繁殖重构获 取子代个体，其具体方式为：

301)搜索属于雄性类可行路径与其他所有属于雌性类可行路径相同的基因 片段；

302)将阈值大于基因交换概率的基因片段找出，再使用变异概率最大的等 位基因片段进行交换；

当可行路径属于一妻多夫制类时，则与属于雄性类的可行路径进行繁殖重 构获取子代个体，其具体方式为：

401)搜索属于雌性类可行路径与其他所有属于雄性类可行路径相同的基因 片段；

402)将阈值大于基因交换概率的基因片段找出，再使用变异概率最大的等 位基因片段进行交换；

当可行路径属于多夫多妻制类时，则与属于雌性类的可行路径进行繁殖重 构获取子代个体，其具体方式为：

501)搜索所有属于雌性类可行路径与其他所有属于雄性类可行路径相同的 基因片段；

502)将阈值大于基因交换概率的基因片段找出，再使用变异概率最大的等 位基因片段进行交换。

优选的，所述确定的适应性函数为路径长度、时间、延误、费用或排放，

当适应性函数为路径长度时，即根据路径的长短对可行路径进行分类，路 径长则花费多，路径短则花费少；

当适应性函数为时间时，即根据经过可行路径时间的长短对可行路径进行 分类，时间长则花费多，时间短则花费少；

当适应性函数为延误时，即根据经过可行路径延误的时间长短对可行路径 进行分类，延误时间长则花费多，时间延误短则花费少；

当适应性函数为费用时，即根据经过可行路径所需费用的多少对可行路径 进行分类，费用多则花费多，费用少则花费少；

当适应性函数为排放时，即根据经过可行路径所需排放的多少对可行路径 进行分类，排放多则花费多，排放少则花费少。

优选的，所述可行路径的路径长度的具体计算方式如下：

$l=\underset{i=S}{\overset{D}{\Sigma }}\underset{j\ne i}{\overset{D}{\underset{j=S}{\Sigma }}}{C}_{\mathrm{ij}}·I_{\mathrm{ij}}$

C_ij为节点i到节点j间的价值系数，S、D分别表示目标路径的首、尾节 点；I_ij表示节点i到节点j间路段是否属于目标路径，

优选的，在步骤S6获取若干条可行路径后，还对其中重复路段进行消除， 即将重复节点中路段去掉。

与现有技术相比，本发明的有益效果为：

(1)相对于传统的Dijkstra算法，本发明利用了鸟类进化算法和路径基因 编码实现了一种更为高效的最短路径选择方式。

(2)模仿鸟类繁殖进化的优化策略使得该算法相较与其他启发类搜索算法 而言有更快的收敛速度及求解能力。

附图说明

图1是可行路径编码示意图。

图2是鸟类单性生殖产生新路径的方式示意图。

图3是鸟类单配制产生新路径的方式示意图。

图4是本发明算法流程框架图。

图5是实验路网(广州大学城)示意图。

图6对图5寻找的最短路径示意图。

图7是采用本发明优化算法的收敛曲线图。

具体实施方式

下面结合附图对本发明做进一步的描述，但本发明的实施方式并不限于此。

最短路径寻优是网络优化和图论中的基础问题，指从某顶点出发，沿图的 边到达另一顶点所经过的路径中，求各边上权值之和最小的一条路径——最短 路径。

最短路径寻优问题的数学表达如下：网络拓扑结构可由一个有向图G(N,A) 表达。其中N表示网络中的节点的集合，A表示网络中的有向边集合，每一条 有向边都对应一个价值系数C_ij，表征有向边的属性(如时间，长度等)，其下 标i，j为有向边的首尾节点，路径的首，尾节点分别为S，D。I_ij表示节点i到 节点j间路段是否属于目标路径。

I_ij可以做如下定义：

最短路径的网络优化算法描述如下

Minimize

$\underset{i=S}{\overset{D}{\Sigma }}\underset{j\ne i}{\overset{D}{\underset{j=S}{\Sigma }}}{C}_{\mathrm{ij}}·I_{\mathrm{ij}}$

Subject to

And

I_ij∈{0,1},for all i.

其中优化的目标为选取路径使得经过的路径花费最少(当价值系数为路段 长度、时间，延误，费用，排放等参数时，最优解即为最短路径)。其中优化模 型中的第一个约束确保路径在起终点间是连通的，第二个约束确保没有重复路 径的出现。

采用鸟类基因对可行路径进行表达

在鸟类繁殖进化优化算法中，每只鸟个体表示一个可行解，在本实施方式 中即为一条可行路径，在应用该进化算法前，需要将可行解进行基因编码，对 于一条包含N个节点的可行路径，可用一条长度为N的染色体表示，N应小于 路网节点的最大值，节点在路径上的排序对应基因在染色体上的排序。

图1为将一条可行路径编码成一条染色体的例子，首位基因和末位基因对 应路径的起终点。可行路径应满足连通和非重复两个条件，值得注意的是寻找 初始可行路径时保证路径的连通性是比较简单的，但常会出现路径中出现重复 路段，此时只要将相同节点间的节点去掉即可。

根据鸟类繁殖方式对可行路径进行分类

鸟类分为雄性和雌性，每一个个体又会按照不同的方式繁殖进化，参照物 种进化原理和自然界中的规律，设计如下可行路径分类方法。

首先随机生成若干条可行路径，每一条路径为一只鸟类的染色体，每一个 节点对应染色体上的一个基因，基因长度为路径长度，基因顺序为路径节点顺 序。然后确定适应性函数，在本实施方式中适应度函数设为路径长度，接着根 据每条可行路径的路径长度为鸟类排序。随后根据排序截取相应的区间进行分 类，具体如下。

首先按性别分，拥有较好基因的个体分到雌性群体中，其余的分到雄性群 体中。其次按繁殖方式分，雌性群体可等分为两类，拥有较好基因的个体分入 第一类，采用单性生殖的方式繁殖，其余的分入第二类，采用一妻多夫制繁殖。 雌性群体可分为三类，拥有较好基因的个体分入第一类，采用单配制繁殖，拥 有次好基因的个体分入第二类，采用一夫多妻制繁殖，其余的分入第三类，采 用多夫多妻制繁衍后代。

则可行路径的分类方式为：

1)根据路径长度的长短将可行路径分为雌性类和雄性类，其中，路径长度 小于等于阈值A时，则对应的可行路径属于雌性类，否则属于雄性类；

2)对属于雌性类的可行路径进行分类，根据路径长度将其分为单性生殖类 和一妻多夫制类，其中，路径长度小于等于阈值B时，则对应的可行路径属于 单性生殖类，否则属于一妻多夫制类；

对属于雄性类的可行路径进行分类，根据路径长度将其分为单配制类、一 夫多妻制类和多夫多妻制类，其中，路径长度小于等于阈值C时，则对应的可 行路径属于单配制类，路径长度大于阈值C且小于等于阈值D时，则属于一夫 多妻制类，路径长度大于阈值D时，则属于多夫多妻制类；

其中A>B，D>C>A。

根据鸟类进化方式对可行路径进行繁衍重构

鸟类分为雄性和雌性，雌性拥有种群中最好的基因。鸟类共有5种繁殖方 式，包括单性生殖，单配制，一夫多妻制，一妻多夫制度，多夫多妻制。在算 法中，将采用对应的方式产生新的解数据

(1)单性生殖，即雌鸟不需要雄鸟的帮助便能独立完成繁殖过程，对应雌性 鸟类自身基因的变异，在繁殖的过程中，雌鸟自身染色体的某些基因片段会随 机改变，对应单性生殖方式的新路径产生方法如下：模仿鸟类单性生殖产生的 新路径的过程分为两步，第一步随机生成需要变异的基因片段，第二步在相应 的基因位(路段节点位置)重新生成可行路径完成变异，如图2所示。

第一步：为每个节点生成一个节点变异概率rn_i，当rn_i大于节点变异概率 阈值时，节点发生变异，两个变异节点间的基因片段为待变异基因片段。

第二步：为每个待变异基因片段生成一个基因变异概率rpv_j，当rpv_j大于 基因片段变异概率阈值时，该基因片段发生变异，根据该段基因的首尾节点重 新生成一条可行路径替换掉原来相应的部分。

(2)单配制，即一只雄鸟只与一只雌鸟交配完成繁殖过程。在这个过程中， 两只鸟类的“等位基因片段”(指一条可行路径当中首尾节点相同的部分路段集， 如图3)会随机交换，对应的单配制的新路径产生方法如下：

模仿鸟类单配置产生的新路径的过程分为两步，第一步搜索两条染色体间 相同的基因片段。第二步随机交换相应的基因片段。图3中rpc_j为随机生成的 基因片段交换概率，当概率大于交换阈值时，基因片段交换。

(3)多配制，分为一夫多妻制，一妻多夫制，多夫多妻制。

a)一夫多妻制，即一只雄鸟只与多只雌鸟交配完成繁殖过程。在这个过程 中，一只雄鸟的会和多只雌鸟的“等位基因片段”(指一条可行路径当中首尾节 点相同的部分路段集)随机交换，对应的一夫多妻制的新路径产生方法如下：

模仿鸟类一夫多妻制产生的新路径的过程分为两步，第一步搜索雄性染色 体间与其他所有雌性染色体间相同的基因片段。第二步先将阈值大于基因交换 概率的基因片段找出，再使用变异概率最大的等位基因片段进行交换。

b)一妻多夫制，即一只雌鸟只与多只雄鸟交配完成繁殖过程。其新路径产 生方法与一夫多妻制相似，不再赘述。

c)多夫多妻制，即多只雄鸟只与多只雌鸟交配完成繁殖过程。在BMO算法 中，新路径产生方法与一夫多一妻制相似，不再赘述。

通过以上算法产生的新路径中，会有重复路段出现的情况，此时需要对重 复路段进行消除，消除时只需要将重复节点中路段去掉即可。

模仿鸟类进化方式的路径优化算法流程如图4，包括以下步骤：

S1.随机生成若干条可行路径，每一条路径对应一只鸟类的染色体，每一个 节点对应染色体上的一个基因，基因长度为路径长度，基因顺序为路径节点顺 序；

S2.确定路径长度为适应性函数；

S3.根据每条可行路径的路径长度对可行路径进行排序，并对其进行分类， 其具体分类方式如下：

1)根据路径长度的长短将可行路径分为雌性类和雄性类，其中，路径长度 小于等于阈值A时，则对应的可行路径属于雌性类，否则属于雄性类；

2)对属于雌性类的可行路径进行分类，根据路径长度将其分为单性生殖类 和一妻多夫制类，其中，路径长度小于等于阈值B时，则对应的可行路径属于 单性生殖类，否则属于一妻多夫制类；

对属于雄性类的可行路径进行分类，根据路径长度将其分为单配制类、一 夫多妻制类和多夫多妻制类，其中，路径长度小于等于阈值C时，则对应的可 行路径属于单配制类，路径长度大于阈值C且小于等于阈值D时，则属于一夫 多妻制类，路径长度大于阈值D时，则属于多夫多妻制类；

其中A>B，D>C>A；

S4.计算属于多夫多妻制类的可行路径的数目为E，并重新随机生成αE个 新可行路径，0<α<1，替代属于多夫多妻制类的αE个可行路径；这样可以增 加算法的探索性以避免陷入局部最优；

S5.各条可行路径按照其所属鸟类物种进化方式进行繁殖重构，完成繁殖重 构后，比较父代个体与子代个体的路径长度，保留路径长度短的可行路径；

S6.重复步骤S3到S5直到到达设定的迭代次数阈值，获取若干条可行路径， 对其中重复路段进行消除，即将重复节点中路段去掉；

S7.对步骤S6获取的可行路径中选取路径长度最小的路径作为优选路径。

针对不同的路网规模和路网复杂度，可行路径基因分类参数的最优设置值 会有所不用。参照自然界中具体生物行为的一般规律和相关实验，在本实施例 中，步骤S3中关于可行路径基因分类参数设置的一般规律如下：

基因排次第一的一类为单性生殖的雌鸟(5％)

基因排次第二的一类为一雌多雄的雌鸟(5％)(与基因排次前10的雄鸟交 配)

基因排次第三的一类为单配制的雄鸟(50％)

基因排次第四的一类为一雄多雌的雄鸟(30％)

基因排次第五的一类为多夫多妻的雄鸟(10％)

其中基因排次第三、四、五类皆为雄鸟，其交配的对象都是基因排次第一、 第二类的雌鸟。

实施例1

本实施例实验的路网为自制的广州大学城路网，路网节点为335个，弧段 为408个，如图5所示。

本实施例中的各项参数的取值如下：初始可行路径为100条，即鸟类种群 大小为100；采用单性生殖的鸟类5只，采用一妻多夫制繁殖的鸟类5只，采 用单配制的鸟类繁殖50只，采用一夫多妻制繁殖的鸟类30只，采用多夫多妻 制繁殖的鸟类10只。节点变异概率为10，等位基因片段的交叉概率与变异概 率取为0.5，进化代数的上限值定为10代。路径的起终节点标识在图6中。图 6为利用本实施方式算法寻找到的最短路径(点划线)。图7为收敛曲线，其中 纵坐标为路径长度(米)，横坐标为迭代次数，本实验中算法在第四代开始收敛， 最短路径长度为4908米。

以上所述的本发明的实施方式，并不构成对本发明保护范围的限定。任何 在本发明的精神原则之内所作出的修改、等同替换和改进等，均应包含在本发 明的权利要求保护范围之内。