王興元++侯憲鋒++董文昭++丁金存

摘 要：城市環(huán)境對人類生活和生態(tài)環(huán)境的協(xié)調(diào)有著重要意義。文章針對城市環(huán)境監(jiān)測的環(huán)境因素種類多和監(jiān)測點分布區(qū)域廣的特點，分析了遺傳算法在城市環(huán)境監(jiān)測點布局的可行性，利用遺傳算法來實現(xiàn)城市環(huán)境監(jiān)測點的布局優(yōu)化，使監(jiān)測點的監(jiān)測效率和監(jiān)測結果達到最優(yōu)化。

關鍵詞：遺傳算法；城市環(huán)境監(jiān)測；監(jiān)測點布局；遺傳算子

引言

遺傳算法是由美國的J·Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子：選擇運算、交叉運算和變異運算，對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止[1-2]。

隨著城市承載著越來越多的人口和工業(yè)化生產(chǎn)的壓力，建立全面的城市環(huán)境監(jiān)測對人類社會和生態(tài)環(huán)境的協(xié)調(diào)發(fā)展具有重要意義。但是由于城市環(huán)境監(jiān)測要考慮SO2、NOX、降塵等多個指標情況，同時監(jiān)測節(jié)點分布區(qū)域廣[3-4]，如果采用前處理優(yōu)化方法，如加權組合法等。這類方法首先通過各種方法構造評價函數(shù)把多目標問題轉(zhuǎn)化為單目標問題后再進行優(yōu)化為一個多目標的最優(yōu)解。還可以使用后處理法，利用多目標最優(yōu)解必為有效解這一事實，能夠同時生成多目標問題的所有或部分有效解。這類方法最大的優(yōu)點就是能夠讓決策者從最終的優(yōu)化結果中選出適合決策者的有效解，從而得到解決問題的最優(yōu)解。

1 遺傳算法分析

文章首先將目標地區(qū)用尺寸相同的網(wǎng)格進行劃分，每一個網(wǎng)格交點代表一個可能的布點位置。用整數(shù)對其進行編碼，在網(wǎng)格陣中，按從左到右，從上到下的順序，從網(wǎng)格陣的左上角第一個網(wǎng)格中心點開始，給每一個網(wǎng)格一個序號N（從0開始），則序號N與網(wǎng)格一一對應，全部序號點構成集合X。個體編碼方法，將預設監(jiān)測點的位置用網(wǎng)格代碼表示，將得到的代碼序列作為一種布點方案。

根據(jù)不同時間各點的數(shù)據(jù)計算各監(jiān)測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優(yōu)化布點選取。其中各網(wǎng)格監(jiān)測數(shù)據(jù)由空氣質(zhì)量模擬系統(tǒng)提供，如Models-3/CMAQ等。

為確定優(yōu)化過程中的所需的適應度函數(shù)，使用如下矩陣：

其中ai和aj分別是第i個和第j個網(wǎng)格點所對應的不同時間的綜合觀測值；n和m分別代表網(wǎng)格的行數(shù)和列數(shù)。矩陣R的非對角元越小，則說明各個監(jiān)測點的監(jiān)測結果關聯(lián)性越小，即獨立性越好，監(jiān)測點位越合理。

將優(yōu)化布點問題轉(zhuǎn)化為由目標函數(shù)和約束條件兩部分構成的最優(yōu)化問題：

其中x代表所選監(jiān)測點位置代碼序列（x1，x2，K，xM），f（x）是由x所對應的R矩陣非對角元的最大值。約束條件還包括：監(jiān)測點部署的目標地區(qū)的地形，可布點區(qū)域，用來減少網(wǎng)格數(shù)量；空間覆蓋約束，在有限的監(jiān)測點位的前提下，盡可能大地覆蓋監(jiān)測區(qū)域。

遺傳算法在進化搜索時基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，來評估解群的優(yōu)劣，并利用種群中每個個體的適應度值來進行搜索。本方案優(yōu)化的準則是搜索各個監(jiān)測點，使其對應的R矩陣的非對角元的最大值最小化，所以目標函數(shù)是最小化問題。而遺傳算法中解群的適應度為最大化問題，因此不能直接采用目標函數(shù)作為適應度函數(shù)，需應用目標函數(shù)構造一個最大化的適應度函數(shù)。由于R矩陣非對角元的最大值為1，故構造如下適應度函數(shù)：

