基于并行遺傳算法的概率最小生成樹問題的研究.pdf

1、’f’論文題目：基于并行遺傳算法的概率最小生成樹問題的研究學(xué)科名稱：計(jì)算機(jī)軟件與理論研究生：馬凡簽名：墨＆指導(dǎo)教師：王竹榮副教授摘要簽名：概率最小生成樹問題是對(duì)傳統(tǒng)最小生成樹問題中樹的頂點(diǎn)附加一定的存在概率，從而形成的一類重要的約束最小生成樹問題，它是一個(gè)典型的NP完全問題，同時(shí)，對(duì)它的求解是一個(gè)NP—hard問題。實(shí)際生活中的很多組合優(yōu)化問題，例如，網(wǎng)絡(luò)設(shè)計(jì)、超大規(guī)模集成電路的設(shè)計(jì)等等優(yōu)化問題，都可以抽象為概率最小生成樹問題，通過對(duì)概

2、率最小生成樹問題及其求解方法的研究，提出有效求解概率最小生成樹問題的方法，可以很好地解決實(shí)際生活中的以上組合優(yōu)化問題，所以對(duì)概率最小生成樹問題的研究具有較大的理論意義和實(shí)用價(jià)值。本文通過對(duì)概率最小生成樹問題進(jìn)行分析，采用基于行列式因子分解編碼的遺傳算法和并行遺傳算法對(duì)它進(jìn)行求解。研究工作如下：1)對(duì)基于行列式因子分解編碼的遺傳算法和并行遺傳算法中涉及的問題進(jìn)行了分析；2)在用基于行列式因子分解編碼的遺傳算法求解問題的過程中，給出了算法的

3、行列式因子分解編碼的有效性判斷依據(jù)，并對(duì)非可行個(gè)體進(jìn)行修正，從而保證算法更高效地求解問題；3)對(duì)以上遺傳算法進(jìn)行并行化，通過和消息傳遞并行編程模型MPI相結(jié)合，設(shè)計(jì)了一種粗粒度并行遺傳算法對(duì)具體的概率最小生成樹問題進(jìn)行求解。參照有關(guān)文獻(xiàn)給出的按隨機(jī)方式生成概率最小生成樹問題的方法，通過設(shè)計(jì)隨機(jī)生成器來產(chǎn)生若干個(gè)概率最小生成樹問題，用本文所提的算法對(duì)上述問題進(jìn)行測(cè)試，并將測(cè)試數(shù)據(jù)與現(xiàn)有文獻(xiàn)中求解概率最小生成樹問題的相關(guān)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了比較，