胡煥耀　董渭清

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

關(guān)鍵詞：多目標(biāo)進(jìn)化；最優(yōu)解集；非支配集；偽二叉樹法則

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)志碼：文章編號(hào)：0253—987X(2009)02—0029—04