則Fit（x）就是染色體x對應的適應度，max{Fit（x）}就是種群，即所有染色體的適應度的最大值，這樣就將目標函數(shù)的最小化問題轉(zhuǎn)化為適應度函數(shù)的最大化問題。

初始種群按照洗牌方式從監(jiān)測點集合X隨機選擇群體大小為M的節(jié)點種群，即M個監(jiān)測點的布點方式。對節(jié)點種群執(zhí)行如下的遺傳操作：選擇運算，交叉運算，變異運算。

使用下列三種遺傳算法：（1）選擇運算，實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作，適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。使用最優(yōu)保存策略，保留相關度最低的兩個監(jiān)測點；（2）交叉運算，指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換器部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產(chǎn)生新個體的主要方法。使用部分匹配交叉（PMX）算子，隨機產(chǎn)生兩個交叉點，交換交叉點中的預定監(jiān)測點，得到新的部署；（3）變異運算，根據(jù)變異概率Pm將個體編碼串中的某些基因值用其他基因值來替換，從而形成一個新的個體。在監(jiān)測點序列中隨機選取一點，與未被選中的區(qū)域中隨機一點互換[5]。

遺傳算法的4個運行參數(shù)M，T，Pc，Pm需預先設定。M為群體大小，即群體中所含個體的數(shù)量，根據(jù)網(wǎng)格實際數(shù)量給定；T為遺傳算法的終止進化代數(shù)，取T=450；Pc為交叉概率，取Pc=0.8；Pm為變異概率，取Pm=0.01。

根據(jù)上述方案運用遺傳算法進行優(yōu)化，得到最優(yōu)解序列與網(wǎng)格中位置對應，即得到最優(yōu)監(jiān)測部署點位。

2 結束語

通過對遺傳算法的分析，得出了遺傳算法在城市環(huán)境監(jiān)測點布局方面應用具有可行性。遺傳算法能夠滿足城市環(huán)境監(jiān)測點監(jiān)測的環(huán)境因素多，同時環(huán)境監(jiān)測點分布區(qū)域廣的特殊性，使城市環(huán)境監(jiān)測點的監(jiān)測效率達到最優(yōu)化，為城市環(huán)境安全監(jiān)測預警提供高效數(shù)據(jù)。

參考文獻

[1]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，10：2911-2916.

[2]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，4：1201-1206.

[3]蘇曉丹，唐立娜，董仁才.城市環(huán)境監(jiān)測結果發(fā)布系統(tǒng)的推送服務設計[J].環(huán)境科學與技術，2011，12：383-387.

[4]李偉，龔敏玉.城市環(huán)境空氣中顆粒物源解析研究[J].江蘇環(huán)境科技，2007，6：19-22.

[5]劉紅，韋穗.遺傳算子的分析[J].計算機技術與發(fā)展，2006，10：80-82.endprint

摘 要：城市環(huán)境對人類生活和生態(tài)環(huán)境的協(xié)調(diào)有著重要意義。文章針對城市環(huán)境監(jiān)測的環(huán)境因素種類多和監(jiān)測點分布區(qū)域廣的特點，分析了遺傳算法在城市環(huán)境監(jiān)測點布局的可行性，利用遺傳算法來實現(xiàn)城市環(huán)境監(jiān)測點的布局優(yōu)化，使監(jiān)測點的監(jiān)測效率和監(jiān)測結果達到最優(yōu)化。

關鍵詞：遺傳算法；城市環(huán)境監(jiān)測；監(jiān)測點布局；遺傳算子

引言

遺傳算法是由美國的J·Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子：選擇運算、交叉運算和變異運算，對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止[1-2]。

隨著城市承載著越來越多的人口和工業(yè)化生產(chǎn)的壓力，建立全面的城市環(huán)境監(jiān)測對人類社會和生態(tài)環(huán)境的協(xié)調(diào)發(fā)展具有重要意義。但是由于城市環(huán)境監(jiān)測要考慮SO2、NOX、降塵等多個指標情況，同時監(jiān)測節(jié)點分布區(qū)域廣[3-4]，如果采用前處理優(yōu)化方法，如加權組合法等。這類方法首先通過各種方法構造評價函數(shù)把多目標問題轉(zhuǎn)化為單目標問題后再進行優(yōu)化為一個多目標的最優(yōu)解。還可以使用后處理法，利用多目標最優(yōu)解必為有效解這一事實，能夠同時生成多目標問題的所有或部分有效解。這類方法最大的優(yōu)點就是能夠讓決策者從最終的優(yōu)化結果中選出適合決策者的有效解，從而得到解決問題的最優(yōu)解。

