首页 > 编程语言 >优化算法——遗传算法

优化算法——遗传算法

时间:2023-06-14 21:01:38浏览次数:49  
标签:杂交 编码 二进制 个体 变异 算法 遗传算法 优化


与遗传算法的第一次接触

遗传算法是我进入研究生阶段接触的第一个智能算法,从刚开始接触,到后来具体去研究,再到后来利用遗传算法完成了水利水电的程序设计比赛,整个过程中对遗传算法有了更深刻的理解,在此基础上,便去学习和研究了粒子群算法,人工蜂群算法等等的群体智能算法。想利用这个时间,总结下我对于遗传算法的理解,主要还是些基本的知识点的理解。
##遗传算法的基本概念
遗传算法(Genetic Algorithm, GA)是由Holland提出来的,是受遗传学中的自然选择和遗传机制启发发展起来的一种优化算法,它的基本思想是模拟生物和人类进化的方法求解复杂的优化问题。

基本定义

  1. 个体(individual):在遗传学中表示的是基因编码,在优化问题中指的是每一个解。
  2. 适应值(fitness):评价个体好坏的标准,在优化问题中指的是优化函数。
  3. 群体(population): 由个体组成的集合
  4. 遗传操作:遗传操作的主要目的是用于在当前的群体中产生新的群体,主要的操作包括:选择(selection)、交叉(crossover)、变异(mutation)。

遗传算法的基本流程

遗传算法的过程中主要包括这样几个要素:1、参数的编码。2、初始群体的设定。3、适应度函数的设计。4、遗传操作设计。5、控制参数的设定。

基本遗传算法的具体过程如下:

优化算法——遗传算法_遗传算法

遗传算法过程中的具体操作

参数的编码

遗传算法中的参数编码的方式主要有:1、二进制编码。2、Gray编码。3、实数编码。4、有序编码。

二进制编码

二进制编码是最原始的编码方式,遗传算法最初是在二进制编码的方式下进行运算的。二进制编码也是遗传算法中使用最为直接的运算编码方式。二进制编码是指利用优化算法——遗传算法_优化问题_02优化算法——遗传算法_优化问题_03对问题的解向量进行编码。例如,对于如下的优化问题:

优化算法——遗传算法_遗传操作_04

优化算法——遗传算法_遗传操作_05

其三维图像如下图所示:

优化算法——遗传算法_优化问题_06


在对这样的优化问题进行二进制编码的过程中,是将问题的可能解编码为二进制位串,例如问题的可能解为实数对优化算法——遗传算法_GA_07,首先必须将优化算法——遗传算法_GA_08优化算法——遗传算法_GA_09分别使用二进制位串表示,然后将他们的二进制位串组合在一起。对于每一个变量的二进制位串的长度取决于变量的定义域所要求的精度。


二进制位串的长度的计算方法如下:
假设优化算法——遗传算法_优化问题_10,所要求的精度是小数点后优化算法——遗传算法_遗传算法_11位。这要求将区间划分为至少优化算法——遗传算法_遗传操作_12份。假设表示变量优化算法——遗传算法_优化算法_13的位串的长度用优化算法——遗传算法_遗传操作_14表示,则优化算法——遗传算法_遗传操作_14可取为满足下列不等式的最小数优化算法——遗传算法_优化问题_16
优化算法——遗传算法_遗传操作_17
即有:
优化算法——遗传算法_优化问题_18


对于上述的优化问题,假设精度为小数点后优化算法——遗传算法_优化问题_19位,则:

优化算法——遗传算法_GA_20

优化算法——遗传算法_遗传算法_21

那么表示变量优化算法——遗传算法_GA_08的二进制位串的长度为优化算法——遗传算法_遗传算法_23

同理,对于变量优化算法——遗传算法_GA_09

优化算法——遗传算法_优化算法_25

优化算法——遗传算法_GA_26

表示变量优化算法——遗传算法_GA_09的二进制位串的长度为优化算法——遗传算法_遗传算法_28

此时,个体可以表示为:

优化算法——遗传算法_优化算法_29


其中,前优化算法——遗传算法_优化算法_30位表示的是优化算法——遗传算法_GA_08,后优化算法——遗传算法_遗传操作_32位表示的是优化算法——遗传算法_GA_09

