基于混合策略的快速非支配排序算法II

張茂清，汪 鐳，崔志華，郭為安

(1.同濟大學 電子與信息工程學院，上海 201804；2.太原科技大學 計算機科學與技術學院，山西 太原 030024；3.同濟大學 中德工程學院，上海 201804)

0 引言

在實際工程應用中，有許多目標函數為2～3個的優化問題[1-3]，且目標函數間具有彼此沖突的特點，此類問題一般被認為NP-Hard問題。傳統的方法，如線性規劃、梯度下降等，由于對問題特征具有較為嚴格的要求，導致解決此類問題時要付出極為昂貴的時間代價，甚至在有限時間內無法獲得滿意解。進化算法的出現為此類問題提供了新思路。典型算法如NSGA-II[4]、SPEAII(improved strength pareto evolutionary algorithm)[5],以及NNIA(multi-objective immune algorithm with non- dominated neighbor-based selection)[6]等在此類問題上均表現突出。其中，NSGA-II作為多目標優化算法的典型代表，受到很多研究者的廣泛關注。根據研究角度不同，可將近些年研究成果作如下分類。

就應用角度而言，NSGA-II及其改進方法已經被應用到許多實際優化問題中。為解決服裝調度生產中最大完成時間和最小延期交貨時間的問題，陸金芳[7]提出改進排序適應度和按需分層策略，極大提高了服裝調度的效率。黃敏鎂等[8]為了最大化供應鏈環境下協商Agent自身效用和合作企業建議相似度，采用了正整數和小數混合的實數編碼方式，并在遺傳操作中增加了約束限制，以剔除算法運行中產生不可行個體。在應急物流系統設計中，需要綜合考慮系統總成本、總耗時以及道路安全性等問題。陳剛等[9]針對此問題特點提出了改進個體交叉和變異方式，并進一步將精英策略融入NSGA-II。在將NSGA-II應用于水污染修復管理模型時，NSGA-II不能有效地收斂到真實Pareto 前沿。……