求解復雜耦合問題的多系統(tǒng)優(yōu)化方法

馬海平,朱 聰,母佳鑫,孫 超

(1.紹興文理學院電子工程系,浙江紹興 312000;2.成都理工大學信息科學與技術(shù)學院,四川成都 610059)

1 引言

國務院印發(fā)的《新一代人工智能發(fā)展規(guī)劃》中明確強調(diào)要圍繞新一輪產(chǎn)業(yè)變革的重大需求,應用人工智能提升產(chǎn)業(yè)發(fā)展,大力推進智能系統(tǒng)的集成應用.同時隨著工業(yè)系統(tǒng)的大規(guī)模集成,具有多系統(tǒng)、多目標、多約束、多尺度和不確定特征的復雜耦合問題也隨之大量涌現(xiàn),這對相關(guān)領(lǐng)域的傳統(tǒng)研究方法提出了挑戰(zhàn).目前針對工業(yè)系統(tǒng)中復雜耦合問題的研究已取得很多成果,但仍存在少部分子系統(tǒng)與子系統(tǒng),或環(huán)節(jié)與環(huán)節(jié)之間信息交互與反饋關(guān)系不明確,從而難以保證整個問題的全局最優(yōu).因此在當今國際競爭激烈與國家重大戰(zhàn)略需求環(huán)境下,迫切需要尋求更好地求解此類問題的方法和策略,實現(xiàn)局部與整體、短期與長遠、效益與安全和環(huán)境影響之間的全局優(yōu)化,為實現(xiàn)我國智能工業(yè)打下堅實的基礎[1–4].毫無疑問解決產(chǎn)業(yè)變革中的復雜耦合問題具有非常重大的現(xiàn)實意義和廣泛的應用前景,已成為相關(guān)學科的研究熱點和重要研究方向.

2 復雜耦合問題

本文中的復雜耦合問題,主要指的是復雜耦合系統(tǒng)中的優(yōu)化問題,其往往由多個不同功能的子系統(tǒng)耦合而成,每個子系統(tǒng)又包含多個目標和多個約束,同時各子系統(tǒng)之間存在不同程度的交互,比如部分目標相同或變量共享等,其數(shù)學模型描述為

式中:Fi為第i個子系統(tǒng),K為子系統(tǒng)個數(shù),為所有子系統(tǒng)第j個共同目標函數(shù),M0為共同目標函數(shù)個數(shù),fik為第i個子系統(tǒng)中的第k個私有目標函數(shù),Mi為私有目標函數(shù)個數(shù);為所有子系統(tǒng)第j個共同約束方程,q0為共同約束方程個數(shù),gik為第i個子系統(tǒng)中的第k個私有約束方程,qi為私有約束方程個數(shù);為所有子系統(tǒng)共享決策變量,x為私有決策變量.從式(1)可以看到,該模型是對復雜耦合問題中多個子系統(tǒng)的整體優(yōu)化.

此類復雜耦合問題具有兩個顯著特點:一方面,其涉及不同功能的多個子系統(tǒng),各子系統(tǒng)緊密耦合且耦合關(guān)系復雜;另一方面,子系統(tǒng)內(nèi)部的目標和約束相互沖突,難以調(diào)和.因此,不能簡單地將復雜耦合問題看成一類傳統(tǒng)的單目標優(yōu)化問題或多目標優(yōu)化問題,前者只涉及一個目標函數(shù)的優(yōu)化,后者涉及兩個或以上相互沖突目標函數(shù)的優(yōu)化.復雜耦合問題包含多個優(yōu)化子系統(tǒng),每個子系統(tǒng)又類似于傳統(tǒng)意義上的多目標優(yōu)化問題,也就是說,復雜耦合問題是多個多目標優(yōu)化問題的集成,這里將其稱之為多系統(tǒng)優(yōu)化問題.但是必須指出,這樣的案例實際上大量存在于產(chǎn)業(yè)變革的各個方面,比如在云計算環(huán)境下,基于多客戶按需服務的多級供應鏈網(wǎng)絡就是一個典型的多系統(tǒng)優(yōu)化問題,包括用于生產(chǎn)制造的多目標車間作業(yè)調(diào)度子系統(tǒng)、用于產(chǎn)品儲存的多目標分配子系統(tǒng)和用于產(chǎn)品派發(fā)的多目標旅行商子系統(tǒng)[5–7].該案例的求解任務就是整體優(yōu)化供應鏈網(wǎng)絡,以期獲得各級網(wǎng)絡的最優(yōu)解.

