智能优化算法——遗传算法原理（附代码）

最新推荐文章于 2024-04-16 22:46:08 发布

置顶 hser-chen

最新推荐文章于 2024-04-16 22:46:08 发布

阅读量1w

点赞数 25

分类专栏：优化算法 c++ 研究生数学文章标签：遗传算法 C++ 实现应用实例智能优化算法

本文链接： https://blog.csdn.net/weixin_41788456/article/details/100550968

版权

c++ 同时被 3 个专栏收录

25 篇文章 3 订阅

订阅专栏

研究生数学

12 篇文章 4 订阅

订阅专栏

优化算法

8 篇文章 3 订阅

订阅专栏

遗传算法从代表问题的潜在解集的一个种群开始，而种群由基因编码的一定数目的个体组成。个体是染色体带有特征的实体，染色体由多个基因组成，也可以把基因描述成未编码之前的优化变量。每一代，根据个体适应度选择个体，借助自然遗传学的遗传算子进行组合交叉和变异来更新种群，整个过程模拟自然进化，末代种群的最优个体通过解码就是问题的最优解。

算法模型

遗传算法流程图

相关生物学术语

基因型(genotype)：性状染色体的内部表现；

表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；

进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness)：度量某个物种对于生存环境的适应程度。

选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。

交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。

编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。

解码(decoding)：基因型到表现型的映射。

个体（individual）：指染色体带有特征的实体；

种群（population）：个体的集合，该集合内个体数称为种群

遗传算法的基本操作

编码

即表现型转为基因型，在算法里为实数转化为二进制，解码反之。

举个例子：对于x∈[-1, 2] ，结果精确到6位小数，十进制实数与二进制编码之间应满足怎样的数学关系？

1.将二进制串 $\left ( b_{21} b_{20}b_{19}\cdots b_{0}\right )_{2}$ 转换为十进制为：

       $x{}'=\left ( b_{21} b_{20}b_{19}\cdots b_{0}\right )_{2}=(\sum_{i=0}^{21}b_{i}\cdot 2^{i})_{10}$                               (1)

2.将二进制串对应的实数x为

          $x=-1.0+\frac{x{}'}{2^{22}-1}\times 3$                                 (2)

    例如(1000101110110101000111)表示0.637197，因为

    $x{}'=(\sum_{i=0}^{21}b_{i}\cdot 2^{i})_{10}=2288967$                                             (3)

          $x=-1.0+\frac{2288967}{2^{22}-1}\times 3=0.637197$                                  (4)

选择

选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中，主要思想: 适应值较高的染色体有较大的选择(复制)机会。

轮盘法：

将种群中所有染色体的个体相加求总和，个体适应值按其比例转化为选择概率Ps；
产生一个在0与总和之间的的随机数m；
从种群中第一个个体开始，将其适应值与后续个体的适应值相加，直到累加和等于或大于m，更新种群中的个体。

设种群的规模为N， $x_{i}$ 为种群的第i个个体，F(x)为适应度函数，则个体 $x_{i}$ 被选择的概率：

$P_{s}=\frac{F(x_{i}))}{\sum_{j=1}^{N}F(x_{j})}$ (5)

从上面可以得出，遗传算法的适应度函数的值要取正值，并且优化模型应该是求最大值和非负的目标函数。

交叉

遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。

单点交叉方法：在双亲的父代染色体中以一定概率随机产生一个交叉点位置，在交叉点位置分离双亲染色体互换交叉点位置右边的基因码产生两个子代个体。本文采用两点交叉，确定方法类似。

变异

以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由1变成0。

停止准则

种群中个体的最大适应值超过预设定值
种群中个体的平均适应值超过预设定值
种群中个体的进化代数超过预设定值

参数分析

种群规模N

当规模太小时，会出现近亲交配，产生病态基因；种群规模较大，难以收敛，稳健性下降。一般取0—100。

变异概率

