遗传算法

‘壹’ 关于遗传算法

遗传算法（Genetic Algorithm，简称GA）是美国 Michigan大学的 John Golland提出的一种建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、具有广泛适用性的搜索方法。现在已被广泛用于学习、优化、自适应等问题中。图4-1 给出了 GA搜索过程的直观描述。图中曲线对应一个具有复杂搜索空间（多峰空间）的问题。纵坐标表示适应度函数（目标函数），其值越大相应的解越优。横坐标表示搜索点。显然，用解析方法求解该目标函数是困难的。采用 GA时，首先随机挑选若干个搜索点，然后分别从这些搜索点开始并行搜索。在搜索过程中，仅靠适应度来反复指导和执行 GA 搜索。在经过若干代的进化后，搜索点后都具有较高的适应度并接近最优解。

一个简单GA由复制、杂交和变异三个遗传算子组成：

图4-2 常规遗传算法流程图

‘贰’ 遗传算法程序

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* Change any of these parameters to match your needs */

#define POPSIZE 50 /* population size */
#define MAXGENS 1000 /* max. number of generations */
#define NVARS 3 /* no. of problem variables */
#define PXOVER 0.8 /* probability of crossover */
#define PMUTATION 0.15 /* probability of mutation */
#define TRUE 1
#define FALSE 0

int generation; /* current generation no. */
int cur_best; /* best indivial */
FILE *galog; /* an output file */

struct genotype /* genotype (GT), a member of the population */
{
double gene[NVARS]; /* a string of variables */
double fitness; /* GT's fitness */
double upper[NVARS]; /* GT's variables upper bound */
double lower[NVARS]; /* GT's variables lower bound */
double rfitness; /* relative fitness */
double cfitness; /* cumulative fitness */
};

struct genotype population[POPSIZE+1]; /* population */
struct genotype newpopulation[POPSIZE+1]; /* new population; */
/* replaces the */
/* old generation */

/* Declaration of proceres used by this genetic algorithm */

void initialize(void);
double randval(double, double);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);
void report(void);

/***************************************************************/
/* Initialization function: Initializes the values of genes */
/* within the variables bounds. It also initializes (to zero) */
/* all fitness values for each member of the population. It */
/* reads upper and lower bounds of each variable from the */
/* input file `gadata.txt'. It randomly generates values */
/* between these bounds for each gene of each genotype in the */
/* population. The format of the input file `gadata.txt' is */
/* var1_lower_bound var1_upper bound */
/* var2_lower_bound var2_upper bound ... */
/***************************************************************/

void initialize(void)
{
FILE *infile;
int i, j;
double lbound, ubound;

if ((infile = fopen("gadata.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n");
exit(1);
}

/* initialize variables within the bounds */

for (i = 0; i < NVARS; i++)
{
fscanf(infile, "%lf",&lbound);
fscanf(infile, "%lf",&ubound);

for (j = 0; j < POPSIZE; j++)
{
population[j].fitness = 0;
population[j].rfitness = 0;
population[j].cfitness = 0;
population[j].lower[i] = lbound;
population[j].upper[i]= ubound;
population[j].gene[i] = randval(population[j].lower[i],
population[j].upper[i]);
}
}

fclose(infile);
}

/***********************************************************/
/* Random value generator: Generates a value within bounds */
/***********************************************************/

double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return(val);
}

/*************************************************************/
/* Evaluation function: This takes a user defined function. */
/* Each time this is changed, the code has to be recompiled. */
/* The current function is: x[1]^2-x[1]*x[2]+x[3] */
/*************************************************************/

void evaluate(void)
{
int mem;
int i;
double x[NVARS+1];

for (mem = 0; mem < POPSIZE; mem++)
{
for (i = 0; i < NVARS; i++)
x[i+1] = population[mem].gene[i];

population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];
}
}

/***************************************************************/
/* Keep_the_best function: This function keeps track of the */
/* best member of the population. Note that the last entry in */
/* the array Population holds a of the best indivial */
/***************************************************************/

void keep_the_best()
{
int mem;
int i;
cur_best = 0; /* stores the index of the best indivial */

for (mem = 0; mem < POPSIZE; mem++)
{
if (population[mem].fitness > population[POPSIZE].fitness)
{
cur_best = mem;
population[POPSIZE].fitness = population[mem].fitness;
}
}
/* once the best member in the population is found, the genes */
for (i = 0; i < NVARS; i++)
population[POPSIZE].gene[i] = population[cur_best].gene[i];
}

/****************************************************************/
/* Elitist function: The best member of the previous generation */
/* is stored as the last in the array. If the best member of */
/* the current generation is worse then the best member of the */
/* previous generation, the latter one would replace the worst */
/* member of the current population */
/****************************************************************/

