一、遗传算法的生物背景

二、遗传算法(GA)思想

2.1遗传算法的组成

2.2编码

2.3适应度函数

2.4遗传算子

2.4 运行参数

三、基本遗传算法(SGA)伪代码

3.1算法流程图

3.2 算法伪代码

四、遗传算法的优化、应用前景

4.2 遗传算法的优化

4.3 遗传算法的应用

五、遗传算法实例分析

一、遗传算法的生物背景

生物在自然界中生存繁衍,显示出了其对自然环境的优异自适应能力.遗传算法(Genetic Algorithms,简称GA)就是对生物遗传和进化过程的计算机模拟.它是一种自适应全局优化概率搜索算法,于1980年左右正式诞生.

首先我们要知道,遗传算法是基于生物进化理论而产生的,因此作为遗传算法生物背景的介绍,下面的概念有必要了解:

种群(Population):生物进化以群体形式进行,这样的一个群体称种群;
个体:组成种群的单个生物;
基因(Gene):一个遗传因子;
染色体(Chromosome):包含一组的基因;
遗传与变异:新个体会遗传父母双方各一部分的基因,同时有一定的几率发生基因变异;
选择(Selection):按一定概率从种群中选择若干个体,选择过程是基于适应度的优胜劣汰;
交叉(Crossover):两个染色体某一相同位置处的DNA被切断,然后两者交叉组合形成两个新的染色体;
编码(Coding):DNA中遗传信息的排列,是从表现型到基因型的映射;
解码(Decoding):基因型到表现型的映射;

按照达尔文进化理论,物种生存竞争,适者生存,对环境适应度高的、牛b的个体参与繁殖的机会比较多,后代就会越来越多,适应度低的个体参与繁殖的机会比较少,后代就会越来越少。进一步概括,就是繁殖过程,会发生基因交叉(Crossover),基因突变(Mutation).适应度(Fitness)低的个体会逐步淘汰,而适应度高的个体会越来越多.那么经过N代的自然选择后,保存下来的个体都是适应度高的,其中很可能包含那个史上适应度最高的个体.

说到这里,善于思考的你一定想到如果把适应度比作一个函数的函数值,而将n个个体比作该函数在给定区间上的部分自变量的值,那么遗传算法不就相当于搜索该区间上令函数取的最值(适应度最大)的自变量(个体)的值嘛,没错,这正是遗传算法的一方面应用,我们在后文中会有具体的实例来向你展示算法到底是怎么做到的.

二、遗传算法(GA)思想

2.1遗传算法的组成

1.编码(产生初始种群)

2.适应度函数

3.遗传算子(选择,交叉,变异)

4.运行参数

借鉴生物进化论,遗传算法将要解决的问题模拟成一个生物进化过程,通过复制,交叉,变异等操作产生下一代的解,并逐步淘汰掉适应度函数值低的解,增加适应度函数值高的解,这样进化N代后就会进化出适应度函数值很高的个体.

举个例子,用遗传算法解决"0-1背包问题"的思路:0-1背包的解可以编码成一串0-1字符串(0:不取,1:取);首先,随机产生m个0-1字符串,然后评价这些字符串作为0-1背包问题的价值的大小;再从中随机选择一部分字符串通过交叉、变异操作产生下一代m个字符串,而且价值较高的解被选中的概率比较高,这样经过n代的进化后就会产生出0-1背包的一个"近似最优解".

作为遗传算法(GA)的入门,我们应做到掌握基本遗传算法(SGA),并了解相应拓展.下面我将着重讲解基本遗传算法(SGA),兼并相应拓展

2.2编码

正如研究基因是从染色体入手的,染色体也就是基因的串,编码也就是基因的编码,需要将问题的解编码成字符串的形式才能使用遗传算法.前辈们研究出了很多种编码方法,其中最常用的编码方式是二进制编码(SGA的编码方式),即将问题的解编码成二进制位数组的形式.例如,问题的解是整数,那么可以就将其编码成二进制数组的形式.将0-1字符串作为0-1背包问题的解就属于二进制编码(例如01001就表示了2号和5号装入背包,其他的不装入).基因能够在一定意义上包含它所代表的的问题的解,不同的编码方式往往取决于问题本身.下面再简单介绍几种常用的编码方式:

