摘 要：簡(jiǎn)要介紹了遺傳算法及并行遺傳算法，PVM編程環(huán)境和并行程序模式。針對(duì)任務(wù)調(diào)度與分配，在數(shù)據(jù)規(guī)模比較小的情況下，采用并行計(jì)算效果反而比較差這一問(wèn)題，采用另一種任務(wù)分配方式。通過(guò)實(shí)驗(yàn)證明，程序運(yùn)行時(shí)間有了明顯提高。

關(guān)鍵詞：并行遺傳算法；PVM；并行計(jì)算

中圖分類(lèi)號(hào)：TP391.41

遺傳算法（Genetic Algorithm，簡(jiǎn)稱(chēng)GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。美國(guó)Michigan大學(xué)的Holland教授及其學(xué)生受到生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)化的自適應(yīng)概率優(yōu)化技術(shù)[1]。但是，對(duì)于具有較大群體規(guī)模，需要對(duì)較多的個(gè)體進(jìn)行大量的遺傳和進(jìn)化操作，特別是要對(duì)大量的個(gè)體進(jìn)行適應(yīng)度計(jì)算或評(píng)價(jià)，從而使得算法的進(jìn)化運(yùn)算過(guò)程進(jìn)展緩慢，難以達(dá)到計(jì)算速度上的要求[2]。

遺傳算法具有天然的并行性，并行遺傳算法（Parallel Genetic Algorithm，簡(jiǎn)稱(chēng)PGA）可以不同程度的提高程序的運(yùn)行時(shí)間。

1 并行遺傳算法

PGA是基于各種并行計(jì)算機(jī)或局域網(wǎng)實(shí)現(xiàn)。由于平行計(jì)算機(jī)價(jià)格比較昂貴，常用的方法是采用局域網(wǎng)，將不同的計(jì)算機(jī)連接起來(lái)，通過(guò)PVM（Parallel Virtual Machine）軟件包組成像一組分布式的并行處理器。

1.1 PVM并行環(huán)境

PVM最早由美國(guó)的田納西大學(xué)，橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室以及埃默里大學(xué)開(kāi)發(fā)成功。PVM是一個(gè)源代碼公開(kāi)的、開(kāi)發(fā)和運(yùn)行并行應(yīng)用程序的軟件環(huán)境[3]。PVM是一種基于消息傳遞機(jī)制的并行編程環(huán)境，使得人們可以應(yīng)用現(xiàn)成的計(jì)算機(jī)硬件來(lái)解決復(fù)雜的問(wèn)題，而花費(fèi)并不會(huì)增加很多。

1.2 并行程序模式

PVM提供兩種基本的編程模式[4]，即Master/Slave模式和SPMD模式。實(shí)際使用中可以將任意一臺(tái)作為Master，另外兩臺(tái)作為Slave。Master和Slave在程序運(yùn)行過(guò)程中都以獨(dú)立的進(jìn)程存在。Master是主控塊，負(fù)責(zé)分配任務(wù)和接收結(jié)果，協(xié)調(diào)各Slave之間與Master通信和同步正常。Slave從屬塊完成子任務(wù)的計(jì)算，并將結(jié)果返回給Master。

Master主控塊程序

（1）初始化種群，設(shè)置最大進(jìn)化代數(shù)T，設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0。采用實(shí)數(shù)編碼，隨機(jī)生成M個(gè)個(gè)體組成的初始種群P（t），并求出各個(gè)個(gè)體的適應(yīng)度，同時(shí)選出最好的個(gè)體。

（2）選擇運(yùn)算。采用隨機(jī)聯(lián)賽選擇方式，對(duì)種群P（t）進(jìn)行選擇運(yùn)算，得到種群p（t）’。

（3）交叉操作。以概率Pc對(duì)種群p（t）’進(jìn)行單點(diǎn)交叉運(yùn)算，得到種群p（t）”。