1 遺傳算法分析

文章首先將目標地區(qū)用尺寸相同的網(wǎng)格進行劃分，每一個網(wǎng)格交點代表一個可能的布點位置。用整數(shù)對其進行編碼，在網(wǎng)格陣中，按從左到右，從上到下的順序，從網(wǎng)格陣的左上角第一個網(wǎng)格中心點開始，給每一個網(wǎng)格一個序號N（從0開始），則序號N與網(wǎng)格一一對應，全部序號點構成集合X。個體編碼方法，將預設監(jiān)測點的位置用網(wǎng)格代碼表示，將得到的代碼序列作為一種布點方案。

根據(jù)不同時間各點的數(shù)據(jù)計算各監(jiān)測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優(yōu)化布點選取。其中各網(wǎng)格監(jiān)測數(shù)據(jù)由空氣質(zhì)量模擬系統(tǒng)提供，如Models-3/CMAQ等。

為確定優(yōu)化過程中的所需的適應度函數(shù)，使用如下矩陣：

其中ai和aj分別是第i個和第j個網(wǎng)格點所對應的不同時間的綜合觀測值；n和m分別代表網(wǎng)格的行數(shù)和列數(shù)。矩陣R的非對角元越小，則說明各個監(jiān)測點的監(jiān)測結果關聯(lián)性越小，即獨立性越好，監(jiān)測點位越合理。

將優(yōu)化布點問題轉(zhuǎn)化為由目標函數(shù)和約束條件兩部分構成的最優(yōu)化問題：

其中x代表所選監(jiān)測點位置代碼序列（x1，x2，K，xM），f（x）是由x所對應的R矩陣非對角元的最大值。約束條件還包括：監(jiān)測點部署的目標地區(qū)的地形，可布點區(qū)域，用來減少網(wǎng)格數(shù)量；空間覆蓋約束，在有限的監(jiān)測點位的前提下，盡可能大地覆蓋監(jiān)測區(qū)域。

遺傳算法在進化搜索時基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，來評估解群的優(yōu)劣，并利用種群中每個個體的適應度值來進行搜索。本方案優(yōu)化的準則是搜索各個監(jiān)測點，使其對應的R矩陣的非對角元的最大值最小化，所以目標函數(shù)是最小化問題。而遺傳算法中解群的適應度為最大化問題，因此不能直接采用目標函數(shù)作為適應度函數(shù)，需應用目標函數(shù)構造一個最大化的適應度函數(shù)。由于R矩陣非對角元的最大值為1，故構造如下適應度函數(shù)：

則Fit（x）就是染色體x對應的適應度，max{Fit（x）}就是種群，即所有染色體的適應度的最大值，這樣就將目標函數(shù)的最小化問題轉(zhuǎn)化為適應度函數(shù)的最大化問題。

初始種群按照洗牌方式從監(jiān)測點集合X隨機選擇群體大小為M的節(jié)點種群，即M個監(jiān)測點的布點方式。對節(jié)點種群執(zhí)行如下的遺傳操作：選擇運算，交叉運算，變異運算。

使用下列三種遺傳算法：（1）選擇運算，實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作，適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。使用最優(yōu)保存策略，保留相關度最低的兩個監(jiān)測點；（2）交叉運算，指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換器部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產(chǎn)生新個體的主要方法。使用部分匹配交叉（PMX）算子，隨機產(chǎn)生兩個交叉點，交換交叉點中的預定監(jiān)測點，得到新的部署；（3）變異運算，根據(jù)變異概率Pm將個體編碼串中的某些基因值用其他基因值來替換，從而形成一個新的個體。在監(jiān)測點序列中隨機選取一點，與未被選中的區(qū)域中隨機一點互換[5]。

遺傳算法的4個運行參數(shù)M，T，Pc，Pm需預先設定。M為群體大小，即群體中所含個體的數(shù)量，根據(jù)網(wǎng)格實際數(shù)量給定；T為遺傳算法的終止進化代數(shù)，取T=450；Pc為交叉概率，取Pc=0.8；Pm為變異概率，取Pm=0.01。

