[摘要]介紹基于遺傳算法的大氣污染總量控制方法中遺傳算法軟件的結(jié)構(gòu)設(shè)計、功能模塊實現(xiàn)與性能優(yōu)化技術(shù)，并給出若干關(guān)鍵功能模塊的完整實現(xiàn)代碼。對該軟件進行性能檢驗的結(jié)果表明，該軟件能穩(wěn)定地求得問題的全局最優(yōu)解，具有很好的推廣應(yīng)用前景。

[關(guān)鍵詞]大氣污染 總量控制 遺傳算法 程序設(shè)計 性能優(yōu)化

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0220004－02

大氣污染總量控制（Atmospheric Pollutant Total Emission Control，APTEC）是我國目前正在積極推行的一種先進的大氣污染防治策略[1,2]，它以大氣環(huán)境容量為依據(jù)，控制給定區(qū)域內(nèi)大氣污染物的允許排放總量，并且優(yōu)化分配到各污染源，從而確保該區(qū)域能實現(xiàn)大氣環(huán)境質(zhì)量目標[1-3]?；谶z傳算法的大氣污染總量控制方法[4,5]是利用遺傳算法（Genetic Algorithm，GA）的全局搜索尋優(yōu)功能[6]，從地面控制點濃度來反推源強分布，從而得到經(jīng)過全局優(yōu)化的區(qū)域大氣污染總量控制方案的一種新的大氣污染總量控制技術(shù)。本文介紹基于遺傳算法的大氣污染總量控制方法中遺傳算法軟件的結(jié)構(gòu)設(shè)計、編程實現(xiàn)與性能優(yōu)化技術(shù)，并對其獲取全局最優(yōu)解的穩(wěn)定性進行必要的檢驗。

一、遺傳算法用于大氣污染總量控制的基本原理

在基于遺傳算法的大氣污染總量控制中，設(shè)總量控制區(qū)域中有M個污染源，在該區(qū)域中選定N個有代表性的控制點。我們約定，在總量控制區(qū)內(nèi)確定的這N個控制點用來確定整個區(qū)域的總量控制是否達到了控制標準，即只要這N個點達到了控制標準，則整個控制區(qū)域也就達到了控制標準。于是，一旦風(fēng)向、風(fēng)速、穩(wěn)定度等影響因子確定了，則控制點的濃度由污染源的源強確定。改變各源的排污負荷分配，就會得到一個對應(yīng)的濃度場。為了充分利用大氣環(huán)境容量，我們希望區(qū)域允許排放總量達到最大，則應(yīng)該使各控制點的實際污染濃度嚴格趨于標準濃度值。因為若某控制點的實際污染濃度低于標準濃度值，則可以認為該點所能代表的空間里還存在著剩余的環(huán)境容量沒有得到有效的利用；相反，若實際污染濃度超過標準濃度值，則無疑是不符合大氣污染總量控制的要求的。這樣，在風(fēng)向、風(fēng)速、穩(wěn)定度等影響到大氣污染物擴散的因子確定了的情況下，如果能夠找到某一種源強布局，使各個控制點的污染濃度正好等于它們所執(zhí)行的大氣環(huán)境質(zhì)量標準，則認為此源強布局即為當(dāng)前氣象條件下最佳的源強布局，亦即總量控制問題的最優(yōu)可行解。用遺傳算法求算這一最優(yōu)可行解的步驟是：

1．確定控制區(qū)域，根據(jù)功能分區(qū)確定控制點并給出各控制點將要執(zhí)行的大氣環(huán)境質(zhì)量標準。通?？筛鶕?jù)實際情況將控制區(qū)域劃分為若干行、若干列的正方形網(wǎng)格，控制點取在正方形網(wǎng)格的中心點上，對污染源則按照有效源高分為若干層。

2．選定擴散模式，用于計算控制點的污染濃度?？刂泣c的計算濃度與執(zhí)行標準之間的偏差將作為衡量遺傳算法中染色體優(yōu)劣的標準，即利用這種偏差來計算個體的適應(yīng)度，偏差越小，適應(yīng)度越大。

