基于極坐標變換的改進NSGA-II算法

劉　江,魏靜萱

(西安電子科技大學 計算機學院,陜西 西安　710071)

?

基于極坐標變換的改進NSGA-II算法

劉江,魏靜萱

(西安電子科技大學 計算機學院,陜西 西安710071)

摘要在實際工程中存在著大量的多目標優化問題,而由于大部分多目標優化問題有無窮多個最優解,且傳統的數學方法如梯度下降法和牛頓法,無法求解一些不可微或表達式過于復雜的多目標優化問題。為避免以上局限,NSGA-II作為求解多目標優化問題的代表算法被提出,但NSGA-II算法仍存在著一些不足,如變異算子功能過于簡單,降低了Pareto最優解的多樣性。為增加Pareto最優解的多樣性,文中設計了一種基于極坐標變換的改進NSGA-II算法,該算法可使得Pareto最優解分布更加均勻,并最終通過標準的測試函數驗證了算法的有效性。

關鍵詞NSGA-II;極坐標變換;多目標優化

實際中,諸多問題均是由相互沖突和影響的多個目標組成。即多目標優化問題(Multi-objective Optimization Problem,MOP)[1-2]。多目標優化問題在工程應用等現實生活中普遍存在,并處于重要的位置,這些實際問題通常較為復雜,如問題的表達式過于復雜,或表達式存在不可微,不可導的情況。

2002 年Deb等人提出了一種改進型非支配排序遺傳算法(Non-Dominated Sorting Genetic Algorithm,NSGA-II)[3]。算法先對種群中的個體按照支配關系進行分層,處于同一層上的各個個體都是彼此非支配的,且層級序值小的個體支配層級序值大的個體。然而,NSGA-II中使用的變異算子屬于單點變異,個體的變異范圍在線性范圍內變異。這就導致種群在進化工程中的種群多樣性受到影響,最終降低非劣最優解集的多樣性。……