用偽二叉樹法則構造多目標Ｐａｒｅｔｏ最優解集的方法

胡煥耀　董渭清

摘要：針對多目標進化算法中如何提高非支配集構造效率的問題，提出了一種用偽二叉樹法則構造多目標Pareto最優解集的方法。根據多目標解的性質，將解的比較結果分為支配、被支配以及不相關3種類型，再根據解的比較結果生成排序偽二叉樹。在每一輪比較中，從進化群體中選出一個個體，將該個體與當前非支配集中的個體進行比較，淘汰被支配的個體，而未被淘汰的個體將插入到非支配集中第一個被淘汰個體的位置。依次進行，直到進化群體中的個體比較完畢，從而。生成排序的偽二叉樹。同時，在理論上證明了采用該方法獲取的非支配集為目標進化群體的最大非支配集，分析得知其在最差情況下的時間復雜度為O(rN^{2/2)。實驗結果表明，當目標數較大時(r≥5)，在構造非支配集的效率上偽二又樹法要明顯優于Deb、Jensen算法及擂臺賽法則。}

關鍵詞：多目標進化；最優解集；非支配集；偽二叉樹法則

中圖分類號：TP301文獻標志碼：文章編號：0253—987X(2009)02—0029—04