void elitist()
{
int i;
double best, worst; /* best and worst fitness values */
int best_mem, worst_mem; /* indexes of the best and worst member */

best = population[0].fitness;
worst = population[0].fitness;
for (i = 0; i < POPSIZE - 1; ++i)
{
if(population[i].fitness > population[i+1].fitness)
{
if (population[i].fitness >= best)
{
best = population[i].fitness;
best_mem = i;
}
if (population[i+1].fitness <= worst)
{
worst = population[i+1].fitness;
worst_mem = i + 1;
}
}
else
{
if (population[i].fitness <= worst)
{
worst = population[i].fitness;
worst_mem = i;
}
if (population[i+1].fitness >= best)
{
best = population[i+1].fitness;
best_mem = i + 1;
}
}
}
/* if best indivial from the new population is better than */
/* the best indivial from the previous population, then */
/* the best from the new population; else replace the */
/* worst indivial from the current population with the */
/* best one from the previous generation */

if (best >= population[POPSIZE].fitness)
{
for (i = 0; i < NVARS; i++)
population[POPSIZE].gene[i] = population[best_mem].gene[i];
population[POPSIZE].fitness = population[best_mem].fitness;
}
else
{
for (i = 0; i < NVARS; i++)
population[worst_mem].gene[i] = population[POPSIZE].gene[i];
population[worst_mem].fitness = population[POPSIZE].fitness;
}
}
/**************************************************************/
/* Selection function: Standard proportional selection for */
/* maximization problems incorporating elitist model - makes */
/* sure that the best member survives */
/**************************************************************/

void select(void)
{
int mem, i, j, k;
double sum = 0;
double p;

/* find total fitness of the population */
for (mem = 0; mem < POPSIZE; mem++)
{
sum += population[mem].fitness;
}

/* calculate relative fitness */
for (mem = 0; mem < POPSIZE; mem++)
{
population[mem].rfitness = population[mem].fitness/sum;
}
population[0].cfitness = population[0].rfitness;

/* calculate cumulative fitness */
for (mem = 1; mem < POPSIZE; mem++)
{
population[mem].cfitness = population[mem-1].cfitness +
population[mem].rfitness;
}

/* finally select survivors using cumulative fitness. */

for (i = 0; i < POPSIZE; i++)
{
p = rand()%1000/1000.0;
if (p < population[0].cfitness)
newpopulation[i] = population[0];
else
{
for (j = 0; j < POPSIZE;j++)
if (p >= population[j].cfitness &&
p<population[j+1].cfitness)
newpopulation[i] = population[j+1];
}
}
/* once a new population is created, it back */

for (i = 0; i < POPSIZE; i++)
population[i] = newpopulation[i];
}

/***************************************************************/
/* Crossover selection: selects two parents that take part in */
/* the crossover. Implements a single point crossover */
/***************************************************************/

void crossover(void)
{
int i, mem, one;
int first = 0; /* count of the number of members chosen */
double x;

for (mem = 0; mem < POPSIZE; ++mem)
{
x = rand()%1000/1000.0;
if (x < PXOVER)
{
++first;
if (first % 2 == 0)
Xover(one, mem);
else
one = mem;
}
}
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/

void Xover(int one, int two)
{
int i;
int point; /* crossover point */

/* select crossover point */
if(NVARS > 1)
{
if(NVARS == 2)
point = 1;
else
point = (rand() % (NVARS - 1)) + 1;

for (i = 0; i < point; i++)
swap(&population[one].gene[i], &population[two].gene[i]);

}
}

/*************************************************************/
/* Swap: A swap procere that helps in swapping 2 variables */
/*************************************************************/

void swap(double *x, double *y)
{
double temp;

temp = *x;
*x = *y;
*y = temp;

}

/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and */
/* upper bounds of this variable */
/**************************************************************/

void mutate(void)
{
int i, j;
double lbound, hbound;
double x;

for (i = 0; i < POPSIZE; i++)
for (j = 0; j < NVARS; j++)
{
x = rand()%1000/1000.0;
if (x < PMUTATION)
{
/* find the bounds on the variable to be mutated */
lbound = population[i].lower[j];
hbound = population[i].upper[j];
population[i].gene[j] = randval(lbound, hbound);
}
}
}

/***************************************************************/
/* Report function: Reports progress of the simulation. Data */
/* mped into the output file are separated by commas */
/***************************************************************/

void report(void)
{
int i;
double best_val; /* best population fitness */
double avg; /* avg population fitness */
double stddev; /* std. deviation of population fitness */
double sum_square; /* sum of square for std. calc */
double square_sum; /* square of sum for std. calc */
double sum; /* total population fitness */

sum = 0.0;
sum_square = 0.0;

for (i = 0; i < POPSIZE; i++)
{
sum += population[i].fitness;
sum_square += population[i].fitness * population[i].fitness;
}

avg = sum/(double)POPSIZE;
square_sum = avg * avg * POPSIZE;
stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));
best_val = population[POPSIZE].fitness;

