改进的遗传算法
A. 用改进遗传算法求取水文地质参数
任广军1 张勇2
（1.山东省鲁南地质工程勘察院，兖州272000；2.山东省地矿工程集团有限公司，济南250013）
作者简介：任广军（1972—），男，工程师，主要从事水文地质、环境地质等。
摘要：本文利用非稳定流抽水试验资料，采用改进的十进制遗传算法在计算机上自动优选含水层水文地质参数。该方法同传统上使用的配线法相比较，具有节省时间，减少人工配线误差，所求参数逼真，且能对一些线性、非线性问题求解，具有很高的推广和应用价值。
关键词：遗传算法；随机模拟；含水层；水文地质参数；优选
0 引言
利用改进的十进制遗传算法，根据抽水试验资料来认识水文地质条件、反求水文地质参数是水文地质计算中的基本问题。具体地讲，在探明含水层范围、类型的基础上，建立描述该含水层水流运动模型，利用抽水试验过程中的地下水位变化过程资料来确定水文地质参数。
虽然非稳定抽水试验公式适用条件非常苛刻，但能反映出含水层非稳定流的一些基本特点，还可运用叠加原理解决某些比较复杂的非稳定流问题。此外，作为检验数值方法精确性的重要依据，具有广泛应用和发展前景。
目前，由于非稳定流抽水试验确定水文地质参数的具体实现方法主要有人工配线法或以计算辅助的配线法，但这种方法的效果好坏完全取决于肉眼观察，带有很大的主观性。本文作者选取了一些典型实例，采用遗传算法建立了一种计算机全自动求参的全局优选法，通过与人工配线分析比较，确定本方法计算机求参的高精度与高可靠性。
求取参数是通过实测结果与模型计算结果的最佳拟合（仿真）程度来实现的，参数的精确程度在很大程度上取决于实测资料的精度。
1 遗传算法介绍
生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
遗传算法简称GA（Genetic Algorithm），在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
2 目标函数的确定
通过综合考虑计算程序的运算时间、速度以及含水层的类型，确立利用抽水实测资料和计算资料的拟合程度为目标函数。其计算公式为：
山东省环境地质文集
式中：s实测为实测抽水试验观测孔的降深；s计算为计算抽水试验观测孔的降深；NT为计算时段。
3 计算实例及结果分析
3.1 承压含水层地下水降深公式
承压含水层地下水降深公式为：
山东省环境地质文集
式中：S为以固定流量Q抽水时与抽水井距离为r处任一时间的水位降深（m）；T为导水系数；Q为涌水量；W（u）为井函数，是一个指数积分函数：
山东省环境地质文集
式中：u为井函数的自变量，
例1：某地区进行非稳定流抽水试验。区域地层剖面是：地表下18～25 m是由含砾粗砂层组成的含水层，其底板由粘土质沉积物组成，18 m以上是粘土、泥炭层。抽水井的过滤器安装在含水层的整个厚度上。观测孔距抽水井30m，观测资料如表1所示。主井作定流量抽水，Q＝788m3/d，抽水接近14小时。试根据观测资料求取水文地质参数。
（1）lgS-lgt配线法所求参数：T配线＝439m2/d，s配线＝1.694×10-4；
（2）S-lgt直线图解法所求参数：T配线＝450.7m2/d，s配线＝1.392×10-4；
（3）计算机所求参数：T＝383.0088m2/d，s＝ 1.78×10-4。
为更直观地说明上述所求参数的可靠性，由上述参数所求计算降深与实测降深进行比较（图1）。通过比较，进一步确定了计算机求参的高精度与稳定性。承压含水层配线参数与优选参数比较分析：T配线＝439m2/d，s配线＝0.0001694；T计算＝383.0088m2/d，s计算＝0.0001780。
表1 遗传算法计算水位降深与实测水位降深结果表
图1 计算降深与实测降深比较图
3.2 在有越流补给的承压含水层地下水降深公式
在有越流补给的承压含水层地下水降深公式为：
山东省环境地质文集
式中：u同（3）式；
山东省环境地质文集
例2：有一无限分布的承压含水层，厚度20m，其底部为绝对隔水的粘土层；上部为弱透水的亚砂土层，厚2m；弱透水层之上为潜水含水层。在承压含水层中有一完整抽水井，抽水时的稳定流量Q＝5530m3/d。距抽水井r＝17.34m处有一观测孔据观测知，在抽水过程中上部潜水的水位不变。抽水层的水位降深值载于表2，试计算含水层水文地质参数。
（1）lgS-lgt配线法所求参数：T配线＝853.50m2/d，s配线＝4.20×10-4；B配线＝568.50m；
（2）lgS-lgt配线法所求参数：T计算＝817.19m2/d，s计算＝4.31×10-4；B计算＝482.80m。
为更直观地说明上述所求参数的可靠性，由上述参数所求计算降深与实测降深进行比较（图2）。通过比较，进一步确定了计算机求参的高精度与稳定性。有越流时承压含水层优选参数误差分析：T配线＝853.50m2/d，s配线＝0.00042，B配线＝568.50m；T计算＝817.1950m2/d，s计算＝0.00043103，B计算＝482.798m。
表2 遗传算法计算水位降深与实测水位降深结果表
续表
图2 计算降深与实测降深比较图
3.3 考虑有滞后补给的潜水含水层地下水降深公式
根据博尔顿理论，潜水含水层地下水降深公式计算公式可分为抽水前期、抽水中期和抽水后期。参数优选主要根据抽水前期和抽水后期的资料拟合而得：
山东省环境地质文集
其中D为疏干因子。
抽水前期计算公式：
抽水后期计算公式：同（2）式。
4 结论及不足之处
4.1 结论
通过上述实例计算结果表明：计算结果同人工加以计算机辅助配线法相比较，其计算水文地质参数精度较高，且其参数初值依赖程度较低，对于复杂的线性、非线性及多态性、多峰值问题在全局优化方面有着其他方法所无法比拟的优势，具有很高的推广和应用价值。
4.2 不足之处
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还存在着各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最优解位置；最后，遗传算法的参数选择尚未有定量方法。对于遗传算法，一是还需要进一步研究其数学基础理论；二是还需要在理论上证明它与其他优化技术的优劣及原因；三是还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。此外，对于地下水渗流问题的数值解反求多类各种水文地质参数虽有成功实例，对于运算速度问题，还存在着相当大的难度。
参考文献
陈崇希，唐仲华.1990.地下水流动问题数值方法.武汉：中国地质大学出版社
陈喜.1998.含水层水文地质参数自动优选方法.工程勘察，（2）
郭东屏.1994.地下水动力学.西安：陕西科学技术出版社
GB 50027—2001 供水水文地质勘察规范
李俊亭，王愈吉.1987.地下水动力学.北京：地质出版社
刘宝碇，赵瑞清，王纲.2003.不确定规划及应用.北京：清华大学出版社
朱国祥，王峰.1999.利用配线法水文地质参数计算机程序简介.工程勘察，（3）
邹正盛，赵智荣.2001.浅析抽水水文地质参数确定中的问题.水文地质工程地质，（3）
B. 遗传算法改进的模糊C-均值聚类MATLAB源码范例
function [BESTX,BESTY,ALLX,ALLY]=GAFCM(K,N,Pm,LB,UB,D,c,m)
%% 此函数实现遗传算法，用于模糊C－均值聚类
%% 输入参数列表
% K 迭代次数
% N 种群规模，要求是偶数
% Pm 变异概率
% LB 决策变量的下界，M×1的向量
% UB 决策变量的上界，M×1的向量
% D 原始样本数据，n×p的矩阵
% c 分类个数
% m 模糊C均值聚类数学模型中的指数
%% 输出参数列表
% BESTX K×1细胞结构，每一个元素是M×1向量，记录每一代的最优个体
% BESTY K×1矩阵，记录每一代的最优个体的评价函数值
% ALLX K×1细胞结构，每一个元素是M×N矩阵，记录全部个体
% ALLY K×N矩阵，记录全部个体的评价函数值
%% 第一步：
M=length(LB);%决策变量的个数
%种群初始化，每一列是一个样本
farm=zeros(M,N);
for i=1:M
x=unifrnd(LB(i),UB(i),1,N);
farm(i,:)=x;
end
%输出变量初始化
ALLX=cell(K,1);%细胞结构，每一个元素是M×N矩阵，记录每一代的个体
ALLY=zeros(K,N);%K×N矩阵，记录每一代评价函数值
BESTX=cell(K,1);%细胞结构，每一个元素是M×1向量，记录每一代的最优个体
BESTY=zeros(K,1);%K×1矩阵，记录每一代的最优个体的评价函数值
k=1;%迭代计数器初始化
%% 第二步：迭代过程
while k<=K
%% 以下是交叉过程
newfarm=zeros(M,2*N);
Ser=randperm(N);%两两随机配对的配对表
A=farm(:,Ser(1));
B=farm(:,Ser(2));
P0=unidrnd(M-1);
a=[A(1:P0,:);B((P0+1):end,:)];%产生子代a
b=[B(1:P0,:);A((P0+1):end,:)];%产生子代b
newfarm(:,2*N-1)=a;%加入子代种群
newfarm(:,2*N)=b;???
for i=1:(N-1)
A=farm(:,Ser(i));
B=farm(:,Ser(i+1));
P0=unidrnd(M-1);
a=[A(1:P0,:);B((P0+1):end,:)];
b=[B(1:P0,:);A((P0+1):end,:)];
newfarm(:,2*i-1)=a;
newfarm(:,2*i)=b;
end
FARM=[farm,newfarm];
%% 选择复制
SER=randperm(3*N);
FITNESS=zeros(1,3*N);
fitness=zeros(1,N);
for i=1:(3*N)
Beta=FARM(:,i);
FITNESS(i)=FIT(Beta,D,c,m);
end
for i=1:N
f1=FITNESS(SER(3*i-2));
f2=FITNESS(SER(3*i-1));
f3=FITNESS(SER(3*i));
if f1<=f2&&f1<=f3
farm(:,i)=FARM(:,SER(3*i-2));
fitness(:,i)=FITNESS(:,SER(3*i-2));
elseif f2<=f1&&f2<=f3
farm(:,i)=FARM(:,SER(3*i-1));
fitness(:,i)=FITNESS(:,SER(3*i-1));
else
farm(:,i)=FARM(:,SER(3*i));
fitness(:,i)=FITNESS(:,SER(3*i));
end
end
%% 记录最佳个体和收敛曲线
X=farm;
Y=fitness;
ALLX{k}=X;
ALLY(k,:)=Y;
minY=min(Y);
pos=find(Y==minY);
BESTX{k}=X(:,pos(1));
BESTY(k)=minY;???
%% 变异
for i=1:N
if Pm>rand&&pos(1)~=i
AA=farm(:,i);
BB=GaussMutation(AA,LB,UB);
farm(:,i)=BB;
end
end
disp(k);
k=k+1;
end
%% 绘图
BESTY2=BESTY;
BESTX2=BESTX;
for k=1:K
TempY=BESTY(1:k);
minTempY=min(TempY);
posY=find(TempY==minTempY);
BESTY2(k)=minTempY;
BESTX2{k}=BESTX{posY(1)};
end
BESTY=BESTY2;
BESTX=BESTX2;
plot(BESTY,'-ko','MarkerEdgeColor','k','MarkerFaceColor','k','MarkerSize',2)
ylabel('函数值')
xlabel('迭代次数')
grid on
忘记写了，这个是源代码！谢谢谢谢！
C. 怎样解决遗传算法的局部最优问题
这个看看遗传算法的专着吧。
局部收敛，就是所谓的“早熟现象”是遗传算法的一个很让人头疼的问题。对应的措施，我举个例子，可以是提高变异算子的变异概率。变异算子是跳出局部收敛的重要操作算子，当然，遗传算法有很多的改进类型。这里不多说了，我介绍本书，叫《MATLAB遗传算法工具箱及应用》，雷英杰，西安电子科技大学出版社
D. 关于遗传算法
遗传算法（Genetic Algorithm，简称GA）是美国 Michigan大学的 John Golland提出的一种建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、具有广泛适用性的搜索方法。现在已被广泛用于学习、优化、自适应等问题中。图4-1 给出了 GA搜索过程的直观描述。图中曲线对应一个具有复杂搜索空间（多峰空间）的问题。纵坐标表示适应度函数（目标函数），其值越大相应的解越优。横坐标表示搜索点。显然，用解析方法求解该目标函数是困难的。采用 GA时，首先随机挑选若干个搜索点，然后分别从这些搜索点开始并行搜索。在搜索过程中，仅靠适应度来反复指导和执行 GA 搜索。在经过若干代的进化后，搜索点后都具有较高的适应度并接近最优解。
一个简单GA由复制、杂交和变异三个遗传算子组成：
图4-2 常规遗传算法流程图
E. matlab遗传算法改进bp神经网络
你提供的代码是一个基本的BP神经网络训练过程。一般都是用GA训练，之后再用改进动量法继续训练，直至最后达到目标。
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(indivial)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
F. 为什么我用遗传算法改进的BP还不如不改进呢
两种可能：一是遗传算法程序编的有问题（前提是BP网络没问题）；二就是遗传算法的评价标准或者停止准则选择不当。
G. 遗传算法执行策略的改进的具体方法（详细）
GA最典型的应用之一是解决行商问题，行商问题是这样的：
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
GA的思路是，先随机排序产生n条路线，这些路线当然长短不一，然后从中选出路径最短的若干条路线（优胜劣汰），再基于他们产生新的路线（杂交），同时引入一些新的路线（防止最初的基因不好，怎么遗传都产生不了精英），当然，还要保留其中最短的那条（那可是目前来说最nb的精英哦），再取其中最短的若干条路线（优胜劣汰）。。。。一直到我们最nb的精英基本上不能更好为止。整个过程符合进化论观点。
GA是不保证结果最优的，但按照性价比的观点来说，它通常能在较短的时间内获得一个较优结果。
http://www.longen.org/e-k/GA.htm
http://www.wikilib.com/wiki/%e9%81%97%e4%bc%a0%e7%ae%97%e6%b3%95 （这个比较详尽^_^）
很遗憾，这两天国外网站访问不了，不然可以帮你分析个例程
H. 遗传算法
遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。
5.4.1 非线性优化与模型编码
假定有一组未知参量
xi（i=1，2，…，M）
构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界αi及bi，即αi≤x≤bi，同时可用间隔di把它离散化，使
di=（bi-αi）/N （5.4.1）
于是，所有允许的模型m将被限制在集
xi=αi+jdi（j=0，1，…，N） （5.4.2）
之内。
通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集xi，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为
地球物理数据处理教程
其中M为未知参数xi的个数。由此式可见，K决定于每个参数离散化的间隔di及其变化范围（αi，bi），在大多数情况下它们只能靠先验知识来选择。
一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。
假设地球为有三个水平层的层次模型，含层底界面深度hj（j=1，2，3）及层速度vj（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：
h1=6，h2=18，h3=28，单位为10m
v1=6，v2=18，v3=28，单位为 hm/s
按正常的二进制编码法它们可分别用以下字符串表示为：
地球物理数据处理教程
为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距di都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：
地球物理数据处理教程
模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。
图5.8 遗传算法实现过程
5.4.2 遗传算法在地震反演中的应用
以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为
地球物理数据处理教程
式中：Ti，0为观测资料中提取出的地震走时；Ti，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；NA为合成地震数据的个数，它可以少于实测Ti，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据Tj，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h1＜h2＜h3…）在遗传算法中是容易实现的。
对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为
地球物理数据处理教程
式中：P0（ωk，vj）为实测地震道的频谱；ωk为角频率；vj为第j层的波速；Ps（ωk，vj）为相应的合成地震道；A（ωk）为地震仪及检波器的频率滤波器，例如，可取
A（ω）=sinC4（ω/ωN） （5.4.6）
式中ωN为Nyquist频率，即ωN=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令
地球物理数据处理教程
式中：tmax为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。
用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。
遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率Ps的变化范围加大。
对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。
I. 关于遗传算法的疑惑！请高人指点！非常感谢！ 模拟退火遗传算法和免疫遗传算法哪个改进的效果好
这些算法的本质都是随机搜索，带有随机性，对参数依赖程度还是比较强的，所以出现结果时好时坏也是正常的。
至于这些算法的比较，你可以查查相关的论文。特别是首先提出该改进算法的论文，不过要注意，国内的论文的实验结果可信程度还是值得怀疑的。作者往往为了“证明”其算法的优势，只列举那些对算法效果有利的实验结果，不好的结果经常不列出来。所以你看到别人说什么算法好，但你自己用的时候却没发现该算法的优势也是正常的。
J. 遗传算法 多种群是什么个概念 加入多种群策略有什么改进
采用PSO优化的思想进行算法的改进：把全局分为多个种群进行进化，最后取各个种群的局部极值中最大的作为全局是优值：优点是比传统的遗传算法不容易陷入局部极值