當前,針對復雜耦合問題優(yōu)化的研究已有一些相似的文獻發(fā)表[8–9].國外學者Martins等[10]較早研究了多學科耦合系統(tǒng)的設計問題,提出了多學科設計優(yōu)化(multidisciplinary design optimization,MDO)方法,其主要思想是考慮各學科之間的協(xié)同效應,應用有效的優(yōu)化框架來組織和管理整個系統(tǒng)的求解過程,該方法本質(zhì)上只是一個設計框架,沒有涉及具體的優(yōu)化機制和實現(xiàn)過程.對于復雜耦合問題,更多的研究者則從設計層面將其轉(zhuǎn)化為多目標優(yōu)化特別是眾目標優(yōu)化(many-objective optimization,MOO)問題[11],然后在此基礎上進行傳統(tǒng)的優(yōu)化求解.張青富等[12]提出一種基于分解的高效計算框架,將一個多目標優(yōu)化問題分解成一系列單目標優(yōu)化子問題,然后融合相鄰子問題的信息加速求解各子問題.C.A.Coello 等[13]提出了協(xié)同進化優(yōu)化方法,運用生物協(xié)同演化的思想和分而自治的策略,通過構(gòu)造多個種群,建立它們之間的競爭或合作關(guān)系來模擬復雜系統(tǒng)的演化環(huán)境,以達到整體優(yōu)化的目的.Y.S.Ong等[14–15]針對多個任務的求解提出了多因子優(yōu)化(multiobjective multifactorial EA,MO–MFEA)方法,其基本思想是將多個不同任務的解空間統(tǒng)一到一個擴展的解空間中,經(jīng)過進化操作后,針對不同任務再將統(tǒng)一表示的解集解碼到各任務原來的解空間中,從而達到同步優(yōu)化多個任務的目的,數(shù)值仿真結(jié)果表明該方法在求解多任務問題上具有很好的性能.

綜合分析,求解復雜耦合問題無疑是智能優(yōu)化方法設計和應用的重要研究方向,非常有必要對其進一步的探索.本文從求解復雜耦合問題出發(fā),借鑒多種群進化算法的智能平行特征,利用種群間進化信息的繼承和交互作用,提出多系統(tǒng)優(yōu)化(multi-system optimization,MSO)方法,同時通過基準函數(shù)驗證了新方法的高效性和優(yōu)越性.進一步根據(jù)供應鏈理論和實際需求,建立基于多客戶按需服務的三級供應鏈網(wǎng)絡,并將所提出的MSO方法應用到該網(wǎng)絡中,仿真結(jié)果表明所提出的方法具有很好的優(yōu)化性能.

3 多系統(tǒng)優(yōu)化方法

MSO方法的設計原理是借鑒多種群進化算法的智能平行特征,將一個子系統(tǒng)的優(yōu)化環(huán)境用一個子種群來表示,每個子系統(tǒng)通過優(yōu)秀的進化算子求解一類多目標優(yōu)化問題,子系統(tǒng)之間則通過變量共享、目標函數(shù)和約束條件的相似程度來實現(xiàn)信息遷移與反饋,完成不同子系統(tǒng)內(nèi)部多個目標的同步優(yōu)化,從而得到各子系統(tǒng)的全局最優(yōu).其基本思想是根據(jù)進化信息的繼承性和優(yōu)化環(huán)境的關(guān)聯(lián)性,在一個子系統(tǒng)內(nèi)部產(chǎn)生的優(yōu)秀解集大概率對其他子系統(tǒng)的優(yōu)化有很大的正向幫助和啟發(fā),從而能夠加速子系統(tǒng)全局尋優(yōu).基于所述設計原理和思想,一種用于求解復雜耦合問題的MSO方法框架如圖1所示,主要包括子系統(tǒng)內(nèi)部的進化操作和子系統(tǒng)之間的遷移操作,接下去詳細闡述各自的實現(xiàn)過程.

