大气污染总量控制遗传算法的实现与性能优化

2009-03-14刘品高

新媒体研究 2009年4期

[摘要]介绍基于遗传算法的大气污染总量控制方法中遗传算法软件的结构设计、功能模块实现与性能优化技术，并给出若干关键功能模块的完整实现代码。对该软件进行性能检验的结果表明，该软件能稳定地求得问题的全局最优解，具有很好的推广应用前景。

[关键词]大气污染总量控制遗传算法程序设计性能优化

中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0220004－02

大气污染总量控制（Atmospheric Pollutant Total Emission Control，APTEC）是我国目前正在积极推行的一种先进的大气污染防治策略[1,2]，它以大气环境容量为依据，控制给定区域内大气污染物的允许排放总量，并且优化分配到各污染源，从而确保该区域能实现大气环境质量目标[1-3]。基于遗传算法的大气污染总量控制方法[4,5]是利用遗传算法（Genetic Algorithm，GA）的全局搜索寻优功能[6]，从地面控制点浓度来反推源强分布，从而得到经过全局优化的区域大气污染总量控制方案的一种新的大气污染总量控制技术。本文介绍基于遗传算法的大气污染总量控制方法中遗传算法软件的结构设计、编程实现与性能优化技术，并对其获取全局最优解的稳定性进行必要的检验。

一、遗传算法用于大气污染总量控制的基本原理

在基于遗传算法的大气污染总量控制中，设总量控制区域中有M个污染源，在该区域中选定N个有代表性的控制点。我们约定，在总量控制区内确定的这N个控制点用来确定整个区域的总量控制是否达到了控制标准，即只要这N个点达到了控制标准，则整个控制区域也就达到了控制标准。于是，一旦风向、风速、稳定度等影响因子确定了，则控制点的浓度由污染源的源强确定。改变各源的排污负荷分配，就会得到一个对应的浓度场。为了充分利用大气环境容量，我们希望区域允许排放总量达到最大，则应该使各控制点的实际污染浓度严格趋于标准浓度值。因为若某控制点的实际污染浓度低于标准浓度值，则可以认为该点所能代表的空间里还存在着剩余的环境容量没有得到有效的利用；相反，若实际污染浓度超过标准浓度值，则无疑是不符合大气污染总量控制的要求的。这样，在风向、风速、稳定度等影响到大气污染物扩散的因子确定了的情况下，如果能够找到某一种源强布局，使各个控制点的污染浓度正好等于它们所执行的大气环境质量标准，则认为此源强布局即为当前气象条件下最佳的源强布局，亦即总量控制问题的最优可行解。用遗传算法求算这一最优可行解的步骤是：

1．确定控制区域，根据功能分区确定控制点并给出各控制点将要执行的大气环境质量标准。通常可根据实际情况将控制区域划分为若干行、若干列的正方形网格，控制点取在正方形网格的中心点上，对污染源则按照有效源高分为若干层。

2．选定扩散模式，用于计算控制点的污染浓度。控制点的计算浓度与执行标准之间的偏差将作为衡量遗传算法中染色体优劣的标准，即利用这种偏差来计算个体的适应度，偏差越小，适应度越大。

3．将各污染源的源强编码为字符串，作为遗传算法操作的对象。按照遗传算法的工作流程逐步进化，直到找到符合要求的染色体为止。实际操作中，通常可以将计算浓度和环境标准之间的总体差异达到某个事先约定的小量作为终止进化的条件。

二、遗传算法软件的结构设计

为了将遗传算法用于大气污染总量控制，需要设计遗传算法软件。一般说来，选用什么样的编程语言并不重要，在常用的各种编程平台上都可以达到这一目的。但从软件的通用性和简捷性考虑，我们选用了比较容易掌握且拥有庞大用户群的Microsoft Visual C#.NET语言，开发了一个通用的遗传算法应用软件系统。

该软件包括系统初始化模块、适应度计算模块、轮盘选择模块、遗传操作模块和其它辅助模块。图1为遗传算法软件的结构图，图中给出了整个软件的模块组成以及它们之间的逻辑关系。

三、遗传算法软件的实现

（一）系统初始化模块

系统初始化模块完成系统参数的初始化及初始群体的生成。

1．系统参数初始化。系统参数包括群体规模、进化代数、目标精度、染色体长度、复制概率、交换概率、变异概率等，在系统启动时从磁盘文件中读入，在进化过程中允许对它们进行动态调整，以达到提高进化效率的目的。

2．初始群体的生成。初始群体的生成主要依靠一个随机数生成函数GetRndInt：

int GetRndInt(int lowerbound,int upperbound){

Random ra=new Random();return (int)((upperbound-lowerbound+1)*ra.NextDouble()+lowerbound);}

