于萍 胡卉芪 錢衛(wèi)寧

摘要：針對多目標貨物配載問題，建立了以最大化總訂單貨物重量、最小化車次總數(shù)、最小化貨物裝卸地 總數(shù)為目標的配載模型，提出了一種快速收斂的基于精英策略多目標遺傳算法（Fast Convergence Based on the Elitism Genetic Algorithm， FEGA）.首先，在遺傳算法的基礎上加入Pareto支配關系上的分層結構 和精英保留策略，從而提高種群的多樣性，同時還可以加快算法的局部搜索能力;其次，修改初始種群的隨 機結構，并加入雙種群策略，添加自適應操作算子，依次提高算法的全局搜索能力，加速種群的收斂速度; 最后，基于新算法，利用真實的貨物數(shù)據(jù)驗證算法的可行性與優(yōu)化效果.結果表明，與傳統(tǒng)遺傳算法相比， 所提算法在求解強約束條件、龐大搜索空間的貨物配載過程中具有較好的優(yōu)化效果，搜索性能與收斂性都有所提升. 關鍵詞：多目標優(yōu)化;貨物配載;遺傳算法

中圖分類號：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引 言

隨著鋼鐵物流行業(yè)的飛速發(fā)展，大宗貨物的配載現(xiàn)已進入蓬勃發(fā)展的階段，行業(yè)內的許多頑固問

收稿日期：2021-07-27 基金項目：國家自然科學基金（U191120（3）

通信作者：胡丼苗，男，副教授，主要研究方向為數(shù)據(jù)庫系統(tǒng)、分布式系統(tǒng).E-mail： hqhu@dase.ecnu.edu.cn

題也逐漸暴露.鋼材運輸具有距離長、運載重量過大的特點，只有重型卡車才能滿足運載要求.但重型 卡車的數(shù)量有限，且卡車分布不均勻，鋼鐵企業(yè)普遍面臨著重卡超載、貨物堆積、訂單逾期等嚴重問 題.傳統(tǒng)的貨物配載方案是由人工實時制定，基于最大化卡車負載來確定每輛卡車的貨物配載方案， 可忽視了整體車輛的裝載情況、司機對于運輸任務的滿意程度等其他信息，但這些因素都與鋼鐵物流 平臺的利潤息息相關.因此，研究鋼鐵物流的配載問題對降低物流平臺運送成本、提高經濟收益等都 有積極意義.

在實際的貨物配載場景下，物流平臺為了降低運送成本、提高經濟收益，需要從貨物特征、司機 滿意度等多個維度綜合考慮，同時優(yōu)化多個互相沖突和影響的目標，因此本文根據(jù)實際業(yè)務中的配載 目標，建立貨物配載多目標優(yōu)化模型.