圖1 多系統(tǒng)優(yōu)化方法框架Fig.1 The framework of MSO method

3.1 子系統(tǒng)內(nèi)的進化操作

對于子系統(tǒng)內(nèi)的進化操作,采用常規(guī)的遺傳算子,主要包括選擇、交叉和變異.其中選擇算子采用輪盤賭選擇法,其概率的分布與候選解集的秩成正比關(guān)系,反映了子系統(tǒng)中不同候選解所對應的相對性能.在多目標優(yōu)化領(lǐng)域,一般采用經(jīng)典的非支配排序法來計算候選解集的秩[16].考慮本文提到的復雜耦合問題存在大量約束條件,且在實際問題中,這些約束條件尤為重要,因此有必要在候選解集排序過程中優(yōu)先考慮約束影響.結(jié)合適應度值,修改后候選解集的秩計算如下:首先計算每個候選解的約束沖突數(shù),然后對約束沖突數(shù)進行非支配排序,當候選解的約束沖突數(shù)相等時,則進一步對其按常規(guī)的適應度值進行非支配排序.接下去執(zhí)行交叉,可以選擇均勻交叉、多點交叉等,目的是通過替換或重組生成新的解集.最后執(zhí)行變異,根據(jù)概率隨機修改候選解中的決策變量,增加子種群中解集的多樣性.需要說明的是,子系統(tǒng)內(nèi)的進化操作是一個相對獨立的演化過程,完全可以采用其他更優(yōu)秀的進化算子或群體智能算子來提高優(yōu)化性能.

3.2 子系統(tǒng)間的遷移操作

子系統(tǒng)間的遷移操作是MSO方法的關(guān)鍵技術(shù),其通過變量共享關(guān)系、目標函數(shù)和約束條件的相似程度來實現(xiàn)不同子系統(tǒng)之間信息的遷移和反饋.整個遷移操作歸納為3步:第1步選擇需要遷移的子系統(tǒng)對,第2步在該子系統(tǒng)對內(nèi)選擇需要遷移的候選解,第3步完成它們之間的遷移.

首先根據(jù)不同子系統(tǒng)目標值和約束值的相似程度匹配子系統(tǒng)對,也就是說,使用相似程度來決定與遷入子系統(tǒng)構(gòu)成遷移關(guān)系的遷出子系統(tǒng).根據(jù)優(yōu)化環(huán)境的關(guān)聯(lián)性,具有高相似度的子系統(tǒng)對比具有低相似度的子系統(tǒng)對更有可能通過遷移操作而相互受益.不同子系統(tǒng)之間的相似系數(shù)SL的計算如算法1所示,其中G和H表示不同子系統(tǒng)內(nèi)目標函數(shù)值或約束值的集合.算法1的目的是在不同子系統(tǒng)集合中,通過比較找到目標函數(shù)值或約束值相同的個數(shù),SL值越大,子系統(tǒng)間相似程度越高.

算法1子系統(tǒng)間相似系數(shù)的計算.

然后在已獲得的相似系數(shù)基礎上,計算選擇遷出子系統(tǒng)的概率,公式如下:

式中:Pmigration為遷出子系統(tǒng)的選擇概率,其值越大,被選擇作為遷出子系統(tǒng)的可能性越大;SL1,SL2,SL1,max和SL2,max分別為不同子系統(tǒng)之間目標值相似系數(shù)、約束值相似系數(shù)、最大目標值相似系數(shù)和最大約束值相似系數(shù).遷出子系統(tǒng)的選擇過程如算法2所示.

算法2遷出子系統(tǒng)的選擇.

進一步在已確定遷出子系統(tǒng)基礎上選擇遷出候選解.本文采用候選解之間的歐氏距離計算遷出候選解的選擇概率,然后基于該概率使用輪盤賭法選擇遷出對象,過程如圖2所示,圖中D為根據(jù)歐氏距離計算得到的選擇概率.這是因為解集間的歐氏距離越大,其種群多樣性就越高,從而為找到最優(yōu)解提供更多可能性.