fprintf(galog, "\n%5d, %6.3f, %6.3f, %6.3f \n\n", generation,
best_val, avg, stddev);
}

/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover & mutation and then */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied */
/**************************************************************/

void main(void)
{
int i;

if ((galog = fopen("galog.txt","w"))==NULL)
{
exit(1);
}
generation = 0;

fprintf(galog, "\n generation best average standard \n");
fprintf(galog, " number value fitness deviation \n");

initialize();
evaluate();
keep_the_best();
while(generation<MAXGENS)
{
generation++;
select();
crossover();
mutate();
report();
evaluate();
elitist();
}
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n Best member: \n");

for (i = 0; i < NVARS; i++)
{
fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i]);
}
fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");
}
/***************************************************************/

‘叁’ 遗传算法概念

遗传算法是模拟达尔文的生物进化理论，结合进化中优胜劣汰的概念，是一种基于自然选择和遗传学原理的搜索算法。

‘肆’ 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。

5.4.1 非线性优化与模型编码

假定有一组未知参量

x_i（i=1，2，…，M）

构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界α_i及b_i，即α_i≤x≤b_i，同时可用间隔d_i把它离散化，使

d_i=（b_i-α_i）/N （5.4.1）

于是，所有允许的模型m将被限制在集

x_i=α_i+jd_i（j=0，1，…，N） （5.4.2）

之内。

通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集x_i，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为

地球物理数据处理教程

其中M为未知参数x_i的个数。由此式可见，K决定于每个参数离散化的间隔d_i及其变化范围（α_i，b_i），在大多数情况下它们只能靠先验知识来选择。

一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。

假设地球为有三个水平层的层次模型，含层底界面深度h_j（j=1，2，3）及层速度v_j（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：

h₁=6，h₂=18，h₃=28，单位为10m

v₁=6，v₂=18，v₃=28，单位为 hm/s

按正常的二进制编码法它们可分别用以下字符串表示为：

地球物理数据处理教程

为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距d_i都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：

地球物理数据处理教程

模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。

图5.8 遗传算法实现过程

5.4.2 遗传算法在地震反演中的应用

以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为

地球物理数据处理教程

式中：T_i，0为观测资料中提取出的地震走时；T_i，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；N_A为合成地震数据的个数，它可以少于实测T_i，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据T_j，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h₁＜h₂＜h₃…）在遗传算法中是容易实现的。

对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为

地球物理数据处理教程

式中：P₀（ω_k，v_j）为实测地震道的频谱；ω_k为角频率；v_j为第j层的波速；P_s（ω_k，v_j）为相应的合成地震道；A（ω_k）为地震仪及检波器的频率滤波器，例如，可取

A（ω）=sinC⁴（ω/ω_N） （5.4.6）

式中ω_N为Nyquist频率，即ω_N=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令

地球物理数据处理教程

式中：t_max为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。

用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。

遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率P_s的变化范围加大。

对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。

‘伍’ 遗传算法的一般算法

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法： 繁殖(包括子代突变)
带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。 各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。 这个函数是计算个体在群体中被使用的概率。

‘陆’ 什么是遗传算法

遗传算法是模拟自然界中按“优胜劣汰”法则进行进化过程而设计的算法。Bagley和Rosengerg于1967年在他们的博士论文中首先提出了遗传算法的概念。1975年Holland出版的专着奠定了遗传算法的理论基础。如今遗传算法不但给出了清晰的算法描述，而且也建立了一些定量分析的结果，在众多领域得到了广泛的应用，如用于控制(煤气管道的控制)、规划(生产任务规划)、设计(通信网络设计)、组合优化(TSP问题、背包问题)以及图像处理和信号处理等。

‘柒’ 什么是混合遗传算法

一楼回答的对，混合遗传算法就是将遗传算法与其他算法相混合，互取所长，互补所短。比如遗传算法与模拟退火算法的混合，就是将遗传算法的全局搜索能力与模拟退火算法的局部搜索能力结合起来，形成一种强大的算法。类似的还有：遗传算法与最速下降法的混合、蚁群算法与遗传算法的混合等。

‘捌’ 混合遗传算法和遗传算法有什么区别

遗传算法是一种全局搜索算法，不需要目标函数的导数信息，它能够很快搜索到最优值所处范围范围。
而混合遗传算法是在遗传算法的基础上引入其它优化算法（如局部寻优能力强的算法），以保证遗传算法全局性能的基础上大大减小计算量，提高收敛速度。一般引入的算法有：传统梯度类算法、单纯形法及模拟退火等等）这些算法都很容易与遗传算法兼容。

‘玖’ 什么是遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：
遗传算法式中x为决策
变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。
遗传算法的基本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(indivial)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。