该函数获得某一区间内的随机整数，其中lowerbound为下限，upperbound为上限。Random使用与时间相关的默认种子值，初始化 Random 类的新实例。NextDouble()函数返回大于或等于0.0而小于1.0的双精度浮点数字。对污染物的源强而言，其下限为0，上限可以根据扩散模式初步估算出来，它与源高、扩散参数、气象条件及所执行的大气环境质量标准有关，面积为1km2的面源的二氧化硫年允许排放量上限通常为几百吨。如果用二进制编码，基因长度可取为9，则最大源强为29-1=511吨。如果要精确到0.1吨或0.01吨，可以将源强放大10倍或100倍编码，仍用整数来表示源强，隐含一到两位小数，在使用源强计算浓度时再还原为原来的小数（乘以0.1或0.01）即可。这样做的好处在于：一方面编码方便，可以不处理小数点；另一方面整型数占用内存较少，而且处理整型数总是比处理浮点数要快，在能用整数的地方尽量用整数，可以加快软件的运行速度。

（二）适应度计算模块

适应度的计算非常重要，因为它是遗传算法能够利用的唯一信息，它实际上是遗传进化的根本驱动力。计算适应度面临的最大困难是适应度的离散程度不好把握。如果适应度不具有一定的离散程度，遗传算法对个体的选择将趋于盲目，进化过程将趋于停滞状态；而如果适应度过于离散，适应度大的个体将很快充斥整个群体，适应度小的个体将很快被灭绝，基因的多样性丧失，其后果是遗传算法早熟，也就是陷于局部极小而无法搜索出全局最优的个体。

所以，适应度的计算有很高的技巧，很多文献都对此进行了研究，提出了一些改进措施，如缩放适应函数[10]、用线性或非线性加速适应函数取代简单适应函数[9]以及引入排序适应函数[9]等等。但是，在实践中我们发现，针对一个具体的问题，适应度函数应该有其自身的特色，不能生搬硬套，往往要根据实际问题的特点来精心设计，并且反复尝试，才有可能找到比较合适的适应度计算方法。在大气污染总量控制中，我们考虑全部控制点的计算浓度与环境质量标准整体上的接近程度，整体接近程度越高，个体越优良，其适应度也越大。在实际操作中，还必须对群体的适应度作动态的跟踪和分析，适时调整适应度的计算方法或者参数，使适应度总是落在某个区间且离散程度合理。当变异个体的适应度很低时，也可以考虑人为赋给一个相对小的适应度，使它既不至于很活跃，又不至于完全迅速灭绝，这样对保持群体的多样性是有益的。

（三）轮盘选择模块

轮盘选择模块根据个体适应度的大小，用概率选择法确定参与遗传操作的个体。这种选择机制使得适应度大的个体有更多的繁殖机会，体现了适者生存的原则，它是遗传算法的精华所在。轮盘选择可以用如下的过程来实现：

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 j=1;j

if(Upbound>=Rand[j]){SelectedDNANo[j]=i;}}}}

在这个过程中，根据参数HowMany决定选取多少个个体，被选中的个体的序号存放在全局数组SelectedDNANo中，在此过程之外就可以对被选中的个体进行操作，使它们获得参与复制、交换、变异等遗传操作的机会。在该过程中用到了上文介绍的GetRndInt函数，用来得到指定区间的随机整数。数组ADP中保存的数据即个体的适应度，GroupSize即群体的规模。由于每次要选择的个体数目可能不同，为节省计算机内存，定义了两个动态数组SelectedDNANo和Rand，它们包含的元素个数即当前要求选择的个体的数目，由参数HowMany决定。

（四）遗传操作模块

遗传操作模块实现个体的复制、交换和变异，是遗传算法中最核心的模块，这些功能都是通过字符串操作来实现的。

1．复制。首先根据复制概率和群体规模确定将取得复制权的个体数目，再用轮盘选择法选出待复制的优良个体，然后从适应度最小的个体开始，在群体中依次淘汰相等数目的劣质个体，代之以刚刚获选的优良个体，就完成了优良个体的复制过程。程序片段如下：

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表示被选定的个体数目，DNA数组中保存的即染色体字符串，Elimination数组记录被淘汰的个体的序号。因为复制过程中能获得复制权的个体一般都具有较大的适应度，而淘汰的个体都是适应度很小的，所以经过一次复制，整个群体的整体适应度都有增大的趋势。