多目標優(yōu)化問題根據(jù)用戶偏好信息的決策時機分為先驗和后驗兩類.其中先驗方法是指在求解 過程之前將偏好信息轉化為顯性的偏好因子，利用偏好因子將多目標量化為單目標，最終轉化為單目 標優(yōu)化問題，通過求解該單目標優(yōu)化問題得到解.權重求和法利用用戶偏好信息為每個目標設定權 重值，利用權重求和將多個目標量化為單個目標，最終求解最值得到最優(yōu)解.字典法通過解析用戶 的偏好信息將目標按照重要性進行排序，最終轉化為求解一系列單目標形式的最優(yōu)化問題.但是偏好 因子的定性表示存在主觀性，除非可以找到一個可靠而精確的偏好向量進行標量化，否則轉化為單目 標問題得到的解相當主觀.當偏好因子無法被精確表示時，可以采用后驗方法.后驗方法首先找到多 個目標的多重權衡下的最優(yōu)解集，然后利用用戶的偏好信息從多個解決方案中選擇其中一個.大多數(shù) 后驗方法分為兩類：基于數(shù)學規(guī)劃的后驗方法，該方法通過其中一個算法重復運行，每次運行該算法 產生一個折中解;進化算法則通過運行一次該算法可以產生一組折中解.數(shù)學方法中法線邊界相交 （NBI）'法線約束（NC）[4-5]，連續(xù)Pareto優(yōu)化（SPO）[6]，定向搜索域（DSDfl方法通過構造若干標量來 求解多目標問題，該標量化過程是以獲得均勻分布的折中解為目標來構造的.但是多目標優(yōu)化本身屬 于NP問題，當產生的折中解數(shù)量過多時，則需要更多的計算時間，在實際應用場景下該方法無法在 有限的時間內產生足夠的折中解.進化類算法[8]是目前產生多目標優(yōu)化問題的折中解最常用的方法， 它可以在有限的時間內產生足夠多的折中解供決策者選擇.其中NSGA-II[9]和NSGA-m[10]基于遺傳 算法提出Pareto最優(yōu)解的概念以及解與解之間的支配關系，通過支配關系將所有的可行解進行排序， 進而提高算法的搜索效率.SPEA-II[n]在此基礎上提出根據(jù)每個個體的支配個體數(shù)目和被支配個體數(shù) 目來進一步計算適應度的值，從而加快種群的收斂速度.MOEA/D[12]基于分解的思想，將逼近整個 Pareto前沿面的問題分解為一定數(shù)量的單目標優(yōu)化問題，然后利用進化算法同時求解這些單目標優(yōu) 化問題，使得種群保持多樣性.仿生類算法以及仿物類算法如蟻群算法[13]、粒子群算法[14]、模擬退火算 法[15]是通過模擬生物和自然界物體的行為特征來設計種群更新的方法.該類算法無法同時兼顧種群 的多樣性和收斂性，算法效率不高.物流領域中1161綜合了 NSGA-II和基于生物地理學的優(yōu)化算法來處 理生產調度中的多目標車間作業(yè)調度問題，在提高算法的局部搜索能力的同時又加快了種群的收斂 速度.文獻[17]構建的電網資源分配模型，在預測模塊中使用了神經網絡，結合多目標優(yōu)化算法 SPEA，實現(xiàn)了經濟成本、環(huán)境收益、能源利用率的多目標優(yōu)化.

綜上所述，并不存在適用所有場景的多目標方法，而物流領域中的貨物配載問題關注貨物特征和 業(yè)務場景，在具有多種約束條件的情況下對貨物進行排列組合，大多數(shù)研究1181都利用啟發(fā)式算法求解 貨物配載相關問題，比如集裝箱問題.但集裝箱類問題主要考慮貨物的體積、集裝箱的空間利用率，約 束規(guī)則較少，且與實際業(yè)務問題關聯(lián)較淺.還有一部分配載問題119-201重在解決倉庫協(xié)調過程，與本文 背景不符.

目前，啟發(fā)式算法被認為是求解近似最優(yōu)解較為有效的算法，其算法內部的隨機優(yōu)化結構需要根 據(jù)具體的問題單獨設計，而智能算法中粒子群算法更容易陷入局部最優(yōu)，不適合求解離散問題.實際 的貨物裝配問題帶有強約束條件，模擬退火算法和爬山算法都不適用于大規(guī)模多約束問題，而遺傳算 法不僅可以很好地處理多約束條件下的離散問題，而且相較于其他智能算法，還具有更強的全局搜索 能力.

本文在對鋼鐵物流配載流程、特點和貨物配載目標充分調研的基礎上，建立了貨物配載多目標優(yōu) 化模型，并針對該問題特點，設計了一種基于精英保留策略的改進遺傳算法，為了進一步加快種群的 全局搜索能力，提出了一種可以快速收斂的基于精英策略的改進遺傳算法（FEGA），在提高最優(yōu)解質 量的同時，增強算法全局與局部搜索能力.通過實際的貨物數(shù)據(jù)，說明FEGA在面對約束條件復雜、 搜索空間大的多目標優(yōu)化問題時，在計算效率、收斂性和多樣性上都優(yōu)于普通遺傳算法.

1 多目標貨物配載模型

1.1問題描述