圖2 基于輪盤賭法的遷出解選擇Fig.2 Emigrating solution selection based on roulette wheel method

在復雜耦合問題中,由于不同子系統(tǒng)通常具有不同的候選解結(jié)構(gòu),即決策變量存在不同程度的共享,因此在計算歐氏距離前,解的結(jié)構(gòu)需要一致,以表1中的兩個子系統(tǒng)為例,子系統(tǒng)1缺失變量3,子系統(tǒng)2缺失變量2和4.

表1 不同子系統(tǒng)中的候選解結(jié)構(gòu)Table 1 Candidate solution structures in different subsystems

首先要求每個候選解應包含整個問題的所有變量,如果某一子系統(tǒng)中的某一變量不存在,用N/A表示該缺失數(shù)據(jù).然后重新定義歐氏距離計算公式為

式中:xik和xjl分別為第i和j個子系統(tǒng)中的第k和l個候選解,?ikjl為它們之間的距離;n和s分別為候選解長度和決策變量序號.

最后,在確定遷出子系統(tǒng)中的遷出候選解后,執(zhí)行遷移算子,定義為

兩個子系統(tǒng)間的遷移過程如算法3所示.可以看到,遷入候選解的每個決策變量都有可能被其他子系統(tǒng)中的決策變量所替換.整個子系統(tǒng)間遷移操作的優(yōu)點在于其考慮了一般智能優(yōu)化方法的共性核心問題—探索與開發(fā)的權(quán)衡問題,即通過目標值和約束值的相似程度來促進不同子系統(tǒng)的快速尋優(yōu),通過解集距離來提高子系統(tǒng)的多樣性.

算法3子系統(tǒng)間的遷移.

3.3 方法流程

基于上述設計原理,給出MSO方法的實現(xiàn)步驟,描述如下:

步驟1初始化控制參數(shù):設定子系統(tǒng)數(shù)K及對應的子種群大小Ni、交叉概率pc、變異概率pm、遷移閾值概率pv、精英E0以及最大迭代次數(shù)T;

步驟2初始化每個子系統(tǒng),即隨機產(chǎn)生相應的候選解集;

步驟3對每個子系統(tǒng),根據(jù)非支配排序法計算每個候選解的秩并按比例計算選擇概率,然后按第2.1節(jié)所述,依概率執(zhí)行子系統(tǒng)內(nèi)的進化操作,包括選擇、交叉和變異,或直接移植NSGA–II作為子系統(tǒng)內(nèi)進化操作的主體;

步驟4基于算法1和式(2)計算不同子系統(tǒng)間目標值和約束值相似系數(shù)SL及遷出子系統(tǒng)的選擇概率Pmigration,并基于算法2依概率選擇需要遷移的子系統(tǒng)對;然后,基于式(3)計算該子系統(tǒng)對內(nèi)部候選解之間的歐氏距離σ,根據(jù)圖2計算遷出候選解的選擇概率D,并使用輪盤賭法選擇需要遷移的候選解;最后,按照算法3完成不同子系統(tǒng)候選解之間的遷移,即根據(jù)閾值概率pv判斷是否用遷出候選解的決策變量替換遷入候選解對應位置的決策變量,整個子系統(tǒng)間遷移過程的具體執(zhí)行細節(jié)參考第2.2節(jié)所述.

步驟5保存每個子系統(tǒng)中的最佳解作為精英,并用上一代的精英替代當代中的最差解;

步驟6如果滿足停止準則或最大迭代次數(shù)T,輸出結(jié)果并停止運算;否者,回到步驟3進行下一次迭代,算法4給出MSO方法其中一代的實現(xiàn)過程.

算法4MSO方法其中一代實現(xiàn)過程.

3.4 理論分析

接下去考慮MSO方法的收斂性,根據(jù)其設計原理和實現(xiàn)過程,參考文獻[17]中多種群多目標進化優(yōu)化算法的馬爾科夫鏈模型推導過程,由于兩者之間的運行機理基本相同而面向?qū)ο蟛煌?可以直接得到第i個子系統(tǒng)從種群分布v轉(zhuǎn)移到種群分布u的狀態(tài)轉(zhuǎn)移概率Pi(u|v)為

