進化算法在大規模優化問題中的應用綜述

梁 靜， 劉 睿， 瞿博陽， 岳彩通

(1.鄭州大學 電氣工程學院，河南 鄭州 450001；2.中原工學院 電子信息學院，河南 鄭州 450007)

0 引言

當今很多優化問題已經從簡單問題發展成為復雜問題.許多科學和工程應用問題都可以設計成大規模優化問題來進行求解，例如：大型電力系統、大量的資源調度問題、大規模交通網絡的車輛路徑規劃等.然而隨著優化問題越來越復雜，一些經典的算法已經不能滿足實際需要.最近幾年進化優化在許多實值和組合優化問題上取得了很大的成功，但是大多數的隨機優化算法都會遭受“維數災難”.因此，近些年學者們利用進化算法進行了多種有價值的嘗試，并且針對大規模優化問題組織了專題會議，如Special Session on Evolutionary Computation for Large Scale Global Optimization，設計了新的測試函數、建立了相關的網站，并且在IEEE Transactions on Evolutionary Computation、Information Sciences、Soft Computing、Applied Soft Computing等優秀期刊也刊登了對于大規模問題的研究進展，顯示出此研究領域的重要性.

1 數學表述

大規模優化問題可以用式(1)表述：

min/maxF(x)=f(x1,x2,…,xn)，x∈X.

(1)

式中，X?n表示可行解集；n表示搜索空間的維數(即決策變量的個數)；x=(x1,x2,…,xn)∈n表示決策變量；f:X→則表示一個從n維空間映射到一維適應度值F(x)的實值非連續性目標函數.在大規模設置中決策變量的個數n一般大于100[1]，通常達到1 000維以上.

2 解決方法

在算法開始階段，文獻[2]給出了針對大規模問題的初始化方法，可以更加有效地尋找極點.而對于算法的主體部分，一般來說主流的策略可以分為兩大類：協同進化策略和不分組策略.協同進化策略是由分治策略進化而來，主要思想是把大規模復雜問題分解成單變量或低維簡單問題逐一解決；……