物流平臺每天在零點獲取倉庫的庫存數(shù)據(jù)，結合貨物的品種、倉庫、規(guī)格等特征以及不同品種的 貨物之間拼貨時需滿足的限制條件，對客戶訂單進行拆分、組合，生成一批裝車清單，并上傳至平臺供 司機選擇.當前平臺使用的配載方法是通過順序遍歷貨物列表，在符合業(yè)務規(guī)則的條件下，以最大化 單輛車的貨物重量為目標為車次分配貨物.該方法沒有考慮到后續(xù)的貨物信息和剩余空車次數(shù)量，無 法實現(xiàn)全局最優(yōu)的貨物分配，導致大量貨物積壓，部分單車貨物重量遠低于車輛載重上限.

針對上述貨物配載效率太低及貨車利用率不高等問題，本文提出了多目標優(yōu)化貨物配載模型，根 據(jù)實際的業(yè)務調研結果，從物流平臺和貨車司機雙方的角度綜合考慮.物流平臺需要考慮運輸利益與 運力成本，其中平臺利益與貨物發(fā)運量成正比.配載過程需要考慮貨物狀態(tài)，即是否存在客戶催貨、超 出合同約定期的貨物，故應盡可能優(yōu)先發(fā)運該類貨物，而倉庫堆積的貨物越多也越不利于后續(xù)生產的 貨物發(fā)運，導致上一輪貨物堆積時間更長.在單批次配載過程中，應發(fā)運盡可能多的貨物，減少尾貨. 物流平臺不僅需要考慮貨物運輸重量，同時需要承擔運力成本，一份裝車清單需要一輛車運載，平臺 需要向司機付運費，故在考慮發(fā)運盡可能多的貨物的同時，應盡量減少訂單數(shù)，即減少車次數(shù)，從而降 低運力成本，實現(xiàn)用更少的車運載更多貨物的目標.從貨車司機的角度考慮，貨車通過裝車清單去往 倉庫取貨，如果倉庫擁擠則還需排隊等待，若有多個取貨倉庫則會大大提高司機的時間成本.同理，若 有多個卸貨地，司機也需要額外的等待時間.在實際運輸過程中，司機更傾向于選擇單個裝卸貨地的 運單，而多個裝貨、卸貨的裝車清單往往需要手動派單.

經過分析后設計以下三個具有實際應用價值的目標.從物流平臺的角度考慮，通過增加單批次所 有訂單的貨物總重量，減少單批次訂單數(shù)即減少車次數(shù)來降低平臺成本.與此同時，在貨車不超載的 情況下盡可能增大單輛車的裝載重量，從而在提高配載效率的同時可以提升平臺經濟收益;從貨車司 機的角度考慮，盡可能降低貨車中貨物的裝卸地數(shù)量，可減少司機的時間成本，給司機帶來最大的便 利.在實際的業(yè)務調研中發(fā)現(xiàn)，管理員在對貨物進行分配時具有明顯的優(yōu)先級考慮，在平臺利益與司 機便利程度上比較，管理員優(yōu)先考慮平臺利益，在考慮平臺利潤的前提下，優(yōu)先考慮貨物狀態(tài)，再考慮 平臺雇用車輛成本，由此為這三個目標設定優(yōu)先級，優(yōu)先最大化所有訂單的貨物總重量，其次減少總 訂單數(shù)，減少總訂單的貨物裝卸地優(yōu)先級最低.

1.2數(shù)學模型

根據(jù)對貨物配載問題的分析，貨物配載模型主要參數(shù)描述如下.

本文使用K （1 < *彡m）表示可供使用的車次中第*輛車;^ （1 < j < n）表示當前庫存可發(fā)運貨 物中第J件貨物;使用裝車清單描述車輛依次運輸任務需要裝載的貨物情況;%表示貨物^的重 量，單位為噸;表示車貨狀態(tài)，取值為O或1; ^表示車輛K的載重上限，單位為噸，并根據(jù)貨物卸 貨地進行區(qū)分;%表示車輛K上的貨物裝卸地數(shù)總和，可能的取值為2， 3， 4，每輛貨車的裝卸情況 至少是一裝一卸，最多兩裝兩卸.模型的目標方程如下.

（1）最大化總訂單貨物重量：