2．交换。与复制类似，我们希望参与交换的个体都具有优良的基因，所以仍然用轮盘选择法确定参与交换的个体，再让这些个体两两交叉，互换某个基因片段，从而产生两个新的个体，即杂交的后代。由于双亲携带优良基因，后代中可能会出现优于父代的个体，这样进化就发生了。为了确定交换的片段的起始位置，用随机数生成函数产生染色体长度范围内的两个随机整数，将序号位于这两个数之间的字符子串交换即可。程序片段如下：

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．变异。变异操作也是用轮盘选择法选定一定数目的个体，然后让这些个体的某些位发生突变，从而产生出新的个体。对于二进制编码的字符串，位突变就是将“0”变为“1”，而将“1”变为“0”。程序片段如下：

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为群体中发生变异的个体的比例，Pm2为一个突变个体中发生突变的位的比例。变异得到的个体优于父代的可能性不大，但变异能弥补大量个体被淘汰时造成的基因损失，增加群体的多样性，是避免算法早熟必不可少的措施。

4．辅助模块。以上各模块是遗传算法软件中的主要的功能模块，但是，为了提高程序的性能，还需要有一些辅助模块的支持，这些辅助模块包括对群体适应度的动态监控模块、系统参数自动调整模块、自动存盘和用户干预进化过程的操作相应模块等。

四、遗传算法性能的优化

为了提高遗传算法的性能，本文采取了以下几个方面的优化措施：

1．通过对群体适应度的动态跟踪，可以实时地调整适应度的计算方法和参数，这样使遗传算法既具有一定的进化动力又不会因早熟而陷于局部极小。具体做法是，动态跟踪适应度值，自动绘制适应度变化曲线，当适应度值调整不明显时，通过软件界面调整计算方法和参数。这种调整立即生效而且同时被记录在参数文件中。

2．可以实现各种参数的自动调节，保证遗传进化过程的稳步进行。例如在遗传算法进化的后期，变异个体具有很小的适应度，导致群体无法收敛，此时可以减小变异的概率，在编程时可以将变异概率设计为随着进化代数增加而逐渐减小或者随着最大适应度的增大而趋于零的动态因子，这样改善了整个遗传算法的性能，提高了解的质量。

3．遗传进化过程可以随时中断，下次可以在中断处继续进行。由于遗传算法的进化过程可能比较长，该项措施具有重要的实际意义。软件每隔一定时间将把进化结果及环境参数自动保存到磁盘上，即使系统因掉电或机器故障等原因异常中止，前面的工作也不会白费，系统在下次运行时将自动找到上次运行中断处继续运行。

五、遗传算法性能的检验

本文对上述遗传算法软件进行了性能检验。对最优解已知的问题，我们只需检验进化的结果与期望的最优解的逼近程度就可以断定软件的性能如何，但如果问题的最优解未知且不可预测，对程序进行性能的检验就比较困难了。对大气污染总量控制问题，我们采用如下的方法来检验遗传算法的性能：

1．如果遗传算法收敛于全局最优解，我们得到的源强分布应该是最优的，一方面可以反过来用多源模式进行计算，看在这样的源强分布下是否真正能达到预期的环境质量目标，即各控制点的计算浓度是否在总体上趋于所执行的大气环境质量标准；另一方面可以在进化所得最优源强上施加随机的微小的人为变化，看各控制点的污染浓度是否在整体上偏离环境标准更远。如果这两项检验都通过，可以初步断定遗传算法收敛于全局最优，性能可靠。

2．如果遗传算法所得结果为全局最优解，则它应该与进化的起点无关，所以可以尝试从不同的起点开始进化，如从实际排放量开始，从纯随机数开始，将所有源强都置为零开始，等等，如果都能得到相同的解，则该解应为全局最优解，软件性能可靠。当然，从不同起点开始进化所花时间是不一样的。

3．如果遗传算法的进化结果是全局最优解，则它与染色体的编码方式无关，我们分别采用二进制编码和十进制编码，若得到相同结果，则可以断定该解确实是全局最优解。

本文结合大气污染总量控制实例对遗传算法软件进行了上述3个方面的性能检验，结果表明，应用该软件确实能求得问题的全局最优解，该软件系统的性能是稳定的。

六、结束语

本文介绍了一个用于大气污染总量控制的遗传算法软件的结构设计、功能模块实现以及性能优化技术，并给出若干关键模块的详细实现源代码。为检验软件的全局搜索寻优性能，从三个不同角度设计了检验方法。经性能检

验，本文实现的遗传算法软件能以高效率稳定地求得问题的全局最优解，具有很好的推广应用前景。

参考文献：

[1]马小明、李诗刚、栾胜基等，大气污染总量控制方案的区域排放当量制定方法[J].中国环境科学，1996,16(5):350-353.

[2]王金南、潘向忠，线性规划方法在环境容量资源分配中的应用[J].环境科学，2005,26(6):195-198.

[3]刘品高，基于遗传算法的大气污染总量控制方法研究[D].南京：南京气象学院，2001.

[4]马思红，遗传算法的改进与应用[J].电脑知识与技术，2008,4(6):1461-1462,1468.

[5]高扬、王玉姣，基于改进遗传算法的移动机器人路径规划[J].电脑知识与技术，2008,4(4):951-953.