大氣污染總量控制遺傳算法的實(shí)現(xiàn)與性能優(yōu)化

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

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

中圖分類號：TP3文獻(xiàn)標(biāo)識碼：A文章編號：1671－7597（2009）0220004－02

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

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

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

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

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

3．將各污染源的源強(qiáng)編碼為字符串，作為遺傳算法操作的對象。按照遺傳算法的工作流程逐步進(jìn)化，直到找到符合要求的染色體為止。實(shí)際操作中，通?？梢詫⒂?jì)算濃度和環(huán)境標(biāo)準(zhǔn)之間的總體差異達(dá)到某個事先約定的小量作為終止進(jìn)化的條件。

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

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

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

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

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

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

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

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

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

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

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

（三）輪盤選擇模塊

輪盤選擇模塊根據(jù)個體適應(yīng)度的大小，用概率選擇法確定參與遺傳操作的個體。這種選擇機(jī)制使得適應(yīng)度大的個體有更多的繁殖機(jī)會，體現(xiàn)了適者生存的原則，它是遺傳算法的精華所在。輪盤選擇可以用如下的過程來實(shí)現(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決定選取多少個個體，被選中的個體的序號存放在全局?jǐn)?shù)組SelectedDNANo中，在此過程之外就可以對被選中的個體進(jìn)行操作，使它們獲得參與復(fù)制、交換、變異等遺傳操作的機(jī)會。在該過程中用到了上文介紹的GetRndInt函數(shù)，用來得到指定區(qū)間的隨機(jī)整數(shù)。數(shù)組ADP中保存的數(shù)據(jù)即個體的適應(yīng)度，GroupSize即群體的規(guī)模。由于每次要選擇的個體數(shù)目可能不同，為節(jié)省計(jì)算機(jī)內(nèi)存，定義了兩個動態(tài)數(shù)組SelectedDNANo和Rand，它們包含的元素個數(shù)即當(dāng)前要求選擇的個體的數(shù)目，由參數(shù)HowMany決定。

（四）遺傳操作模塊

遺傳操作模塊實(shí)現(xiàn)個體的復(fù)制、交換和變異，是遺傳算法中最核心的模塊，這些功能都是通過字符串操作來實(shí)現(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ù)組記錄被淘汰的個體的序號。因?yàn)閺?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)于父代的個體，這樣進(jìn)化就發(fā)生了。為了確定交換的片段的起始位置，用隨機(jī)數(shù)生成函數(shù)產(chǎn)生染色體長度范圍內(nèi)的兩個隨機(jī)整數(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)生出新的個體。對于二進(jì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)于父代的可能性不大，但變異能彌補(bǔ)大量個體被淘汰時造成的基因損失，增加群體的多樣性，是避免算法早熟必不可少的措施。

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

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

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

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

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

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

五、遺傳算法性能的檢驗(yàn)

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

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

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

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

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

六、結(jié)束語

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

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

參考文獻(xiàn)：

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

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

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

作者簡介：

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