大氣污染總量控制遺傳算法的實現與性能優化

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

[關鍵詞]大氣污染 總量控制 遺傳算法 程序設計 性能優化

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

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

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

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

1．確定控制區域，根據功能分區確定控制點并給出各控制點將要執行的大氣環境質量標準。通常可根據實際情況將控制區域劃分為若干行、若干列的正方形網格，控制點取在正方形網格的中心點上，對污染源則按照有效源高分為若干層。

2．選定擴散模式，用于計算控制點的污染濃度。控制點的計算濃度與執行標準之間的偏差將作為衡量遺傳算法中染色體優劣的標準，即利用這種偏差來計算個體的適應度，偏差越小，適應度越大。

3．將各污染源的源強編碼為字符串，作為遺傳算法操作的對象。按照遺傳算法的工作流程逐步進化，直到找到符合要求的染色體為止。實際操作中，通?？梢詫⒂嬎銤舛群铜h境標準之間的總體差異達到某個事先約定的小量作為終止進化的條件。

二、遺傳算法軟件的結構設計

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

該軟件包括系統初始化模塊、適應度計算模塊、輪盤選擇模塊、遺傳操作模塊和其它輔助模塊。圖1為遺傳算法軟件的結構圖，圖中給出了整個軟件的模塊組成以及它們之間的邏輯關系。

三、遺傳算法軟件的實現

（一）系統初始化模塊

系統初始化模塊完成系統參數的初始化及初始群體的生成。

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

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

int GetRndInt(int lowerbound,int upperbound){

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

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

（二）適應度計算模塊

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

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

（三）輪盤選擇模塊

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

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;}}}}

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

（四）遺傳操作模塊

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

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

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表示被選定的個體數目，DNA數組中保存的即染色體字符串，Elimination數組記錄被淘汰的個體的序號。因為復制過程中能獲得復制權的個體一般都具有較大的適應度，而淘汰的個體都是適應度很小的，所以經過一次復制，整個群體的整體適應度都有增大的趨勢。

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

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．變異。變異操作也是用輪盤選擇法選定一定數目的個體，然后讓這些個體的某些位發生突變，從而產生出新的個體。對于二進制編碼的字符串，位突變就是將“0”變為“1”，而將“1”變為“0”。程序片段如下：

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為群體中發生變異的個體的比例，Pm2為一個突變個體中發生突變的位的比例。變異得到的個體優于父代的可能性不大，但變異能彌補大量個體被淘汰時造成的基因損失，增加群體的多樣性，是避免算法早熟必不可少的措施。

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

四、遺傳算法性能的優化

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

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

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

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

五、遺傳算法性能的檢驗

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

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

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

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

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

六、結束語

本文介紹了一個用于大氣污染總量控制的遺傳算法軟件的結構設計、功能模塊實現以及性能優化技術，并給出若干關鍵模塊的詳細實現源代碼。為檢驗軟件的全局搜索尋優性能，從三個不同角度設計了檢驗方法。經性能檢

驗，本文實現的遺傳算法軟件能以高效率穩定地求得問題的全局最優解，具有很好的推廣應用前景。

參考文獻：

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

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

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

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

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

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

作者簡介：

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