最小生成樹問題的分析與研究

引言

組合優(yōu)化研究的是具有有限個(gè)可行解的優(yōu)化問題。其中最具挑戰(zhàn)性的問題就是組合爆炸。近年來，遺傳算法在組合優(yōu)化學(xué)界里日益受到重視，并在許多工業(yè)工程實(shí)驗(yàn)與實(shí)際應(yīng)用中取得了良好的成果，特別是在解決組合優(yōu)化領(lǐng)域中的最小生成樹問題MST中，顯示了它的巨大潛力。

一、問題的描述

考慮一個(gè)連通的無向圖G=(V，E)，其中，V={ν1，ν2，…，νn}是代表終端或通信站的有線的端點(diǎn)集。 E={eij|eij=(νi，νj)，νi，νj∈V}是代表終端或站間連線的有限邊集。每條邊由一個(gè)記為W={wij|wij=w(νi，νj)，wij＞0，νi，νj∈V}的正實(shí)數(shù)的權(quán)重，代表距離、價(jià)格等。生成樹是連接V中所有端點(diǎn)的來自E的最小邊集，因此對于圖G至少可找到一棵生成樹。最小生成樹記為T*，是邊的權(quán)重和最小的生成樹。其描述如下:，其中，T為圖G的生成樹的集合。

在一些實(shí)際問題中，端點(diǎn)的度不是可任意選取的。通信網(wǎng)絡(luò)中為防止節(jié)點(diǎn)故障帶來的脆弱性，對節(jié)點(diǎn)的度也有限制。即確定極小化總的邊權(quán)的生成樹時(shí)，往往要求端點(diǎn)νi的度di不大于一個(gè)給定值bi。令T*dc是圖G的所有樹中滿足度約束的最小生成樹，則問題可描述為:。為方便起見，這里僅討論完全圖上的對稱問題，即，wij=wji，且bi=b對所有νi∈V。

二、染色體表達(dá)

dc-MST問題是MST問題加上度約束的擴(kuò)展，所以染色體表達(dá)中應(yīng)含有顯式的或隱式的各個(gè)端點(diǎn)的度信息。在幾種樹的編碼中，只有Prufer數(shù)編碼含有顯式端點(diǎn)的度的信息，在Prufer數(shù)編碼中度為d的端點(diǎn)正好出現(xiàn)d-1次。因此，通常采用Prufer數(shù)編碼。

三、交叉和變異

Prufer數(shù)編碼任意交叉和變異后仍代表一棵樹。簡單的采用單點(diǎn)交叉，變異則可隨機(jī)的變?yōu)?和n中的一個(gè)整數(shù)。……