1.二进制编码:正如上文说到,基本遗传算法采用二进制编码,这是将基因用0和1表示的方式

2.互换编码:(用于解决排序问题,如TSP问题和调度问题),在TSP问题中,一串基因编码用来表示遍历的城市序列,如:651234,表示六个城市,先经过城市6,再经过城市5.以此类推.

3.树形编码:(用于解决遗传规划中的演化编程或者表示),例如问题:给出多个输入和输出,要求写出一个函数使得每个输入尽可能进地映射为输出.则基因就是树形结构中的一些函数.

2.3适应度函数

适应度函数(Fitness Function):用于评价某个染色体或者个体的适应度,用f(x)表示.有时需要区分染色体的适应度函数和问题的目标函数.例如:0-1背包问题的目标函数是所取的物品的价值,但将物品价值作为染色体的适应度函数可能并不一定合适.适应度函数与目标函数是正相关的,可对目标函数做一些变形来得到适应度函数.

2.4遗传算子

遗传算子分为选择算子,交叉算子,变异算子

2.4.1选择算子

遗传算法使用选择运算对个体进行优胜劣汰操作,基本遗传算法(SGA)一种常用的选择策略是"比例选择",也就是个体被选中的概率与其适应度函数值成正比.假设群体的总个数是n,那么一个个体Xi被选中的概率就是f(Xi)/(f(X1)+f(X2)+……+f(Xn)).

$遗传算法(GA)入门知识梳理(超详细)-编程知识网$

比例选择的实现算法就是所谓的'轮盘赌算法'(RWS),可以简单地用以下代码表示轮盘赌算法

/*

* 按设定的概率，随机选中一个个体

* P[i]表示第i个个体被选中的概率

*/

int RWS()

