朱彥廷

(河池職業(yè)學(xué)院 計(jì)算機(jī)系,廣西 河池 547000)

用遺傳算法求最小生成樹

朱彥廷

(河池職業(yè)學(xué)院 計(jì)算機(jī)系,廣西 河池 547000)

以圖論和遺傳算法為基礎(chǔ),給出了一個(gè)改進(jìn)的求最小生成樹的算法,提出了“無性生殖”的方式,舍棄了逆轉(zhuǎn)算子,改進(jìn)了換位算子,調(diào)整了選擇算子,更簡(jiǎn)單,因而編程更容易,效率更高 .使用該算法可以在較短的時(shí)間內(nèi)以較高的概率獲得一組最小或次小生成樹,而傳統(tǒng)算法一般只能得到一個(gè)最小生成樹 .

最小生成樹;遺傳算法;優(yōu)化

1 基本原理

遺傳算法借助于生物進(jìn)化機(jī)制與遺傳學(xué)原理,先隨機(jī)產(chǎn)生一些個(gè)體,然后進(jìn)行選擇、交叉和變異操作,模擬自然界中生物的進(jìn)化過程,使個(gè)體的性能不斷提高,逼近問題的最優(yōu)解 .它用于求解組合優(yōu)化問題非常有效,尋找最小生成樹實(shí)際也是組合優(yōu)化問題,因此可以考慮使用遺傳算法 .

2 算法設(shè)計(jì)

2.1 編碼

設(shè)一無向圖共有ND個(gè)頂點(diǎn),NP條邊,對(duì)邊進(jìn)行編號(hào) .一個(gè)個(gè)體是一個(gè)二進(jìn)制代碼,長(zhǎng)為NP,代表圖的一個(gè)子圖,若某位為 1,表示它所對(duì)應(yīng)的邊是子圖的邊;若為 0,表示它所對(duì)應(yīng)的邊不是子圖的邊 .

2.2 適應(yīng)度函數(shù)

2.3 遺傳算子

交叉算子以某一概率隨機(jī)交換 2個(gè)個(gè)體的部分位,得到 2個(gè)新個(gè)體 .變異算子以某一概率隨機(jī)改變個(gè)體的某些位,得到 1個(gè)新個(gè)體 .對(duì)于本問題,它們極可能破壞個(gè)體的可行性,即得到的新個(gè)體不是只有ND-1位為 1,根本不代表一個(gè)生成樹,沒有意義,因此不能直接用這 2個(gè)算子 .

已有人對(duì)此做過研究,概括起來,他們[2-4]提出了換位算子和逆轉(zhuǎn)算子,相當(dāng)于舍棄了交叉算子,對(duì)變異算子做了修改 .如果說一般遺傳算法采用的是“有性生殖”(使用交叉算子,1個(gè)新個(gè)體由 2個(gè)個(gè)體得到),那么這里的遺傳算法采用的就是“無性生殖”(舍棄交叉算子,1個(gè)新個(gè)體由 1個(gè)個(gè)體得到).生物進(jìn)化了幾十億年,無性生殖仍廣泛存在于自然界中,說明它有存在的價(jià)值,遺傳算法要更好地模擬生物進(jìn)化過程,也應(yīng)包括這種方式 .

換位算子:隨機(jī)產(chǎn)生 2個(gè)換位位,對(duì)其進(jìn)行換位 .以個(gè)體 011100為例,若換位位為 0、2,換位后為110100.文獻(xiàn)[2,4]提出換位次數(shù)隨機(jī)產(chǎn)生,不固定是 1,假設(shè)換位次數(shù)為 2,對(duì) 110100再次換位,可能得到的個(gè)體不如它,但它卻被丟棄了,因此應(yīng)固定是 1.而若換位位為 1、2,對(duì)應(yīng)的數(shù)值相同,或換位位為 1、1,換位沒有價(jià)值 .