Gray编码

这种编码方式在求解优化问题时,本人基本上没做过任何研究。

实数编码

在二进制编码的过程中存在这样的一个问题,即在计算适应值的时候需要将二进制编码转换成十进制的编码进行运算,这样,很显然会想到能否直接使用十进制编码直接进行运算,如上例中的优化算法——遗传算法_GA_07这样的编码方式。

有序编码

有序编码主要使用在TSP问题中,在本文中主要涉及二进制编码和实数编码

初始群体的设定

在解决了个体的编码问题后,需要解决的问题是如何利用个体表示群体。在上述中,我们知道,群体是个体的集合。假设初始群体的大小为优化算法——遗传算法_GA_35。对于二进制编码方式与实数编码方式产生优化算法——遗传算法_GA_36个初始解。如:
优化算法——遗传算法_遗传算法_37
对应的实数编码的方式则为:
优化算法——遗传算法_优化问题_38
对于二进制编码则是随机初始化优化算法——遗传算法_GA_36组这样的初始解,每组初始解随机初始化优化算法——遗传算法_优化算法_40位的优化算法——遗传算法_GA_41编码。而对于实数编码方式,则是在区间上随机初始化优化算法——遗传算法_GA_36组初始解。

适应度函数的计算

适应度函数的目的是评价个体的好坏,如上面的优化问题中,即为最终的优化目标函数。对于二进制编码,则需要先将二进制编码转换成实数编码,再进行适应值函数的计算,对于实数编码方式,则直接进行适应值函数的计算。

遗传操作设计

遗传操作主要包括:选择(selection)、交叉(crossover)、变异(mutation),遗传操作的主要目的是从当前的群体中产生新的群体,这样便能使得产生新的更优的个体。

选择(selection)

选择操作的目的是选择出父体,用于参加交叉(crossover)和变异(mutation)操作。一般使用较多的方式是轮盘赌的选择策略(Roulette Wheel Selection)。根据每个个体的适应值,计算出相对适应值大小,即:

优化算法——遗传算法_遗传算法_43

相对适应值又称为选择概率,将一个圆盘划分成优化算法——遗传算法_GA_44份,即群体的大小。每个扇面的面积与其选择概率成正比。轮盘如下图所示:

优化算法——遗传算法_遗传算法_45


现在在优化算法——遗传算法_优化算法_46上产生一个随机数优化算法——遗传算法_优化算法_47,若:

优化算法——遗传算法_遗传算法_48

则选择第优化算法——遗传算法_优化算法_49个个体。

重复此操作优化算法——遗传算法_GA_44次,选择出优化算法——遗传算法_GA_44个父体。轮盘赌的算法过程如下所示:

优化算法——遗传算法_遗传操作_52

交叉(crossover)

交叉操作也称为杂交,其目的是产生新的个体。

对于二进制编码方式,主要有单点杂交和多点杂交。单点杂交是指在二进制串中随机选择一位,交换两个父体中该位以后的二进制串,用以产生新的个体,操作如下图所示:

优化算法——遗传算法_优化算法_53


多点杂交是指在二进制串中选择某几位进行杂交,其中以两点杂交最为常见,其过程如下图所示:

优化算法——遗传算法_遗传算法_54


具体的操作过程为:设定一个杂交的概率优化算法——遗传算法_遗传算法_55,对选择操作中产生的优化算法——遗传算法_GA_44个父体,每个父体产生一个优化算法——遗传算法_优化算法_46区间上的随机数优化算法——遗传算法_遗传操作_58,若优化算法——遗传算法_遗传算法_59,则将第优化算法——遗传算法_优化问题_60个个体用于杂交,若选择出来的个体数目是奇数,则在父体集合中再随机挑选一个,以保证挑选出的是偶数个,之后进行两两杂交操作。

对于实数编码形式,可以将实数转换成二进制编码的形式进行杂交运算,但是这样同样存在效率的问题,在实数编码中,主要采用的是算术杂交方式,算术杂交分为:部分算术杂交和整体算术杂交。部分算术杂交是指在父体向量中选择一部分分量进行算术运算,而整体算术杂交是指全部的分量都进行算术运算。我们以整体算术杂交为例:先在优化算法——遗传算法_优化算法_46生成优化算法——遗传算法_优化问题_62个随机数优化算法——遗传算法_遗传算法_63,经杂交算子后,所得到的两个后代为:

