基于遗传算法的多目标货物配载研究

于萍 胡卉芪 钱卫宁

摘要：针对多目标货物配载问题，建立了以最大化总订单货物重量、最小化车次总数、最小化货物装卸地 总数为目标的配载模型，提出了一种快速收敛的基于精英策略多目标遗传算法（Fast Convergence Based on the Elitism Genetic Algorithm， FEGA）.首先，在遗传算法的基础上加入Pareto支配关系上的分层结构 和精英保留策略，从而提高种群的多样性，同时还可以加快算法的局部搜索能力;其次，修改初始种群的随 机结构，并加入双种群策略，添加自适应操作算子，依次提高算法的全局搜索能力，加速种群的收敛速度; 最后，基于新算法，利用真实的货物数据验证算法的可行性与优化效果.结果表明，与传统遗传算法相比， 所提算法在求解强约束条件、庞大搜索空间的货物配载过程中具有较好的优化效果，搜索性能与收敛性都有所提升. 关键词：多目标优化;货物配载;遗传算法

中图分类号：TP311       文献标志码：A DOI： 10.3969/j.issn.1000-5641.2021.05.016

Research on multi-objective cargo allocation based on an

improved genetic algorithm

YU Ping， HU Huiqi， QIAN Weining

（School of Data Science and Engineering， East China Normal University， Shanghai 200062， China）

Abstract： In this paper， we propose a mathematical model to solve the multi-objective cargo allocation problem with greater stability and efficiency; the model for cargo allocation maximizes the total cargo weight， minimizes the total number of trips， minimizes the number of cargo loading and unloading points， and offers fast convergence based on the elitism genetic algorithm （FEGA）. First， a hierarchical structure with the Pareto dominance relation and an elitism retention strategy were added on the basis of the genetic algorithm. This helped to improve the population diversity while accelerating the local search ability of the algorithm. Then， the random structure of the initial population was modified， and a double population strategy was designed. An adaptive operation was subsequently added to sequentially improve the global search ability of the algorithm and accelerate the convergence speed of the population. Based on the new algorithm， real cargo data were used to demonstrate the feasibility and optimization potential of the new method. The results show that compared with the traditional genetic algorithm， the proposed algorithm has a better optimization effect in solving the cargo allocation process with strong constraints and a large search space; the search performance and convergence， moreover， are also improved.

Keywords： multi-objective optimization; cargo allocation; genetic algorithm

0引 言

随着钢铁物流行业的飞速发展，大宗货物的配载现已进入蓬勃发展的阶段，行业内的许多顽固问

收稿日期：2021-07-27 基金项目：国家自然科学基金（U191120（3）

通信作者：胡丼苗，男，副教授，主要研究方向为数据库系统、分布式系统.E-mail： hqhu@dase.ecnu.edu.cn

题也逐渐暴露.钢材运输具有距离长、运载重量过大的特点，只有重型卡车才能满足运载要求.但重型 卡车的数量有限，且卡车分布不均匀，钢铁企业普遍面临着重卡超载、货物堆积、订单逾期等严重问 题.传统的货物配載方案是由人工实时制定，基于最大化卡车负载来确定每辆卡车的货物配载方案， 可忽视了整体车辆的装载情况、司机对于运输任务的满意程度等其他信息，但这些因素都与钢铁物流 平台的利润息息相关.因此，研究钢铁物流的配载问题对降低物流平台运送成本、提高经济收益等都 有积极意义.

在实际的货物配载场景下，物流平台为了降低运送成本、提高经济收益，需要从货物特征、司机 满意度等多个维度综合考虑，同时优化多个互相冲突和影响的目标，因此本文根据实际业务中的配载 目标，建立货物配载多目标优化模型.