当变异概率太小时，种群的多样性下降太快，导致有效基因的迅速丢失且不容易修补；当变异概率太大是，高阶模式被破坏的概率随之增大。一般取0.0001—2。

交叉概率

更新种群的重要方式，交配概率太大破坏已有的有利模式，随机性增大，容易错失最优个体；交配概率太小不能有效更新种群，一般取0.4—0.99。

进化代数

进化代数太小，算法不容易收敛，种群还没有成熟；代数太大，进化没有意义，浪费时间和资源。一般取100—500。

C++程序测试Sphere函数

$f\left ( x \right )=\sum_{i=1}^{D}x_{i}^{2}$

通过程序计算，迭代200步，用origin整理如下：

从上图可以看书，收敛用时还是比较少，在50步左右就收敛了。

总结

遗传算法的优点：

与问题领域无关、快速随机的搜索能力。
潜在的并行性，多个个体的同时比较，鲁棒性强。
使用概率机制进行迭代，具有随机性。
具有可扩展性，容易与其他算法结合。

遗传算法的缺点：

编程实现比较复杂,需要对问题进行编码,得到最优解还需要解码。
另外三个算子的实现也有许多参数,如交叉率和变异率，并且这些参数的选择严重影响解的品质，而目前这些参数的选择大部分是依靠经验。
算法的搜索速度比较慢，要得要较精确的解需要较多的时间。
算法的并行机制的潜在能力没有得到充分的利用。

visual studio2017c++源代码

pch.h头文件：

// Geneti_algorithm.cpp : 遗传算法实现过程。更新于2020.5.3
//开发人员：陈帅   开始日期：2019.8.5-8.8         邮箱：chenshuai0614@hrbeu.edu.cn
#ifndef PCH_H
#define PCH_H
#include <iostream>
# include <fstream>
#include <iomanip>
#include <math.h>
#include <vector>
#include<random>
#include<ctime>
using namespace std;
//产生随机小数或整数
class RandomNumber {
public:
	RandomNumber() {
		srand(time(0));    //析构函数，在对象创建时数据成员执行初始化操作
	}
	int integer(int begin, int end)
	{
		return rand() % (end - begin + 1) + begin;
	}
	double decimal(double a, double b)
	{
		return double(rand() % 10000) / 10000 * (b - a) + a;
	}
};
//ga用于定义优化变量范围，以及遗传算法过程中的选择、交叉、变异算子、解码、个体适应度计算等函数。
class ga
{
private:
       //==========================遗传算法参数设置=============================
	int  N_genetic ;                //种群规模，太小产生病态基因；种群规模太大，难以收敛，一般0-100
	double M_pgentic ;            //变异概率，与种群多样性有关，一般0.0001-0.2
	double C_pgentic ;             //交叉概率，概率太大，容易错失最优个体，太小布恩那个有效更新种群，一般0.4-0.99.
	int E_gentic ;                 //进化代数，太小，算法不容易收敛，太大增加时间和资源浪费，一般100-500.
	int L_variable;                //个体变量的字符串长度(基因数)
	double precision;
	int N_variable ;                 //个体变量的个数
public:
	vector<vector<double>>x_i;          //优化变量
	vector<double>x_best;               //最优个体
	vector<vector<int>>x_binary;        //个体染色体
	vector<double> fitness;             //个体适应度;由于适应度函数要比较排序并在此基础计算选择概率，适应度函数的值应该取正值。
	double best_fitness;                //种群最优适应度
	vector<double> sumfitness;          //前面个体适应度和
	vector<double> P_i;                 //个体被选择的概率	
	vector<double>x_low = { -600 };     //优化变量最小值
	vector<double>x_high = { 600 };     //优化变量最大值
	void initialize();//初始化，产生初始种群
	vector<double> Real_trans(vector<int>x_binary);   //二进制转换为实数
	void SetParameters();               //设置算法参数
	void Optimization_iteration();
	void select_operator();             //选择算子
	void crossover_operator();          //交叉算子
	void mutate_operator();             //变异算子	
};
double function(vector<double> x); //目标函数
#endif //PCH_H