优化算法——遗传算法_优化算法_64

优化算法——遗传算法_遗传操作_65

变异(mutation)

变异操作的目的是使得基因突变,在优化算法中,可以防止算法陷入局部最优,从而跳出局部最优,帮助算法找到全局最优解。
二进制编码时的变异算子非常简单,只是依一定的概率(称为变异概率)将所选个体的位取反。即若是优化算法——遗传算法_优化问题_03,则取优化算法——遗传算法_优化问题_02;若是优化算法——遗传算法_优化问题_02,则取优化算法——遗传算法_优化问题_03
具体的操作为:设定一个变异概率优化算法——遗传算法_遗传算法_70,对杂交操作后的优化算法——遗传算法_GA_44个父体,对父体中的每一个位产生一个优化算法——遗传算法_优化算法_46区间上的随机数优化算法——遗传算法_优化问题_73,若优化算法——遗传算法_优化算法_74,则该位变异。
对于实数编码方式,可以采用均匀变异和非均匀变异方式,在均匀变异中,假设优化算法——遗传算法_遗传算法_75是要变异的个体,随机产生一个随机整数优化算法——遗传算法_优化算法_76,产生新的后代优化算法——遗传算法_遗传算法_77,其中优化算法——遗传算法_优化算法_78优化算法——遗传算法_遗传操作_79中服从均匀分布的一个随机数。
另一种是非均匀变异,,假设优化算法——遗传算法_遗传算法_75是要变异的个体,随机产生一个随机整数优化算法——遗传算法_优化算法_76,产生新的后代优化算法——遗传算法_遗传算法_77,其中:
优化算法——遗传算法_优化算法_83
这里优化算法——遗传算法_遗传算法_11是当前演化代数,函数优化算法——遗传算法_优化问题_85返回优化算法——遗传算法_优化算法_86中的一个值,并且优化算法——遗传算法_优化问题_85优化算法——遗传算法_遗传算法_11的增加而趋于优化算法——遗传算法_优化问题_02的概率增大。函数优化算法——遗传算法_优化问题_85具体形式为:
优化算法——遗传算法_GA_91
或者
优化算法——遗传算法_优化算法_92
其中,优化算法——遗传算法_优化算法_47优化算法——遗传算法_优化算法_46上的一个随机数,优化算法——遗传算法_优化问题_95表示最大演化代数。优化算法——遗传算法_优化算法_96是确定非均匀度的一个参数,通常取优化算法——遗传算法_优化算法_97

控制参数的设定

控制参数主要包括种群的规模优化算法——遗传算法_GA_44,演化代数优化算法——遗传算法_优化问题_95,杂交概率优化算法——遗传算法_遗传算法_55,变异概率优化算法——遗传算法_遗传算法_70等等。


在实现遗传算法时,一个常用的方法是将到当前代为止演化的最好个体单独存放起来,在遗传算法结束后,将演化过程中发现的最好个体作为问题的最优解或近似最优解。


求解优化问题的实例

问题描述

优化算法——遗传算法_优化算法_102
其中,优化算法——遗传算法_GA_103

问题分析

这是一道不带约束条件的函数优化的问题,既可以采用二进制编码方式,也可以采用十进制的编码方式,在本题的解决过程中,采用十进制的编码方式。首先通过Matlab得到的函数图像大致如下,从图像中可以观察到当优化算法——遗传算法_优化算法_104时,我们可以在优化算法——遗传算法_遗传操作_105附近取得函数的最小值。

优化算法——遗传算法_优化算法_106

算法设计

基于以上的分析,当优化算法——遗传算法_优化算法_104时,以下分别从个体的编码、适应值函数、选择策略、杂交算子、变异算子、参数设置、初始化以及终止条件这八个方面对程序的设计作简要的描述:

个体编码

采用实数向量编码,每一个个体是一实数对优化算法——遗传算法_GA_07

适应值函数

