22702.基于單親遺傳算法的度約束最小生成樹問(wèn)題研究

1、學(xué)校代碼：10126分類號(hào)：——學(xué)號(hào)i——編號(hào)：——論文題目學(xué)院：數(shù)堂型堂堂院專業(yè)：數(shù)堂研究方向：篡法盆板生遮讓姓名g鄞仨態(tài)指導(dǎo)教師：紅玉副熬拯2014年4月23日基于單親遺傳算法的度約束最小生成樹問(wèn)題研究摘要最小生成樹問(wèn)題是組合優(yōu)化中的經(jīng)典問(wèn)題，并在通信網(wǎng)絡(luò)設(shè)計(jì)和最短路連接等方面有廣泛的應(yīng)用。在實(shí)際應(yīng)用中，生成樹頂點(diǎn)的度往往需要滿足某些條件。比如通信網(wǎng)絡(luò)設(shè)計(jì)中為了防止節(jié)點(diǎn)故障帶來(lái)的脆弱性，對(duì)節(jié)點(diǎn)的度要有一定的限制。這種頂點(diǎn)帶有度約束的

2、最小生成樹問(wèn)題稱為度約束最小生成樹問(wèn)題。遺傳算法作為一種啟發(fā)式搜索優(yōu)化算法，它為求解度約束最小生成樹問(wèn)題提供了一個(gè)有效的途徑。本文通過(guò)結(jié)合遺傳算法的思想，針對(duì)度約束最小生成樹問(wèn)題的特點(diǎn)，提出了采用單親遺傳算法求解這一問(wèn)題，并設(shè)計(jì)了新的編碼方案和相應(yīng)的遺傳操作。本文首先對(duì)度約束最小生成樹問(wèn)題的研究背景作了介紹。其次，介紹了一些求解度約束最小生成樹問(wèn)題的常用算法。最后，提出了在完全圖下求解度約束最小生成樹問(wèn)題的單親遺傳算法。本文通過(guò)對(duì)prf