面向多起点均衡多旅行商问题的进化算法_孙冰.pdf

年月第 卷第期计算机工程与设计 面向多起点均衡多旅行商问题的进化算法孙冰，王川，杨强，刘晓芳，毛文涛（河南师范大学 计算机与信息工程学院，河南 新乡 ；河南师范大学 软件学院，河南 新乡 ；南京信息工程大学 人工智能学院，江苏 南京 ；南开大学 人工智能学院，天津 ）摘要：为解决多起点均衡多旅行商问题，分析问题的特点，从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发，提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标，构建新型评价函数，设计双染色体编码方式。在此基础上，引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集 上，与其它求解多旅行商问题的进化算法进行对比，验证算法的有效性。关键词：遗传算法；均衡多旅行商问题；旅行商问题；进化算法；多目标；优化；变异策略中图法分类号：文献标识号：文章编号：（）：收稿日期：；修订日期：基金项目：国家自然科学基金青年基金项目（）；江苏省自然科学基金青年基金项目（）；江苏省高等学校自然科学研究面向基金项目（）作者简介：孙冰（），男，河南平顶山人，硕士研究生，研究方向为智能计算；通讯作者：王川（），男，河南新乡人，硕士，副教授，研究方向为人工智能理论及应用；杨强（），男，江苏南京人，博士，教授，会员，研究方向为计算智能及其应用；刘晓芳（），女，天津人，博士，讲师，研究方向为进化计算和机器学习及其应用；毛文涛（），男，河南新乡人，博士，教授，研究方向为机器学习和时序大数据分析。：，（，；，；，；，）：，：；引言多起点均衡多旅行商问题（，）是 多 旅 行 商 问 题（，）的一类典型扩展问题。与 类似，在该优化问题中，每个旅行商从起点出发，第 卷第期孙冰，王川，杨强，等：面向多起点均衡多旅行商问题的进化算法协同访问完所有城市，并最终返回起点，而且每个城市必须被访问且仅能被访问一次，要求所有旅行商的路程之和最短。不同于 ，一方面，多起点均衡多旅行商问题中起点由一个推广至多个，即每个旅行商均有一个独享的起点，而且该起点不事先确定，需要在优化过程中动态决定；另一方面，该类优化问题不仅要求最小化所有旅行商的总路程，而且要求最小化各个旅行商间的路程差距，即保持各个旅行商路程的均衡性。多旅行商问题广泛存在于现实生活和工业生产中，该问题通过对个体的分配和优化实现总成本最小的目标。但 缺乏对旅行商工作量公平性的要求，在实际应用中，表现为工作量分配不公平，不能很好满足对均衡性有要求的应用场景。因此，相对于 ，多起点的 更贴近于日常生活和工业生产的实际需求，如快递点的设置、充电桩的选址和多无人机的航路规划等，这类问题不仅要求最小化总成本，还要求公平分配任务，因此，将这些问题建模为均衡多旅行商问题更为合理。相关研究和进展由于起始点的不确定性以及各个旅行商路径间的均衡性限制，多起点均衡多旅行商问题的复杂性和优化难度远远大于传统的多旅行商问题。这直接导致了传统优化算法在应用于多起点 时性能急剧下降，比如禁忌搜索算法、模拟退火算法等精确算法，往往无法在可接受的时间内获得最优解或者近似最优解。启发 于 生 物 进 化 论 的 遗 传 算 法（，）全局探索能力强、具有问题独立性、内在并行性等优势。因此，研究者们尝试扩展，比如，提出新的编码策略、改进 交 叉 算 子、与 其 它 算 法 结 合 等 来 求 解 。但是，这些算法只考虑了多旅行商总路径最小化的目标，忽略了旅行商间的路径差异性，导致在实际应用中产生不合理的解。为此，研究者们进一步提出了能有效求解均衡多旅行商问题的遗传算法，如 等 依据城市的地理特征，通过 聚类算法将城市划分为不同的簇，并将簇分配给各个旅行商，再分别优化各个旅行商的路径；设计了基于遗传算法和模拟退火算法的混合算法，在求解均衡 时用环境温度来控制算法的收敛速度；等 对遗传算法的个体评价方法进行了修改，将每个旅行商的最小哈密顿循环长度替换为平均循环长度以维持路径均衡；等 设计了一种双染色体编码策略，通过等长的旅行商染色体来控制访问顺序，并在杂交过程中引入环境温度概念以控制杂交过程，从而实现均衡 问题的有效求解。虽然已有部分先行学者针对均衡多旅行商问题提出了诸多有效算法，这些研究工作主要集中于单起点或者固定起点的均衡多旅行商问题。因此，如何有效求解多起点的均衡多旅行商优化问题仍有待研究。为此，本文提出一种新型遗传算法以求解该问题。均衡多旅行商问题 问题分析多起点均衡多旅行商问题与传统单旅行商问题和多旅行商问题存在明显不同。具体来说，传统单旅行商问题旨在为一个旅行商寻找一条路程最短的哈密顿回路；多旅行商问题只考虑最小化所有旅行商的总路程，。本文研究的多起点均衡多旅行商问题中，除了要求所有旅行商总路程之和最小外，还要求旅行商们行走的路程相对均衡。综上所述，与 和现有 问题相比，多起点的均衡多旅行商问题主要有以下特点：（）各个旅行商起点独立且需要在优化过程中确定，因此，每个旅行商的起点也成为了优化算法需要优化的目标之一，这导致了多起点 问题的解空间大大增加，增加了问题的优化难度。（）多起点的均衡多旅行商问题不仅要求所有旅行商的总路程最小，而且要求各个旅行商间的路程距离差异最小，从而使得各个旅行商路径尽量均衡。以上两个优化准则更贴近于生活实际，所得到的最优解更符合现实需求；比如在物流调度中，物流公司要最小化物流车所消耗的总代价，同时确保各辆物流车的工作量尽量均衡。然而，上述两个优化目标存在一定的冲突性，这一特性极大增加了均衡多旅行商问题的优化难度。基于上述两个特征，相较于传统的旅行商问题，多起点的均衡多旅行商问题优化难度更大，复杂度更高。因此，亟需研究高效的优化算法进行求解。问题建模总体上，多起点均衡多旅行商问题可以描述为：假设个旅行商从个不同城市出发，需要协同访问个城市（其中），除各起点城市外，每个城市仅能被旅行商访问一次且仅一次，最后旅行商们返回到各自出发城市。本问题中，起点城市的选取对结果的影响至关重要，因此，个起点城市的选择也是优化的内容。基于上述描述，多起点均衡多旅行商问题可以按如下方式建模：首先，设第个旅行商的路程为，则所有旅行商的路程之和可以计算为（）为了表示旅行商们路程的均衡状况，采用表示所有旅行商路径的差异程度。其中，两旅行商之间的路程之差用 表示，则可以计算为 （）计算机工程与设计 年由于多起点均衡多旅行商问题不仅要求所有旅行商的总路程最小，而且要求各个旅行商间的路程差异总和也最小。综合上述两个优化目标，可以定义为 （）（）其中，参数为常量，其主要控制着旅行商总路程最小化与旅行商路程均衡目标化这两个目标在算法优化时的权重。关于对于优化结果的影响将在实验环节讨论。对比式（）和式（）可以发现，两个优化目标的量级存在着较大差异。理想情况下，应该为，而却是一个很大的数。当城市规模较大时，的量级可能远远高于的量级。为此，本文采用归一化操作，分别将各个旅行商的路程以及旅行商间路程的差值归一到，以此消除量纲的影响。此时，被归一化为如下形式 （）其中，和 分别为所有旅行商中路程的最小值和最大值，为第个旅行商的路程。不同于式（），在式（）中，本文考虑所有旅行商路程的平均值，而非所有路程的总和。采用这一策略的主要目的是为了消除归一化后和的累加项数不同造成的影响。类似地，归一化两两旅行商间的路程差异后，优化目标变为如下形式（）（）其中，和 分别为旅行商之间路程差异的最小值和最大值，为旅行商和旅行商的路程差 （）（）将式（）和 式（）分 别 引 入 权 重，则 可 以 得 到式（）。其中作为修正后评价指标。根据问题定义，应使评价指标尽可能小以满足 的要求。本算法以式（）作为适应度函数。遗传算法求解多起点 遗传算法是启发于达尔文“适者生存”理论的一种元启发式优化算法。该算法通过维持一个种群，经过选择、交叉和变异等操作，迭代式地搜索解空间，以寻求优化问题的最优解。已经被验证能够很好地求解诸如旅行商问题、背包问题 等 难问题。虽然已经广泛被应用于求解单旅行商问题 以及其它的 ，但这些算法无法直接应用于求解多起点 。为此，本文提出了基于双染色体编码的新型遗传算法，以有效求解该问题。基于双染色体的编码在优化多起点均衡多旅行商问题时，算法需要同时优化分配给各旅行商的城市以及这些城市的访问顺序。因此，传统采用单条染色体编码的 无法直接求解均衡 问题，。为此，本文设计了双染色体编码策略对均衡 问题进行求解。具体地，为种群中的每个个体设置两条不同染色体，其中染色体段表示在染色体段 中每个旅行商起点城市的索引；染色体段 为所有城市的访问序列；其与传统单旅行商 问题的解表示相似，主要负责优化各个旅行商访问城市节点的顺序。为更形象地解释上述解码过程，本文以名旅行商和 座城市为例进行阐述。假设某个体的染色体如图所示。染色体段的编码为（，），表示个旅行商的起点城市分别为染色体段 中的第号、第号和第号所对应的城市。由此，在染色体段 中上标为到位置的城市（、）组成第一个旅行商的城市访问序列，即第一名旅行商的环游路径为：；同理，第二名旅行商的环游路径为染色体段 上标为到的城市序列，即；最后，旅行商的环游路径为上标为到的城市序列，即。图双染色体的解码 交叉策略如前所述，每个个体拥有两条染色体，而且每条染色体的表示方法不同，代表的含义也不同。因此，需要根据不同的染色体设计不同的交叉策略。在优化过程中，染色体段 对城市访问顺序的排序优化与传统单旅行商 问题相同，但染色体段基于染色体段 进行城市分配，因此，染色体段 不仅影响城市的分配，而且影响各个旅行商路径的优化，对优化结果的影响较大，需要设计有效的交叉策略。具体交叉过程如下：染色体段：该染色体主要通过对各个旅行商起始点控制来实现旅行商访问城市的分配，其长度为旅行商个数。与染色体段 相比，染色体相对简单。因此，本文直接采用文献 使用的部分交叉法来实现对染色体段的交叉。染色体段：该染色体为所有城市的一个排列，负责优化各个城市的访问顺序，间接达到优化各旅行商路径的目的。三交换启发式交叉法 是传统求解多旅行商问题经常使用的交叉策略。本文对三交换启发式交叉法在双染色体编码下进行了改进，以使其适应求解 均衡多 旅行商问题。举例来说，如图所示，本文以个城市，个旅行商为例，详细说明上述交叉过程。父代中旅行商的路径第 卷第期孙冰，王川，杨强，等：面向多起点均衡多旅行商问题的进化算法包含两个城市，旅行商的路径包含个城市，旅行商的路径包含个城市。因此，在进行染色体段 的交叉时，子代个体的染色体段直接父代的染色体段，即在子代个体中，个旅行商也分别访问，和个城市。父代和父代为随机选择的两个个体。随后，染色体段 按如下步骤进行交叉：步骤先选取第一个父代的第一个城市作为子代第一个旅行商的起始城市。如图的步骤所示，直接作为子代第一个旅行商的起始城市。随后，另外两个父代的城市序列向左环移，直至将染色体段 的城市移到第位。此时，所有父代的城市序列均变为作为第个城市。步骤获取个父代现有序列中与上一个被选中的城市（即）相邻的城市，即、和。随后，比较与的距离，若距离最近，则将确定为子代的第二个城市。随后，父代和父代的剩余未被选择的城市序列向左环移，直至将城市移到剩余序列的第一位。此时需要注意的是，已被选过的城市（例中为城市）不参与环移。旅行商的路径构建完成，即。步骤此时，开始构建第二个旅行商的路径。如图的步骤所示，第二个旅行商的第一个城市直接设为当前父代中未被选中城市序列中的第一个城市，即。随后，依照步骤，父代和父代的未被访问的城市序列不断向左环移，直至将环移至未被访问序列的第一位；然后，从个父代中，获得与相邻的城市，即、和。从中选择距离最近的城市作为第二个城市；依此类推，逐渐构建完成旅行商的路。随后，按照上述流程逐城市构建完成旅行商的路径。图三交换启发式交叉法过程依照上述交叉过程，三交叉启发式算法最终会生成一个不重复城市的序列作为子代的染色体段。通过上述交叉方式，所产生的新序列能够同时继承个父代的优良片段，有利于生成更高质量的解，从而加快 找到最优解的速度。变异策