该优化问题是一个极小化问题,可对目标函数作简单变换,同时考虑到在选择策略时选择的是轮盘赌的选择策略,轮盘赌的选择策略有一个要求就是个体的适应值要为正数,因此,可以作如下的变换:优化算法——遗传算法_遗传操作_109,这里的优化算法——遗传算法_遗传算法_110是取的一个上界。这样,既保证了变换后的适应值函数式中为正,而且我们可以将极小化问题转换成一个极大值问题考虑。

选择策略

采用轮盘赌的选择策略,因为在计算适应值时已经作了处理,即适应值始终为正,这样就可以使用轮盘赌的选择策略。轮盘赌的选择策略是一种基于适应值比例的选择策略,适应值越大被选择到下一代的概率也会越大。

杂交算子

采用整体算术杂交,即给定两个父体,产生一个随机数,经杂交后得到两个后代个体,优化算法——遗传算法_GA_111优化算法——遗传算法_优化算法_112,产生一个随机数优化算法——遗传算法_遗传操作_113,经杂交后得到两个后代个体:优化算法——遗传算法_遗传算法_114优化算法——遗传算法_优化问题_115

变异算子

采用非均匀变异,即对于要变异的个体优化算法——遗传算法_遗传操作_116,随机产生整数优化算法——遗传算法_优化问题_117,例如优化算法——遗传算法_优化算法_118,然后产生后代优化算法——遗传算法_GA_119,其中
优化算法——遗传算法_遗传操作_120

参数设置

  • 种群规模优化算法——遗传算法_遗传操作_121
  • 个体长度优化算法——遗传算法_GA_122
  • 演化代数优化算法——遗传算法_优化算法_123
  • 杂交概率优化算法——遗传算法_GA_124
  • 变异概率优化算法——遗传算法_遗传操作_125
  • 函数上界优化算法——遗传算法_遗传操作_126

初始化

在区间内随机初始化种群的个体,并置个体的适应值,适应值之和以及相对适应值比例为优化算法——遗传算法_优化问题_02

终止条件

采用代数作为终止条件,当算法运行到指定的最大代数时,程序停止。

实验代码

#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<cmath>
#include<fstream>

using namespace std;


const int COLONY_SIZE=100;  //个体数目
const int Size=2;//个体的长度
const int Generation=3000;//代数
const double OVER=0.7;//杂交的概率
const double MUTATE=0.1;//变异的概率
const double UPPER=30.0;//函数的上界

struct Indival
{
	double code[Size];
	double fitness;
	double cfitness;
	double rfitness;
}Group[COLONY_SIZE];

Indival newGroup[COLONY_SIZE];

Indival bestChrom;//记录最好的个体

int GenNum=0;

double random(double, double);
void initiate();
void calvalue();
void select();
void crossOver();
void xOver(int,int);
void mutate();
double delta(int,double,double,double);
void sort();

/*****************主函数***************/
int main()
{
	ofstream output;
	srand((unsigned)time(NULL));
	initiate();
	calvalue();
	output.open("data.txt");
	while(GenNum<=Generation)
	{
		GenNum++;
		select();	
		crossOver();
		mutate();	
		calvalue();	
		sort();
		if (bestChrom.fitness<Group[0].fitness)
		{
			bestChrom.code[0]=Group[0].code[0];
			bestChrom.code[1]=Group[0].code[1];
			bestChrom.fitness=Group[0].fitness;
		}
// 		output<<"gen: "<<GenNum<<"最优解为:"<<endl;
// 		output<<"x1: "<<bestChrom.code[0]<<"  x2: "<<bestChrom.code[1]<<"   函数值为: "<<(30-bestChrom.fitness)<<endl;
		output<<GenNum<<"	"<<(30-bestChrom.fitness)<<endl;
	}
	output.close();
	cout<<"运行结束!"<<endl;//提示运行结束
 	return 0;
}


/******************************函数的实现*****************************************/