（4）變異操作。以概率Pm對(duì)種群p（t）’’進(jìn)行隨機(jī)均勻交叉運(yùn)算，得到種群p（t）”’。

（5）PVM并行計(jì)算。將計(jì)算個(gè)體適應(yīng)度值并行計(jì)算，由Master統(tǒng)一分配任務(wù)，接收Slave返回的結(jié)果。

（6）終止條件判斷。若：更新進(jìn)化迭代計(jì)數(shù)器t=t+1，然后轉(zhuǎn)到第（2）步；若：t>T則輸出結(jié)果，計(jì)算結(jié)束。

Slave從屬塊程序

（1）初始化PVM，等待Master發(fā)來(lái)的數(shù)據(jù)。

（2）根據(jù)接收的數(shù)據(jù)計(jì)算出個(gè)體適應(yīng)度。

（3）將計(jì)算的結(jié)果返回給Master。

2 任務(wù)調(diào)度與分配

PVM對(duì)任務(wù)分配和負(fù)載平衡方面沒(méi)有提供很多的支持，這個(gè)工作留給了程序設(shè)計(jì)員[5]，但是PVM的任務(wù)分配可以采用靜態(tài)分配和動(dòng)態(tài)分配兩種方法。動(dòng)態(tài)分配根據(jù)計(jì)算機(jī)的計(jì)算能力來(lái)分配任務(wù)，充分發(fā)揮了各臺(tái)計(jì)算機(jī)的性能。因此通常采用動(dòng)態(tài)分配，任務(wù)分配過(guò)程見(jiàn)圖1。

2.1 單個(gè)數(shù)據(jù)分配

在Master分配數(shù)據(jù)給Slave時(shí)，當(dāng)數(shù)據(jù)規(guī)模比較大時(shí)，常采用Master每次分配一個(gè)個(gè)體給Slave計(jì)算，這樣可以充分利用Slave來(lái)計(jì)算適應(yīng)度值。但是，當(dāng)數(shù)據(jù)規(guī)模比較小時(shí)，采用上述方法，花費(fèi)在通訊和等待的時(shí)間較多，反而效率降低。通過(guò)改進(jìn)，采用多個(gè)數(shù)據(jù)分配，每次Master分配多個(gè)個(gè)體給Slave計(jì)算。

2.2 多個(gè)數(shù)據(jù)分配

在Master分配數(shù)據(jù)給Slave時(shí)，設(shè)置分配的個(gè)體數(shù)為N，這樣每次分配N(xiāo)個(gè)個(gè)體給Slave計(jì)算，如果在數(shù)據(jù)規(guī)模比較小時(shí)，可以減少通信時(shí)間，加快程序的運(yùn)行速度，增加程序設(shè)計(jì)的靈活性，方便實(shí)驗(yàn)算例的需要，通過(guò)任意設(shè)置N的值，進(jìn)而得到程序運(yùn)行時(shí)間的提高。當(dāng)然，N的值要取的適中，如果N的值太小，就相當(dāng)于單個(gè)數(shù)據(jù)分配，如果N的值過(guò)大，會(huì)影響整個(gè)任務(wù)分配，使得有些Slave得不到充分的利用。

3 算例

實(shí)驗(yàn)環(huán)境采用兩臺(tái)PC機(jī)，其配置是第一臺(tái)是P4 2.66GHz，512M內(nèi)存，第二臺(tái)是P4 2.80GHz，1G內(nèi)存。分別對(duì)單個(gè)數(shù)據(jù)分配，多個(gè)數(shù)據(jù)分配做比較實(shí)驗(yàn)，程序在VC6.0環(huán)境下編寫(xiě)。實(shí)驗(yàn)算例如下：

例一：Minimize

?（x）=（x1-10）2+5（x2-12）2+x34+3（x4-11）2+10x56+7x62+x74+4x6x7-10x6+8x7

Subject to g1（x）=127-2x12-3x24-x3+4x42-5x5≥0