多目标优化问题根据用户偏好信息的决策时机分为先验和后验两类.其中先验方法是指在求解 过程之前将偏好信息转化为显性的偏好因子，利用偏好因子将多目标量化为单目标，最终转化为单目 标优化问题，通过求解该单目标优化问题得到解.权重求和法利用用户偏好信息为每个目标设定权 重值，利用权重求和将多个目标量化为单个目标，最终求解最值得到最优解.字典法通过解析用户 的偏好信息将目标按照重要性进行排序，最终转化为求解一系列单目标形式的最优化问题.但是偏好 因子的定性表示存在主观性，除非可以找到一个可靠而精确的偏好向量进行标量化，否则转化为单目 标问题得到的解相当主观.当偏好因子无法被精确表示时，可以采用后验方法.后验方法首先找到多 个目标的多重权衡下的最优解集，然后利用用户的偏好信息从多个解决方案中选择其中一个.大多数 后验方法分为两类：基于数学规划的后验方法，该方法通过其中一个算法重复运行，每次运行该算法 产生一个折中解;进化算法则通过运行一次该算法可以产生一组折中解.数学方法中法线边界相交 （NBI）'法线约束（NC）[4-5]，连续Pareto优化（SPO）[6]，定向搜索域（DSDfl方法通过构造若干标量来 求解多目标问题，该标量化过程是以获得均匀分布的折中解为目标来构造的.但是多目标优化本身属 于NP问题，当产生的折中解数量过多时，则需要更多的计算时间，在实际应用场景下该方法无法在 有限的时间内产生足够的折中解.进化类算法[8]是目前产生多目标优化问题的折中解最常用的方法， 它可以在有限的时间内产生足够多的折中解供决策者选择.其中NSGA-II[9]和NSGA-m[10]基于遗传 算法提出Pareto最优解的概念以及解与解之间的支配关系，通过支配关系将所有的可行解进行排序， 进而提高算法的搜索效率.SPEA-II[n]在此基础上提出根据每个个体的支配个体数目和被支配个体数 目来进一步计算适应度的值，从而加快种群的收敛速度.MOEA/D[12]基于分解的思想，将逼近整个 Pareto前沿面的问题分解为一定数量的单目标优化问题，然后利用进化算法同时求解这些单目标优 化问题，使得种群保持多样性.仿生类算法以及仿物类算法如蚁群算法[13]、粒子群算法[14]、模拟退火算 法[15]是通过模拟生物和自然界物体的行为特征来设计种群更新的方法.该类算法无法同时兼顾种群 的多样性和收敛性，算法效率不高.物流领域中1161综合了 NSGA-II和基于生物地理学的优化算法来处 理生产调度中的多目标车间作业调度问题，在提高算法的局部搜索能力的同时又加快了种群的收敛 速度.文献[17]构建的电网资源分配模型，在预测模块中使用了神经网络，结合多目标优化算法 SPEA，实现了经济成本、环境收益、能源利用率的多目标优化.

综上所述，并不存在适用所有场景的多目标方法，而物流领域中的货物配载问题关注货物特征和 业务场景，在具有多种约束条件的情况下对货物进行排列组合，大多数研究1181都利用启发式算法求解 货物配载相关问题，比如集装箱问题.但集装箱类问题主要考虑货物的体积、集装箱的空间利用率，约 束规则较少，且与实际业务问题关联较浅.还有一部分配载问题119-201重在解决仓库协调过程，与本文 背景不符.

目前，启发式算法被认为是求解近似最优解较为有效的算法，其算法内部的随机优化结构需要根 据具体的问题单独设计，而智能算法中粒子群算法更容易陷入局部最优，不适合求解离散问题.实际 的货物装配问题带有强约束条件，模拟退火算法和爬山算法都不适用于大规模多约束问题，而遗传算 法不仅可以很好地处理多约束条件下的离散问题，而且相较于其他智能算法，还具有更强的全局搜索 能力.

本文在对钢铁物流配载流程、特点和货物配载目标充分调研的基础上，建立了货物配载多目标优 化模型，并针对该问题特点，设计了一种基于精英保留策略的改进遗传算法，为了进一步加快种群的 全局搜索能力，提出了一种可以快速收敛的基于精英策略的改进遗传算法（FEGA），在提高最优解质 量的同时，增强算法全局与局部搜索能力.通过实际的货物数据，说明FEGA在面对约束条件复杂、 搜索空间大的多目标优化问题时，在计算效率、收敛性和多样性上都优于普通遗传算法.

1 多目标货物配载模型

1.1问题描述

物流平台每天在零点获取仓库的库存数据，结合货物的品种、仓库、规格等特征以及不同品种的 货物之间拼货时需满足的限制条件，对客户订单进行拆分、组合，生成一批装车清单，并上传至平台供 司机选择.当前平台使用的配载方法是通过顺序遍历货物列表，在符合业务规则的条件下，以最大化 单辆车的货物重量为目标为车次分配货物.该方法没有考虑到后续的货物信息和剩余空车次数量，无 法实现全局最优的货物分配，导致大量货物积压，部分单车货物重量远低于车辆载重上限.