式中Ni和ni分別為第i個子系統(tǒng)的種群大小及候選解長度,其中

式中P(1),P(2)和U分別為進化(選擇和交叉)、遷移和變異的轉(zhuǎn)移概率,其下標依次為子系統(tǒng)、候選解和決策變量序號.進一步,由于式(6)的結(jié)構(gòu)與文獻[18]中的式(11)相同,可以用相同的定理和步驟證明所提出的方法在精英策略下必然收斂.

3.5 方法特點

MSO方法與其他智能優(yōu)化方法一樣,是一種模擬自然現(xiàn)象規(guī)律和生物進化機制的優(yōu)化方法.但是又與其他方法有本質(zhì)的區(qū)別.首先MSO方法與第1節(jié)中提到的眾目標優(yōu)化方法比較,區(qū)別在于:1)概念不同,已有方法屬于多目標優(yōu)化,本文所提方法屬于多系統(tǒng)優(yōu)化;2)機理不同,已有方法需要對多目標或決策變量進行分解或轉(zhuǎn)換,策略的選擇影響優(yōu)化性能,本文所提方法對復雜耦合問題的優(yōu)化是一種自然行為,即無需先驗知識,根據(jù)問題建立子系統(tǒng),不再需要考慮目標函數(shù)或決策變量的處理策略.接著MSO方法與協(xié)同進化優(yōu)化方法比較,它們的共同點都是運用多個種群來模擬演化環(huán)境,其區(qū)別在于協(xié)同進化優(yōu)化方法是通過競爭或合作關(guān)系來實現(xiàn)單個目標或多個目標的優(yōu)化,而MSO方法是通過遷移算子來實現(xiàn)多個子系統(tǒng)的優(yōu)化.最后MSO方法與MO–MFEA比較,它們的共同點都是用于優(yōu)化多系統(tǒng)問題,擴大了智能優(yōu)化方法的應用范疇;其區(qū)別在于MO–MFEA需要對子系統(tǒng)的解空間進行統(tǒng)一編碼及目標函數(shù)標量化,并在統(tǒng)一的表示空間內(nèi)進行知識的遷移,MSO方法是通過信息反饋機制,即目標值和約束值的相似程度與解集歐氏距離的折中來實現(xiàn)不同子系統(tǒng)間決策變量的遷移,其演化過程是一種自組織和自學習的動態(tài)協(xié)調(diào)過程.總的來說,MSO方法對各子系統(tǒng)的求解是平行同步優(yōu)化的,根據(jù)問題的耦合性和進化信息的關(guān)聯(lián)性,在一個子系統(tǒng)內(nèi)部產(chǎn)生的優(yōu)秀解集,很大程度上也會對其他子系統(tǒng)產(chǎn)生積極的優(yōu)化效果,因此通過子系統(tǒng)間的遷移,能夠加速各子系統(tǒng)的全局優(yōu)化,從而減少所需的迭代次數(shù),縮短計算時間.

4 實驗仿真

為了驗證所提的MSO方法的有效性,本節(jié)采用文獻[19]中的9個基準函數(shù)(見表2)進行仿真實驗,并分別與文獻[16]中的NSGA–II,文獻[12]中的MOEA/D和文獻[14–15]中的MO–MFEA進行比較,選擇這3種算法的原因是前兩者是經(jīng)典的多目標優(yōu)化方法,后者是目前為數(shù)不多且求解多任務性能最好的多因子優(yōu)化方法.對于表2中的基準函數(shù),其由2個子系統(tǒng)構(gòu)成,每個子系統(tǒng)包含2到3個目標函數(shù).這些基準函數(shù)是根據(jù)目標值的相似程度和決策變量的共享程度建立的,其中相似程度分為高(HS)、中(MS)和低(LS),用Sim(T1,T2)來表示子系統(tǒng)T1和T2的相似概率,共享程度分為完全(CI)、部分(PI)和不共享(NI),由此組合構(gòu)成9個測試函數(shù),這里相似程度和共享程度的分類依據(jù)參考文獻[19].