Genetic_algorithm.cpp主函数

#include "pch.h"
int main()
{
	ga GA;          //定义全局遗传算法相关函数
	//=========================设置算法参数====================
	GA.SetParameters();
	//========================初始化并赋值=====================
	GA.initialize();
	//=====================优化迭代并输出结果=======================
	GA.Optimization_iteration();
}

ga_function.cpp函数文件：

#include "pch.h"
//=============================设置参数====================================
void ga::SetParameters()
{
	N_genetic = 50;                //种群规模，太小产生病态基因；种群规模太大，难以收敛，一般0-100
	M_pgentic = 0.25;            //变异概率，与种群多样性有关，一般0.0001-0.2
	C_pgentic = 0.5;             //交叉概率，概率太大，容易错失最优个体，太小布恩那个有效更新种群，一般0.4-0.99.
	E_gentic = 400;                 //进化代数，太小，算法不容易收敛，太大增加时间和资源浪费，一般100-500.
	precision=0.001;
	L_variable =  int(log((x_high[0] - x_low[0]) / precision + 1) / log(2));//个体变量的字符串长度(基因数)
	N_variable=2;
}
//***************************
//二进制转换为实数
//******************************
vector<double> ga::Real_trans(vector<int>x_binary)
{
	vector<int>x_decimal(N_variable);
	vector<double>x(N_variable);
	for (int j = 0; j < N_variable; j++)
	{
		for (int k = j * L_variable, l_gen = 0; k < (j + 1)*L_variable; k++, l_gen++)
		{
			x_decimal[j] = x_decimal[j] + x_binary[k] * pow(2, l_gen);
		}
		x[j] = x_low[0] + double(x_decimal[j]) / (pow(2, L_variable ) - 1)*(x_high[0] - x_low[0]);
	}
	return x;
}
//*******************
//初始化并赋值
//*******************
void ga::initialize()
{
	extern RandomNumber r;       //定义全局随机数
	x_i.resize(N_genetic, vector<double>(N_variable));
	x_best.resize(N_variable);
	fitness.resize(N_genetic);
	x_binary.resize(N_genetic, vector<int>(N_variable*L_variable)); //优化变量二进制
	for (int i = 0; i < N_genetic; i++)
	{
   //================================基因编码===============================================
		for (int j = 0; j < N_variable*L_variable; j++)
		{
			x_binary[i][j] = r.integer(0,1);
			cout<< x_binary[i][j];
		}
		cout << endl;
		x_i[i]=Real_trans(x_binary[i]);
		fitness[i] =1/function(x_i[i]);
	}
	x_best = x_i[0];                      //初始化最优个体
	best_fitness = fitness[0];
	for (int i = 1; i < N_genetic; i++)
	{
		if (best_fitness < fitness[i])
		{
			best_fitness = fitness[i];
			x_best = x_i[i];
		}
	}
}
void ga::Optimization_iteration()
{
	clock_t startTime, endTime; //定义程序开始运行时间和结束时间
	startTime = clock();        //计时开始
	ofstream out("遗传算法优化结果.txt");
	for (int i = 0; i < E_gentic; i++)
	{
		select_operator();  //选择父代更新个体
		crossover_operator();  //有交配权的所有父代进行交叉
		mutate_operator();     //个体变异
		for (int j = 0; j< N_genetic; j++)
		{
			fitness[j] = 1 / function(x_i[j]);
			if (best_fitness < fitness[j])
			{
				best_fitness = fitness[j];
				x_best = x_i[j];
			}
		}   //种群选优
		out << i << fixed << setw(12) << setprecision(5) <<1/ best_fitness << endl;

	}
	out << "最优变量:" << endl;
	for (int i = 0; i < N_variable; i++)
	{
		out << "x" << i << "=" << fixed << setw(12) << setprecision(5) << x_best[i] << endl;//输出最优变量
	}
	out << "最优值=" << fixed << setw(12) << setprecision(5) << 1 / best_fitness << endl;
	endTime = clock();//计时结束
	out << "run time:" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	out.close();
}

