并行進化算法及其在組合優(yōu)化中的應用.pdf

1、大多數(shù)組合優(yōu)化問題都是NP完全問題，這類問題很難找到多項式時間的最優(yōu)化算法，也就是說其算法的時間花費通常隨著問題規(guī)模的增大呈指數(shù)增長。然而進化算法在求解組合最優(yōu)化問題時，盡管它不能保證在多項式時間內(nèi)找到NP完全問題的最優(yōu)解，但是常常能找到組合最優(yōu)化問題很好的次優(yōu)解，數(shù)值實驗結果表明進化算法在解的質(zhì)量和執(zhí)行效果上都優(yōu)于傳統(tǒng)的啟發(fā)式算法。所以進化算法以及其他智能算法對組合最優(yōu)化問題的解決具有十分重要的意義。 首先，提出了一種新的求解

2、多目標最小生成樹問題的進化算法。該算法采用邊集合編碼表示生成樹，給出了一種新的隨機(服從均勻分布)生成樹算法，并用來產(chǎn)生初始種群；同時設計了一種新的交叉算子和變異算子。第二，針對度約束的最小生成樹問題給出了一種改進的進化算法，該算法也采用邊集合編碼表示生成樹，給出了一種新穎的初始種群生成算法和一種改進的交叉算子。數(shù)值實驗結果表明上述的兩種進化算法是有效的。第三，對帶約束的最小生成樹問題給出了一種有效的枚舉算法。最后，介紹了實現(xiàn)并行進化算