基于遺傳算法的城市環境監測點布局分析

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

摘 要：城市環境對人類生活和生態環境的協調有著重要意義。文章針對城市環境監測的環境因素種類多和監測點分布區域廣的特點，分析了遺傳算法在城市環境監測點布局的可行性，利用遺傳算法來實現城市環境監測點的布局優化，使監測點的監測效率和監測結果達到最優化。

關鍵詞：遺傳算法；城市環境監測；監測點布局；遺傳算子

引言

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

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

1 遺傳算法分析

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

根據不同時間各點的數據計算各監測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優化布點選取。其中各網格監測數據由空氣質量模擬系統提供，如Models-3/CMAQ等。

為確定優化過程中的所需的適應度函數，使用如下矩陣：

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

將優化布點問題轉化為由目標函數和約束條件兩部分構成的最優化問題：

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

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

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

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

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

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

根據上述方案運用遺傳算法進行優化，得到最優解序列與網格中位置對應，即得到最優監測部署點位。

2 結束語

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

參考文獻

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

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

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

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

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

摘 要：城市環境對人類生活和生態環境的協調有著重要意義。文章針對城市環境監測的環境因素種類多和監測點分布區域廣的特點，分析了遺傳算法在城市環境監測點布局的可行性，利用遺傳算法來實現城市環境監測點的布局優化，使監測點的監測效率和監測結果達到最優化。

關鍵詞：遺傳算法；城市環境監測；監測點布局；遺傳算子

引言

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

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

1 遺傳算法分析

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

根據不同時間各點的數據計算各監測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優化布點選取。其中各網格監測數據由空氣質量模擬系統提供，如Models-3/CMAQ等。

為確定優化過程中的所需的適應度函數，使用如下矩陣：

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

將優化布點問題轉化為由目標函數和約束條件兩部分構成的最優化問題：

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

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

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

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

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

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

根據上述方案運用遺傳算法進行優化，得到最優解序列與網格中位置對應，即得到最優監測部署點位。

2 結束語

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

參考文獻

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

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

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

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

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

摘 要：城市環境對人類生活和生態環境的協調有著重要意義。文章針對城市環境監測的環境因素種類多和監測點分布區域廣的特點，分析了遺傳算法在城市環境監測點布局的可行性，利用遺傳算法來實現城市環境監測點的布局優化，使監測點的監測效率和監測結果達到最優化。

關鍵詞：遺傳算法；城市環境監測；監測點布局；遺傳算子

引言

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

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

1 遺傳算法分析

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

根據不同時間各點的數據計算各監測點結果的相關情況，選取最不相關的點作為目標點。再結合實際情況，進一步優化布點選取。其中各網格監測數據由空氣質量模擬系統提供，如Models-3/CMAQ等。

為確定優化過程中的所需的適應度函數，使用如下矩陣：

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

將優化布點問題轉化為由目標函數和約束條件兩部分構成的最優化問題：

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

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

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

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

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

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

根據上述方案運用遺傳算法進行優化，得到最優解序列與網格中位置對應，即得到最優監測部署點位。

2 結束語

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

參考文獻

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

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

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

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

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