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

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

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