针对上述货物配载效率太低及货车利用率不高等问题，本文提出了多目标优化货物配载模型，根 据实际的业务调研结果，从物流平台和货车司机双方的角度综合考虑.物流平台需要考虑运输利益与 运力成本，其中平台利益与货物发运量成正比.配载过程需要考虑货物状态，即是否存在客户催货、超 出合同约定期的货物，故应尽可能优先发运该类货物，而仓库堆积的货物越多也越不利于后续生产的 货物发运，导致上一轮货物堆积时间更长.在单批次配载过程中，应发运尽可能多的货物，减少尾货. 物流平台不仅需要考虑货物运输重量，同时需要承担运力成本，一份装车清单需要一辆车运载，平台 需要向司机付运费，故在考虑发运尽可能多的货物的同时，应尽量减少订单数，即减少车次数，从而降 低运力成本，实现用更少的车运载更多货物的目标.从貨车司机的角度考虑，货车通过装车清单去往 仓库取货，如果仓库拥挤则还需排队等待，若有多个取货仓库则会大大提高司机的时间成本.同理，若 有多个卸货地，司机也需要额外的等待时间.在实际运输过程中，司机更倾向于选择单个装卸货地的 运单，而多个装货、卸货的装车清单往往需要手动派单.

经过分析后设计以下三个具有实际应用价值的目标.从物流平台的角度考虑，通过增加单批次所 有订单的货物总重量，减少单批次订单数即减少车次数来降低平台成本.与此同时，在货车不超载的 情况下尽可能增大单辆车的装载重量，从而在提高配载效率的同时可以提升平台经济收益;从货车司 机的角度考虑，尽可能降低货车中货物的装卸地数量，可减少司机的时间成本，给司机带来最大的便 利.在实际的业务调研中发现，管理员在对货物进行分配时具有明显的优先级考虑，在平台利益与司 机便利程度上比较，管理员优先考虑平台利益，在考虑平台利润的前提下，优先考虑货物状态，再考虑 平台雇用车辆成本，由此为这三个目标设定优先级，优先最大化所有订单的货物总重量，其次减少总 订单数，减少总订单的货物装卸地优先级最低.

1.2数学模型

根据对货物配载问题的分析，货物配载模型主要参数描述如下.

本文使用K （1 < *彡m）表示可供使用的车次中第*辆车;^ （1 < j < n）表示当前库存可发运货 物中第J件货物;使用装车清单描述车辆依次运输任务需要装载的货物情况;%表示货物^的重 量，单位为吨;表示车货状态，取值为O或1; ^表示车辆K的载重上限，单位为吨，并根据货物卸 货地进行区分;%表示车辆K上的货物装卸地数总和，可能的取值为2， 3， 4，每辆货车的装卸情况 至少是一装一卸，最多两装两卸.模型的目标方程如下.

（1）最大化总订单货物重量：

（2）最小化实际运输车次数量：

其中表示最大化第*辆车货物总重量：

（3）最小化货车货物装卸地数量：

约束条件如以下公式（4）、（5）所示.

（1） 车货状态表示为Xj，取值为1或者O，分别表示货物Cj是否被分配至车辆Ti中：

（2）每辆车中装载的货物总重量不得超过货车的载重上限：

2       EGA算法求解多目标货物配载模型

遗传算法是模仿生物群落演化的过程，实现随着时间群组不断演化最后收敛的算法，其主要模仿 的是自然界中生物个体和基因繁殖、杂交和变异的现象，因此遗传算法的过程主要包括四个组成部 分：初始种群的表示方式、优秀个体的选择、基因之间的交叉、基因自身的变异.

本文在对历史数据的统计与分析过程中发现，在实际的货物配载过程中，最大化总订单货物重量 往往需要对多份货物进行拆分并重新组合.与此同时，单份订单中的货物装卸地数量也随之增加，这 表明配载过程中多个目标之间互相冲突，而传统的遗传算法并不能体现多个目标之间的冲突与竞争 关系.遗传算法在进化阶段选择个体时，普遍采用随机结构，但受制于配载过程中严格的约束条件，随 机挑选的个体极有可能都不符合配载规则，导致种群进化过程中需要耗费大量的时间来寻找第一代 可行解，这严重影响了计算效率.而一旦种群在进化过程中产生了符合约束的个体，种群会提前进入 收敛状态，这导致最终得到的最优解质量较差.同时，遗传算法本身依靠基因之间的交叉与变异这对既 相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力，在复杂的约束条件下，传统 的交叉、变异方法可能会失去作用，交叉或变异操作都可能会破坏掉原本已有的优秀个体的基因结 构，导致解的多样性不足，即便进入种群进化的中后期，最终解仍然有可能停留在找到第一代可行解 的阶段.