（2）最小化實際運輸車次數(shù)量：

其中表示最大化第*輛車貨物總重量：

（3）最小化貨車貨物裝卸地數(shù)量：

約束條件如以下公式（4）、（5）所示.

（1） 車貨狀態(tài)表示為Xj，取值為1或者O，分別表示貨物Cj是否被分配至車輛Ti中：

（2）每輛車中裝載的貨物總重量不得超過貨車的載重上限：

2?????? EGA算法求解多目標貨物配載模型

遺傳算法是模仿生物群落演化的過程，實現(xiàn)隨著時間群組不斷演化最后收斂的算法，其主要模仿 的是自然界中生物個體和基因繁殖、雜交和變異的現(xiàn)象，因此遺傳算法的過程主要包括四個組成部 分：初始種群的表示方式、優(yōu)秀個體的選擇、基因之間的交叉、基因自身的變異.

本文在對歷史數(shù)據(jù)的統(tǒng)計與分析過程中發(fā)現(xiàn)，在實際的貨物配載過程中，最大化總訂單貨物重量 往往需要對多份貨物進行拆分并重新組合.與此同時，單份訂單中的貨物裝卸地數(shù)量也隨之增加，這 表明配載過程中多個目標之間互相沖突，而傳統(tǒng)的遺傳算法并不能體現(xiàn)多個目標之間的沖突與競爭 關系.遺傳算法在進化階段選擇個體時，普遍采用隨機結構，但受制于配載過程中嚴格的約束條件，隨 機挑選的個體極有可能都不符合配載規(guī)則，導致種群進化過程中需要耗費大量的時間來尋找第一代 可行解，這嚴重影響了計算效率.而一旦種群在進化過程中產生了符合約束的個體，種群會提前進入 收斂狀態(tài)，這導致最終得到的最優(yōu)解質量較差.同時，遺傳算法本身依靠基因之間的交叉與變異這對既 相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力，在復雜的約束條件下，傳統(tǒng) 的交叉、變異方法可能會失去作用，交叉或變異操作都可能會破壞掉原本已有的優(yōu)秀個體的基因結 構，導致解的多樣性不足，即便進入種群進化的中后期，最終解仍然有可能停留在找到第一代可行解 的階段.

針對以上問題，本文提出基于精英保留策略的改進遺傳算法（elitism genetic algorithm， EGA），主 要在遺傳算法（genetic algorithm， GA）的基礎上進行了以下三個部分的優(yōu)化.

1.引人基于Pareto支配關系的分層結構.引入Pareto支配關系，利用Pareto支配關系對個體進 行分層，使得更優(yōu)秀的個體基因以更大的概率被保留到下一代種群中.

2.采用改進的精英保留策略.通過Pareto支配關系對個體進行分層后，再保留父代種群中的非支 配解，使其直接進入子代種群，避免父代中優(yōu)秀個體的丟失.

3.設計獨立的交叉、變異算子.根據(jù)約束條件設計特殊的交叉、變異操作，在提高算法局部搜索 能力的同時加快種群收斂的速度.

2.1基于Pareto支配關系的分層結構

文獻[21-24]在多目標優(yōu)化問題中引入Pareto支配關系的概念，其定義為：假設任何兩個解負及 為對所有目標而言，負均優(yōu)于知則稱負支配知若負沒有被其他解所支配，則負稱為非支配解（不 受支配的解），也稱為Pareto解，為稱為受支配解.在多目標優(yōu)化問題中，如果目標之間存在沖突與競 爭關系，會存在多個非支配解，此時一組目標函數(shù)最優(yōu)解的表示形式為Pareto最優(yōu)解集.

本文提到的相關數(shù)學定義如下所示.

定義1（Pareto支配）設^和y是種群中任意兩個個體，若滿足下式（6），則稱y支配a;，記作y?x..

定義2（非支配解）設a是集合Q中的任意解，若滿足下式（7），則稱a為集合Q中的非支配解.

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

定義3（Pareto最優(yōu)解）設a是可行域況中任意個體，若滿足下式（8），則稱個體a為Pareto最 優(yōu)解.

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

