一种基于杂交育种策略的多负载agv路径规划方法
技术领域
1.本发明涉及智慧工厂中agv路径规划技术领域，更具体地，涉及一种基于杂交育种策略的多负载agv路径规划方法。
背景技术：
2.随着数字化工厂、工业物联网、人工智能等先进技术得到了迅速发展，对生产方式和物流运输方式也提出了更高的要求。自动导引小车(agv)是自动化物流设备中的重要组成部分，具有运输成本低、运输效率高、运输准确率高、便于标准化管理等等优势，在降低企业成本、提高生产运输效率等方面发挥了不可替代的作用。
3.agv的研发涉及多个领域，例如计算机、自动控制、电子技术、信息通讯和机械设计等，这是集成光、机电和计算机技术的高新技术。为了保证agv能够安全可靠的运行，必须先解决agv路径规划的问题，该问题是指通过已知环境信息和实时传感器获取的数据，生成一条安全的移动路径。蚁群优化算法(aco)是模拟蚁群觅食行为而提出的一种群集智能优化算法，在离散组合优化问题中得到了广泛的应用，主要是将求解的组合优化问题转换为蚂蚁搜索路径的寻优问题。多负载agv路径规划是典型的组合优化问题，蚁群优化算法在处理此类问题时具有很好的适用性。
4.相较于传统的优化算法，蚁群优化算法具有鲁棒性强、搜索效率高和正反馈机制等优点，在旅行商问题、智能交通、网络优化等领域都有成功的应用。然而，蚁群优化算法也存在一些不足，如蚁群优化算法时间复杂度较高，易陷入局部最优解；同时，随着算法迭代次数的增加，蚁群优化算法无法保持种群多样性和局部搜索能力之间的平衡。
5.为了提升基本aco的寻优性能，受杂交育种机制启发，本发明设计杂交育种协同进化蚁群优化算法的多负载agv路径规划方法，充分发挥不同种群各自的优点，有效扩大搜索范围，从而有效提高解的质量，使算法稳步地向最优解方向迈进。
技术实现要素：
6.本发明针对现有技术中存在的传统agv路径规划基于蚁群优化算法，无法保持种群多样性和局部搜索能力之间的平衡的技术问题。
7.本发明提供了一种基于杂交育种策略的多负载agv路径规划方法，包括以下步骤：
8.步骤1：初始化agv的环境地图，获取目的地址信息作为原始输入集；
9.步骤2：初始化种群和算法所需初始化参数；
10.步骤3：划分种群，将种群分为elitist ant system(eas)、ant colony system(acs)和max-min ant system(mmas)三种种子群；
11.步骤4：不同种子群各自进化，完成路径访问；
12.步骤5：计算各种子群的种群相似度，并判断是否需要进行种群间通讯，若需要进行种群间通讯，则执行种群间通讯；
13.步骤6：完成信息素更新；
14.步骤7：判断是否满足终止条件，其中，终止条件设置为达到最大迭代次数，若否，则返回执行步骤4；若是，则输出全局最优路径。
15.优选地，所述初始化参数包括信息素因子α、启发式因子β、信息素衰减系数ρ、信息素质量系数q、最大迭代次数nc
max
、种群数量m。
16.优选地，所述步骤4具体包括：
17.当子种群为eas时，种群完成路径访问时，最优路径表示为t
bs
，其长度为l
bs
，路径(i,j)上遗留的信息素浓度为τ
ij
，经过信息素的计算如公式(1)和公式(2)：
[0018][0019][0020][0021][0022]
其中，表示在时刻t经过t个时刻的路径访问后,由精英蚂蚁引起的路径(i,j)上的信息素的增加，σ表示精英蚂蚁的数量，q表示蚂蚁完成一次循环所释放的信息素总量，lk表示蚂蚁k在本次循环中走过的路径长度，表示在时刻t经过t个时刻的路径访问后，精英蚂蚁k在路径(i,j)上的信息素的增加，lk表示精英蚂蚁k在本次路径访问中的路径长度。
[0023]
优选地，所述步骤4具体包括：
[0024]
当子种群为acs时，种群完成路径访问时，蚂蚁个体选择下一任务点时遵循的伪随机比例规则如公式(5)：
[0025][0026]
其中，sk为蚂蚁k选择的下一个转移城市，q是一个区间范围在[0,1]的随机数，q0为初始时设定的阈值，η
ij
为路径(i,j)的能见度，即启发函数，反映了由城市i转移到城市j的启发程度，τ
ij
为蚂蚁k在本次迭代中留在路径(i,j)的信息素量。
[0027]
优选地，所述步骤4具体包括：蚂蚁在选择下一个城市之前，首先进行一次随机实验得到随机数q，若q≤q0，则在所有可行的城市中找出最大的城市，即为下一个要选择的城市，反之则按照公式(6)选择下一个城市，为蚂蚁k在城市i选择城市j作为下一步转移城市的转移概率；
[0028][0029]
优选地，所述步骤4具体包括：在一次循环完成后只对搜索到最优路径的蚂蚁进行全局信息素的更新，信息素更新规则如公式(7)和公式(8)：
[0030][0031]
τ
ij
(t t)＝(1-ρ)τ
ij
(t) ρδτ
ij
(t,t t)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0032][0033]
其中，ρ是一个区间在[0,1]之间的常数；l
gb
为蚁群本次循环中所得的最优路径长度。
[0034]
优选地，所述步骤4具体包括：当子种群为mmas时，路径上信息素的浓度范围限制于区间[τ
min
,τ
max
]内，当路径上的信息素浓度超出这个范围时将会被强制设置为τ
min
或τ
max
；同时，信息素的初始值设为最大值τ
max
。
[0035]
优选地，所述步骤5具体包括：
[0036]
计算相似度系数；
[0037]
计算子种群内部相似度，蚁群内部相似度表示经过若干次迭代后，子种群内所有蚂蚁遍历得到的路径与目前最佳遍历路径的重合程度；
[0038]
计算子种群间的相似度，蚁群间相似度表示经过若干次迭代后，子种群与子种群之间的相似度，表示两个子种群在进化过程中，进化方向的差异；
[0039]
计算种群间信息交流频率；
[0040]
选择种群间信息交流对象，假设子种群colony(i)选择子种群colon(y)j作为信息交流的对象，则种群间信息交流对象的选择由下式确定：
[0041][0042]
其中，r代表子种群的个数。
[0043]
优选地，所述步骤6具体包括：
[0044]
当需要进行交流的子种群colony(i)为acs时，作为交流对象的种群为colony(j)，那么acs信息素更新满足下式：
[0045]
τ
ij
(t t)＝(1-ρ)τ
ij
(t) ρδτ
ij
(t,t t) et
[0046]
其中δτ
ij
(t,t t)按下式更新：
[0047][0048]
其中，et为子种群colony(j)对子种群colony(i)的信息素贡献，即强化信息，l
pg
表示子种群colony(j)在本次迭代中的最优路径，nc为当前迭代的次数，
[0049]
当需要进行交流的子种群colony(i)为eas时,作为交流对象的种群为colony(j)，那么colony(i)信息素更新满足下式：
[0050][0051][0052][0053]
当需要进行交流的子种群colony(i)为mmas时,作为交流对象的种群为colony(j)，那么mmas信息素更新方式与acs相同。
[0054]
有益效果：本发明提供的一种基于杂交育种策略的多负载agv路径规划方法，通过对基本蚁群优化算法进行改进，设计了协同进化异构蚁群优化算法，来弥补单一种群在解的多样性方面的不足，并提出一种基于种群相似度的策略来判断经过固定代数的迭代后是否需要进行交流，在种群多样性和收敛速度之间保持动态平衡，使算法具有较高全局收敛速度的同时收获高质量的解，可用于路径规划相关技术领域中。本发明能够快速的获得多负载agv在面对多任务时的最优路径选择，在保证获得最优路径的前提下，提高路径规划速度，能够满足智慧工厂等领域多负载agv路径规划的需求，为提高agv路径规划效率提供更有效的技术方法。
附图说明
[0055]
图1为本发明提供的一种基于杂交育种策略的多负载agv路径规划方法流程图。
具体实施方式
[0056]
下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。
[0057]
图1为本发明提供的一种基于杂交育种策略的多负载agv路径规划方法，包括以下步骤：
[0058]
步骤1：初始化agv的环境地图，获取目的地址信息作为原始输入集；
[0059]
步骤2：初始化种群、算法所需参数，包括信息素因子α、启发式因子β、信息素衰减系数ρ、信息素质量系数q、最大迭代次数nc
max
、种群数量
ma
；
[0060]
步骤3：划分种群，受杂交育种策略启发，将种群分为el itist ant system(eas)、ant colony system(acs)和max-min ant system(mmas)三种种子群；
[0061]
步骤4：不同子种群各自进化，完成路径访问；
[0062]
步骤5：计算各子种群的种群相似度，并判断是否需要进行种群间通讯，若需要进行种群间通讯，则执行种群间通讯；
[0063]
步骤6：完成信息素更新；
[0064]
步骤7：判断是否满足终止条件，其中，终止条件设置为达到最大迭代次数，若否，则返回执行步骤4；若是，则输出全局最优路径。
[0065]
在上述的一种基于杂交育种策略的协同进化蚁群优化算法的多负载agv路径规划方法，所述的步骤4具体实现包括以下子步骤：
[0066]
步骤4.1：当子种群为eas时，种群完成路径访问时，最优路径表示为t
bs
，其长度为l
bs
，路径(i,j)上遗留的信息素浓度为τ
ij
，信息素的计算如公式(1)和公式(2)：
[0067][0068][0069]
其中，
[0070][0071][0072]
其中，表示在时刻t经过t个时刻的路径访问后,由精英蚂蚁引起的路径(i,j)上的信息素的增加，σ表示精英蚂蚁的数量，q表示蚂蚁完成一次循环所释放的信息素总量，lk表示蚂蚁k在本次循环中走过的路径长度，表示在时刻t经过t个时刻的路径访问后，精英蚂蚁k在路径(i,j)上的信息素的增加，lk表示精英蚂蚁k在本次路径访问中的路径长度。
[0073]
步骤4.2：当子种群为acs时，种群完成路径访问时，蚂蚁个体选择下一任务点时遵循的伪随机比例规则如公式(5)：
[0074][0075]
其中，sk为蚂蚁k选择的下一个转移城市，q是一个区间范围在[0,1]的随机数，q0为初始时设定的阈值，η
ij
为路径(i,j)的能见度，即启发函数，反映了由城市i转移到城市j的启发程度，τ
ij
为蚂蚁k在本次迭代中留在路径(i,j)的信息素量。蚂蚁在选择下一个城市之前，首先进行一次随机实验得到随机数q，若q≤q0，则在所有可行的城市中找出最大的城市，即为下一个要选择的城市，反之则按照公式(6)选择下一个城市，为蚂蚁k在城市i选择城市j作为下一步转移城市的转移概率，allowdk＝{1,2,...,n}表示蚂蚁k下一步可以选择的城市。
[0076][0077]
在一次循环完成后只对搜索到最优路径的蚂蚁进行全局信息素的更新，信息素更新规则如公式(7)和公式(8)：
[0078]
τ
ij
(t t)＝(1-ρ)τ
ij
(t) ρδτ
ij
(t,t t)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0079][0080]
其中，ρ是一个区间在[0,1]之间的常数；l
gb
为蚁群本次循环中所得的最优路径长度。
[0081]
在acs中，蚂蚁在构造路径的同时进行局部更新。信息素局部更新规则如公式(9)：
[0082]
τ
ij
(t t)＝(1-ρ)τ
ij
(t) ρτ
ij
(t,t t)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)
[0083]
其中，ρ是一个区间在[0,1]之间的常数，τ
ij
(t,t t)通常取值为路径上信息素的初值。
[0084]
步骤4.3：当子种群为mmas时，路径上信息素的浓度范围限制于区间[τ
min
,τ
max
]内，当路径上的信息素浓度超出这个范围时将会被强制设置为τ
min
或τ
max
；同时，信息素的初始值设为最大值τ
max
。
[0085]
在上述的一种基于杂交育种策略的协同进化蚁群优化算法的多负载agv路径规划方法，所述的步骤5具体实现包括以下子步骤：
[0086]
步骤5.1：计算相似度系数，相似度是用来描述蚂蚁遍历得到的路径的重合程度，计算方式可以用公式(10)和公式(11)来表示：
[0087][0088][0089]
其中，s
ij
为蚂蚁ai与蚂蚁aj遍历得到的路径相似程度，表示蚂蚁ai遍历得到的路径中第k个节点与同此迭代中蚂蚁aj遍历路径是否重合，若重合则其值为1，否则其值为0。
[0090]
步骤5.2：计算子种群内部相似度，蚁群内部相似度表示经过若干次迭代后，子种群内所有蚂蚁遍历得到的路径与目前最佳遍历路径的重合程度，计算如公式(12)、公式(13)：
[0091][0092][0093]
其中，s
colony(i)
表示子种群colony(i)内每个蚂蚁遍历得到的路径与目前最佳遍历路径的相似程度，表示子种群中，各蚂蚁ai在本次迭代中得到的最佳遍历路径的第k个节点是否与子种群内蚂蚁a
best
目前最佳遍历路径是否存在重合，若重合则其值为1，否则其值为0。
[0094]
步骤5.3：计算子种群间的相似度，蚁群间相似度表示经过若干次迭代后，子种群与子种群之间的相似度，表示两个子种群在进化过程中，进化方向的差异，计算如公式(14):
[0095][0096]
其中，s
colony(i,j)
表示子种群colony(i)与子种群colony(j)遍历得到的最佳路径之间的相似程度，表示子种群colony(i)目前遍历得到的最佳路径的第k个节点与本次迭代中子种群colony(j)遍历得到的最佳路径是否有重合，如果重合其值为1，反之为0。
[0097]
步骤5.4：计算种群间信息交流频率，设子种群colony(i)在经过次迭代后，其交换指标为p
interval(i)
，该值决定了是否同其他子种群进行交流，交换概率p
interval(i)
计算如公式(15)：
[0098]
p
interval(i)
＝1-s
colony(i)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(15)
[0099]
当子种群colony(i)对应的相似度s
colony(i)
较大时，p
interval(i)
值较小，当其小于0.5时，意味着此时子种群colony(i)的解相对集中，种群的多样性降低，影响子种群更深一步的探索，因此需要增加子种群colony(i)与其他外部子种群的交流来改善子种群的进化环境；反之，当子种群colony(i)对应的相似度s
colony(i)
较小时，p
interval(i)
值较大，当其大于0.5时，此时子种群colony(i)的解相对分散，多样性较好，因此不需要进行子种群colony(i)与其他外部子种群的交流，防止破坏种群内部的探索，因此，种群的交流频率计算如公式(16)：
[0100][0101]
步骤5.5：选择种群间信息交流对象，假设子种群colony(i)选择子种群colony(j)作为信息交流的对象，则种群间信息交流对象的选择由公式(17)确定：
[0102][0103]
其中，r代表子种群的个数。
[0104]
上述的一种基于杂交育种策略的协同进化蚁群优化算法的多负载agv路径规划方法，所述的步骤6具体实现包括以下子步骤：
[0105]
步骤6.1：信息素更新，在信息素更新时，为了保留作为交流对象的子种群对该种群的贡献，同样将另一种群最优解以及两种群之间的相似度看作强化信息，作为本种群信息素更新的一部分。当需要进行交流的子种群colony(i)为acs时，作为交流对象的种群为colony(j)，那么acs信息素更新满足公式(18)：
[0106]
τ
ij
(t t)＝(1-ρ)τ
ij
(t) ρδτ
ij
(t,t t) et
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(18)
[0107]
其中δτ
ij
(t,t t)按公式(19)更新：
[0108][0109]
其中，et为子种群colony(j)对子种群colony(i)的信息素贡献，即强化信息，l
pg
表示子种群colony(j)在本次迭代中的最优路径，nc为当前迭代的次数。
[0110]
当需要进行交流的子种群colony(i)为eas时,作为交流对象的种群为colony(j)，那么colony(i)信息素更新满足公式(20)：
[0111][0112]
其中τ
ij
(t,t t)按公式(21)更新，按公式(22)更新，et按公式(19)更新。
[0113][0114][0115]
当需要进行交流的子种群colony(i)为mmas时,作为交流对象的种群为colony(j)，那么mmas信息素更新方式与acs相同。
[0116]
尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。
[0117]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包括这些改动和变型在内。