3．將各污染源的源強編碼為字符串，作為遺傳算法操作的對象。按照遺傳算法的工作流程逐步進化，直到找到符合要求的染色體為止。實際操作中，通常可以將計算濃度和環(huán)境標準之間的總體差異達到某個事先約定的小量作為終止進化的條件。

二、遺傳算法軟件的結(jié)構(gòu)設(shè)計

為了將遺傳算法用于大氣污染總量控制，需要設(shè)計遺傳算法軟件。一般說來，選用什么樣的編程語言并不重要，在常用的各種編程平臺上都可以達到這一目的。但從軟件的通用性和簡捷性考慮，我們選用了比較容易掌握且擁有龐大用戶群的Microsoft Visual C#.NET語言，開發(fā)了一個通用的遺傳算法應(yīng)用軟件系統(tǒng)。

該軟件包括系統(tǒng)初始化模塊、適應(yīng)度計算模塊、輪盤選擇模塊、遺傳操作模塊和其它輔助模塊。圖1為遺傳算法軟件的結(jié)構(gòu)圖，圖中給出了整個軟件的模塊組成以及它們之間的邏輯關(guān)系。

三、遺傳算法軟件的實現(xiàn)

（一）系統(tǒng)初始化模塊

系統(tǒng)初始化模塊完成系統(tǒng)參數(shù)的初始化及初始群體的生成。

1．系統(tǒng)參數(shù)初始化。系統(tǒng)參數(shù)包括群體規(guī)模、進化代數(shù)、目標精度、染色體長度、復(fù)制概率、交換概率、變異概率等，在系統(tǒng)啟動時從磁盤文件中讀入，在進化過程中允許對它們進行動態(tài)調(diào)整，以達到提高進化效率的目的。

2．初始群體的生成。初始群體的生成主要依靠一個隨機數(shù)生成函數(shù)GetRndInt：

int GetRndInt(int lowerbound,int upperbound){

Random ra=new Random();return (int)((upperbound-lowerbound+1)*ra.NextDouble()+lowerbound);}

該函數(shù)獲得某一區(qū)間內(nèi)的隨機整數(shù)，其中l(wèi)owerbound為下限，upperbound為上限。Random使用與時間相關(guān)的默認種子值，初始化 Random 類的新實例。NextDouble()函數(shù)返回大于或等于0.0而小于1.0的雙精度浮點數(shù)字。對污染物的源強而言，其下限為0，上限可以根據(jù)擴散模式初步估算出來，它與源高、擴散參數(shù)、氣象條件及所執(zhí)行的大氣環(huán)境質(zhì)量標準有關(guān)，面積為1km2的面源的二氧化硫年允許排放量上限通常為幾百噸。如果用二進制編碼，基因長度可取為9，則最大源強為29-1=511噸。如果要精確到0.1噸或0.01噸，可以將源強放大10倍或100倍編碼，仍用整數(shù)來表示源強，隱含一到兩位小數(shù)，在使用源強計算濃度時再還原為原來的小數(shù)（乘以0.1或0.01）即可。這樣做的好處在于：一方面編碼方便，可以不處理小數(shù)點；另一方面整型數(shù)占用內(nèi)存較少，而且處理整型數(shù)總是比處理浮點數(shù)要快，在能用整數(shù)的地方盡量用整數(shù)，可以加快軟件的運行速度。

（二）適應(yīng)度計算模塊

適應(yīng)度的計算非常重要，因為它是遺傳算法能夠利用的唯一信息，它實際上是遺傳進化的根本驅(qū)動力。計算適應(yīng)度面臨的最大困難是適應(yīng)度的離散程度不好把握。如果適應(yīng)度不具有一定的離散程度，遺傳算法對個體的選擇將趨于盲目，進化過程將趨于停滯狀態(tài)；而如果適應(yīng)度過于離散，適應(yīng)度大的個體將很快充斥整個群體，適應(yīng)度小的個體將很快被滅絕，基因的多樣性喪失，其后果是遺傳算法早熟，也就是陷于局部極小而無法搜索出全局最優(yōu)的個體。