double random(double start, double end){//随机产生区间内的随机数	
	return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

void initiate()//初始化
{
	for(int i=0;i<COLONY_SIZE;i++)
	{
		Group[i].code[0]=random(-30,30);
		Group[i].code[1]=random(-30,30);
		Group[i].fitness=0;//适应值
		Group[i].cfitness=0;//相对适应值比例之和
		Group[i].rfitness=0;//相对适应值比例
	}
}

void calvalue()//计算适应值
{
	double x1,x2;
	double sum=0;
	double part1,part2;//将函数分成几个部分
	for(int i=0;i<COLONY_SIZE;i++)
	{
		x1=Group[i].code[0];
		x2=Group[i].code[1];
		part1=-0.2*sqrt((x1*x1+x2*x2)/Size);
		part2=(cos(2*3.1415926*x1)+cos(2*3.1415926*x2))/Size;
		Group[i].fitness=UPPER-(-20*exp(part1)-exp(part2)+20+2.71828);//适应值
		sum+=Group[i].fitness;//计算适应值之和
	}
	for(int mem=0;mem<COLONY_SIZE;mem++)//轮盘赌选择机制里所要求的几个参数
	{
		Group[mem].rfitness=Group[mem].fitness/sum;//适应值的比例
	}
	Group[0].cfitness=Group[0].rfitness;
	for(mem=1;mem<COLONY_SIZE;mem++)
	{
		Group[mem].cfitness=Group[mem-1].cfitness+Group[mem].rfitness;//模拟轮盘
	}


}
void select()
{
	double p;
	for(int i=0;i<COLONY_SIZE;i++)//挑选出N个个体
	{
		p=random(0,1);//随机产生0到1之间的随机数
		if(p<Group[0].cfitness)
			newGroup[i]=Group[0];
		else
		{
			for(int j=1;j<COLONY_SIZE;j++)//往轮盘后走
			{
				if(p>=Group[j-1].cfitness&&p<Group[j].cfitness)
				{
					newGroup[i]=Group[j];
					break;
				}
			}
		}
	}
	for(i=0;i<COLONY_SIZE;i++)//从newGroup复制到Group中
		Group[i]=newGroup[i];
}
void crossOver()
{
	int mem,one;
	int first=0;//记录杂交的数目
	double x;
	for(mem=0;mem<COLONY_SIZE;mem++)
	{
		x=random(0,1);
		if(x<OVER)
		{
			++first;
			if(first%2==0)//若为偶数
				xOver(one,mem);
			else 
				one=mem;
		}
	}
}
void xOver(int one,int two)
{
	double point;
	point=random(0,1);
	Group[one].code[0]=Group[one].code[0]*point+Group[two].code[0]*(1-point);
	Group[one].code[1]=Group[one].code[1]*point+Group[two].code[1]*(1-point);
	Group[two].code[0]=Group[one].code[0]*(1-point)+Group[two].code[0]*point;
	Group[two].code[1]=Group[one].code[1]*(1-point)+Group[two].code[1]*point;
}
void mutate()
{
	double x;
	for(int i=0;i<COLONY_SIZE;i++)
	{
		for(int j=0;j<Size;j++)
		{
			x=random(0,1);
			if (x<MUTATE)
			{
				Group[i].code[j]=delta(GenNum,Group[i].code[0],30,-30);
			}
		}
	}
}


double delta(int t,double x,double u,double l)
{
	double temp1;
	double temp2;
	double y;
	double r=random(0,1);
	temp1=pow((1-t/Generation),4);
	temp2=pow(r,temp1);
	int a=(int)random(0,2);
	if(a==0)
	{
		y=u-x;
		return (x+y*(1-temp2));
	}else
	{
		y=x-l;
		return (x-y*(1-temp2));
	}
}

void sort()//排序
{
	Indival temp;
	for(int i=0;i<COLONY_SIZE-1;i++)
	{
		for(int j=i+1;j<COLONY_SIZE;j++)
		{
			if(Group[i].fitness<Group[j].fitness)
			{
				temp=Group[i];
				Group[i]=Group[j];
				Group[j]=temp;
			}
		}
	}
}

最终结果

优化算法——遗传算法_优化算法_128

我在这里简单介绍了遗传算法,遗传算法是一个研究较多的算法,还有利用遗传算法求解组合优化问题,带约束的优化问题,还有一些遗传算法的理论知识,如模式定理,积木块假设,在这里就不一一列举了,希望我的博文对你的学习有帮助,也欢迎转载,谢谢,有不到位的地方还请指出。


标签:杂交,编码,二进制,个体,变异,算法,遗传算法,优化
From: https://blog.51cto.com/u_16161414/6481117

相关文章

  • 简单易学的机器学习算法——因子分解机(Factorization Machine)
    一、因子分解机FM的模型    因子分解机(FactorizationMachine,FM)是由SteffenRendle提出的一种基于矩阵分解的机器学习算法。1、因子分解机FM的优势    对于因子分解机FM来说,最大的特点是对于稀疏的数据具有很好的学习能力。现实中稀疏的数据很多,例......
  • 优化算法——模拟退火算法
    模拟退火算法原理爬山法是一种贪婪的方法,对于一个优化问题,其大致图像(图像地址)如下图所示:其目标是要找到函数的最大值,若初始化时,初始点的位置在处,则会寻找到附近的局部最大值点处,由于点出是一个局部最大值点,故对于爬山法来讲,该算法无法跳出局部最大值点。若初始点选择在处,根据爬......
  • 挑战数据结构和算法面试题——最大间隔
    分析:本题首先需要理解清楚最大间隔的最小:最初的间隔为:[1,1,4,1],此时最大间隔为4删除2后的间隔为:[2,4,1],此时最大间隔为4删除3后的间隔为:[1,5,1],此时最大间隔为5删除7后的间隔为:[1,1,5],此时最大间隔为5在删除元素后的间隔为:[4,5,5],最小值为:4方法:intget_min_max_margin(int*a,constintn){......
  • 挑战数据结构和算法——栈的push、pop序列
    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判断一个序列是否是栈的pop序列是一种常见的问题,可以通过模拟push和pop的过程,push和pop总是成对出现的,如:方法:#definepush1#def......
  • 【数据结构和算法面试题】跳台阶问题
    题目来源“数据结构与算法面试题80道”。问题分析:假设为跳台阶的总跳法,当时,;当时,;当时,如果先跳1级台阶,有种方法,如果先跳2级台阶,有种方法,依次类推,可以得到下面的递推公式:方法:intget_kind(intn){ if(n<=0)return0; intresult; int*cal=(int*)malloc(sizeof(int)*n);......
  • 挑战数据结构和算法——整数的二进制表示中1的个数
    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。问题分析:本题涉及到二进制的处理,在本题使用到&操作和>>操作。方法:intget_num(intn){intnum=0;if(n<0){num+=1;n=n*(-1);}while(n!=0){......
  • 推荐系统中的常用算法——Wide & Deep
    1.概述在前DeepLearning时代,以LogisticRegression(LR)为代表的广义线性模型在CTR,CVR中得到了广泛的应用,主要原因包括:模型足够简单,相当于不包括隐含层的神经网络;可扩展性强;可解释性强,因为是线性的模型,可以很方便的显现出特征对最终结果的强弱。虽然线性模型有如上的优点,但同时也存在......
  • 【数据结构与算法面试题】二叉树节点的最大距离
    题目来源“数据结构与算法面试题80道”。问题分析:涉及的知识点是二叉树的遍历,遍历的方法主要有:先序遍历中序遍历后序遍历层次遍历在本题中,使用先序遍历的方法。方法:voidm_length(BSTreeNode*root,int*length,int*max_length){if(NULL==root||(NULL==root......
  • 机器学习算法实现解析——libFM之libFM的训练过程之Adaptive Regularization
    本节主要介绍的是libFM源码分析的第五部分之二——libFM的训练过程之AdaptiveRegularization的方法。5.3、AdaptiveRegularization的训练方法5.3.1、SGD的优劣在“机器学习算法实现解析——libFM之libFM的训练过程之SGD的方法”中已经介绍了基于SGD的FM模型的训练方法,SGD的方法的......
  • 推荐算法——非负矩阵分解(NMF)
    1.矩阵分解回顾在博文推荐算法——基于矩阵分解的推荐算法中,提到了将用户-商品矩阵进行分解,从而实现对未打分项进行打分。矩阵分解是指将一个矩阵分解成两个或者多个矩阵的乘积。对于上述的用户-商品矩阵(评分矩阵),记为,可以将其分解成两个或者多个矩阵的乘积,假设分解成两个矩阵和,......