定義4（Pareto前沿）Pareto最優(yōu)解構成的集合6*PS中所有Pareto最優(yōu)解在目標空間上的映射， 稱為 Pareto 前沿（Pareto Front， PF）

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

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

算法1基于Pareto支配關系的個體分層 輸人：染色體種群規(guī)模#

輸出：分層后的各級支配層{&}， *表示非支配層數(shù)

1：????? For j： =1 to N do

2：????? For g： = 1 to N do

3：????? 基于適應度函數(shù)比較個體xj和個體x〃的支配關系

4：????? 如果不存在任何一個個體x3支配個體xj ，那么xj被標記為非支配個體

5：????? End for

6：????? End for

首次運行該分層算法可得到第一級非支配層;忽略這些非支配個體，重復該算法，得到第二級非 支配層;以此類推，直到所有種群中的個體被分類.

2.2精英保留策略

文獻[25]提出精英保留策略，即把種群進化過程的優(yōu)秀個體設置為精英個體，直接將精英個體復 制到下一代作為子代個體.但是傳統(tǒng)的精英策略容易收斂于局部最優(yōu)、保持種群多樣性能力較差，本 文對其進行了改進：

（1）根據(jù)非支配層對個體分類，分別對各層上的個體集合進行擁擠度排序.

（2）為了保留進化過程中的精英解，對第一級的非支配層上的個體進行排序，將一級非支配層上 的所有個體直接選入子代，至多選擇前fc#個個體.

（3）為了保證解的多樣性，繼續(xù)從其他等級非支配層上的個體挑選精英個體，由于選取的精英個 體數(shù)量不超過種群總個體數(shù)量的m倍，除第一層外個體數(shù)，剩余的名額平均分配給每級非支配層.

每級非支配層個體數(shù)量如下式（10）所示.

其中：i表示非支配層級別;F-表示第*級非支配層的個體集合;N-表示從第*級非支配層F-中選 擇的個體數(shù)目;＼ F- ＼表示第*級非支配層中的個體數(shù)目;#表示種群大小;J表示非支配層數(shù).

2.3交叉、變異操作

遺傳算法的交叉、變異操作很大程度上決定了遺傳算法進化的效率，迄今為止人們已經提出了許 多種交叉、變異方法，如單點交叉、雙點交叉、均勻交叉等交叉算子，單點變異、逆序變異等變異算子. 這些交叉變異方法并不能很好地適應貨物配載問題中多約束的問題，導致大量的個體經過交叉變異 過程之后不但沒有進化，反而產生了大量的無效解（不符合約束條件的解），降低了算法的搜索效率.

本文采用改進的基于位置的交叉（Position-based Crossover， PBX），首先在兩個父代染色體中隨 機選擇幾個不連續(xù)的位置，將父代染色體1在這些位置上的基因復制到子代1相同位置上，再在父代 染色體2上將子代1中缺少的基因按照順序填入.另一個子代以類似方式得到.改進的PBX操作見 圖1.

隨機選取幾個不同位置且不相鄰的基因

基因串逆序變異操作見圖2.

2.4 EGA求解多目標優(yōu)化貨物配載模型流程 EGA求解多目標優(yōu)化貨物配載模型流程圖見圖3.

操作步驟如下：

Stepl初始化迭代次數(shù)、交叉概率、變異概率等參數(shù);

Step2隨機生成#個個體，作為初始種群即第一代父種群巧;

Step3對當前的父代種群巧進行非支配排序操作，對個體進行分層，得到各級Pareto非支配層

F1，F(xiàn)2，…，F(xiàn)n ;

Step4利用精英策略對父代種群巧進行篩選，挑選出精英種群馬，剩余個體即為非精英種群 M，其中精英種群作為子代種群QeUte直接進入下一代進化，非精英種群進行交叉、變異操作;

Step5利用特殊的交叉、變異算子對非精英種群^中的個體進行計算，生成子代種群Qndite，合 并Qnelite和Qente得到最終的子代種群Qt ;

Step6判斷迭代次數(shù)^是否小于等于設定的最大迭代次數(shù)，若是，則將^加1，然后跳轉至Step3 進行下一層迭代過程，否則結束種群迭代過程.

