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

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

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

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