外文翻譯---一種基于樹結(jié)構(gòu)的快速多目標遺傳算法-閱讀頁
2025-06-22 22:31本頁面
【正文】 標進化算法有高計算的需求。Deb 等人提出了一種快速非支配排序算法來減少計算復(fù)雜度，在 NSGAII算法中，非支配排序的計算復(fù)雜度從 )( 3MNO 降到 )( 2MNO 。此外，為了減小難度，一些數(shù)據(jù)結(jié)構(gòu)也被引入。為了促進帶精英策略的非支配排序，引入被支配和非支配的樹結(jié)構(gòu)。然而，它仍然需要進一步調(diào)查這個重要問題并且設(shè)計簡單而又有效的適應(yīng)度評價方法。大多數(shù)基于 Pareto的適應(yīng)度評價要求每個解應(yīng)該與其他大量的解進行比較，這使得大多數(shù)的MOEAs 計算復(fù)雜度限制在 ? ?2GMNO 。然而，在許多情況下， MOEAs 使用種群規(guī)模非常大的，特別是當相互沖突的目標非常多的時候。 附錄 4 通過分析一些常用的適應(yīng)度評價處理過程，我們可以發(fā)現(xiàn)在這些過程中有很多不必要的比較。例如，圖 1 顯示了五個節(jié)點之間的占優(yōu)關(guān)系。減少這些冗余的關(guān)系可能是一個有效的策略來減少適應(yīng)度評價的計算復(fù)雜度。以圖 1 為例，如果我們知道 N4 Pareto 占優(yōu) N3， N3 Pareto 占優(yōu) N2，那么不用通過比較我們也可 以得出 N4 Pareto 占優(yōu) N2。我們也注意到了另一個現(xiàn)象，我們只需要獲得種群中每一代的 Pareto 最優(yōu)解集，即使那些占優(yōu)的解仍然對于進化過程有用。也正是由于這個原因，許多解之間的關(guān)系 (例如，解之間的占優(yōu)關(guān)系 )是不必要的知道，因此這些關(guān)系可以去除。我們可以觀察 N4 占優(yōu) N3， N1 占優(yōu) N2。通過以上分析，我們能找到兩個原則來減少不必要的計算時間： （ 1）避免冗余比較（例如依靠推理來推斷這些關(guān)系）；（ 2）只保留必要的關(guān)系（即，忽略那些不是非常重要的關(guān)系） 正如我們提到的，不同于 SOPs 的解之間的關(guān)系， MOPs 的解有三值關(guān)系。 定義 3： Better 的函數(shù) ? ? ? ? ? ?? ? ? ?????? ???ten o n d o m i n n a ,0 ,1 ,112212,1 xFxFxFxFxxB e tte r ???????? 這個 Better 函數(shù)是一個 三值函數(shù)。我們知道，對于排列標量數(shù)的二值關(guān)系來說，二進制排列樹（ BST）是一個非常有效的工具。我們考慮多目標優(yōu)化的三值的關(guān)系也可以被存儲在一個擴展的二叉樹 中。圖 2 中的一個例子表明圖 1 中節(jié)點之間的關(guān)系。作為一個新型的二叉樹，我們稱之為支配樹。一個支配樹是一種二叉樹，定義如下。 2) 每個節(jié)點在支配樹有中四個域： id、計數(shù)器、左連接和右連接。 DT的定義與 BST的定義相似， DT和 BST也擁有近似的性能。 DT也還有一些不同的特點。DT的同級鏈被定義為由它的根節(jié)點和它的右連接節(jié)點構(gòu)成的鏈條。通過跟蹤右連接域，可以獲得同級鏈。此外， N3和 N5也構(gòu)成 DT的同級鏈，其根節(jié)點是 N3。這一部分將在第
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1