基于遗传算法的城市环境监测点布局分析

王兴元++侯宪锋++董文昭++丁金存

摘 要：城市环境对人类生活和生态环境的协调有着重要意义。文章针对城市环境监测的环境因素种类多和监测点分布区域广的特点，分析了遗传算法在城市环境监测点布局的可行性，利用遗传算法来实现城市环境监测点的布局优化，使监测点的监测效率和监测结果达到最优化。

关键词：遗传算法；城市环境监测；监测点布局；遗传算子

引言

遗传算法是由美国的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