根據(jù)上述方案運用遺傳算法進行優(yōu)化，得到最優(yōu)解序列與網(wǎng)格中位置對應，即得到最優(yōu)監(jiān)測部署點位。

2 結束語

通過對遺傳算法的分析，得出了遺傳算法在城市環(huán)境監(jiān)測點布局方面應用具有可行性。遺傳算法能夠滿足城市環(huán)境監(jiān)測點監(jiān)測的環(huán)境因素多，同時環(huán)境監(jiān)測點分布區(qū)域廣的特殊性，使城市環(huán)境監(jiān)測點的監(jiān)測效率達到最優(yōu)化，為城市環(huán)境安全監(jiān)測預警提供高效數(shù)據(jù)。

參考文獻

[1]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，10：2911-2916.

[2]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，4：1201-1206.

[3]蘇曉丹，唐立娜，董仁才.城市環(huán)境監(jiān)測結果發(fā)布系統(tǒng)的推送服務設計[J].環(huán)境科學與技術，2011，12：383-387.

[4]李偉，龔敏玉.城市環(huán)境空氣中顆粒物源解析研究[J].江蘇環(huán)境科技，2007，6：19-22.

[5]劉紅，韋穗.遺傳算子的分析[J].計算機技術與發(fā)展，2006，10：80-82.endprint

摘 要：城市環(huán)境對人類生活和生態(tài)環(huán)境的協(xié)調(diào)有著重要意義。文章針對城市環(huán)境監(jiān)測的環(huán)境因素種類多和監(jiān)測點分布區(qū)域廣的特點，分析了遺傳算法在城市環(huán)境監(jiān)測點布局的可行性，利用遺傳算法來實現(xiàn)城市環(huán)境監(jiān)測點的布局優(yōu)化，使監(jiān)測點的監(jiān)測效率和監(jiān)測結果達到最優(yōu)化。

關鍵詞：遺傳算法；城市環(huán)境監(jiān)測；監(jiān)測點布局；遺傳算子

引言

遺傳算法是由美國的J·Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子：選擇運算、交叉運算和變異運算，對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止[1-2]。

隨著城市承載著越來越多的人口和工業(yè)化生產(chǎn)的壓力，建立全面的城市環(huán)境監(jiān)測對人類社會和生態(tài)環(huán)境的協(xié)調(diào)發(fā)展具有重要意義。但是由于城市環(huán)境監(jiān)測要考慮SO2、NOX、降塵等多個指標情況，同時監(jiān)測節(jié)點分布區(qū)域廣[3-4]，如果采用前處理優(yōu)化方法，如加權組合法等。這類方法首先通過各種方法構造評價函數(shù)把多目標問題轉(zhuǎn)化為單目標問題后再進行優(yōu)化為一個多目標的最優(yōu)解。還可以使用后處理法，利用多目標最優(yōu)解必為有效解這一事實，能夠同時生成多目標問題的所有或部分有效解。這類方法最大的優(yōu)點就是能夠讓決策者從最終的優(yōu)化結果中選出適合決策者的有效解，從而得到解決問題的最優(yōu)解。

1 遺傳算法分析

文章首先將目標地區(qū)用尺寸相同的網(wǎng)格進行劃分，每一個網(wǎng)格交點代表一個可能的布點位置。用整數(shù)對其進行編碼，在網(wǎng)格陣中，按從左到右，從上到下的順序，從網(wǎng)格陣的左上角第一個網(wǎng)格中心點開始，給每一個網(wǎng)格一個序號N（從0開始），則序號N與網(wǎng)格一一對應，全部序號點構成集合X。個體編碼方法，將預設監(jiān)測點的位置用網(wǎng)格代碼表示，將得到的代碼序列作為一種布點方案。

根據(jù)不同時間各點的數(shù)據(jù)計算各監(jiān)測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優(yōu)化布點選取。其中各網(wǎng)格監(jiān)測數(shù)據(jù)由空氣質(zhì)量模擬系統(tǒng)提供，如Models-3/CMAQ等。

為確定優(yōu)化過程中的所需的適應度函數(shù)，使用如下矩陣：