表2 多系統(tǒng)(任務)基準函數(shù)集Table 2 Multi-system(task)benchmark function sets

便于比較的合理性和公正性,通過多次試驗將算法相關(guān)參數(shù)調(diào)節(jié)到相對最優(yōu)來獲得合適的性能.對于本文提出的MSO方法,由于其是對基準函數(shù)兩個子系統(tǒng)同步優(yōu)化,設置子系統(tǒng)數(shù)K=2,每個子種群大小為Ni=100,模擬二進制交叉及pc=1,多項式變異及pm=1,遷移閾值概率pv=1,精英E0=2.對于NSGA–II和MOEA/D,因為兩者均為多目標優(yōu)化算法,因此需要對基準函數(shù)中兩個子系統(tǒng)單獨優(yōu)化,每次優(yōu)化的種群大小為N=100,其他參數(shù)設置參照MSO方法,另外MOEA/D的分解方式采用邊界交叉聚合方法.對于MO–MFEA,由于其整體求解K個子系統(tǒng),種群大小設置為K·Ni=200,另外其框架是以NSGA–II為基礎,因此其他參數(shù)設置與NSGA–II相同.所有方法最大迭代次數(shù)均為1000,算法獨立運行30次,用IGD作為性能衡量指標,其值越小表示性能越好,計算過程參考文獻[19],優(yōu)化結(jié)果(IGD平均值和方差)見表3.

表3的結(jié)果分兩部分討論:

首先,考慮目標值相似程度對性能的影響,將CIHS,PIHS 和NIHS 作為高相似組(HS 組);CIMS,PIMS 和NIMS 作為中相似組(MS組);CILS,PILS和NILS作為低相似組(LS組).由表可知,對于HS組和MS組,本文所提的MSO方法的性能均優(yōu)于NSGA–II,MOEA/D和MO–MFEA,對于LS 組,MSO 方法優(yōu)于NSGA–II和MOEA/D,但在函數(shù)CILS和NILS上,劣于MO–MFEA,這表明目標值相似程度對MSO方法的優(yōu)化性能有很大的影響,基于相似程度來實現(xiàn)子系統(tǒng)間遷移是構(gòu)建MSO方法的一個重要因子.

其次,考慮決策變量共享程度對性能的影響,將CIHS,CIMS 和CILS 作為完全共享組(CI組);PIHS,PIMS和PILS作為部分共享組(PI組);NIHS,NIMS和NILS作為不共享組(NI組).由表可知,對于CI組和NI組,本文所提的MSO方法的性能均優(yōu)于NSGA–II和MOEA/D,但在部分函數(shù)上則劣于MO–MFEA,對于PI組,MSO方法的性能均優(yōu)于NSGA–II,MOEA/D和MO–MFEA,這表明決策變量的共享程度對MSO的優(yōu)化性能也有一定的影響,但規(guī)律不是很明顯,基于共享程度來實現(xiàn)子系統(tǒng)間遷移是構(gòu)建MSO方法的另外一個重要因子.

表3 不同優(yōu)化方法的測試結(jié)果比較Table 3 Result comparisons for different optimization methods

綜合以上兩部分討論,可以得到MSO方法在相似度高和中的基準函數(shù)上比其他方法更具有優(yōu)勢,這也體現(xiàn)了所提方法充分考慮進化信息的繼承性和優(yōu)化環(huán)境的關(guān)聯(lián)性,子系統(tǒng)間的遷移能夠有效利用這些信息加速全局尋優(yōu).

圖3 給出了基準函數(shù)的Pareto 前沿,以及MSO,NSGA–II,MOEA/D和MO–MFEA在這些函數(shù)上的實驗結(jié)果,從圖中可以看到,本文所提的MSO方法在大多數(shù)函數(shù)上能夠接近于理想的Pareto前沿.

圖3 不同優(yōu)化方法在基準函數(shù)上的實驗結(jié)果圖Fig.3 Experimental results of different optimization methods on benchmark functions

5 案例分析

5.1 問題描述