逆轉(zhuǎn)算子:先隨機(jī)產(chǎn)生逆轉(zhuǎn)起始位,再隨機(jī)產(chǎn)生逆轉(zhuǎn)位數(shù),如果要逆轉(zhuǎn)的部分含“1”的個(gè)數(shù)和“0”的個(gè)數(shù)相等(文獻(xiàn)[3]說含“1”的個(gè)數(shù)為偶數(shù),是不準(zhǔn)確的,其它文獻(xiàn)大多敘述含糊,對(duì)這個(gè)關(guān)鍵的地方只字不提),對(duì)其進(jìn)行逆轉(zhuǎn),以個(gè)體 011100為例,若逆轉(zhuǎn)起始位是 2,逆轉(zhuǎn)位數(shù)是 4,則要逆轉(zhuǎn)的部分是 1100,含“1”的個(gè)數(shù)和“0”的個(gè)數(shù)相等,逆轉(zhuǎn)后為 010011.

假設(shè)個(gè)體有n位,逆轉(zhuǎn)起始位只能為 0,1,…,n-1,逆轉(zhuǎn)位數(shù)應(yīng)為偶數(shù),最小是 2,加上相應(yīng)的逆轉(zhuǎn)起始位又不大于n,編程很麻煩 .而如果要逆轉(zhuǎn)的部分含“1”的個(gè)數(shù)和“0”的個(gè)數(shù)不相等,不能進(jìn)行逆轉(zhuǎn)(那將破壞個(gè)體的可行性).

各位被逆轉(zhuǎn)的概率其實(shí)是不同的 .為簡(jiǎn)單起見,假設(shè)個(gè)體有 4位,那么逆轉(zhuǎn)起始位只能為 0、1、2,若逆轉(zhuǎn)起始位為 0,逆轉(zhuǎn)位數(shù)只能為 2、4;若逆轉(zhuǎn)起始位為 1,逆轉(zhuǎn)位數(shù)只能為 2;若逆轉(zhuǎn)起始位為 2,逆轉(zhuǎn)位數(shù)只能為 2,再假設(shè)要逆轉(zhuǎn)的部分含“1”的個(gè)數(shù)和“0”的個(gè)數(shù)相等,可以算出各位被逆轉(zhuǎn)的概率分別是 1/3,2/3,5/6,1/2,這樣可能有的位如果被逆轉(zhuǎn)能得到更好的個(gè)體,但被逆轉(zhuǎn)的概率很小;有的位如果被保留能得到更好的個(gè)體,但被逆轉(zhuǎn)的概率很大,很不合理 .

本算法舍棄了逆轉(zhuǎn)算子,對(duì)換位算子加以改進(jìn),隨機(jī)產(chǎn)生 1個(gè)換位位,如果該位原為 0,變?yōu)?1,為了保證新個(gè)體只有ND-1位為 1,然后向后尋找第 1個(gè)為 1的位,變?yōu)?0,如果沒找到,再?gòu)淖钋懊鎸ふ?一定能找到,否則意味著個(gè)體的各位全是 0,這是不可能的);如果該位原為 1,變?yōu)?0,然后向后尋找第 1個(gè)為 0的位,變?yōu)?1,如果沒找到,再?gòu)淖钋懊鎸ふ襕一定能找到,否則意味著個(gè)體的各位全是 1(說明無向圖已是樹,那就沒必要求了),這是不可能的],這樣換位肯定有價(jià)值 .以個(gè)體 011100為例,如果產(chǎn)生的換位位是 1,則換位后為 001110;如果換位位是 4,換位后為 001110.

選擇算子從群體中選擇較好的個(gè)體,用來進(jìn)行交叉、變異 .一般用個(gè)體的適應(yīng)度與群體中個(gè)體的適應(yīng)度的總和的比值作為其被選擇的概率,個(gè)體的適應(yīng)度越高,被選擇的概率越大,對(duì)于本問題,較好的個(gè)體不一定產(chǎn)生較好的新個(gè)體,二者沒有什么關(guān)系,因此不用這種做法 .因?yàn)樾聜€(gè)體可能不如原個(gè)體好,為更多地保存較好的個(gè)體,以便最后得到更多的最小或次小生成樹,將新群體與原群體混合,按適應(yīng)度高低降序排序,選出最好的不重復(fù)的個(gè)體(約占群體數(shù)目的 80%),這充分體現(xiàn)了優(yōu)勝劣汰的原則,再隨機(jī)產(chǎn)生少量新個(gè)體(約占群體數(shù)目的 20%),合起來組成下一代群體,這可以彌補(bǔ)舍棄逆轉(zhuǎn)算子(它改變個(gè)體的幅度大,因而對(duì)解空間的搜索能力強(qiáng))帶來的不足,保持了群體的多樣性,以免出現(xiàn)早熟現(xiàn)象(進(jìn)化過早停滯).

