如何用混合编码的遗传算法求解污染源定位问题

利用模拟-优化模型求解污染源定位问题时，主要是通过EPANET 模拟器正向输出水力水质的状态，然后和传感器实际检测的水质信息比较。如果误差小于设定的阈值ε，则优化算法得到最优解为污染源，否则，通过优化算法继续求解，直到满足一定的条件，程序结束。模拟-优化的总体框架如图7-1所示。

图7-1　模拟-优化框架图

如图7-1所示，优化算法作为优化器生成污染事件，EPANET 作为模拟器模拟污染事件输出各个节点的实际污染物浓度。本书采用遗传算法作为优化算法，种群中每个个体表示一个污染事件，通过EPANET 模拟器可以模拟污染事件，输出供水管网节点实际的污染物浓度信息，通过与传感器实际检测的信息比较，可以计算每个个体的适应度值，适应度值越小，说明该污染事件发生的可能性越高。

为了求解上述的框架模型，本章提出基于混合编码的遗传算法。遗传算法的思想来源于达尔文的生物进化论，通过模拟自然界中生物的进化过程，以优胜劣汰的原则对解空间进行筛选和搜索，最后求出最优解。自然界中的生物的适应能力越强，就越能适应环境，生存下来的概率也就越大。

遗传算法最初始的操作是对群体的个体进行编码，一般的编码方式有实数编码、二进制编码、整数编码等。污染源定位问题的变量包含污染源位置、开始时间、持续时间和污染物质量注入向量，根据变量的属性，本节采用整数编码与实数编码相结合的方式进行编码，同时根据相应编码方式的改变而改变算法的交叉算子和变异算子，从而更快地找到最优解，提高算法收敛速度，算法流程如图7-2所示。

图7-2　遗传算法流程图

在种群中，每个个体表示一个污染事件，个体包含的4个变量为{节点位置，污染注入时间，持续时间，污染物注入质量}。其中，前3个变量是整数变量，可采用整数编码，第4个变量是实数向量，可采用实数编码。例如污染源节点为73，污染物注入时间为2：00，污染物持续时间为4h，污染源注入质量为（200，216.5，310.9，300），则该污染物注入事件所对应的个体编码为{00073024}和{200，216.5，310.9，300}。

算法编码结合整数编码与实数编码，在相应的交叉和变异操作中也是两种方法的结合，其中，在交叉操作中的整数编码部分，采用双点交叉，实数编码部分，采用实数重组；在变异操作中的整数编码部分，采用单点变异和高斯变异。具体方法如下所述。

1.交叉算子

假设个体1：污染源位置为125，开始注入时间为10：00，持续注入时间为3h，每隔1h注入浓度变化一次，则注入质量向量为（215.1，345.8，457.8）；个体2：污染源位置为96，开始注入时间为3：00，持续注入时间为4h，每隔1h 注入浓度变化一次，则注入质量向量为（300.1，123.4，39.1，356.8）。

编码为：

个体1：{00125103}{215.1，345.8，457.8}

个体2：{00096034}{300.1，123.4，39.1，356.8}

如上所示，前面整数编码为定长8位的整数数组，使用双点交叉，即随机选取两个位置进行交叉变换。假设随机选取的位置为第3位和第6位，则交叉后得到的两个新个体分别为：

个体3：{00096003}{215.1，345.8，457.8}

个体4：{00125134}{300.1，123.4，39.1，356.8}

而后面实数编码为变长的实数数组，根据时间长短的不同长度也不同。实数重组的算法如下：

子个体1=a×父个体1+（1-a）×父个体2

子个体2=（1-a）×父个体1+a×父个体2

其中，a 是一个随机的比例因子，则个体3、个体4实数编码部分经实数重组后可得到交叉后的子个体为（假设a 随机选取为0.7）：

子个体1：{00096003}{240.6，279.08，332.19}

子个体2：{00125134}{274.6，190.12，164.71，249.76}

由于个体3的实数部分只有3位，而个体4有4位，所以在个体4第4位计算时对应的实数取0。

2.变异算子

与交叉算子相似，变异算子也是两个部分分开处理，整数部分为单点变异，实数部分为高斯变异。假设上述交叉后的子个体1保留下来进行变异操作，则先是前面部分进行单点变异，随机选取第8位进行变异，则变异后为{00096005}。

后面部分为高斯变异，即产生一个服从高斯分布的随机数，取代当前基因中的实数，该算法生成的随机数，数学期望应为当前基因的实数数值。本书采用模拟产生6个服从U（0，1）的随机数，以它们的数学期望当作高斯分布随机数的近似。假设近似高斯分布随机数为0.85，注入质量的上界为500，下界为10，则变异如下：(www.xing528.com)

变异后实数=[（0.85×（500-10）+10]+（子个体1）/2

则变异后个体为{00096005}{333.55，352.79，379.34，213.25，39.8}，由于原先个体实数部分本来只有3位，而整数部分第8位变异后为5，所以对于后两位进行随机初始化。

由于供水管网中放置的水质传感器的数量远少于管网节点数目，因此利用有限的水质传感器的检测信息预测整个管网污染物注入状态，可能会得到多个污染物注入场景，因此，应该在算法一次运行过程中尽可能地找出多个最优解，然后对最优解进行筛选，确定真正的污染源。本书通过矩阵相关理论量化说明污染源定位问题是一个多峰函数优化问题，以函数最小化为例：

定义7-2 （全局极小值）对于函数minf：X→R，全局极小值点x* 是指对于任意x∈X满足f（x*）≤f（x），f（x*）是全局极小值。

定义7-3 （多峰函数优化问题）对于函数minf：X→R，在解集X 中存在多个局部极值点或全局极值点，则函数f 为多峰函数，求解该函数极值点的过程为多峰函数优化。

定理7-1 供水管网污染源定位问题是一个多峰函数优化问题。

证 供水管网水力水质传输过程可以描述为一个线性输入输出系统：

假定污染物以相等概率可从管网任意节点注入，而在整个供水管网中布置r 个水质传感器对污染物进行监测，则r 个传感器在时间T 内的污染物累积浓度为Cr×1：

Ar×n 为r×n 矩阵，表示污染物从任意管网节点注入时传感器网络的系统响应。

由式（7-2）和式（7-3）可推导出式（7-4）：

则该方程的解即为优化函数的全局极小值点，由定义7-3可知，如果式（7-5）存在多个解，则优化函数式（7-4）为多峰优化函数。

由于水质传感器的个数r 远小于管网节点n，即r≪n，矩阵A 的秩rank（A）≤r，假定矩阵A 由r 个基向量｛Pi|i=1，2，…，r｝和（n-r）个非基向量｛Pi|i=r+1，r+2，…，n｝构成，对应的Xn×1 由r 个基变量（x1，x2，…，xr）和（n-r）个非基变量（xr+1，xr+2，…，xn）构成。基向量构成基矩阵B，非基向量构成矩阵B′，基变量为XB，非基变量为XB′，带入式（7-5），可得：

则：

由式（7-7）可以看出，方程的解由基变量和非基变量构成，由于非基变量的非唯一性，导致了方程具有多个解，因此污染源定位问题是一个多峰函数优化问题。