遗传算法流程

遗传算法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.cppusing 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;}

测试结果：