{

m =0;

r =Random(0,1); //r为0至1的随机数

for(i=1;i<=N; i++)

{

/* 产生的随机数在m~m+P[i]间则认为选中了i

* 因此i被选中的概率是P[i]

*/

m=m+P[i];

if(r<=m) return i;

}

2.4.2交叉算子

所谓交叉运算,是指两个相互配对的染色体依据交叉概率Pc按照某种方式相互交换其部分基因,从而形成像个新的个体.交叉运算在GA中起关键作用,是产生新个体的主要方法.交叉的方法也有很多,基本遗传算法(SGA)主要采用单点交叉法,即选择一个交叉点,两条染色体交换部分基因,构造两条新染色体,例如:

交叉前：

染色体1: 00000|011100000000|10000

染色体2: 11100|000001111110|00101

交叉后：

染色体1: 00000|000001111110|10000

染色体2: 11100|011100000000|00101

染色体交叉是以一定概率发生的,这个概率记为Pc

另外,在这里介绍两种其他交叉方法:

1.双点交叉法:选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,部分来自另一个父代基因,如:

交叉前：

染色体1: 01 |0010| 11|00

染色体2: 11 |0111| 01|10

交叉后：

染色体1:11 |0010| 01|00

染色体2:01 |0111| 11|10

2.基于"与/或"的交叉法:

对父代按位"与"逻辑运算产生一子代A,按位"或"逻辑运算产生另一子代B.如:

交叉前:

染色体1: 01001011

染色体2: 11011101

交叉后：

染色体1: 01001001(A,两个染色体与运算结果)

染色体2: 11011111(B,两个染色体或运算结果)

2.4.3变异算子

变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。

注：变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm > 0.5，这时GA退化为随机搜索。

在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm

变异算子也有很多,基本遗传算法(GA)采用基本位变异算子

基本位变异算子:

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。

变异前：

000001110000000010000

变异后：

000001110000100010000

2.4 运行参数

GA运行时参数的选择应视具体问题而定,在一般情况下,GA都应包括的参数有:

1.种群规模M

种群规模指的是群体中个体的个数.实验发现,种群规模并不是越大就能优化遗传算法,种群的大小推荐使用20-30,一些研究表明,种群规模的大小取决于编码的方法,具体说就是编码串的大小.也就是说,如果基因编码为32位时种群规模大小最好为32的话,那么当基因编码为16位时种群的规模就变为原来的两倍.

2.交叉率Pc

交叉率一般来说应该比较大,推荐使用80%-95%.

3.变异率Pm

变异率一般来说应该比较小,一般使用0.1%-1%最好.

4.终止进化代数T

设定一个值,作为进化的代数.

三、基本遗传算法(SGA)伪代码

3.1算法流程图

3.2 算法伪代码

/*

* Pc：交叉发生的概率

* Pm：变异发生的概率

* M：种群规模

* G：终止进化的代数

* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程

*/

初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop

do

{

　　计算种群Pop中每一个体的适应度F(i)。

　　初始化空种群newPop

do

{

　　　　根据适应度以比例选择算法从种群Pop中选出2个个体

if ( random ( 0 , 1 ) < Pc )

{

　　　　　　对2个个体按交叉概率Pc执行交叉操作

}

if ( random ( 0 , 1 ) < Pm )

{

　　　　　　对2个个体按变异概率Pm执行变异操作

}

将2个新个体加入种群newPop中

} until ( M个子代被创建 )

用newPop取代Pop

}until ( 任何染色体得分超过Tf，或繁殖代数超过G )

四、遗传算法的优化、应用前景

4.1遗传算法的优缺点

优点:

群体搜索，易于并行化处理;

不是盲目穷举，而是启发式搜索;

适应度函数不受连续、可微等条件的约束，适用范围很广;

容易实现。一旦有了一个遗传算法的程序，如果想解决一个新的问题，只需针对新的问题重新进行基因编码就行；如果编码方法也相同，那只需要改变一下适应度函数就可以了;

缺点:

全局搜索能力不强,很容易陷入局部最优解跳不出来;

将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向目标函数的局部最优解收敛，从而很难找到全局最优解。

4.2 遗传算法的优化

针对遗传算法的缺点,人们想出来很多方法来优化遗传算法,例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提出了竞争选择、按续挑选等改进方案；针对原先的一点交算子，提出了两点交、多点交、均匀交等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了退化遗传算法、自适应遗传算法等。这里讲两种经常用到的方法:

4.2.1灾变

遗传算法的局部搜索能力较强，但是很容易陷入局部极值。引用网上的一段原话: “那么如何解决遗传算法容易陷入局部极值的问题呢？让我们来看看大自然提供的方案。

六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球至少经历了5次物种大灭绝，每次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。”

灾变就是杀掉最优秀的个体，这样才可能产生更优秀的物种。那何时进行灾变，灾变次数又如何设定？

何时进行灾变，可以采用灾变倒计数的方式。如果n代还没有出现比之前更优秀的个体时，可以发生灾变。灾变次数可以这样来确定，如果若干次灾变后产生的个体的适应度与没灾变前的一样，可停止灾变。

4.2.2精英主义

当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。

精英主义的思想是,在每一次产生新的一代时，首先把当前最优解原封不动的复制到新的一代中。然后按照前面所说的那样做就行。精英主义方法可以大幅提高运算速度，因为它可以防止丢失掉找到的最好的解。

精英主义是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。

4.3 遗传算法的应用

遗传算法的主要有以下八方面的应用：

（1）组合优化（2）函数优化（3）自动控制（4）生产调度

（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘

五、遗传算法实例分析

我们先来看一个简单地问题:求二次函数 $遗传算法(GA)入门知识梳理(超详细)-编程知识网$ 在区间[0,4]上的最大值

采用遗传算法,可以找到相应的参数:

解空间:区间[0,4];

个体:区间[0,4]之间的点x;

适应度函数:由于目标函数值易计算,直接将目标函数作为适应度函数;

交叉概率:该问题Pc取1;

变异概率:Pm可取0.005;

问题求解:

1.编码,确定种群规模

我们采用4位二进制编码,这样会产生16种不同的结果,相当于将区间分成了16份,每一份长度0.25;

取种群规模为4;初始种群为随机产生的4个二进制字符串:

x1:0110

x2:1100

x3:0011

x4:0010

2.定义适应度函数 $遗传算法(GA)入门知识梳理(超详细)-编程知识网$

四个个体的适应度为:

f(x1)=f(6×0.25)=2.25

f(x2)=f(12×0.25)=9

f(x3)=f(3×0.25)=0.5625

f(x4)=f(2×0.25)=0.25

3.根据轮盘赌算法计算各个个体的选择概率:

p(x1)=0.184

p(x2)=0.75

p(x3)=0.046

p(x4)=0.02

从0和1之间产生四个随机数,如果随机数的值小于p(x),则表明该个体被选中,进行一轮复制;假设随机数为r1=0.13,r2=0.42,r3=0.36,r4=0.11,则产生的群体为

x1'=0110;

x2'=1100;

x3'=0110(x3被舍去,复制x1);

x4'=0010(x4被舍去,复制x2);

4.交叉

产生随机数,若小于交叉概率Pc,则发生交叉,假设x1'与x2'的后两位发生交换,得到种群

x1''=0100

x2''=1110

x3'=0110

x4'=0010

5.变异

产生随机数.若小于变异概率Pm,则发生变异,假设x2''的最后以为发生变异,得到种群

x1''=0100

x2'''=1111

x3'=0110

x4'=0010

这样进行一轮进化,得到的新种群

x1''=0100

x2'''=1111(适应度最高)

x3'=0110

x4'=0010

出现了适应度最高的个体x2''',将该字符串输出,就得到相应区间[0,4]中的函数值最大的x=4

这是一个简单的二次函数实例,有了这个思想,在实际操作中,我们更常用到的是二元函数的最值问题,例如:

求 $遗传算法(GA)入门知识梳理(超详细)-编程知识网$ , $遗传算法(GA)入门知识梳理(超详细)-编程知识网$ 的最大值

如以下代码:

#pragma once//保证文件只被编译一次
#include<random>
#include<vector>
#include<iostream>
#include<cmath>
#include<ctime>
#include <cstdlib>
#include <bitset>
#include<iomanip>
using namespace std;
const double PI = 3.141592653589793;//定义一个不可改变的常量值PI
const int Po_Size = 50;//种群规模
const int Ev_Algebra = 500;//进化代数
const double Ov_Probability = 0.850; //交叉概率,交叉概率用于判断两两个体是否需要交叉
const double Va_Probability = 0.050;//变异概率,变异概率用于判断任一个体是否需要变异
const int De_Variable = 2;//函数自变量的个数,如果要进行多元函数的最值求解，直接修改自变量数个De_Variable即可
const int length1 = 24;//精确到6位小数，用24位二进制编码
const int length2 = 23;//精确到6位小数，用23位二进制编码
class X_Range //自变量取值范围类，适用于多个变量
{
private:double Upper;//变量的上界取值double Lower;//变量的下界取值
public:X_Range(double m_Upper, double m_Lower);//构造函数double GetUpper()const;//获取变量上限double GetLower()const;//获取变量下限
};
class Individual //定义个体类
{
private:double Variable[De_Variable];//存放变量x1,x2,x3........double Fitness;//适应值double ReFitness;//适应值概率double SumFitness;//累加概率，为轮盘转做准备
public:Individual() {}//默认构造函数Individual(double* m_Variable);//构造函数double* GetVariable();//获取变量值void ChaFitness(const double m_fitness);//修改适应值void ChaReFitness(const double m_ReFitness);//修改适应值概率void ChaSumFitness(const double m_SumFitness);//修改累加概率double GetFitness()const;//获取适应值double GetReFitness()const;//获取适应值概率double GetSumFitness()const;//获取累加概率
};
void Initialize();//随机初始化种群，得到第一代个体
void CaculaFitness();//计算个体的适应值
void CaculaReFitness();//计算个体的适应值概率
void CalculaSumFitness();//计算累加个体概率
void seclect();//种群选择
double Scand();//随机产生0到49的随机整数
void crossing();//杂交
void variating();//变异
void genetic_algorithm();//遗传算法
#include"GeneticAlgorithm.h"//包含头文件
//自变量取值范围向量和种群向量定义
const X_Range Range[De_Variable] = { X_Range(-3.0,12.1) ,X_Range(4.1,5.8) };//自变量（或者基因）x1,x2的取值范围
vector<Individual> nowpopulation;//P(t)种群
vector<Individual> midpopulation;//中间种群，存放轮盘选择后的优秀个体
vector<Individual> nextpopulation;//P(t+1)种群
//X_Range类实现
X_Range::X_Range(double m_Lower, double m_Upper) :Lower(m_Lower), Upper(m_Upper){}//X_Range类构造函数实现
double X_Range::GetUpper()const//获取变量上限
{return Upper;
}
double X_Range::GetLower()const//获取变量下限
{return Lower;
}
//Individual类实现
Individual::Individual(double* m_Variable)//构造函数
{for (int i = 0; i < De_Variable; i++)//用for循环自变量逐个赋值{if (m_Variable[i] >= Range[i].GetLower() && m_Variable[i] <= Range[i].GetUpper())//这里要进行自变量取值范围判断{Variable[i] = m_Variable[i];//自变量赋值}else//不满足要求则发出出错警告并返回{cerr << "自变量取值不满足要求" << endl;exit(1);//停止程序，我会以随机函数的方式生成自变量的值(基因值)，这里说明基因值不在规定范围内}}//初始化时默认适应值等值为0this->Fitness = 0;this->ReFitness = 0;this->SumFitness = 0;
}
double* Individual::GetVariable()//获取基因值
{return Variable;
}
double Individual::GetFitness()const//获取适应值
{return Fitness;
}
double Individual::GetReFitness()const //获取适应值概率
{return ReFitness;
}
double Individual::GetSumFitness()const//获取累加概率
{return SumFitness;
}
void Individual::ChaFitness(const double m_fitness)//修改适应值
{this->Fitness = m_fitness;
}
void Individual::ChaReFitness(const double m_ReFitness)//修改适应值概率
{this->ReFitness = m_ReFitness;
}
void Individual::ChaSumFitness(const double m_SumFitness)//修改累加概率
{this->SumFitness = m_SumFitness;
}
//遗传算法的准备工作
void Initialize()//随机初始化种群，得到第一代种群
{
//产生指定范围的随机变量（基因）double X[Po_Size][De_Variable];//为了使程序可以满足多元函数最值的计算，用矩阵保存产生的随机数变量值for (int j = 0; j < De_Variable; j++){default_random_engine e(time(0));//引擎，生成随机序列uniform_real_distribution<double> u(Range[j].GetLower(), Range[j].GetUpper());//分布for (int i = 0; i < Po_Size; i++)//先按列存储随机数{X[i][j] = u(e);//循环结束时，所有随机值就保存在X矩阵中}}
//生成对象（染色体）并加入到初始种群中for (int i = 0; i < Po_Size; i++){double variable[De_Variable];for (int j = 0; j < De_Variable; j++){variable[j] = X[i][j];//按行保存}Individual Indivi(variable);//生成一个对象（染色体）nowpopulation.push_back(Indivi);//加入到种群population中}
}
void CaculaFitness()//计算个体的适应值
{//f(x1,x2) = 21.5+x1*sin(4pi*x1)+x2*sin(20pi*x2)）为适应度计算函数double fitness = 0;//临时适应值double x[De_Variable];//临时存储自变量（基因）for (int i = 0; i < Po_Size; i++){for (int j = 0; j < De_Variable; j++)x[j] = nowpopulation.at(i).GetVariable()[j];//这样更直观fitness = 21.5 + x[0] * sin(4 * PI*x[0]) + 2 * sin(20 * PI*x[1]);//适应度计算nowpopulation.at(i).ChaFitness(fitness);//修改当前染色体的适应值}
}
void CaculaReFitness()//计算适应值概率
{double sum = 0;//适应值累加器double temp = 0;for (int i = 0; i < Po_Size; i++)//计算出适应值之和{sum += nowpopulation.at(i).GetFitness();}for (int j = 0; j < Po_Size; j++){temp = nowpopulation.at(j).GetFitness() / sum;//计算概率nowpopulation.at(j).ChaReFitness(temp);//修改个体的适应度概率}
}
void CalculaSumFitness()//计算累加个体概率
{double summation = 0;//累加器for (int k = 0; k < Po_Size; k++){summation += nowpopulation.at(k).GetReFitness();nowpopulation.at(k).ChaSumFitness(summation);//当前累加结果赋值}
}
void seclect() //种群选择
{//随机生生成0到1的小数double array[Po_Size];//随机数保存变量default_random_engine e(time(0));//引擎，生成随机序列uniform_real_distribution<double> u(0.0, 1.0); //分布for (int i = 0; i < Po_Size; i++)array[i] = u(e);//轮盘进行选择for (int j = 0; j < Po_Size; j++){for (int i = 1; i < Po_Size; i++){if (array[j] < nowpopulation[i - 1].GetSumFitness()){midpopulation.push_back(nowpopulation.at(i - 1));//加入到中间种群}if (array[j] >= nowpopulation.at(i - 1).GetSumFitness() && array[j] <= nowpopulation.at(i).GetSumFitness()){midpopulation.push_back(nowpopulation.at(i));//加入到中间种群}}}nowpopulation.clear();//清空nowpopulation
}
double Scand() //随机产生0到1的小数
{int N = rand() % 999;return double(N)/1000.0;;//随机产生0到1的小数
}
void crossing()//杂交
{int num = 0;//记录次数double corss = 0.0;//保存随机产生的概率值srand((unsigned)time(NULL));//根据系统时间设置随机数种子,设置一次随机种子就行double array1[De_Variable], array2[De_Variable];//临时存储父亲和母亲的变量值while (num< Po_Size-1)//个体1与个体2杂交，个体3与个体4杂交......个体i和个体i+1杂交{//判断双亲是否需要杂交，随机生成一个0到1的小数，如果这个数大于杂交概率，则放弃杂交，直接遗传给下一代，否则，对父母体进行杂交corss = Scand();if (corss <= Ov_Probability)//如果corss小于等于杂交概率Ov_Probability就进行单点杂交{//首先寻找对应下标的个体并且保存for (int i = 0; i < De_Variable; i++){array1[i] = midpopulation.at(num).GetVariable()[i];//父亲的自变量array2[i] = midpopulation.at(num + 1).GetVariable()[i];//母亲自变量}int localx1, localx2;//记录基因交叉点的位置int corssx1[length1], corssx2[length2];//作为交换基因的数组double newx1[2], newx2[2];//分别用来保存基因交换后所对应自变量值bool p1 = true, p2 = true;//然后对双亲变量进行编码并且进行单点杂交for (int j = 0; j < De_Variable; j++)//array1的x1编码之后和array2的x1编码后进行单点杂交，以此类推{if (j == 0)//x1进行编码并且杂交{bitset<length1> array1b1((array1[j] + 3.0)* pow(10, 6));//加上3.0形成一个unsigaed数之后在进行母体1的x1编码bitset<length1> array2b1((array2[j] + 3.0)* pow(10, 6));//加上3.0形成一个unsigaed数之后在进行母体2的x1编码//现在随机生成0到length1-1的数，确定交叉点的位置localx1 = rand() % length1;//现在进行单点交叉，交换双亲localx1后面的基因for (int i = 0; i < localx1; i++)corssx1[i] = array1b1[i];for (int k = 0; k < localx1; k++)array1b1[k] = array2b1[k];for (int s = 0; s < localx1; s++)array2b1[s] = corssx1[s];//新值保存在newx1数组中，x1基因完成单点杂交操作newx1[0] = double(array1b1.to_ullong()) / pow(10, 6) - 3.0;newx2[0] = double(array2b1.to_ullong()) / pow(10, 6) - 3.0;//对新产生的值进行判断，判断是否超出范围，如果超出范围则不杂交if (newx1[0]< Range[0].GetLower() || newx1[0]>Range[0].GetUpper() || newx2[0]<Range[0].GetLower() || newx2[0]>Range[0].GetUpper()){p1 = false;break;}}if (j == 1)//x2进行编码并且杂交{bitset<length2> array1b2((array1[j]) * pow(10, 6));//母体1的x2编码bitset<length2> array2b2((array2[j]) * pow(10, 6));//母体2的x2编码//现在随机生成0到length2-1的数，确定交叉点的位置localx2 = rand() % length2;//现在进行单点交叉，交换双亲localx2后面的基因for (int i = 0; i < localx2; i++)corssx2[i] = array1b2[i];for (int k = 0; k < localx2; k++)array1b2[k] = array2b2[k];for (int s = 0; s < localx2; s++)array2b2[s] = corssx2[s];//新值保存在newx2数组中，x2基因完成单点杂交操作newx1[1] = double(array1b2.to_ullong()) / pow(10, 6);newx2[1] = double(array2b2.to_ullong()) / pow(10, 6);//对新产生的值进行判断，判断是否超出范围，如果超出范围则不杂交if (newx1[1]< Range[1].GetLower() || newx1[1]>Range[1].GetUpper() || newx2[1]<Range[1].GetLower() || newx2[1]>Range[1].GetUpper()){p2 = false;break;}}}if (p1 == true && p2 == true){Individual newchiled1(newx1);Individual newchiled2(newx2);nextpopulation.push_back(newchiled1);nextpopulation.push_back(newchiled2);}else//将原来的个体遗传给下一代{nextpopulation.push_back(midpopulation.at(num));nextpopulation.push_back(midpopulation.at(num + 1));}}else//否则直接遗传给下一代nextpopulation{nextpopulation.push_back(midpopulation.at(num));//生成一个新的个体并且加入到nextpopulation中nextpopulation.push_back(midpopulation.at(num + 1));}num += 2;}midpopulation.clear();//清空midpopulation
}
void variating()//变异
{int num = 0;while (num<Po_Size){double variation = Scand();//随机产生一个0到1的小数，用于判断是否进行变异if (variation <= Va_Probability)//如果variation小于变异系数，则需要进行变异{double x[2];bool p = true;int x1local, x2local;x[0] = nextpopulation.at(num).GetVariable()[0];x[1] = nextpopulation.at(num).GetVariable()[1];bitset<length1> array1((x[0]+ 3.0)* pow(10, 6));//x1编码bitset<length2> array2(x[1]*pow(10,6));//x2编码x1local = rand() % length1;//array1该位取反x2local = rand() % length2;//array2该位取反array1.flip(x1local);//改变array1 x1local位的状态array2.flip(x2local);//改变array2 x2local位的状态x[0] = double(array1.to_ullong()) / pow(10, 6) - 3.0;x[1] = double(array2.to_ullong()) / pow(10, 6);//判断是否符合条件if (x[0]< Range[0].GetLower() || x[0]>Range[0].GetUpper() || x[1]<Range[1].GetLower() || x[1]>Range[1].GetUpper())p = false;if (!p)nowpopulation.push_back(nextpopulation.at(num));if (p){Individual newchiled(x);nowpopulation.push_back(newchiled);}}elsenowpopulation.push_back(nextpopulation.at(num));num++;}nextpopulation.clear();//清空nextpopulation
}
void genetic_algorithm()
{Initialize();//初始化种群,随机生成第一代个体//进化500代for (int i = 0; i < Ev_Algebra; i++){CaculaFitness();//适应度计算CaculaReFitness();//适应度概率计算CalculaSumFitness();//计算累加个体概率seclect();//选择crossing();//杂交variating();//变异}CaculaFitness();//适应度计算double maxfitness=nowpopulation.at(0).GetFitness();int maxid = 0;int k;for (k = 0; k < Po_Size; k++){if (maxfitness < nowpopulation.at(k).GetFitness()){maxfitness = nowpopulation.at(k).GetFitness();maxid = k;}}//进化500代之后输出cout << "x1"<<setw(10)<<"x2" << setw(15)<<"Fitness" << endl;for (int j = 0; j < Po_Size; j++)cout<<nowpopulation.at(j).GetVariable()[0]<<setw(10)<<nowpopulation.at(j).GetVariable()[1] << setw(10) <<nowpopulation.at(j).GetFitness() << endl;cout << "x1=" << nowpopulation.at(maxid).GetVariable()[0] << " ，" << "x2=" << nowpopulation.at(maxid).GetVariable()[1] << "时取得最大值：" << maxfitness << endl;
}
int main()
{genetic_algorithm();system("pause");return 0;
}

运行结果:

遗传算法(GA)入门知识梳理(超详细)

一、遗传算法的生物背景