圖4為基于多客戶按需服務的三級供應鏈網(wǎng)絡,圖中制造商A1–AM用于生產(chǎn)不同類型的產(chǎn)品,并將產(chǎn)品運輸?shù)讲煌瑓^(qū)域的配送中心C1–CN,然后根據(jù)客戶需求調(diào)用車輛,形成送貨路徑,并派發(fā)至不同客戶B1–BL中.從優(yōu)化的角度分析,該三級供應鏈網(wǎng)絡包括:用于生產(chǎn)制造的多目標車間作業(yè)調(diào)度子系統(tǒng)、用于產(chǎn)品儲存的多目標分配子系統(tǒng)和用于產(chǎn)品派發(fā)的多目標旅行商子系統(tǒng),整個供應鏈網(wǎng)絡構(gòu)成一個集中決策的多系統(tǒng)優(yōu)化問題,通過集成優(yōu)化使得供應鏈每個子系統(tǒng)的各自效益達到最優(yōu),以適應市場競爭.

圖4 基于多客戶按需服務的三級供應鏈網(wǎng)絡Fig.4 Three-echelon supply chain network based on multi-customer on-demand service

5.2 數(shù)學模型

1)對于用于生產(chǎn)制造的多目標作業(yè)車間調(diào)度子系統(tǒng),可描述為:存在M個并行獨立制造商,每個制造商加工r類產(chǎn)品,每類產(chǎn)品有m道工序,分別在m臺機器上加工,產(chǎn)品j在機器k上的加工時間固定,不考慮產(chǎn)品加工的優(yōu)先權(quán),同一時刻最多只有一個產(chǎn)品在一臺機器上加工,且加工過程不會間斷,機器間緩沖區(qū)容量為無限.設Tij為制造商i中產(chǎn)品j的完工時間,為制造商i中產(chǎn)品j在機器k上的加工費用,所考慮的目標包括最小化子系統(tǒng)內(nèi)所有產(chǎn)品的最大完工時間和產(chǎn)品的加工總成本,其基本數(shù)學模型可描述為

其中每個子目標數(shù)學描述如下:

其中:式(12)表示每個制造商中每道工序被加工且只被某臺機器加工一次;式(13)表示所有工序的完成時間均為非負值.

2)對于用于產(chǎn)品儲存的多目標分配子系統(tǒng),可描述為:制造商完成不同產(chǎn)品的加工后,需運輸?shù)轿挥诓煌瑓^(qū)域的配送中心,制造商i運往配送中心h的產(chǎn)品種類為cih,對應的運費為,運輸流量為wih,所考慮的目標為最小化子系統(tǒng)所有產(chǎn)品的運輸總成本和總流量,其基本數(shù)學模型可描述為

其中每個子目標數(shù)學描述如下:

a)子系統(tǒng)內(nèi)所有產(chǎn)品的運輸總成本

b)子系統(tǒng)內(nèi)所有產(chǎn)品的運輸總流量

該子系統(tǒng)的約束條件為

其中:式(17)表示每個制造商加工的產(chǎn)品種類均為r;式(18)表示每個配送中心的運輸量均為非負值.

3)對于用于產(chǎn)品派發(fā)的多目標旅行商子系統(tǒng),可描述為:產(chǎn)品到達不同配送中心后,需要繼續(xù)將其派發(fā)給不同客戶,車輛從配送中心h出發(fā)遍歷Lh個客戶后返回到各自所屬配送中心(可以看為第Lh+1個客戶),設從客戶p到客戶q的距離為dhpq,費用為,所考慮的目標為最小化子系統(tǒng)內(nèi)所有產(chǎn)品的派發(fā)總路程和總成本,其基本數(shù)學模型可描述為

其中每個子目標數(shù)學描述如下:

a)子系統(tǒng)內(nèi)所有產(chǎn)品的派發(fā)總路程

b)子系統(tǒng)內(nèi)所有產(chǎn)品的派發(fā)總成本

該子系統(tǒng)的約束條件為

式(22)表示每個配送中心將不同制造商運輸過來的所有產(chǎn)品分別派發(fā)給Lh個客戶.

5.3 仿真結(jié)果