所以，適應(yīng)度的計算有很高的技巧，很多文獻都對此進行了研究，提出了一些改進措施，如縮放適應(yīng)函數(shù)[10]、用線性或非線性加速適應(yīng)函數(shù)取代簡單適應(yīng)函數(shù)[9]以及引入排序適應(yīng)函數(shù)[9]等等。但是，在實踐中我們發(fā)現(xiàn)，針對一個具體的問題，適應(yīng)度函數(shù)應(yīng)該有其自身的特色，不能生搬硬套，往往要根據(jù)實際問題的特點來精心設(shè)計，并且反復(fù)嘗試，才有可能找到比較合適的適應(yīng)度計算方法。在大氣污染總量控制中，我們考慮全部控制點的計算濃度與環(huán)境質(zhì)量標準整體上的接近程度，整體接近程度越高，個體越優(yōu)良，其適應(yīng)度也越大。在實際操作中，還必須對群體的適應(yīng)度作動態(tài)的跟蹤和分析，適時調(diào)整適應(yīng)度的計算方法或者參數(shù)，使適應(yīng)度總是落在某個區(qū)間且離散程度合理。當(dāng)變異個體的適應(yīng)度很低時，也可以考慮人為賦給一個相對小的適應(yīng)度，使它既不至于很活躍，又不至于完全迅速滅絕，這樣對保持群體的多樣性是有益的。

（三）輪盤選擇模塊

輪盤選擇模塊根據(jù)個體適應(yīng)度的大小，用概率選擇法確定參與遺傳操作的個體。這種選擇機制使得適應(yīng)度大的個體有更多的繁殖機會，體現(xiàn)了適者生存的原則，它是遺傳算法的精華所在。輪盤選擇可以用如下的過程來實現(xiàn)：

void WheelSelect(int HowMany){

int [] SelectedDNANo=new int [HowMany];int [] Rand=new int [HowMany];int i,j,Upbound;Upbound=0;

for(int i=1;i

for(int i=1;i

for(int j=1;j

if(Upbound>=Rand[j]){SelectedDNANo[j]=i;}}}}

在這個過程中，根據(jù)參數(shù)HowMany決定選取多少個個體，被選中的個體的序號存放在全局數(shù)組SelectedDNANo中，在此過程之外就可以對被選中的個體進行操作，使它們獲得參與復(fù)制、交換、變異等遺傳操作的機會。在該過程中用到了上文介紹的GetRndInt函數(shù)，用來得到指定區(qū)間的隨機整數(shù)。數(shù)組ADP中保存的數(shù)據(jù)即個體的適應(yīng)度，GroupSize即群體的規(guī)模。由于每次要選擇的個體數(shù)目可能不同，為節(jié)省計算機內(nèi)存，定義了兩個動態(tài)數(shù)組SelectedDNANo和Rand，它們包含的元素個數(shù)即當(dāng)前要求選擇的個體的數(shù)目，由參數(shù)HowMany決定。

（四）遺傳操作模塊

遺傳操作模塊實現(xiàn)個體的復(fù)制、交換和變異，是遺傳算法中最核心的模塊，這些功能都是通過字符串操作來實現(xiàn)的。

1．復(fù)制。首先根據(jù)復(fù)制概率和群體規(guī)模確定將取得復(fù)制權(quán)的個體數(shù)目，再用輪盤選擇法選出待復(fù)制的優(yōu)良個體，然后從適應(yīng)度最小的個體開始，在群體中依次淘汰相等數(shù)目的劣質(zhì)個體，代之以剛剛獲選的優(yōu)良個體，就完成了優(yōu)良個體的復(fù)制過程。程序片段如下：

int Chosen=Pr*GroupSize;WheelSelect(Chosen);for(int g=1;g

h=0;MinDat=3276666;for(int k=1;k

MinDat){MinDat=ADP[k];h=k;}

Elimination[g]=h;DNA[Elimination[g]]=DNA[SelectedDNANo[g]];ADP[Elimination[g]]=ADP[SelectedDNANo[g]];}

其中Chosen表示被選定的個體數(shù)目，DNA數(shù)組中保存的即染色體字符串，Elimination數(shù)組記錄被淘汰的個體的序號。因為復(fù)制過程中能獲得復(fù)制權(quán)的個體一般都具有較大的適應(yīng)度，而淘汰的個體都是適應(yīng)度很小的，所以經(jīng)過一次復(fù)制，整個群體的整體適應(yīng)度都有增大的趨勢。

2．交換。與復(fù)制類似，我們希望參與交換的個體都具有優(yōu)良的基因，所以仍然用輪盤選擇法確定參與交換的個體，再讓這些個體兩兩交叉，互換某個基因片段，從而產(chǎn)生兩個新的個體，即雜交的后代。由于雙親攜帶優(yōu)良基因，后代中可能會出現(xiàn)優(yōu)于父代的個體，這樣進化就發(fā)生了。為了確定交換的片段的起始位置，用隨機數(shù)生成函數(shù)產(chǎn)生染色體長度范圍內(nèi)的兩個隨機整數(shù)，將序號位于這兩個數(shù)之間的字符子串交換即可。程序片段如下：

Sel1=GetRndInt(1,DNALen);Sel2=GetRndInt(1,DNALen);if(Sel1>Sel2){Sel0=Sel1;Sel1=Sel2;Sel2=Sel0;}

If(j<=Chosen-1){SelStr=Substring(DNA[SelectedDNANo[j]],Sel1,Sel2-Sel1+1);

Substring(DNA[SelectedDNANo[j]],Sel1,Sel2-Sel1+1)=Substring(DNA[SelectedDNANo[j+1]],Sel1,Sel2-Sel1+1);

Substring(DNA[SelectedDNANo[j+1]],Sel1,Sel2-Sel1+1)=SelStr;}

3．變異。變異操作也是用輪盤選擇法選定一定數(shù)目的個體，然后讓這些個體的某些位發(fā)生突變，從而產(chǎn)生出新的個體。對于二進制編碼的字符串，位突變就是將“0”變?yōu)椤?”，而將“1”變?yōu)椤?”。程序片段如下：