g2（x）=282-7x1-3x2-10x32-x4+x5≥0

g3（x）=196-23x1-x22-6x62+8x7≥0

g4（x）=-4x12-x22+3x1x2-2x32-5x6+11x7≥0

-10≤xi≤10，i=1，…，7

問(wèn)題的全局最優(yōu)解是：

x*=（2.330499，1.951372，-0.4775414，4.365726，-0.6244870，1.038131，1.594227）；

?（x*）=680.6300573

例二：Minimize

?（x）=x12+x22+x1x2-14x1-16x2+（x3-10）2+4（x4-5）2+（x5-3）2+2（x6-1）2+5x72+7（x8-11）2+2（x9-10）2+（x10-7）+45

Subject to g1（x）=105-4x1-5x2+3x7-9x8≥0

g2（x）=-10x1+8x2+17x7-2x8≥0

g3（x）=8x1-2x2-5x9+2x10+12≥0

g4（x）=-3（x1-2）2-4（x2-3）2-2x32+7x4+120≥0

g5（x）=-5x12-8x2-（x3-6）2+2x4+40≥0

g6（x）=-x12-2（x2-2）2+2x1x2-14x5+6x6≥0

g7（x）=-0.5（x1-8）2-2（x2-4）2-3x52+x6+30≥0

g8（x）=3x1-6x2-12（x9-8）+7x10≥0

-10≤xi≤10，i=1，…，10

問(wèn)題的全局最優(yōu)解是：

x*=（2.171996，2.363683，8.773926，5.095984，0.9906548，1.430574，1.321644，9.828726，8.280092，8.375927）；

?（x）=24.3062091；

首先，對(duì)算例的兩個(gè)例子進(jìn)行單個(gè)數(shù)據(jù)分配的實(shí)驗(yàn)，取遺傳的代數(shù)250，種群個(gè)體150，交叉率0.8，變異率0.15，實(shí)驗(yàn)結(jié)果見(jiàn)表1。

下面采用多個(gè)數(shù)據(jù)分配方式，每次分配的任務(wù)數(shù)是N，設(shè)N=10，其他參數(shù)和上面一樣，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

4 結(jié)束語(yǔ)

文中介紹了基于PVM并行遺傳算法的實(shí)現(xiàn)，主要針對(duì)在數(shù)據(jù)規(guī)模比較小的情況下，對(duì)任務(wù)分配和調(diào)度做了一些探討，分別采用單個(gè)數(shù)據(jù)分配和多個(gè)數(shù)據(jù)分配進(jìn)行比較，通過(guò)實(shí)驗(yàn)得到，文中的方法對(duì)程序運(yùn)行速度有了很大提高。

參考文獻(xiàn)：

[1]雷英杰，張善文，等.遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.

[2]謝克家，劉昕，等.多核計(jì)算環(huán)境下改進(jìn)的主從式并行遺傳算法[J].微計(jì)算機(jī)信息，2011，9-3：164-166.

[3]吳維剛，董小社，何戈.基于機(jī)群系統(tǒng)的PVM 并行編程技術(shù)研究[J].計(jì)算機(jī)應(yīng)用研究，2003，2：21-23.

[4]GA Geist，A Beguelin，etal.PVM 3.0 User’s Guide and Reference Manual [M].USA：Oak Ridge National Laboratory，1994：27-34.

[5]張建軍，蔣廷耀，郭志鑫.PVM 中動(dòng)態(tài)負(fù)載平衡的設(shè)計(jì)和實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2005（7）：63-64.

作者簡(jiǎn)介：張繼成（1984-），男，河南信陽(yáng)人，講師，碩士，主要研究方向：高性能計(jì)算與網(wǎng)絡(luò)系統(tǒng)（bobzhangjc@163.com）；申文杰（1981-），男，山西高平人，碩士，主要研究方向：并行分布式計(jì)算和優(yōu)化算法。