3 快速收斂的EGA算法

相比于傳統(tǒng)的遺傳算法，上述改進的遺傳算法在三個目標上的優(yōu)化效果有顯著提升，精英保留策

略使得種群在進化過程中可以更快地找到第一批可行解，但算法內部仍采用隨機結構，受制于嚴格的 約束條件，隨機結構并不適用于龐大的搜索空間，在一定程度上降低了算法的搜索效率.對遺傳算法 而言，個體的交叉、變異過程對解的質量以及算法的效率都至關重要.自然環(huán)境中，不同的個體本身擁 有不同的遺傳能力，通過性別鑒定法，可以進一步為不同的個體提高區(qū)分度，進而改變其交叉、變異操 作，使得最優(yōu)解逼近真實Pareto前沿，同時提高算法的搜索效率.

為了加快種群的收斂速度，在保證解的多樣性的同時使得算法可以更快地達到全局收斂狀態(tài)，本 文在基于精英保留策略遺傳算法的基礎上進行了以下三個部分的改進.

（1）修改種群初始化方法.不再使用隨機結構生成全部的初始種群，而采用貪心算法和隨機結構 相結合的方式，快速得到較好的初始解.

（2）引人雙種群策略.根據(jù)是否符合約束條件將個體分為有效個體與無效個體，再根據(jù)性別鑒定 法將有效個體分為繁殖能力強的繁殖個體和普通個體，對不同的個體采用不同的交叉、變異操作.

（3）采用自適應的交叉、變異算子.在種群進化前期設置高交叉概率，提高種群的全局搜索能力， 提高進化速度，后期設置高變異概率，防止陷入局部最優(yōu)，提高局部搜索能力.

3.1種群初始化

傳統(tǒng)的遺傳算法利用隨機結構生成作為初始父代種群，由于貨物配載問題中的約束條件過于復 雜，隨機生成的個體會有極高的概率不符合約束條件而失效，從而降低了算法的收斂速度.在實際問 題中，可以先利用貪心算法生成一部分裝車清單，即符合約束條件的可行解，作為一部分初始種群（^greedy）， 之后與隨機生成的初始種群（Random）合并為初始的父代種群，結合精英保留策略，這一部分可行解會 成為初代精英解直接進入下一代進化，直接加快了種群的收斂速度.

3.2雙種群進化策略

大多數(shù)多目標進化算法的進化過程比較單一，迭代過程中單一的種群增加了算法的隨機性，很大 程度上削弱了算法的搜索能力和找到最優(yōu)解的速度.而使用雙種群進化策略可以降低算法的隨機性， 使種群往特定的方向進化，從而擴大了整體的搜索空間，而且在避免算法陷入局部最優(yōu)的同時可以加 快算法的收斂速度.在進化過程中，根據(jù)種群的比例參數(shù)和繁殖能力鑒定法將種群拆分為兩個種群， 并對兩個種群采用不同的遺傳操作.

性別鑒定法分為計算和評判染色體種群中個體繁殖能力兩個部分，具體流程描述如下.

Stepl初始化參數(shù)：染色體種群大小測試種群大小&個體分割比例值達

Step2隨機生成測試種群;

Step3分別計算染色體種群中每個個體的繁殖能力;

Step4評判染色體種群中個體的繁殖能力;

Step5分割種群.對具有繁殖能力的個體進行排序，挑選前# X ^個個體，作為子代種群1，如果 數(shù)量不足，則根據(jù)普通個體的繁殖能力進行排序，挑選繁殖能力高的普通個體作為補充;剩余的個體 組合作為子代種群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自適應的交叉、變異算子

遺傳算法的參數(shù)中交叉概率和變異概率的選擇是影響遺傳算法行為和性能的關鍵所在，它們直 接影響算法的收斂性.交叉概率越大，新個體產生的速度就越快，然而過大的交叉概率可能會破壞原 本的個體基因結構，但過小的交叉概率會降低搜索性能.變異概率越小，越不容易生成新的基因結構， 而過大的變異概率可能會使得遺傳算法具有更強的隨機性，讓種群進化失去方向.

