1550
1
0
2023-05-06 19:42:21
2023-05-06
孟子曰：“魚,，我所欲也,；熊掌,，亦我所欲也,。二者不可得兼,，舍魚而取熊掌者也,。”在實際生產(chǎn)生活中,，人們往往更希望魚與熊掌兼得,。例如,，人們希望在降低服裝購買成本的情況下使其舒適度最大化,，或者希望在減少車輛能耗和污染物排放的情況下使車輛性能最優(yōu)化,。
圖1 生活中的多目標(biāo)組合優(yōu)化問題
一、錯綜復(fù)雜：多目標(biāo)組合優(yōu)化問題
多目標(biāo)組合優(yōu)化問題（Multiobjective Combinatorial Optimization Problem, MOCOP）是涉及多個目標(biāo)函數(shù)同時優(yōu)化的數(shù)學(xué)問題[2],，需要權(quán)衡兩個或多個相互沖突的目標(biāo),，進(jìn)而做出最優(yōu)決策。目前,，該問題已被應(yīng)用于工程,、經(jīng)濟(jì)、物流等多個領(lǐng)域,。MOCOP的基本數(shù)學(xué)模型如公式(1)所示,。
當(dāng)多目標(biāo)組合優(yōu)化問題的解在目標(biāo)空間分布的距離與決策空間分布的距離呈非正相關(guān)關(guān)系時，現(xiàn)有算力分配方法的求解性能會變差[3-6],。這將導(dǎo)致相鄰目標(biāo)向量所對應(yīng)的決策向量差異性大,。例如，圖2中Y1和Y2是兩個相鄰的目標(biāo)向量,，X1和X2是決策空間中對應(yīng)的兩個解,。如果X1和X2所屬的決策空間不相鄰，那么從一個子問題的解轉(zhuǎn)移到其相鄰子問題的解是十分困難的,。這導(dǎo)致現(xiàn)有的基于分解算法的算力分配方法在求解MOCOPs時的性能會變差,。
圖2 目標(biāo)空間的距離與決策空間的距離非正相關(guān)示例
如何選擇子問題并合理分配有限的算力是提升基于分解算法求解MOCOPs性能的關(guān)鍵之一。因此,，針對背包與二次分配多目標(biāo)組合優(yōu)化問題存在的相鄰目標(biāo)向量所對應(yīng)的決策向量差異程度大這一問題,，智能算法研究中心的研究人員提出基于稀疏目標(biāo)子區(qū)域微搜索的多目標(biāo)組合優(yōu)化算法（Local-diversity Evaluation Assignment Strategy for Decomposition-based Multiobjective Evolutionary Algorithm, MOEA/D-LdEA）[1]。MOEA/D-LdEA通過劃分目標(biāo)空間獲得微小的多目標(biāo)子區(qū)域,，使算法能夠在多目標(biāo)組合優(yōu)化問題的大規(guī)模搜索空間中找到有效決策子集,，并依據(jù)多目標(biāo)子區(qū)域的稀疏度動態(tài)分配算力，在不同的子區(qū)域進(jìn)行定向搜索,，節(jié)省了計算代價,，最終獲得多目標(biāo)組合優(yōu)化問題的高質(zhì)量解集。目前,，該研究工作已發(fā)表在國際頂級期刊IEEE Transactions on Systems, Man, and Cybernetics: Systems（JCR一區(qū),，影響因子11.471）。
MOEA/D-LdEA算法的流程如圖3所示,。該算法主要包括兩部分：微小搜索子區(qū)域的稀疏度評估模型和有效決策子集的算力分配策略LdEA,。
圖3 MOEA/D-LdEA算法流程圖
二、排沙簡金：微小搜索子區(qū)域的稀疏度評估模型
微小搜索子區(qū)域是通過在多目標(biāo)優(yōu)化問題中使用分解算法來確定的,。分解算法將多目標(biāo)問題分解為一組單目標(biāo)子問題,，每個子問題都是在不同權(quán)重向量下的優(yōu)化目標(biāo)函數(shù)。因此,，搜索空間的規(guī)模僅限于每個單目標(biāo)問題的權(quán)重向量,，而不是整個多目標(biāo)問題的搜索空間,。算法將在微小范圍內(nèi)進(jìn)行定向搜索，這樣極大地減少了計算成本,，節(jié)省了算力,。
微小搜索子區(qū)域的稀疏度評估模型主要用于估計每個目標(biāo)子區(qū)域的局部密度。首先,，假定目標(biāo)空間被劃分為K個目標(biāo)子區(qū)域,，其中，可以被定義為：
圖4 微小搜索子區(qū)域的稀疏度評估模型對目標(biāo)空間的劃分
當(dāng)目標(biāo)空間被劃分為多個子區(qū)域后,，由于每個解與一個目標(biāo)子區(qū)域相關(guān)聯(lián),，因此可以通過采用公式(3)計算與目標(biāo)子區(qū)域相連的解的個數(shù)來估計目標(biāo)子區(qū)域的局部密度：
其中， 表示在種群C中由得到適應(yīng)值評估的第j個子問題所生成的解的數(shù)量,，其中C包含e(e ≤ N)個在各個目標(biāo)均不相等時適應(yīng)度值的解,。
圖5 目標(biāo)空間中不同稀疏度的子區(qū)域
如公式(4)所示,，當(dāng)局部密度值與所選目標(biāo)子區(qū)域的概率成反比,，即目標(biāo)子區(qū)域稀疏度越高，則目標(biāo)子區(qū)域被選擇的概率越大,。被選中的目標(biāo)子區(qū)域即為該微搜索過程的有效決策子集,。
最后，可以根據(jù)目標(biāo)子區(qū)域的稀疏度,，采用公式(5)計算被選定目標(biāo)子區(qū)域的概率,，即：
因為搜索算法傾向于更頻繁地探索多樣性更強(qiáng)的區(qū)域，所以搜索算法的效率取決于搜索空間不同部分之間的差異程度,。因此,，我們提出有效決策子集的算力分配策略LdEA，將算力分配給具有較低目標(biāo)函數(shù)值和較高多樣性的個體,，實現(xiàn)算力的相對均勻分配,，從而減少不必要的算力消耗，節(jié)省計算成本,。
當(dāng)MOCOPs的解滿足目標(biāo)空間距離與決策空間距離呈非正相關(guān)的前提時,，在有效決策子集中確定權(quán)重向量的子問題z（如圖6(b)所示），可以使有效決策子集中的子問題z比其它子問題獲得更多的適應(yīng)度評估次數(shù),。LdEA策略對不同有效決策子集所關(guān)聯(lián)的不同子問題進(jìn)行不均等的算力分配,，避免算力冗余或者被重復(fù)分配，最終在確定被選中的子問題后生成解,。
圖6 采用LdEA策略對子問題進(jìn)行選擇的過程說明
為了驗證LdEA策略的有效性,，研究人員評估了MOEA/D-LdEA與四個對比算法在MOMKP 實例和MQAP實例上所獲得的反向世代距離（Inverted Generational Distance, IGD）和超體積（Hypervolume, HV）指標(biāo)值。
表1 MOEA/D-LdEA 與對比算法在求解MOMKP測試問題上所獲得的IGD和HV指標(biāo)值
表2 MOEA/D-LdEA 與對比算法在求解MQAP測試問題上所獲得的IGD和HV指標(biāo)值
從表1和表2可見,，MOEA/D-GUS在移除了LdEA策略后對MOMKP實例和 MQAP實例進(jìn)行求解所得的IGD值和HV值差于MOEA/D-LdEA所獲得的IGD值和HV值,。這驗證了采用LdEA策略求解滿足目標(biāo)空間距離與決策空間距離非正相關(guān)的空間化目標(biāo)先驗特性的MOMKP和MQAP測試問題的有效性,。此外，MOEA/D-LdEA能夠在多個有效決策子集中實現(xiàn)分配更少的算力來獲得高質(zhì)量的非支配解,，具備較好的折衷收斂性與多樣性,，從而在所獲得的IGD值和HV值上優(yōu)于MOEA/D-EEA、NSGA-III和RVEA,。
圖7展示了MOEA/D-LdEA與四個對比算法在 MOMKP 測試問題和MQAP測試問題上獲得的最終解集,。與采用不同算力分配策略的其他對比算法相比，MOEA/D-LdEA獲得的解集更逼近帕累托前沿（Praeto Front, PF）,。這說明通過確定微小搜索子區(qū)域和有效決策子集算力分配策略,，MOEA/D-LdEA可以在目標(biāo)空間的更多有效決策子集獲得更優(yōu)的最終解集，克服從一個子問題的解轉(zhuǎn)移到其鄰近子問題的解這一困難,，更有利于解決 MOCOPs,。
圖7 MOEA/D-LdEA、MOEA/D-CRA,、OPE-MOEA,、MOEA/D-IRA 和PPLS/D 在MOMKP (1) 和MQAP (2) 實例上獲得的最終解集
綜上所述，MOEA/D-LdEA通過運(yùn)用微搜索方法選定目標(biāo)子區(qū)域,，然后將選中的目標(biāo)子區(qū)域作為定向搜索方向并分配更多的算力,，在求解背包問題、二次分配問題等多目標(biāo)組合優(yōu)化問題方面獲得了顯著成效,，在性能上明顯優(yōu)于OPE-MOEA,、PPLS/D等現(xiàn)有算力分配的算法。
長期以來,，智能算法研究中心致力于運(yùn)用微搜索算法解決我國實際工業(yè)生產(chǎn)中的“卡脖子”難題,，目前已在柔性車間生產(chǎn)調(diào)度[10]和濾波器調(diào)參[11]問題上初見成效。今后,，我們將嘗試使用代理模型與微搜索算法相結(jié)合的方法求解超大規(guī)模的復(fù)雜組合優(yōu)化問題,，從而提升微搜索算法的求解速度，以適應(yīng)當(dāng)今發(fā)展迅速的工業(yè)時代,。
參考文獻(xiàn)