其中ai和aj分別是第i個和第j個網(wǎng)格點所對應的不同時間的綜合觀測值；n和m分別代表網(wǎng)格的行數(shù)和列數(shù)。矩陣R的非對角元越小，則說明各個監(jiān)測點的監(jiān)測結果關聯(lián)性越小，即獨立性越好，監(jiān)測點位越合理。

將優(yōu)化布點問題轉(zhuǎn)化為由目標函數(shù)和約束條件兩部分構成的最優(yōu)化問題：

其中x代表所選監(jiān)測點位置代碼序列（x1，x2，K，xM），f（x）是由x所對應的R矩陣非對角元的最大值。約束條件還包括：監(jiān)測點部署的目標地區(qū)的地形，可布點區(qū)域，用來減少網(wǎng)格數(shù)量；空間覆蓋約束，在有限的監(jiān)測點位的前提下，盡可能大地覆蓋監(jiān)測區(qū)域。

遺傳算法在進化搜索時基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，來評估解群的優(yōu)劣，并利用種群中每個個體的適應度值來進行搜索。本方案優(yōu)化的準則是搜索各個監(jiān)測點，使其對應的R矩陣的非對角元的最大值最小化，所以目標函數(shù)是最小化問題。而遺傳算法中解群的適應度為最大化問題，因此不能直接采用目標函數(shù)作為適應度函數(shù)，需應用目標函數(shù)構造一個最大化的適應度函數(shù)。由于R矩陣非對角元的最大值為1，故構造如下適應度函數(shù)：

則Fit（x）就是染色體x對應的適應度，max{Fit（x）}就是種群，即所有染色體的適應度的最大值，這樣就將目標函數(shù)的最小化問題轉(zhuǎn)化為適應度函數(shù)的最大化問題。

初始種群按照洗牌方式從監(jiān)測點集合X隨機選擇群體大小為M的節(jié)點種群，即M個監(jiān)測點的布點方式。對節(jié)點種群執(zhí)行如下的遺傳操作：選擇運算，交叉運算，變異運算。

使用下列三種遺傳算法：（1）選擇運算，實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作，適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。使用最優(yōu)保存策略，保留相關度最低的兩個監(jiān)測點；（2）交叉運算，指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換器部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產(chǎn)生新個體的主要方法。使用部分匹配交叉（PMX）算子，隨機產(chǎn)生兩個交叉點，交換交叉點中的預定監(jiān)測點，得到新的部署；（3）變異運算，根據(jù)變異概率Pm將個體編碼串中的某些基因值用其他基因值來替換，從而形成一個新的個體。在監(jiān)測點序列中隨機選取一點，與未被選中的區(qū)域中隨機一點互換[5]。

遺傳算法的4個運行參數(shù)M，T，Pc，Pm需預先設定。M為群體大小，即群體中所含個體的數(shù)量，根據(jù)網(wǎng)格實際數(shù)量給定；T為遺傳算法的終止進化代數(shù)，取T=450；Pc為交叉概率，取Pc=0.8；Pm為變異概率，取Pm=0.01。

根據(jù)上述方案運用遺傳算法進行優(yōu)化，得到最優(yōu)解序列與網(wǎng)格中位置對應，即得到最優(yōu)監(jiān)測部署點位。

2 結束語

通過對遺傳算法的分析，得出了遺傳算法在城市環(huán)境監(jiān)測點布局方面應用具有可行性。遺傳算法能夠滿足城市環(huán)境監(jiān)測點監(jiān)測的環(huán)境因素多，同時環(huán)境監(jiān)測點分布區(qū)域廣的特殊性，使城市環(huán)境監(jiān)測點的監(jiān)測效率達到最優(yōu)化，為城市環(huán)境安全監(jiān)測預警提供高效數(shù)據(jù)。

參考文獻

[1]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，10：2911-2916.

[2]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012，4：1201-1206.

[3]蘇曉丹，唐立娜，董仁才.城市環(huán)境監(jiān)測結果發(fā)布系統(tǒng)的推送服務設計[J].環(huán)境科學與技術，2011，12：383-387.

[4]李偉，龔敏玉.城市環(huán)境空氣中顆粒物源解析研究[J].江蘇環(huán)境科技，2007，6：19-22.

[5]劉紅，韋穗.遺傳算子的分析[J].計算機技術與發(fā)展，2006，10：80-82.endprint