针对以上问题，本文提出基于精英保留策略的改进遗传算法（elitism genetic algorithm， EGA），主 要在遗传算法（genetic algorithm， GA）的基础上进行了以下三个部分的优化.

1.引人基于Pareto支配关系的分层结构.引入Pareto支配关系，利用Pareto支配关系对个体进 行分层，使得更优秀的个体基因以更大的概率被保留到下一代种群中.

2.采用改进的精英保留策略.通过Pareto支配关系对个体进行分层后，再保留父代种群中的非支 配解，使其直接进入子代种群，避免父代中优秀个体的丢失.

3.设计独立的交叉、变异算子.根据约束条件设计特殊的交叉、变异操作，在提高算法局部搜索 能力的同时加快种群收敛的速度.

2.1基于Pareto支配关系的分层结构

文献[21-24]在多目标优化问题中引入Pareto支配关系的概念，其定义为：假设任何两个解负及 為对所有目标而言，负均优于知则称负支配知若負没有被其他解所支配，则负称为非支配解（不 受支配的解），也称为Pareto解，為称为受支配解.在多目标优化问题中，如果目标之间存在冲突与竞 争关系，会存在多个非支配解，此时一组目标函数最优解的表示形式为Pareto最优解集.

本文提到的相关数学定义如下所示.

定义1（Pareto支配）设^和y是种群中任意两个个体，若满足下式（6），则称y支配a;，记作y?x..

定义2（非支配解）设a是集合Q中的任意解，若满足下式（7），则称a为集合Q中的非支配解.

?y ∈ Q ： y ? x.      （7）

定义3（Pareto最优解）设a是可行域况中任意个体，若满足下式（8），则称个体a为Pareto最 优解.

?y ∈ R ： y ? x.（8）

定义4（Pareto前沿）Pareto最优解构成的集合6*PS中所有Pareto最优解在目标空间上的映射， 称为 Pareto 前沿（Pareto Front， PF）

SPF = {f （x） ∈ R|x ∈ SPS} .  （9）

基于Pareto支配关系的分层流程如算法1所述.

算法1基于Pareto支配关系的个体分层 输人：染色体种群规模#

输出：分层后的各级支配层{&}， *表示非支配层数

1：      For j： =1 to N do

2：      For g： = 1 to N do

3：      基于适应度函数比较个体xj和个体x〃的支配关系

4：      如果不存在任何一个个体x3支配个体xj ，那么xj被标记为非支配个体

5：      End for

6：      End for

首次运行该分层算法可得到第一级非支配层;忽略这些非支配个体，重复该算法，得到第二级非 支配层;以此类推，直到所有种群中的个体被分类.

2.2精英保留策略

文献[25]提出精英保留策略，即把种群进化过程的优秀个体设置为精英个体，直接将精英个体复 制到下一代作为子代个体.但是传统的精英策略容易收敛于局部最优、保持种群多样性能力较差，本 文对其进行了改进：

（1）根据非支配层对个体分类，分别对各层上的个体集合进行拥挤度排序.

（2）为了保留进化过程中的精英解，对第一级的非支配层上的个体进行排序，将一级非支配层上 的所有个体直接选入子代，至多选择前fc#个个体.

（3）为了保证解的多样性，继续从其他等级非支配层上的个体挑选精英个体，由于选取的精英个 体数量不超过种群总个体数量的m倍，除第一层外个体数，剩余的名额平均分配给每级非支配层.

每级非支配层个体数量如下式（10）所示.

其中：i表示非支配层级别;F-表示第*级非支配层的个体集合;N-表示从第*级非支配层F-中选 择的个体数目;＼ F- ＼表示第*级非支配层中的个体数目;#表示种群大小;J表示非支配层数.

2.3交叉、变异操作

遗传算法的交叉、变异操作很大程度上决定了遗传算法进化的效率，迄今为止人们已经提出了许 多种交叉、变异方法，如单点交叉、双点交叉、均匀交叉等交叉算子，单点变异、逆序变异等变异算子. 这些交叉变异方法并不能很好地适应货物配载问题中多约束的问题，导致大量的个体经过交叉变异 过程之后不但没有进化，反而产生了大量的无效解（不符合约束条件的解），降低了算法的搜索效率.

本文采用改进的基于位置的交叉（Position-based Crossover， PBX），首先在两个父代染色体中随 机选择几个不连续的位置，将父代染色体1在这些位置上的基因复制到子代1相同位置上，再在父代 染色体2上将子代1中缺少的基因按照顺序填入.另一个子代以类似方式得到.改进的PBX操作见 图1.

