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

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

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

引言

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

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

1 遺傳算法分析

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)束語

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

參考文獻(xiàn)

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

[2]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2012，4：1201-1206.

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

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

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

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

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

引言

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

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

1 遺傳算法分析

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)束語

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

參考文獻(xiàn)

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

[2]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2012，4：1201-1206.

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

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

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

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

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

引言

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

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

1 遺傳算法分析

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)束語

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

參考文獻(xiàn)

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

[2]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2012，4：1201-1206.

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

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

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