本文針對種群進化的不同階段，設計自適應的交叉、遺傳算子，使得交叉概率和變異概率能夠自 動改變.在前期產生的優(yōu)秀個體的質量較差，為了加快種群找到支配解的速度，故設置較大的交叉概 率Pc ，從而提高算法的全局搜索能力;在中后期已經產生部分優(yōu)秀解時，為了防止算法陷入局部最優(yōu)， 設置較大的變異概率Pm ，從而提高算法的全局搜索能力.

交叉概率范圍設置為（0.4， 0.8），變異概率范圍設置為（0.01， 0.（3），計算公式見式（11）、（12）.

其中：Pc （i）表示第t代的交叉概率;Pm （i）表示為第t代的變異概率;G為總迭代次數(shù);maxPc為最大 交叉概率值;minPc為最小交叉概率值;maxPm為最大變異概率值;minPm為最小變異概率值.

3.4 FEGA算法求解多目標優(yōu)化貨物配載模型

FEGA算法求解多目標優(yōu)化貨物配載模型流程圖見圖4.

操作步驟如下：

Stepl設置迭代次數(shù)、交叉變異概率等初始化參數(shù);

Step2利用貪心算法生成0.3N個個體，再隨機生成0.7N個個體，最后合并生成父代種群P* ;

Step3對當前的父代種群P*進行非支配排序，將個體分層，得到各級Pareto非支配層巧，

f2， · · · ，F(xiàn)n ;

Step4通過繁殖能力鑒定法拆分種群，得到繁殖種群1和普通種群2;

Step5對種群1和種群2分別采用不同的自適應交叉、變異算子操作，得到子代種群;

Step6利用精英策略對子代種群進行篩選，挑選出精英種群，剩余個體即為非精英種群;

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

Step8判斷迭代次數(shù)p是否小于等于設定的最大迭代次數(shù)，若是，則將p加1，然后跳轉至Step3 進行下一層迭代過程，否則結束種群迭代過程.

4?????? 實驗設置與結果分析

為驗證FEGA算法求解的有效性，使用京創(chuàng)智匯物流平臺提供的真實歷史數(shù)據(jù)對所提算法進行 性能測試，然后結合三個優(yōu)化目標驗證算法的實用性，同時對結果進行可視化.

部分實際可發(fā)庫存信息見表1，該數(shù)據(jù)取自京創(chuàng)智匯物流平臺庫存管理系統(tǒng)，主要包括品種名 稱、取貨倉庫、卸貨地址、貨物件數(shù)、貨物重量等數(shù)據(jù)項.實驗中一個批次的可發(fā)庫存數(shù)據(jù)共674條， 合計貨物13367條.

4.1參數(shù)設置

實驗在Windows10環(huán)境下運行，米用Python3.7語言編寫，在CPU為AMD Ryzen 7 4800U的處 理器和內存為16 GB RAM的機器上進行測試驗證.在該實驗中，參數(shù)設置如下：種群規(guī)模#= 100， 最大迭代次數(shù)G = 1000，交叉概率范圍（0.4， 0.8），變異概率范圍（0.01，0.3）.

4.2評價指標

（1）非支配解數(shù)量

非支配解的數(shù)量表示不被其他解占優(yōu)的解集合大小，其定義見下式（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實驗結果分析

本文選取目前多目標優(yōu)化中較為常用的NSGA-II和PSO算法進行對比實驗.首先通過對比多目 標算法的非支配解個數(shù)和HV指標值證明算法可行性，只有EGA、FEGA、NSGA-II算法利用多目標 優(yōu)化，所以通過NSGA-II算法來進行對比.同時，本文通過實際的應用場景對業(yè)務指標進行評估，實 際的業(yè)務指標轉化為本文提出的3個優(yōu)化目標.基礎算法選取GA來進行對比，此處的遺傳算法利用 單目標優(yōu)化問題求解，將3個優(yōu)化目標進行權重求和轉化為單個目標.最后對比GA、NSGA-II和本文 提出的兩個算法的收斂性，由此證明算法性能.