2.4 算法流程

(1)設(shè)置群體大小M、最大進(jìn)化代數(shù)T;

(2)隨機(jī)生成M個(gè)個(gè)體作為初始群體,計(jì)算各個(gè)個(gè)體的適應(yīng)度;

(3)如果進(jìn)化代數(shù)t=T,轉(zhuǎn)到(7);

(4)變異,計(jì)算各個(gè)個(gè)體的適應(yīng)度;

(5)選擇,得到下一代群體;

(6)t=t+1,轉(zhuǎn)到(3);

(7)輸出最終群體 .

3 實(shí)例

現(xiàn)有 10個(gè)雷達(dá)站,23條可能的光纜,如圖 1所示(括號(hào)內(nèi)為光纜長(zhǎng)度),想建立一雷達(dá)網(wǎng),擬求一組光纜總長(zhǎng)度最短或次短的方案 .采用圖論中的經(jīng)典算法一般只能得到一個(gè)權(quán)為 60的最小生成樹 .應(yīng)用本文算法,參數(shù)設(shè)置如下:M=10,T=200,結(jié)果如表 1所示,可獲得 8個(gè)(1～7號(hào)個(gè)體)最小或次小生成樹(權(quán)為60～62(F0為 99),9、10號(hào)個(gè)體是隨機(jī)產(chǎn)生的,不代表生成樹),可以結(jié)合其它因素進(jìn)一步確定選擇哪一個(gè) .

表 1 最終群體

圖 1 雷達(dá)網(wǎng)初步連接圖

4 結(jié)語

本文提出了“無性生殖”的方式,豐富了遺傳算法的概念 .和已有的算法比,本文算法敘述清晰,舍棄了逆轉(zhuǎn)算子 (可能耗費(fèi)了時(shí)間,卻不能進(jìn)行逆轉(zhuǎn)),改進(jìn)了換位算子 (可能耗費(fèi)了時(shí)間,卻不能有效進(jìn)行換位),調(diào)整了選擇算子 (可以彌補(bǔ)舍棄逆轉(zhuǎn)算子的缺點(diǎn)),更簡(jiǎn)單,因而編程更容易,效率更高 (因?yàn)樯釛壛四孓D(zhuǎn)算子,改進(jìn)了換位算子,使其肯定能有效進(jìn)行).應(yīng)用時(shí)可以每隔幾代 (如 5、10代)計(jì)算一次選出的最好的不重復(fù)的個(gè)體的平均適應(yīng)度,并和上次比較,如小于某個(gè)閾值,可以考慮停止進(jìn)化,這樣更省時(shí)間 .

[1]唐策善,李龍澍,黃劉生.數(shù)據(jù)結(jié)構(gòu)[M].北京:高等教育出版社,1992,137-142.

[2]周榮敏,買文寧,雷延峰.基于遺傳算法的最小生成樹算法[J].鄭州大學(xué)學(xué)報(bào) (工學(xué)版),2002,23(1):45-48.

[3]劉志成,錢建剛.基于改進(jìn)遺傳算法的最小生成樹算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2004,25(9):1620-1622.

[4]張強(qiáng),李曉莉.交通選線優(yōu)化算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(8):226-228.

A Genetic Algorithm to Determ ine theM in imum Spann ing Tree

ZHU Yan-ting

(Department of Computer Science,Hechi Vocational College,Hechi Guangxi547000,China)

Based on graphic theory and genetic algorithm,an improved algorithm to deter mine the minimum spanning tree is given,the“asexual reproduction”method introduced,the transposition operator abandoned,the transposition operator improved,and the selection operator adjusted,which makes program easier and more efficient.Using the algorithm,we can obtain a group ofminimum or less spanning trees in a shorter time and with a higher probability,while using the traditional algorithms,we can only get a minimum spanning tree.

minimum spanning tree;genetic algorithm;optimization

TP3

A

1672-9021(2010)02-0062-04

朱彥廷 (1976—),男,遼寧建昌人,河池職業(yè)學(xué)院計(jì)算機(jī)系助教,碩士,主要研究方向:遺傳算法等.

2009-12-25

[責(zé)任編輯陽(yáng)崇波 ]