遗传算法c++实现

算法c++实现"/>

遗传算法c++实现

遗传算法流程

遗传算法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];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];}delete group0;delete fitnessval0;}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];}delete group1;delete fitnessval1;}for (int i = 0; i < _Size; i++) {avgfitness[i] = fitnessval[i] / sum;}for (int i = 1; i < _Size; i++) {	//适应度累加avgfitness[i] += avgfitness[i - 1];}//生成的新个体数目等同于_Sizefor (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]];}delete fitnessval;delete avgfitness;delete id;
}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,以及最值numberdecode(group[max_id], x);number = _f(x);delete fitnessval;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步就可以收敛到最值附近。