随机选取几个不同位置且不相邻的基因

基因串逆序变异操作见图2.

2.4 EGA求解多目标优化货物配载模型流程 EGA求解多目标优化货物配载模型流程图见图3.

操作步骤如下：

Stepl初始化迭代次数、交叉概率、变异概率等参数;

Step2随机生成#个个体，作为初始种群即第一代父种群巧;

Step3对当前的父代种群巧进行非支配排序操作，对个体进行分层，得到各级Pareto非支配层

F1，F2，…，Fn ;

Step4利用精英策略对父代种群巧进行筛选，挑选出精英种群馬，剩余个体即为非精英种群 M，其中精英种群作为子代种群QeUte直接进入下一代进化，非精英种群进行交叉、变异操作;

Step5利用特殊的交叉、变异算子对非精英种群^中的个体进行计算，生成子代种群Qndite，合 并Qnelite和Qente得到最终的子代种群Qt ;

Step6判断迭代次数^是否小于等于设定的最大迭代次数，若是，则将^加1，然后跳转至Step3 进行下一层迭代过程，否则结束种群迭代过程.

3 快速收敛的EGA算法

相比于传统的遗传算法，上述改进的遗传算法在三个目标上的优化效果有显著提升，精英保留策

略使得种群在進化过程中可以更快地找到第一批可行解，但算法内部仍采用随机结构，受制于严格的 约束条件，随机结构并不适用于庞大的搜索空间，在一定程度上降低了算法的搜索效率.对遗传算法 而言，个体的交叉、变异过程对解的质量以及算法的效率都至关重要.自然环境中，不同的个体本身拥 有不同的遗传能力，通过性别鉴定法，可以进一步为不同的个体提高区分度，进而改变其交叉、变异操 作，使得最优解逼近真实Pareto前沿，同时提高算法的搜索效率.

为了加快种群的收敛速度，在保证解的多样性的同时使得算法可以更快地达到全局收敛状态，本 文在基于精英保留策略遗传算法的基础上进行了以下三个部分的改进.

（1）修改种群初始化方法.不再使用随机结构生成全部的初始种群，而采用贪心算法和随机结构 相结合的方式，快速得到较好的初始解.

（2）引人双种群策略.根据是否符合约束条件将个体分为有效个体与无效个体，再根据性别鉴定 法将有效个体分为繁殖能力强的繁殖个体和普通个体，对不同的个体采用不同的交叉、变异操作.

（3）采用自适应的交叉、变异算子.在种群进化前期设置高交叉概率，提高种群的全局搜索能力， 提高进化速度，后期设置高变异概率，防止陷入局部最优，提高局部搜索能力.

3.1种群初始化

传统的遗传算法利用随机结构生成作为初始父代种群，由于货物配载问题中的约束条件过于复 杂，随机生成的个体会有极高的概率不符合约束条件而失效，从而降低了算法的收敛速度.在实际问 题中，可以先利用贪心算法生成一部分装车清单，即符合约束条件的可行解，作为一部分初始种群（^greedy）， 之后与随机生成的初始种群（Random）合并为初始的父代种群，结合精英保留策略，这一部分可行解会 成为初代精英解直接进入下一代进化，直接加快了种群的收敛速度.

3.2双种群进化策略

大多数多目标进化算法的进化过程比较单一，迭代过程中单一的种群增加了算法的随机性，很大 程度上削弱了算法的搜索能力和找到最优解的速度.而使用双种群进化策略可以降低算法的随机性， 使種群往特定的方向进化，从而扩大了整体的搜索空间，而且在避免算法陷入局部最优的同时可以加 快算法的收敛速度.在进化过程中，根据种群的比例参数和繁殖能力鉴定法将种群拆分为两个种群， 并对两个种群采用不同的遗传操作.

性别鉴定法分为计算和评判染色体种群中个体繁殖能力两个部分，具体流程描述如下.

Stepl初始化参数：染色体种群大小测试种群大小&个体分割比例值达

Step2随机生成测试种群;

Step3分别计算染色体种群中每个个体的繁殖能力;

Step4评判染色体种群中个体的繁殖能力;

Step5分割种群.对具有繁殖能力的个体进行排序，挑选前# X ^个个体，作为子代种群1，如果 数量不足，则根据普通个体的繁殖能力进行排序，挑选繁殖能力高的普通个体作为补充;剩余的个体 组合作为子代种群2.

