遗传算法流程
遗传算法C++实现
这里以类的形式进行实现。具体原理推导以及过程参见遗传算法原理以及Python代码实现。
#pragma once
#include <iostream>
#include <ctime>
#include<vector>
#include<algorithm>
const int num_vari = 4;
const int len = 20;
const int size = 50;
typedef struct node
{ //染色体结构体
bool chromo[num_vari][len];
}node;
template <class T>
class MyGA {
public:
MyGA(int n_generation, int Size, int num_vari, int len, double pcross,double pmutate,double lower[],double upper[],double (*f)(T []) )
{
_n_generation = n_generation;
_Size = Size;
_num_vari = num_vari;
_len = len;
_pcross = pcross;
_pmutate = pmutate;
_lower = lower;
_upper = upper;
_f = f;
bestchromo = NULL;
group = new node[3*Size];
temp = new node[3*Size];
}
template<int n>
void GA(T (&x)[n], double& number);
private:
int _n_generation;//进化代数
int _Size;//种群规模
int _num_vari;//每条染色体包含变量的个数
int _len;//每个变量的长度,越长,GA搜索得到的值精度越高
double _pcross;//交叉概率
double _pmutate;//变异概率
double* _lower;//解区间下界
double* _upper;//解区间上界
double (*_f)(T []);
double _bestval;//适应值最大值
node* bestchromo;//记录最优个体
node* group;//记录种群中的个体的数组
node* temp;//记录种群中的个体的临时数组
void create();
template<int n>
void decode(node& c, T (&x)[n]);
double fitness(node& c);
void cross(node& c1, node& c2, int point);
void mutate(node& c);
void select();
template<int n>
int getBest(T (&x)[n], double& number);
double inline rand0()
{ //产生0到1的随机小数
return rand() % 10000 / 10000.0;
}
};
//MyGA.cpp
using namespace std;
template <class T>
void MyGA<T>::create()
{ //对单个染色体上的各个变量随机赋值
srand((unsigned)time(NULL));//产生随机数种子
for(int k =0; k < _Size; k++)
{
for(int i =0; i < _num_vari; i++)
{
for (int j = 0; j < _len; j++)
{
group[k].chromo[i][j] = rand() % 2;
}
}
}
}
template <class T>
template<int n>
void MyGA<T>::decode(node& c, T (&x1)[n])
{ //二进制解码操作
int num = pow((double)2, _len);//即2的10次方
for(int i = 0; i < _num_vari; i++ )
{
double tem = 0;
int m = 1;
for (int j = 0; j < _len; j++)
{
tem += c.chromo[i][j] * m;
m *= 2;
}
//解码后的数据(一条染色体)放在x中
x1[i] = (_upper[i]-_lower[i])*(tem / num)+_lower[i];
}
}
template <class T>
double MyGA<T>::fitness(node& c)
{ //适应度函数
T x1[num_vari];
decode(c, x1);
return _f(x1);
}
template <class T>
void MyGA<T>::cross(node& c1, node& c2, int point)
{
for(int i =0; i < _num_vari; i++)
{
for (int j = 0; j < _len; j++)
{
group[_Size].chromo[i][j] = c1.chromo[i][j];
group[_Size + 1].chromo[i][j] = c2.chromo[i][j];
}
}
_Size += 2;
//交叉操作
node c3 = c1;
for(int k=0; k < _num_vari; k++)
{
for (int i = 0; i < len - point; i++)
{
c1.chromo[k][point + i] = c2.chromo[k][point + i];
}
for (int j = 0; j < len - point; j++)
{
c2.chromo[k][point + j] = c3.chromo[k][point + j];
}
}
}
template <class T>
void MyGA<T>::mutate(node& c)
{ //变异操作
for(int j = 0; j < _num_vari; j++)
{
int i = rand() % len;
c.chromo[j][i] = !c.chromo[j][i];
}
}
template <class T>
void MyGA<T>::select()
{ //选择操作
//double* fitnessval = new double[_Size];
int n = _Size;
double* fitnessval= new double[_Size];
double sum = 0;
double* avgfitness= new double[_Size];
int* id = new int[_Size];
for (int i = 0; i < _Size; i++)
{
fitnessval[i] = fitness( group[i] );
}
//这里可以适当地排个序
vector<int> idx( _Size);
for (int i = 0; i != idx.size(); ++i) idx[i] = i;
// 根据fitnessval的值对索引排序
sort(idx.begin(), idx.end(), [&](const int& a, const int& b) {return (fitnessval[a] < fitnessval[b]);});//没有问题
int j = 0;
int k = 0;
if(_Size != size)
{
node* group0 = new node[_Size];
double* fitnessval0 = new double[_Size];
for (int i = _Size - size; i < _Size; i++)
{
group0[j] = group[idx[i]];
fitnessval0[k] = fitnessval[idx[i]];
sum += fitnessval0[k];//适应度总和
j++;
k++;
}
_Size = size;
for (int i = 0; i < _Size; i++)
{
fitnessval[i] = fitnessval0[i];
group[i] = group0[i];
}
}
else
{
node* group1 = new node[_Size];
double* fitnessval1 = new double[_Size];
for (int i = 0; i < _Size; i++)
{
group1[i] = group[idx[i]];
fitnessval1[i] = fitnessval[idx[i]];
sum += fitnessval[i];//适应度总和
}
for (int i = 0; i < _Size; i++)
{
fitnessval[i] = fitnessval1[i];
group[i] = group1[i];
}
}
for (int i = 0; i < _Size; i++)
{
avgfitness[i] = fitnessval[i] / sum;
}
for (int i = 1; i < _Size; i++)
{ //适应度累加
avgfitness[i] += avgfitness[i - 1];
}
//生成的新个体数目等同于_Size
for (int i = 0; i < _Size; i++)
{ //轮盘赌选择法
double rannum = rand0();//产生0到1随机数
int j;
for (j = 0; j < _Size - 1; j++)
{
if (rannum < avgfitness[j])
{
id[i] = j;
break;
}
}
if (j == _Size - 1)
{
id[i] = j;
}
}
for (int i = 0; i < _Size; i++)
{ //将新个体替换旧个体
temp[i] = group[i];
}
for (int i = 0; i < _Size; i++)
{
group[i] = temp[id[i]];
}
}
template <class T>
template<int n>
int MyGA<T>::getBest(T (&x)[n], double& number)
{ //取得最优个体对应的位置
double* fitnessval=new double[_Size];
double a;
for (int i = 0; i < _Size; i++)
{
fitnessval[i] = fitness(group[i]);
}
int max_id = 0;
for (int i = 1; i < _Size; i++)
{
if (fitnessval[i] > fitnessval[max_id])
{
max_id = i;
}
}
//当前最值对应的x,以及最值number
decode(group[max_id], x);
number = _f(x);
return max_id;
}
template <class T>
template<int n>
void MyGA<T>::GA(T (&x)[n], double& number)
{
create();
bestchromo = &group[getBest(x, _bestval)];
for (int i = 0; i < _n_generation; i++)
{
select();//选择操作
for(int j = 0; j < size; j++)
{
int p = rand() % len;
int pre = len;
int q = rand() % len;
while(pre == p)
{
pre = rand() % len;
}
//根据概率交叉
if (rand0() < _pcross)
{
cross(group[pre], group[p], q);
}
}
for (int k = 0, pre = -1; k < _Size; k++)
{ //根据概率进行变异
double d = rand0();
if ((rand0() < _pmutate))
{
mutate(group[k]);
}
}
getBest(x, number);
cout << "第" << i+1 << "代" << "最优x值为:" << x[0]<<' '<< x[1]<<' '<< x[2]<<' '<< x[3]<<' '<< "函数值为" << _f(x) << endl;//结果的输出
}
}
?遗传算法测试
#include <iostream>
#include <ctime>
#include "MyGA.h"
double f(double x[])
{ //目标函数,函数最小值点 -> [1, -1, 0, 0],函数最大值点 -> [-1, 1, 1(-1), 1(-1)]
double cost;
cost = (x[0] - 1) * (x[0] - 1) + (x[1] + 1) * (x[1] + 1) + x[2] * x[2] + x[3] * x[3];
return cost;
}
double f2(double x[])
{
//目标函数,函数最小值点 -> [0, 0, 0, 0]
double cost;
cost = 100 * (x[1] - x[0] * x[0]) * (x[1] - x[0] * x[0]) + (x[0] - 1) * (x[0] - 1) +
100 * (x[2] - x[1] * x[1]) * (x[2] - x[1] * x[1]) + (x[1] - 1) * (x[1] - 1) +
100 * (x[3] - x[2] * x[2]) * (x[3] - x[2] * x[2]) + (x[2] - 1) * (x[2] - 1);
return -cost;
}
int main() {
srand((unsigned)time(NULL));
int n_generation = 200;
int Size = 50;
//Size,num_vari,len同步在MyGA.h文件中设定
int num_vari = 4;
int len = 20;
double pcross = 1;
double pmutate = 0.01;
double lower[4] = {-1, -1, -1, -1};
double upper[4] = {1, 1, 1, 1};
double x[4];
double max;
//求最大值
MyGA<double> A(n_generation, Size, num_vari, len, pcross, pmutate, lower, upper, f);
A.GA(x, max);
system("pause");
return 0;
}测试结果：
?
基本100步就可以收敛到最值附近。
