基于多目標(biāo)遺傳算法求解Steiner樹問題.pdf

1、Steiner樹問題是組合優(yōu)化中的一個經(jīng)典問題,它在很多領(lǐng)域得到了廣泛應(yīng)用和深入發(fā)展。但當(dāng)前對Steiner樹問題的研究大都集中在單個目標(biāo)上,即最終只需要達(dá)到一種優(yōu)化目標(biāo)。而現(xiàn)實中需要解決的問題,往往不止一個目標(biāo),而是多個目標(biāo)相互制約、影響,由此提出了多目標(biāo)的Steiner樹問題,使Steiner樹問題變成多目標(biāo)優(yōu)化問題。
　　 目前有很多種解決多目標(biāo)優(yōu)化問題的算法,但這些傳統(tǒng)的算法只是提供了一些不同的途徑,將多目標(biāo)優(yōu)化問題轉(zhuǎn)化

2、為單目標(biāo)優(yōu)化問題,然后采用較為成熟的單目標(biāo)優(yōu)化方法來進(jìn)行求解。其解決問題的基礎(chǔ)仍是依賴單目標(biāo)優(yōu)化,往往難以得到令人滿意的最優(yōu)解集。由于遺傳算法內(nèi)在的并行性,善于在全局范圍內(nèi)進(jìn)行搜索,適用于解決多目標(biāo)優(yōu)化問題。本文提出利用多目標(biāo)遺傳算法解決一種兩個目標(biāo)的Steiner樹問題。
　　 本文的算法中,Steiner生成樹由貪婪算法計算,多目標(biāo)遺傳算法對每一代的個體搜索其Pareto最優(yōu)解集,直到算法結(jié)束,最終得到一組Pareto最優(yōu)解