其算法伪代码见算法2.

算法2性别鉴定法

输人：染色体种群大小况测试种群大小S·，个体分割比例值

输出：繁殖个体种群集合Pro，普通个体种群集合ATormd

1：      For i： = 1 to N do

2：      For j： = 1 to S' do

3：      个体z与个体j进行交叉产生子代个体;

4：      If o//springi      y t， then

5：      / = O//sprm知A +=1 //如果产生的子代个体支配个体t，更新个体t的繁殖能力

6：      End for

7：      End for

8：      For t： = 1 to N do

9：      If P i > Paverage then

10：   Pro ^ Pro U {t}

11：   Else

12：   Normal ^ Normal U {t}

13：   End for

3.3自适应的交叉、变异算子

遗传算法的参数中交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在，它们直 接影响算法的收敛性.交叉概率越大，新个体产生的速度就越快，然而过大的交叉概率可能会破坏原 本的个体基因结构，但过小的交叉概率会降低搜索性能.变异概率越小，越不容易生成新的基因结构， 而过大的变异概率可能会使得遗传算法具有更强的随机性，让种群进化失去方向.

本文针对种群进化的不同阶段，设计自适应的交叉、遗传算子，使得交叉概率和变异概率能够自 动改变.在前期产生的优秀个体的质量较差，为了加快种群找到支配解的速度，故设置较大的交叉概 率Pc ，从而提高算法的全局搜索能力;在中后期已经产生部分优秀解时，为了防止算法陷入局部最优， 设置较大的变异概率Pm ，从而提高算法的全局搜索能力.

交叉概率范围设置为（0.4， 0.8），变异概率范围设置为（0.01， 0.（3），计算公式见式（11）、（12）.

其中：Pc （i）表示第t代的交叉概率;Pm （i）表示为第t代的变异概率;G为总迭代次数;maxPc为最大 交叉概率值;minPc为最小交叉概率值;maxPm为最大变异概率值;minPm为最小变异概率值.

3.4 FEGA算法求解多目标优化货物配载模型

FEGA算法求解多目标优化货物配载模型流程图见图4.

操作步骤如下：

Stepl设置迭代次数、交叉变异概率等初始化参数;

Step2利用贪心算法生成0.3N个个体，再随机生成0.7N个个体，最后合并生成父代种群P* ;

Step3对当前的父代种群P*进行非支配排序，将个体分层，得到各级Pareto非支配层巧，

f2， · · · ，Fn ;

Step4通过繁殖能力鉴定法拆分种群，得到繁殖种群1和普通种群2;

Step5对种群1和种群2分别采用不同的自适应交叉、变异算子操作，得到子代种群;

Step6利用精英策略对子代种群进行筛选，挑选出精英种群，剩余个体即为非精英种群;

Step7合并Stop5—Stop6中得到的两份精英子代种群，生成新一代种群;

Step8判断迭代次数p是否小于等于设定的最大迭代次数，若是，则将p加1，然后跳转至Step3 进行下一层迭代过程，否则结束种群迭代过程.

4       实验设置与结果分析

为验证FEGA算法求解的有效性，使用京创智汇物流平台提供的真实历史数据对所提算法进行 性能测试，然后结合三个优化目标验证算法的实用性，同时对结果进行可视化.

部分实际可发库存信息见表1，该数据取自京创智汇物流平台库存管理系统，主要包括品種名 称、取货仓库、卸货地址、货物件数、货物重量等数据项.实验中一个批次的可发库存数据共674条， 合计货物13367条.

4.1参数设置

实验在Windows10环境下运行，米用Python3.7语言编写，在CPU为AMD Ryzen 7 4800U的处 理器和内存为16 GB RAM的机器上进行测试验证.在该实验中，参数设置如下：种群规模#= 100， 最大迭代次数G = 1000，交叉概率范围（0.4， 0.8），变异概率范围（0.01，0.3）.

4.2评价指标

（1）非支配解数量

非支配解的数量表示不被其他解占优的解集合大小，其定义见下式（13）.

Nn =| S ? {x ∈ S|?y ∈ S? ： y ? x} |，（13）

其中^表示所有非支配解的集合[26].显然N?的值越大，说明得到的解越好.

（2）HV （Hypervolume）超体积

Hypervolume[27]为一个关于非支配解的离散度、收敛性的综合指标，其已成为近年来多目标评价 指标中最常用的指标之一.该指标计算时需要一个参考点，一般设置为真实Pareto前沿中每个目标的 最大值，假设为只=（风，…若得到的HV值越大，说明得到的解越好，其定义见下式（14），其中Leb⑷是集合乂的Lebesgue测度;&是SW中的非支配解集;m为该解集的大小;（x）表示解集 中的第*个解.