4.3.1算法可行性分析

利用5份不同的庫存數(shù)據(jù)進行實驗，并計算NSGA-II、EGA、FEGA這3種算法的非支配解平均 數(shù)量，其對比結果見圖5.

圖5中顯示最終EGA相對于NSGA-II的非支配解數(shù)量和相同，但達到收斂的速度優(yōu)于NSGA-II， 而FEGA無論是最終非支配解的數(shù)量還是達到收斂的速度都明顯優(yōu)于其他算法，表明FEGA在保持 高求解精度的同時還具有快速收斂的性能，具有很好的全局、局部搜索能力.

同時計算其HV指標值，對比結果見圖6.

從圖6中可看出EGA的收斂狀況來回波動，穩(wěn)定性較差，而FEGA的收斂狀態(tài)相對穩(wěn)定，且優(yōu) 于NSGA-II算法，通過設計混合貪心算法和隨機結構生成初始種群，極大地加快了種群的全局搜索能 力，同時自適應操作算子雙種群策略也使得FEGA在貨物配載過程中可以更快地收斂.

4.3.2 多個目標優(yōu)化結果對比

為了驗證快速收斂的精英遺傳算法（FEGA）對多目標貨物配載模型求解的有效性，將運行結果與 精英遺傳算法（EGA）、傳統(tǒng)的遺傳算法（GA）、快速非支配排序遺傳算法（NSGA-II）、粒子群算法 （PSO）的結果進行對比.對比結果見表2.

從表2可以看出：相對于傳統(tǒng)的遺傳算法，兩種算法都取得了較好的測試結果，但隨著問題規(guī)模 的增加，F(xiàn)EGA算法的最優(yōu)解在第一個目標上的結果明顯優(yōu)于其他算法，實際貨物配載場景中，第一 個目標的優(yōu)先級最高，第二個目標的優(yōu)先級次之，第三個目標的優(yōu)先級最低.故相較于基礎的遺傳算 法，本文提出的兩種算法都可以實現(xiàn)貨物配載的多目標優(yōu)化.

4.3.3 收斂性對比

由于第一個優(yōu)化目標的優(yōu)先級最高，所以通過多次實驗計算其對應目標函數(shù)值，進行比較，其對 比結果見圖7.

從圖7的收斂速度曲線對比分析可知，相比于其他算法，F(xiàn)EGA算法在采用雙種群進化策略之后， 不僅可以產生質量更高的最優(yōu)解，算法的收斂速度也明顯提升.EGA算法引入精英保留策略，相較于 普通的遺傳算法可以找到質量更好的解，同時其收斂速度比NSGA-II算法更快.驗證了 FEGA算法 能夠有效改善基礎遺傳算法的搜索性能和提升EGA算法的收斂性能.

5結束語

本文根據(jù)物流平臺需求建立貨物配載多目標優(yōu)化模型，對傳統(tǒng)遺傳算法的全局搜索能力與種群 收斂速度進行優(yōu)化，提出了帶精英策略和自適應算子的雙種群策略的改進遺傳算法——FEGA算法， 該算法在確保種群多樣性的同時，增加算法全局搜索能力，加快種群收斂速度.以真實的貨物數(shù)據(jù)集 驗證了算法求解多目標貨物配載過程的可行性和有效性，證明了該算法在強約束條件和龐大的搜索 空間的情況下可獲得最佳配載方案.

[參考文獻]

[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]覃亮，王志成.整車物流中轎運車裝載方案優(yōu)化研究[J].系統(tǒng)仿真學報，2015， 27（8）： 1868-1874.

[20]徐佳毅.建立整車物流裝運模型及最優(yōu)算法的應用研究[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]張程，賈寶柱，鄒佳奇.基于多目標遺傳算法的柴電混合動力船舶功率分配優(yōu)化[J].計算機應用與軟件，2021， 38（3）： 26-31.

[24]張聞強，邢征，楊衛(wèi)東.基于多區(qū)域采樣策略的混合粒子群優(yōu)化求解多目標柔性作業(yè)車間調度問題[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.

（責任編輯：林晶）