//*******************
//选择算子函数
//*******************
void ga::select_operator()
{
	
	double totalfit = 0, p_i;
	sumfitness.resize(N_genetic);
	P_i.resize(N_genetic);
	extern RandomNumber r;       //随机数
	vector<vector<int>>new_x_binary(N_genetic, vector<int>(N_variable*L_variable));//储存选择产生的新个体
	for (int i = 0; i < N_genetic; i++)
	{
		sumfitness[i] = totalfit + fitness[i];
		totalfit = totalfit + fitness[i];
	}
	//计算个体概率
	for (int i = 0; i < N_genetic; i++)
	{
		P_i[i] = sumfitness[i] / totalfit;
	}
	//选择父代
	for (int i = 0; i < N_genetic; i++)
	{
		p_i = r.decimal(0, 1.0);
		//利用轮盘法选择个体
		if (p_i <= P_i[0])
			new_x_binary[i] = x_binary[0];
		else
		{
			for (int j = 0; j < N_genetic - 1; j++)
			{
				if (p_i > P_i[j]&&p_i <= P_i[j+1])
					new_x_binary[i] = x_binary[j + 1];
			}
		}
	}
	//更新个体
	x_binary = new_x_binary;
}
//*******************
//交叉算子函数，两点交叉
//*******************
void ga::crossover_operator()
{
	int  cpoint1, cpoint2, t;                //交叉点cpoint1, cpoint2生成,t为替换值
	double p_c;                              //随机产生交叉概率
	extern RandomNumber r;       //随机数
	for (int i = 0; i < N_genetic; i = i + 2)
	{//随机产生两个交叉点的数
		cpoint1 = r.integer(0, N_variable* L_variable-1);
		cpoint2 = r.integer(0, N_variable* L_variable-1);
		if (cpoint2 < cpoint1)
		{
			t = cpoint2; cpoint2 = cpoint1; cpoint1 = t;
		}
		p_c = r.decimal(0, 1.0);
		//交叉过程
		if (p_c < C_pgentic)
		{
			for (int j = cpoint1; j <= cpoint2; j++)
			{
				t = x_binary[i][j]; x_binary[i][j] = x_binary[i+1][j]; x_binary[i+1][j] = t;
			}
		}
	}	
}
//*******************
//变异算子函
//*******************
void ga::mutate_operator()
{
	int  mpoint;//变异点mpoint生成
	double p_m;
	extern RandomNumber r;       //定义全局随机数
	for (int i = 0; i < N_genetic; ++i)
	{//随机产生变异点
		mpoint = r.integer(0, N_variable* L_variable-1);
		p_m = r.decimal(0, 1.0);
		if (p_m < M_pgentic)
			if (x_binary[i][mpoint] == 0)
			{
				x_binary[i][mpoint] = 1;
			}
			else {
				x_binary[i][mpoint] = 0;
			}
	}
	//变异后的染色转换为实数
	for (int i = 0; i < N_genetic; i++)
	{
		x_i[i] = Real_trans(x_binary[i]);
	}
}

源文件下载地址

https://download.csdn.net/download/weixin_41788456/11828560

各位阅读文章的朋友觉得文章可以给个好评或者点赞，大家觉得有问题可以在评论区指出来或者发邮箱chenshuai0614@hrbeu.edu.cn联系我！如需要转载请附上链接，谢谢各位朋友！

（更新于2020.05.03）

hser-chen

关注关注

25
点赞
踩
107

收藏

觉得还不错? 一键收藏
7
评论
智能优化算法——遗传算法原理（附代码）

目录基本概念算法模型相关生物学术语遗传算法的基本操作参数分析 C++程序应用实例1 C++程序应用实例2 总结 visual studio2017c++源代码源文件下载地址个人申明基本概念遗传算法（genetic algorithm，GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通...
复制链接

扫一扫