4.3实验结果分析

本文选取目前多目标优化中较为常用的NSGA-II和PSO算法进行对比实验.首先通过对比多目 标算法的非支配解个数和HV指标值证明算法可行性，只有EGA、FEGA、NSGA-II算法利用多目标 优化，所以通过NSGA-II算法来进行对比.同时，本文通过实际的应用场景对业务指标进行评估，实 际的业务指标转化为本文提出的3个优化目标.基础算法选取GA来进行对比，此处的遗传算法利用 单目标优化问题求解，将3个优化目标进行权重求和转化为单个目标.最后对比GA、NSGA-II和本文 提出的两个算法的收敛性，由此证明算法性能.

4.3.1算法可行性分析

利用5份不同的库存数据进行实验，并计算NSGA-II、EGA、FEGA这3种算法的非支配解平均 数量，其对比结果见图5.

图5中显示最终EGA相对于NSGA-II的非支配解数量和相同，但达到收敛的速度优于NSGA-II， 而FEGA无论是最终非支配解的数量还是达到收敛的速度都明显优于其他算法，表明FEGA在保持 高求解精度的同时还具有快速收敛的性能，具有很好的全局、局部搜索能力.

同时计算其HV指标值，对比结果见图6.

从图6中可看出EGA的收敛状况来回波动，稳定性较差，而FEGA的收敛状态相对稳定，且优 于NSGA-II算法，通过设计混合贪心算法和随机结构生成初始种群，极大地加快了种群的全局搜索能 力，同时自适应操作算子双种群策略也使得FEGA在货物配载过程中可以更快地收敛.

4.3.2 多个目标优化结果对比

为了验证快速收敛的精英遗传算法（FEGA）对多目标货物配载模型求解的有效性，将运行结果与 精英遗传算法（EGA）、传统的遗传算法（GA）、快速非支配排序遗传算法（NSGA-II）、粒子群算法 （PSO）的结果进行对比.对比结果见表2.

从表2可以看出：相对于传统的遗传算法，两种算法都取得了较好的测试结果，但随着问题规模 的增加，FEGA算法的最优解在第一个目标上的结果明显优于其他算法，实际货物配载场景中，第一 个目标的优先级最高，第二个目标的优先级次之，第三个目标的优先级最低.故相较于基础的遗传算 法，本文提出的两种算法都可以实现货物配载的多目标优化.

4.3.3 收敛性对比

由于第一个优化目标的优先级最高，所以通过多次实验计算其对应目标函数值，进行比较，其对 比结果见图7.

从图7的收敛速度曲线对比分析可知，相比于其他算法，FEGA算法在采用双种群进化策略之后， 不仅可以产生质量更高的最优解，算法的收敛速度也明显提升.EGA算法引入精英保留策略，相较于 普通的遗传算法可以找到质量更好的解，同时其收敛速度比NSGA-II算法更快.验证了 FEGA算法 能够有效改善基础遗传算法的搜索性能和提升EGA算法的收敛性能.

5结束语

本文根据物流平台需求建立货物配载多目标优化模型，对传统遗传算法的全局搜索能力与种群 收敛速度进行优化，提出了带精英策略和自适应算子的双种群策略的改进遗传算法——FEGA算法， 该算法在确保种群多样性的同时，增加算法全局搜索能力，加快种群收敛速度.以真实的货物数据集 验证了算法求解多目标货物配载过程的可行性和有效性，证明了该算法在强约束条件和庞大的搜索 空间的情况下可获得最佳配载方案.

[參考文献]

[1]TIMOTHY R， JASBIR S. The weighted sum method for multi-objective optimization： New insights [J]. Structural and Multidisciplinary Optimization， 2010， 41（6）： 853-862.

[2] PINCHERA D， PERNA S， MIGLIORE M. A lexicographic approach for multi-objective optimization in antenna array design [J]. Progress in Electromagnetics Research， 2017， 59（2）： 85-102.

[3 ] DAS I， DENNIS J. Normal-boundary intersection： A new method for generating the Pareto surface in nonlinear multicriteria optimization problems [J]. SIAM Journal on Optimization， 1998， 8（3）： 631-657.

[4]MESSAC A， ISMAIL-YAHAYA A， MATTSON C. The normalized normal constraint method for generating the Pareto frontier [J]. Structural and Multidisciplinary Optimization， 2003， 25（2）： 86-98.