采用本文提出的MSO方法求解上述三級供應鏈網(wǎng)絡優(yōu)化問題.整個供應鏈網(wǎng)絡的參數(shù)設置如下:制造商M=5,產(chǎn)品種類r=10,工序m=10,配送中心N=5,客戶Lh=9,其他相關(guān)數(shù)據(jù)分別來自JSPLIB[20],QAPLIB[21],TSPLIB[22]數(shù)據(jù)庫;另外系統(tǒng)所涉及的加工費用S1、運輸費用S2和派送費用S3服從[1,10]的均勻分布.為了驗證所提方法的有效性,同樣與NSGA–II,MOEA/D 和MO–MFEA 進行比較,對于MSO 方法,根據(jù)供應鏈網(wǎng)絡子系統(tǒng)數(shù),設置子種群數(shù)為3,每個子種群的大小為100,對于NSGA–II和MOEA/D,每個子系統(tǒng)單獨運行,每次優(yōu)化的種群大小為100,對于MO–MFEA,種群大小設置為300,所有方法的其他參數(shù)與上一節(jié)實驗仿真中的設置相同,表4給出了作業(yè)調(diào)度子系統(tǒng)、分配子系統(tǒng)和旅行商子系統(tǒng)的仿真結(jié)果,其數(shù)值越小表示性能越好.

表4 不同優(yōu)化方法在供應鏈網(wǎng)絡優(yōu)化問題上的結(jié)果比較Table 4 Result comparisons of different optimization methods for supply chain network

從表4中可以觀察到,本文提出的MSO方法在求解三級供應鏈網(wǎng)絡優(yōu)化問題上,對于其中的車間作業(yè)調(diào)度子系統(tǒng),其性能略優(yōu)于NSGA–II和MOEA/D,與MO–MFEA基本相同,這是因為車間作業(yè)調(diào)度子系統(tǒng)模型跟其它兩個子系統(tǒng)模型相比,交互較少,可以看作為一個相對獨立的多目標優(yōu)化問題,這對于本文提出的MSO方法而言,難以發(fā)揮子系統(tǒng)之間的遷移操作優(yōu)勢,在這種情況下,其退化為改進版的NSGA–II,因此MSO方法在該子系統(tǒng)上難以呈現(xiàn)出性能優(yōu)勢.而對于分配子系統(tǒng)和旅行商子系統(tǒng),MSO方法的性能要遠好于NSGA–II和MOEA/D,略優(yōu)于MO–MFEA,這是因為這兩個子系統(tǒng)與車間作業(yè)調(diào)度子系統(tǒng)相比,其模型表達式和約束更為相似,變量之間的關(guān)聯(lián)也更為密切,因此本文提出的MSO方法在不需要先驗信息的情況下,能夠通過其自身的優(yōu)化機理求解問題,并呈現(xiàn)出好的優(yōu)化潛力.

6 結(jié)論

人工智能的快速發(fā)展引發(fā)了新一輪產(chǎn)業(yè)升級和變革,同時也涌現(xiàn)出大量具有多系統(tǒng)多目標特點的復雜耦合問題.為解決這些優(yōu)化問題,本文提出了一種MSO新方法,其借鑒多種群進化算法的智能平行特征,利用在一個子系統(tǒng)內(nèi)部產(chǎn)生的優(yōu)秀解集通過遷移來幫助和啟發(fā)其他子系統(tǒng)的進化,從而加速整個問題的全局優(yōu)化.同時,為測試新方法的可行性和有效性,將該方法應用到基準函數(shù)和具有多系統(tǒng)優(yōu)化特征的三級供應鏈網(wǎng)絡,仿真實驗結(jié)果表明新方法在基準函數(shù)和應用問題上均具有很好的整體優(yōu)化能力,為解決其他復雜耦合優(yōu)化問題提供了新的思路和較強的參考意義.未來的研究方向一方面從剖析復雜耦合問題內(nèi)在關(guān)系,考慮不同子系統(tǒng)間的異質(zhì)結(jié)構(gòu)和求解策略,來建立更準確的多系統(tǒng)優(yōu)化模型;另一方面在目前的MSO方法框架下,根據(jù)問題支撐條件改進算子結(jié)構(gòu)提高優(yōu)化性能,并力圖求解產(chǎn)業(yè)變革中所涉及的各類復雜耦合問題.