int Chosen=Pm1*GroupSize;WheelSelect(Chosen);for(int j=1;j

for(int h=1;h

if(Substring(DNA[SelectedDNANo[j]],h,1)=="0"){Substring(DNA[SelectedDNANo[j]],h,1)="1";}

else{Substring(DNA[SelectedDNANo[j]],h,1)="0";}}}}

其中Pm1為群體中發(fā)生變異的個體的比例，Pm2為一個突變個體中發(fā)生突變的位的比例。變異得到的個體優(yōu)于父代的可能性不大，但變異能彌補大量個體被淘汰時造成的基因損失，增加群體的多樣性，是避免算法早熟必不可少的措施。

4．輔助模塊。以上各模塊是遺傳算法軟件中的主要的功能模塊，但是，為了提高程序的性能，還需要有一些輔助模塊的支持，這些輔助模塊包括對群體適應(yīng)度的動態(tài)監(jiān)控模塊、系統(tǒng)參數(shù)自動調(diào)整模塊、自動存盤和用戶干預(yù)進化過程的操作相應(yīng)模塊等。

四、遺傳算法性能的優(yōu)化

為了提高遺傳算法的性能，本文采取了以下幾個方面的優(yōu)化措施：

1．通過對群體適應(yīng)度的動態(tài)跟蹤，可以實時地調(diào)整適應(yīng)度的計算方法和參數(shù)，這樣使遺傳算法既具有一定的進化動力又不會因早熟而陷于局部極小。具體做法是，動態(tài)跟蹤適應(yīng)度值，自動繪制適應(yīng)度變化曲線，當(dāng)適應(yīng)度值調(diào)整不明顯時，通過軟件界面調(diào)整計算方法和參數(shù)。這種調(diào)整立即生效而且同時被記錄在參數(shù)文件中。

2．可以實現(xiàn)各種參數(shù)的自動調(diào)節(jié)，保證遺傳進化過程的穩(wěn)步進行。例如在遺傳算法進化的后期，變異個體具有很小的適應(yīng)度，導(dǎo)致群體無法收斂，此時可以減小變異的概率，在編程時可以將變異概率設(shè)計為隨著進化代數(shù)增加而逐漸減小或者隨著最大適應(yīng)度的增大而趨于零的動態(tài)因子，這樣改善了整個遺傳算法的性能，提高了解的質(zhì)量。