[5 ] MESSAC A， MATTSON C. Normal constraint method with guarantee of even representation of complete Pareto frontier [J]. AIAA Journal， 2004， 42（10）： 2101-2111.

[6 ] MUELLER D， GRAEB H， SCHLICHTMANN U. A successive approach to compute the bounded Pareto front of practical multiobjective optimization problems [J]. SIAM Journal on Optimization， 2009， 20（2）： 915-34.

[7 ] TOHID E， SERGEI V. Directed search domain： A method for [J]. Engineering Optimization， 2011， 43（5）： 467-484.

[8 ] VIKHAR P. Evolutionary algorithms： A critical review and its future prospects [C]//2016 International Conference on Global Trends in Signal Processing， Information Computing and Communication （ICGTSPICC）. IEEE， 2016： 261-265.

[9 ] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multi-objective genetic algorithm： NSGA-II[J]. IEEE Transactions on Evolutionary Computation. 2002， 6（2）： 182-197.

[10]YI J H， DEB S， DONG J Y， et al. An improved NSGA-III algorithm with adaptive mutation operator for Big Data optimization problems [J]. Future Generation Computer Systems， 2018， 88： 571-585.

[11]KIM M， HIROYASU T， MIKI M， et al. SPEA2+： Improving the performance of the strength Pareto evolutionary algorithm 2 [C]//International Conference on Parallel Problem Solving from Nature. New York： Springer， 2004： 742-751.

[12]ZHANG Q， LI H. MOEA/D： A multi-objective evolutionary algorithm based on decomposition [J] . IEEE Transactions on Evolutionary Computation， 2008， 11（6）： 712-743.

[13]ALAYA I， SOLNON C， GHEDIRA K. Ant colony optimization for multi-objective optimization problems [C]//19th IEEE International Conference on Tools with Artificial Intelligence （ICTAI 2007）. IEEE， 2007： 450-457.

[14]MOSTAGHIM S， TEICH J. Strategies for finding good local guides in multi-objective particle swarm optimization （MOPSO） [C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium. IEEE， 2003： 26-33.

[15]SUMAN B， KUMAR P. A Survey of simulated annealing as a tool for single and multi-objective optimization [J]. The Journal of the Operational Research Society， 2006， 57（10）： 1143-1160.

[16]AN Y J， CHEN X H， LI Y H， et al. An improved non-dominated sorting biogeography-based optimization algorithm for the （hybrid） multi-objective flexible job-shop scheduling problem [J]. Applied Soft Computing， 2021， 99： 106869.

[17]WU X， CAO W， WANG D， et al. Multi objective optimization based on SPEA for the microgrid energy dispatch [C]//2018 37th Chinese Control Conference （CCC）. IEEE， 2018： 7543-7548.

[18]鄭斐峰，梅启煌，刘明，等.基于遗传算法与贪婪策略的多港口集装箱配载研究[J].运筹与管理，2018， 27（5）： 1-7.

[19]覃亮，王志成.整车物流中轿运车装载方案优化研究[J].系统仿真学报，2015， 27（8）： 1868-1874.

[20]徐佳毅.建立整车物流装运模型及最优算法的应用研究[D].上海：上海交通大学，2012.

[21]NGATCHOU P， ZAREI A， EI A. Pareto multi objective optimization [C]//Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems. IEEE， 2005： 84-91.

[22]张长勇，刘佳瑜.基于混合遗传算法的多箱型集装箱装载问题研究[J].北京航空航天大学学报，2021. DOI： 10.13700/j.bh.100-5965.2020.0665.

[23]张程，贾宝柱，邹佳奇.基于多目标遗传算法的柴电混合动力船舶功率分配优化[J].计算机应用与软件，2021， 38（3）： 26-31.

[24]张闻强，邢征，杨卫东.基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J].计算机应用，2021， 41（8）： 2249-2257.

[25]DE J， ALAN K. Analysis of the behavior of a class of genetic adaptive systems [C]//The Transactions of the Institute of Electrical Engineers of Japan. 1975： 721-726.

[26]PENG Q K， WANG L， QIAN B. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems [J] . Computers and Operations Research， 2008， 36（8）： 2498-2511.

[27]ZITZLER E， THIELE L. Multi-objective evolutionary algorithms： A comparative case study and the strength Pareto approach [C]//IEEE Transactions on Evolutionary Computation. IEEE， 1999： 257—271.

（责任编辑：林晶）