一种多条件约束下的智能路径规划算法

摘要

本发明公开了一种多条件约束下的智能路径规划算法，使用免疫遗传算法结合2‑opt算法，免疫遗传算法可以有效抑制退化现象，提高全局搜索速度，2‑opt可以避免陷入局部最优陷阱，算法实施步骤如下，S1、首先进行抗体编码，将排班路径规划问题转化为免疫系统能够处理的抗原形式，抗体则对应问题的解，S1中采用自然数编码，定义免疫系统由N个抗体组成，即群体规模为N，M表示抗体的基因数，本发明结构科学合理，使用安全方便：本发明结合免疫遗传算法与2‑opt算法，能够更有效的得到最优路径规划，有效抑制退化现象，提高全局搜索速度，避免陷入局部最优的缺点。

说明书

技术领域

本发明涉及智能控制技术领域，具体为一种多条件约束下的智能路径规划算法。

背景技术

业务人员拜访客户的路径规划，受多种条件约束，针对业务人员，需要支持工作有效时间约束、出发点和返回点约束、每日拜访的总数量约束、交通方式的约束，针对客户需要支持客户点停留时间约束、客户拜访频次约束、客户办公时间约束等，在如此众多的约束条件下，如何才能达到路程最短的情况下，有效的完成最多的客户有效拜访，这是路径规划算法的难点。

发明内容

本发明提供一种多条件约束下的智能路径规划算法，可以有效解决上述背景技术中提出每个业务人员在复杂的条件下寻找到最有效的拜访路径，有效提高业务人员工作效率的问题。

为实现上述目的，本发明提供如下技术方案：一种多条件约束下的智能路径规划算法，使用免疫遗传算法结合2-opt算法，免疫遗传算法可以有效抑制退化现象，提高全局搜索速度，2-opt可以避免陷入局部最优陷阱；

算法实施步骤如下：

S1、首先进行抗体编码，将排班路径规划问题转化为免疫系统能够处理的抗原形式，抗体则对应问题的解；

S2、计算抗体与抗体间的亲和力，在进化过程中免疫系统是一个不确定系统，其多样性由平均信息熵来表示；

S3、排除相似抗体；

S4、计算抗原与抗体的亲和度；

S5、选择优良抗体加入记忆库；

S6、交叉、变异、随机产生新抗体。

根据上述技术方案，所述S6中变异操作采用2-opt算法，迭代次数超过预先的设定，则输出最优解，否则返回S2。

根据上述技术方案，所述S1中采用自然数编码，定义免疫系统由N个抗体组成，即群体规模为N，M表示抗体的基因数。

根据上述技术方案，所述S2中定义P

P

则处于j位置的基因信息熵为：

整个群体的基因信息熵为：

那么根据熵的定义，得到抗体v和w的亲和力：

根据上述技术方案，所述S3中AX

根据上述技术方案，所述S4中计算抗原与抗体的亲和度axv， 排除亲合力小于上一代亲和度最小值的抗体；

AX

根据上述技术方案，所述S5中在传统适应度选择比例的基础上 增加基于浓度的调节概率因子，抗体v的浓度计算公式为：

m

个体的选择概率P

根据上述技术方案，所述S6中交叉操作采用顺序交叉，在双亲1中随机选择一个匹配区域，产生原始后代，将双亲2中与匹配区域不同的部分按照原来的顺序插入到原始后代，组成子代1，按照同样的方法组成子代2。

与现有技术相比，本发明的有益效果：本发明结构科学合理，使用安全方便：本发明结合免疫遗传算法与2-opt算法，能够更有效的得到最优路径规划，有效抑制退化现象，提高全局搜索速度，避免陷入局部最优的缺点。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例一起用于解释本发明，并不构成对本发明的限制。

在附图中：

图1是本发明的算法步骤结构示意图。

具体实施方式

以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

实施例：如图1所示，本发明提供技术方案，一种多条件约束下的智能路径规划算法，使用免疫遗传算法结合2-opt算法，免疫遗传算法可以有效抑制退化现象，提高全局搜索速度，2-opt可以避免陷入局部最优陷阱；

算法实施步骤如下：

S1、首先进行抗体编码，将排班路径规划问题转化为免疫系统能够处理的抗原形式，抗体则对应问题的解；

S2、计算抗体与抗体间的亲和力，在进化过程中免疫系统是一个不确定系统，其多样性由平均信息熵来表示；

S3、排除相似抗体；

S4、计算抗原与抗体的亲和度；

S5、选择优良抗体加入记忆库；

S6、交叉、变异、随机产生新抗体。

根据上述技术方案，2-opt 算法在改进路径优化问题中的单条路线上有独特的优势，其基本思想是取路线上的两条线段（i，i+1）和（j，j+1），断开这两条线段，将点i 与j+1相连，j 与i+1 相连，同时将线路反转，形成新的线路，变化后的线路里程比原路径短，则此线路为优化解,否则保留原路线，迭代次数超过预先的设定，则输出最优解，否则返回S2。

根据上述技术方案，S1中采用自然数编码，定义免疫系统由N个抗体组成，即群体规模为N，M表示抗体的基因数。

根据上述技术方案，S2中定义P

P

则处于j位置的基因信息熵为：

整个群体的基因信息熵为：

那么根据熵的定义，得到抗体v和w的亲和力：

根据上述技术方案，S3中AX

根据上述技术方案，S4中计算抗原与抗体的亲和度axv，排除亲 合力小于上一代亲和度最小值的抗体；

AX

根据上述技术方案，S5中在传统适应度选择比例的基础上增加 基于浓度的调节概率因子，抗体v的浓度计算公式为：

m

个体的选择概率P

根据上述技术方案，S6中交叉操作采用顺序交叉，在双亲1中随机选择一个匹配区域，产生原始后代，将双亲2中与匹配区域不同的部分按照原来的顺序插入到原始后代，组成子代1，按照同样的方法组成子代2。

与现有技术相比，本发明的有益效果：本发明结构科学合理，使用安全方便：本发明结合免疫遗传算法与2-opt算法，能够更有效的得到最优路径规划，有效抑制退化现象，提高全局搜索速度，避免陷入局部最优的缺点。

最后应说明的是：以上所述仅为本发明的优选实例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。