3．遺傳進化過程可以隨時中斷，下次可以在中斷處繼續(xù)進行。由于遺傳算法的進化過程可能比較長，該項措施具有重要的實際意義。軟件每隔一定時間將把進化結(jié)果及環(huán)境參數(shù)自動保存到磁盤上，即使系統(tǒng)因掉電或機器故障等原因異常中止，前面的工作也不會白費，系統(tǒng)在下次運行時將自動找到上次運行中斷處繼續(xù)運行。

五、遺傳算法性能的檢驗

本文對上述遺傳算法軟件進行了性能檢驗。對最優(yōu)解已知的問題，我們只需檢驗進化的結(jié)果與期望的最優(yōu)解的逼近程度就可以斷定軟件的性能如何，但如果問題的最優(yōu)解未知且不可預(yù)測，對程序進行性能的檢驗就比較困難了。對大氣污染總量控制問題，我們采用如下的方法來檢驗遺傳算法的性能：

1．如果遺傳算法收斂于全局最優(yōu)解，我們得到的源強分布應(yīng)該是最優(yōu)的，一方面可以反過來用多源模式進行計算，看在這樣的源強分布下是否真正能達到預(yù)期的環(huán)境質(zhì)量目標，即各控制點的計算濃度是否在總體上趨于所執(zhí)行的大氣環(huán)境質(zhì)量標準；另一方面可以在進化所得最優(yōu)源強上施加隨機的微小的人為變化，看各控制點的污染濃度是否在整體上偏離環(huán)境標準更遠。如果這兩項檢驗都通過，可以初步斷定遺傳算法收斂于全局最優(yōu)，性能可靠。

2．如果遺傳算法所得結(jié)果為全局最優(yōu)解，則它應(yīng)該與進化的起點無關(guān)，所以可以嘗試從不同的起點開始進化，如從實際排放量開始，從純隨機數(shù)開始，將所有源強都置為零開始，等等，如果都能得到相同的解，則該解應(yīng)為全局最優(yōu)解，軟件性能可靠。當(dāng)然，從不同起點開始進化所花時間是不一樣的。

3．如果遺傳算法的進化結(jié)果是全局最優(yōu)解，則它與染色體的編碼方式無關(guān)，我們分別采用二進制編碼和十進制編碼，若得到相同結(jié)果，則可以斷定該解確實是全局最優(yōu)解。

本文結(jié)合大氣污染總量控制實例對遺傳算法軟件進行了上述3個方面的性能檢驗，結(jié)果表明，應(yīng)用該軟件確實能求得問題的全局最優(yōu)解，該軟件系統(tǒng)的性能是穩(wěn)定的。

六、結(jié)束語

本文介紹了一個用于大氣污染總量控制的遺傳算法軟件的結(jié)構(gòu)設(shè)計、功能模塊實現(xiàn)以及性能優(yōu)化技術(shù)，并給出若干關(guān)鍵模塊的詳細實現(xiàn)源代碼。為檢驗軟件的全局搜索尋優(yōu)性能，從三個不同角度設(shè)計了檢驗方法。經(jīng)性能檢

驗，本文實現(xiàn)的遺傳算法軟件能以高效率穩(wěn)定地求得問題的全局最優(yōu)解，具有很好的推廣應(yīng)用前景。

參考文獻：

[1]馬小明、李詩剛、欒勝基等，大氣污染總量控制方案的區(qū)域排放當(dāng)量制定方法[J].中國環(huán)境科學(xué)，1996,16(5):350-353.

[2]王金南、潘向忠，線性規(guī)劃方法在環(huán)境容量資源分配中的應(yīng)用[J].環(huán)境科學(xué)，2005,26(6):195-198.

[3]劉品高，基于遺傳算法的大氣污染總量控制方法研究[D].南京：南京氣象學(xué)院，2001.

[4]馬思紅，遺傳算法的改進與應(yīng)用[J].電腦知識與技術(shù)，2008,4(6):1461-1462,1468.

[5]高揚、王玉姣，基于改進遺傳算法的移動機器人路徑規(guī)劃[J].電腦知識與技術(shù)，2008,4(4):951-953.

基金項目：湖南省科技計劃項目（2008SK3138）和湖南省氣象局科研課題（200910）共同資助。

作者簡介：

劉品高,男，湖南省桃江縣人，高級工程師，博士，主要研究方向為大氣環(huán)境與氣候變化、應(yīng)用氣象、氣象信息系統(tǒng)等。