火力與指揮控制
第３５卷第１期
ｊａｎ，２０１０
２０１０年１月
，＼１聲
文章編號一ｏｏ７７一ｏ４
基於混合粒子群優化的多目標決策新方法
徐安 ，趙思巨集。，寇英信 ，黃
俊１３００２２）
（１．空軍工程大學工程學院，西安
摘７１００３８，２．空軍航空大學，長春
要：多目標優化問題中的乙個關鍵在於合理地評判各有效解的優劣。通過引入灰色系統理論中灰色關聯度的概念作
為評判準則，結合粒子群優化演算法進行有約束多目標規劃問題的研究。提出了一種新的不可行解的保留策略，進化過程中以此策略保留適量的不可行解，有利於增強對約束邊界附ｉ￣．－－ｉ能的最優解的搜尋，同時，針對粒子群優化演算法的容易陷入區域性
最優的缺點，實現了以粒子群優化為載體的混合演算法：即對全域性極值鄰域進一步混沌搜尋尋優。**結果表明改進的演算法對
多目標決策問題是有效的。
關鍵詞：多目標決策，粒子群優化，不可行解，混沌搜尋，灰色關聯中圖分類號：ｔｐ３０１．６
文獻標識碼；ａ
優化問題解的優劣性很難評價，因此解的形式經常
表現「非劣解集」，即ｐａｒｅｔｏ集，基於ｐａｒｅｔｏ集的概
多目標決策理論是運籌學的乙個重要分支ｎ］，用多目標決策方法解決決策問題更能滿足實踐的需要。傳統的解決多目標優化辦法是將目標數量化多為少（土要目標法、線性加權法等）或將目標按重要性分類進而逐個優化（分層序列法），上世紀７０年代出現的層次分析法也是發展較快的一種決策分析方法。這些方法的普遍特點是需要對具體問題所涉及
念，許多啟發式搜尋演算法被用於解決此類問題，其優點是一次可以求得多個非劣解，並且所需的領域知
識少。粒子群優化演算法是一種基於群體智慧型的全域性優
化演算法，針對演算法易陷入區域性最優的缺點，人們提出了很多改進演算法和混合演算法ｌ２］，它們都在一定程度上增強了演算法的尋優能力，並成功地解決了許多優
化問題。
的因素進行全面分析和權衡，各種不同思路將導致
不同的處理得失的方法。與單目標優化不同，多目標
多目標決策的數學模型
考慮有約束多目標規劃問題：
ｍｉｎｙ＝廠（ｚ）一
一１，…，ｍ
收稿日期：２００８—１ｏ一１ｏ修回日期
＊**專案：空軍重點科研專案**（ｋｊ０６０９０）
作者簡介：徐安（１９８４一），男，甘肅慶陽人，博士研究
生，主要研究方向：航空綜合火力控制系統及
其中，ｕ］為空間的維向量域，搜尋空間為［ ，ｕ］一｛一
作戰任務規劃。
７８ （總第３５－－００７８）火力與指揮控制２０１０年第１期
…，，ｚ｝為解空間，集合ｆ一用灰色關聯度的概念分析各非劣解與理想解之問的接近程度，實際上是將多目標轉化為單目標優化問
題，優化目標成為：使得關聯度最大化。
灰色關聯分析是灰色系統理論中的一種新的系統分析方法，它利用灰色關聯度定量描述系統各要素的相似程度，關聯度越大，相似程度越大。
設ｘｏ一｛ｘｏ（誌為基準模式向量
構成可行域。若存在∈ｆ使得
ｆ（ｘ ）≤廠（ｚ）成立，則稱ｚ 是，（ｚ）在可行域ｆ上
的全域性最優解，ｆ（ｘ ）是全域性最優值。
２ 改進的粒子群優化演算法
對於單目標優化問題，粒子群的個體極值和全域性極值以適應度為評價標準進行選取，多目標優化（參考序列），ｘｉ｛ｘ （誌為待檢模式則無法直接比較各個解的優劣程度。由於演算法的思想是粒子群追隨兩個極值，如何選擇這兩個極值將
直接影響到演算法的尋優能力和收斂速度。已有的研
究多是針對單目標優化問題，主要通過各種不同的方法來得到「更優」的極值：例如通過對全域性極值鄰
域的進一步搜尋ｒ６］或適時的隨機變異全域性極值或在
約束規劃中保留一定量的不可行解［７］，從而增大尋
優的概率；或是通過引入新的評判準則，如雙適應值
準則力或灰色關聯度來確定個體和全域性極值。２．１基本粒子群優化演算法
粒子群演算法是一種基於群體智慧型的全域性搜尋演算法。假定群體中每個個體都能夠感知自己周圍的區域性最好位置和整個群體的全域性最好位置，並根據當
前群體中的這兩個位置，調整自己的下一步行為，從而使得整個群體表現出一定的智慧型性。在解決優化問題時，每個個體可被相應看成乙個潛在解，按照上述規則，通過概率化地調整這些潛在解，不斷迭代，最終得到所需要的全域性最優解。
該模型可被抽象成如下形式：每個粒子儲存自
身當前速度口一（…，７ｄｉｄ）和位置ｚ 一（ｚ
ｚ …，ｉｚ。），並按如下規則更新：
一戶一一ｚ ）
３７一ｚ ＋
（２）其中，一１，２，…，ｄ代表維數；ｗ 為加權係數，
一般採用線性規律遞減的權重（ｌｄｗ），也可採用自
適應方式進行改變，ｗ 大可對大範圍進行探索，ｗ小可以對小範圍進行挖掘∈［一 ，］，為界限，如果超出範圍則取邊界值．ｆ１、ｃ 稱為學習因子，分別代表了個體對於自身認知能力和對社會新息的認知能力；ｐ為個體極值，即粒子迄今為止搜尋到的
最優位置，ｇ為全域性極值，即整個群體所有粒子所搜
索到的最優位置；，．和，一取處於［ｏ，１３２：問的隨機
數，其作用是增強粒子群運動的隨機性，防止過早收斂於區域性極值。
２．２評價非劣解的灰色關聯度準則
多目標優化問題的乙個關鍵是怎樣界定有效解的優劣程度，類似於單目標優化問題中的適應度評價，本文採用灰色關聯度進行評價。適合評價多目標問題中各有效解的優劣，有利於掌握解空間全貌，利
向量（比較序列），二者的關聯係數定義為：
ｅ，ｒ、
ｍｉｎｌｍｉｎ（誌是）
（愚ｐ為分辨係數，一般取為ｅｏ，１］之間，典型值為
０．５，（愚）＝ｉｘｏ（啟）一ｘｉ（志）ｌ為是時刻（指標、空間）的絕對差為兩極間的最小差志）為兩極間的最大差。定義序列和
ｘ，灰色關聯度為：一÷ ￡（志）（３）
對於進化過程中的各非劣解，以灰色關聯度最
大來指導進化的方向，即粒子群追隨關聯度最大的粒子，從而實現群體的智慧型。２．３不可行解的存活策略
考慮到這樣一類問題，它們的最優餌處於約束邊界附近，那麼在邊界附近的某個不可行解的適應度（這裡是灰色關聯度）將優於已找到的可行解，加入這個不可行解對於收斂到全域性最優解是有益的，
因此，保留適量的不可行解，以增加演算法的全域性搜尋
能力。對於空間的粒子，以式
（）一（４）
』 １表示各個粒子的不可行度；（ｚ）＞０說明粒子為不可行解，且口（ ）越大說明衝突程度越大；
以範數一
（ｚｆ，ｚｊ）一
（５）表示粒子ｚ 和的歐氏空間距離，它代表了這兩個粒子狀態的相似程度。
每次進化後，首先由式（４）判定當前各粒子是否屬於可行域，然後分別對各不可行解粒子作如下處理：①對粒子ｐ ¨給定閾值ｅ＞０；②依據式（４）計算ｐ．ｉｆ的不可行度，如果口（ｚ）＞ｅ，捨棄此粒子，否則轉入下一步；③依據式（５）分別計算ｐ ｉｒ與其他可行解粒子的距離，儲存距其最近的乙個可行解粒子ｐ；④依據式（３）分別計算ｐ 「和ｐ… 的灰色關聯度，如果有較大的關聯度的則保留之，否則捨棄；⑤檢查不可行解粒子的規模，如果超過粒子總
數的２ｏ ，則分別計算其灰色關聯度，捨棄關聯度
最小的乙個。
ｉ√。一
徐安，等：基於混合粒子群優化的多ｈ標決策新方法（總第
閾值￡採用式（６）給出，式中，ｍ為種規模；１／丁
２．５演算法步驟
類似於退火因子，隨著進化逐漸減小，從而使閾值ｅ減小，以逐步增大滿足約束條件的壓力，使搜尋向著可行域收縮。
＾借鑑ｚｉｔｚｌｅｒ和ｔｈｉｅｌｅ在其所設計的多目標演
化演算法ｓｐｅａ２ｃ中的策略，儲存乙個容量受限的外部記憶體，該記憶體的個體集合包含從初始代到當前代群體的非劣個體。本文演算法與ｓｐｅａ２的區別在於：沒有進行記憶體與原始群體的交叉變異而直接產生下一代群體，原因在於混沌尋優策略能保證ｍｃ＝
亭［∑ｖ（ｘ。）］／
『ｉ＝１
（６）２．４全域性極值的混沌優化
基本粒子群優化演算法進化後期收斂慢，針對其區域性尋優較差的缺點，本文以粒子群演算法為載體，提出一種自適應的混沌優化方法在全域性極值鄰域一定範圍內進一步搜尋，在運算量不致明顯增大的情況下增強此演算法的尋優能力。
混沌是非線性系統中的一種演變現象，它不是
由隨機性外因引起，而是確定性規則導致的對初始
條件非常敏感的無固定週期的長期行為。產生混沌的規則很多，式（７）為混沌變數ｃ 的一種演變算
式：ｃｌｚ一４ｃ （１－ｃｘｄ
（７）其中，ｃｚ 為ｃ 第ｋ步演變後的值，當ｃ ｅ
（０，１）且不等於時將產生混沌，ｃｚ在（ｏ，１）內遍歷。
混沌優化的基本思想是把混沌變數從混沌空間對映到解空間，利用混沌變數的遍歷性、隨機性和規
律性的特性進行搜尋。混沌優化演算法具有易跳出區域性極值、全域性收斂等優點。
變數ｚ ｅ，ｂｄ］與混沌變數ｃ 可由式（８）往
返對映：
一日 ）
勳一（８）
混沌搜尋步驟如下：
（１）隨機生成混沌變數ｃ ；
（２）將混沌變數對映到解空間［「 ，］，得到
ｌ，ｒｚ 一日／＋（ 一以 ）ｆ；
（３）對 ０進行混沌搜尋：ｚ 一 ＋ｐ船 ，
為一很小的數，如果／（ｚ ）＜廠則ｆ 一廠（ｚ ），．ｚ ＝
．此時為全域性最優解；
（４）更新ｆｚ 一轉到步驟（２），直到達到最大迭代次數或一定的滿意度時終止。
由於最優解的保留採用貪婪策略，搜尋次數的
增大必然導致運算時間的增大．此處提出一種新的
概率優化策略：
混沌優化的第ｋ步．以溉率
ｐ女＝１一一
（９）決定是否搜尋，戶隨著進化由０逐漸增大並趨
於ｌ，進化初期收斂較快，減少無意義的搜尋以換取
時間，進化後期以接近１的概率進行搜尋，以期跳出區域性最優，得到全域性極值。
下一代粒子狀態「更優」。
步驟簡要敘述如下：
（１）初始化：初始化各引數，生成粒子群；置初始極值；
（２）單目標優化：用恰當的單目標優化演算法求取各目標函式的極值，組成基準序列；
（３）產生新一代：依據式（２）更新粒子群速度和
位置；（４）粒子分類：依據式（４）判斷各個粒子是否屬
於可行域，如果是，轉人步驟（５），否則轉入步驟（７）；
（５）更新極值：由各粒子當前狀態組成比較序
列，與基準序列比較，取關聯度最大的為全域性極值，保留全域性極值，同時保留每個粒子自身的歷史最優值為個體極值；
（６）混沌優化：以混沌搜尋方法對全域性極值的鄰域進行搜尋，並更新全域性極值，直到達到預定的滿意
度或達到最大的混沌搜尋次數時終止，並轉到步驟
（８）；
（７）保留不可行解：對不可行解依據２．３敘述的
策略進行保留，對捨棄的粒子以關聯度最差的可行
解粒子替換；
（８）更新後的粒子群作為當前群體，轉入步驟（３），直到達到預定的滿意度或達到最大進化次數時
終止。３ 演算法**
本例取自文獻［１１］，問題ｋｕｒ的決策空間具
有非凸的特徵，如下：
ｎ－１廠—————一
ａｒｉｎｆｌ（）一
（一１ｏｅｘｐ（一
，一１＿、
ｍｉｎｆ２（ｘ）一２＿５（ｔ
＋５ｓｉｎｘ ）
ｉ＝１其中五ｅ［一５，５］，ｉ一１，２，…，。
先由下頁圖１、圖２給出一３時兩個目標函式三維圖形，可見，三維情況下兩個目標無法同時滿
足，且目標函式２是乙個多極點的函式，在高維狀態
下此問題的求解對多目標決策問題具有普遍意義。
下面實現多目標優化：取以下典型情況：一２，５．１０，粒子數為３ｏ，最大進化代數取為２ ０００，混沌搜尋次數取５ｏ。
８０（總第３５－－００８０）火力與指揮控制２０１０年第１期
４ 結論
本文基於已有的解決單目標優化問題的較為成
熟的方法，提出一種解決多目標優化問題的典型思路。首先，運用灰色關聯的思想給出一種多目標優化問題非劣解的評價準則，使優化的目標成為使關聯圖１目標函式１圖形圖２ 目標函式２圖形一３）
（，ｌ＝３）
（１）首先，應用加入混沌優化的單目標粒子群優
化演算法求兩個目標函式（以，ｚ一５為例）的極值，分別為一３９．７９６ ４和一１８．４５６ １，如圖３，圖４所示：圖中虛線為基本粒子群的進化曲線，可見混沌搜尋使尋優速度和效能得到較大提公升。２８—
３０３２
—３４—
３６—３８—４ｏ
圖３目標函式１極值進圖４ 目標函式２極值進化曲
化曲線線
為便於比較，將各極值隨維數的變化列表如下：
表１各目標函式極值情況
（２）依據灰色關聯的粒子群優化演算法進行多目標優化，粒子數取為５ｏ，進化最大代數取為２００，基準序列由表１組成，其餘各引數均取為典型值，分別在一２，５，１０時進行計算，結果如圖５所示。
由圖５知：灰色關聯度逐漸增大並趨於１，表明最優粒子與優化目標接近程度增大，且隨著維數的上公升，收斂速度較慢（增加幅度小），這是高維函式的複雜性決定的。
最優解進化曲線
ｐａｒｅｔｏ曲線
１０．９９
０．９４
圖５各代最優粒子的灰色關圖６ 各代最優粒子組成
聯度進化曲線
的部分ｐａｒｅｔｏ解集
由圖６可以直觀地看出有效解集的分布，由於只畫出各代最優解，大多數解重合在一起，這也在一
定程度上說明了最優解進化的階梯性。
度達到最大。對於一類有約束規劃，提出一種新的策
略將部分的不可行解保留在粒子群，以增強解的全
局最優性，同時，借鑑目前各種混合演算法，將混沌搜
索加人粒子群優化過程中，力求盡可能好地找到全域性最優值。算例驗證了此優化演算法對於多目標優化問題的有效性。
參考文獻：
［１］運籌學教材編寫組．運籌學［ｍ］．北京：清華大學出
版社，１９９７．
［２］楊俊傑，周建中．基於混沌搜尋的粒子群優化演算法
［ｊ］．計算機工程與應用
［３］英願斌，陳德釗，胡上序，混沌粒子群演算法及其在生
化過程動態優化中的應用［ｊ］．化工學報，２００６，１２
［４］熊盛武，劉麟．改進的多目標粒子群演算法口］．武漢大學學報（理學版
［５］吳惠芳，周
瓊，蔡驊．多目標決策的特殊座標系
求解方法［ｊ］．火力與指揮控制
１０５．
［６］王躍宣，劉連臣．處理帶約束的多目標優化進化演算法
口］．清華大學學報（自然科學版
１０７．
［７］李炳宇，蕭蘊詩，吳啟迪．一種基於粒子群演算法求解
約束優化問題的混合演算法［ｊ］．控制與決策，２００４，１８
［８］劉華鎣，林玉娥，王淑雲．粒子群演算法的改進及其在
求解約束優化問題中的應用［ｊ］．吉林大學學報（理
學版［９３於繁華，劉寒冰，戴金波．求解多目標優化問題的灰
色粒子群演算法口］．計算機應用
２９１６．
［１ｏ］李炳宇，蕭蘊詩，汪
鐳．一種求解高維複雜函式優
化問題的混合粒子群優化演算法［ｊ］．資訊與控制，
［１１１汪祖柱，程家興，張
鈴．一種基於混合交叉策略的
多目標演化演算法［ｊ］．計算機工程與應用，２００５，２８
（９）：１－４．
［１３３楊
懿，武昌，劉涵．改進粒子群演算法在飛彈分
配中的應用［ｊ］．火力與指揮控制２７．
基於遺傳演算法的高速列車執行多目標優化
摘要 隨著我國高速鐵路的迅速發展，人們不僅要求列車安全 正點 執行過程舒適的同時，能耗和執行時間達到鐵路運營部門和旅客都可以接受的程度。同時也對列車的低能耗和舒適性提出了更高的要求。針對這一情況，本文將遺傳演算法運用於列控系統中對高速列車的執行過程進行優化。通過研究列車的運動方程和約束條件，對列車的...
多目標電網規劃的分層最優化方法
摘要 電網規劃是乙個不確定的 多目標的 非線性和多階段性的複雜系統優化問題。隨著市場經濟的發展，電網規劃的經濟性與可靠性之間的矛盾日益加劇，如何選擇合理的電網規劃的最優模型已成為現代電力事業面臨的挑戰。本文 了多目標電網規劃的分層最優方法，並利用算例進行了校驗，證明了該方法的有效性。關鍵詞 多目標 ...
基於多攝像頭協同的多目標跟蹤系統技術報告
本系統是採用mfc和opencv開發的乙個基於多攝像頭協同的多目標跟蹤系統。採用多執行緒設計，可以通過配置檔案選擇實時讀取多路攝像頭 資料或讀取多路錄製好的 進行行人的實時檢測和跟蹤，並儲存跟蹤結果。圖1 1 本系統採用多執行緒設計，對於每個獨立的攝像頭 輸入，採用乙個獨立的執行緒進行處理。對於每個...