遗传算法解决多元函数优化问题（C++实现）

admin1

0、代码使用
代码提供了计算多元函数范围内极值的接口，可以参数的数量、参数范围、编码分辨率、极大值极小值的选择等。解决大部分多元函数优化问题可以直接拿来使用。

GeneticAlgorithm(vector<vector<float>> Domain, int resolution, bool ifMax)
        Domain 二维数组 为参数的范围
        resolution 为编码分辨率，值越大，结果越精确
        ifMax true：求极大值  false：求极小值
1
2
3
4
1、遗传算法原理


2、编码方式
对于实数的编码，如采用IEEE浮点数编码太过复杂，且不利于范围的限制。
这里采用映射的方法，将一定位数的二进制码转换为无符号整数后，通过变换，映射到参数的具体范围内。
假设使用16位编码方式：

比例系数 K = （max - min)/65535
适应度值 fitness = K * 65535 + min

对于多元函数，在以上的前提下，只需要将多个二进制编码拼接成一维数组即可。

    void source2code(){    //将随机数转化为编码
        for (size_t i = 0; i < group.size(); i++)
        {
            group[i].code.clear();
            for(size_t k = 0; k < indenpendentNum; k++){
                for (size_t j = 0; j < resolution; j++)
                    group[i].code.push_back((group[i].sourceVec[k] >> j) & 1);
            }
        }
    }

    void code2val(){//将编码解码为自变量
        for (size_t i = 0; i < group.size(); i++)
        {
            group[i].indenpendentValVec.clear();
            for (size_t j = 0; j < indenpendentNum; j++)
            {
                double tmp = 0;
                for (size_t k = 0; k < resolution; k++)
                    tmp += group[i].code[k + j*resolution] * pow(2, resolution - k - 1);
                group[i].indenpendentValVec.push_back(tmp * translationVec[j] + Domain[j][0]);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
3、选择方式：
轮盘法

void calculatePropers() {  //计算累积概率
                group[0].culmulateProbability = group[0].fitness;
                for (size_t i = 1; i < param.populationSize; i++)
                        group[i].culmulateProbability = group[i - 1].culmulateProbability + group[i].fitness;
                for (size_t i = 0; i < param.populationSize; i++)
                        group[i].culmulateProbability /= group[param.populationSize - 1].culmulateProbability;
        }
void selectCrossGroup() {  //选择交叉种群
                for (size_t i = 0; i < param.crossoverRate*param.populationSize; i++) {
                        double r = (double)rand() / RAND_MAX;
                        if (r < group[0].culmulateProbability) {
                                crossGroup.emplace_back(group[0]);
                                continue;
                        }
                        for (size_t j = 1; j < param.populationSize; j++) {
                                if (r >= group[j - 1].culmulateProbability && r < group[j].culmulateProbability) {
                                        crossGroup.emplace_back(group[j]);
                                        break;
                                }
                        }
                }
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
4、交叉方式:
简单交换法，与生物交叉互换类似

void crossover() {  //交叉   核心代码
    int gsize = crossGroup.size();
    for (size_t i = 0; i < gsize; i += 2) {
        int size = indenpendentNum*resolution * param.crossPercent;
        int r = rand() % (indenpendentNum*resolution-size);
        for (size_t j = r; j < r+size; j++){
            int tmp = crossGroup[i].code[j];
            crossGroup[i].code[j] = crossGroup[i + 1].code[j];
            crossGroup[i + 1].code[j] = tmp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
5、变异方式：
随机对某一位编码取反

void mutation() {  //变异
    for (size_t i = 1; i < group.size(); i++) {
        if (rand() % 100 < param.mutationRate * 100) {
            int r = rand() % resolution*indenpendentNum;
            group[i].code[r] = !group[i].code[r];
        }
    }
}
1
2
3
4
5
6
7
8
6、选择群体方式
择优选取

void selectGroup() {  //选择种群
    int csize = crossGroup.size();
    for (size_t i = 0; i < csize; i++)
        {
            code2val(crossGroup[i]);
            calculateFitness(crossGroup[i]);
            group.emplace_back(crossGroup[i]);
        }
    sort(group.begin(), group.end(), compare);
    group.erase(group.begin() + param.populationSize, group.end());
    crossGroup.clear();
}

//比较函数 用于排序
static bool compare(individual a, individual b) {
    return a.fitness > b.fitness;
}


7、整体代码
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <cstdlib>
using namespace std;

class GeneticAlgorithm {
public:
        struct parameters {
                int populationSize = 200;  //种群大小
                int maxGeneration = 200;    //最大迭代次数
                double mutationRate = 0.05; //变异概率
                double crossoverRate = 0.4; //交叉概率
                int tournamentSize = 50;   //选择种群大小
                float crossPercent = 0.2;   //交叉百分比
        } param;

        struct individual {
                double fitness;                     //适应度
                double culmulateProbability;        //累积概率
        vector<unsigned int> sourceVec;     //源数据
                vector<char> code;                  //编码值
        vector<double> indenpendentValVec; //自变量数组
        };

        vector<individual> group;       //种群
        vector<individual> crossGroup;  //交叉种群

        int resolution;                                        //分辨率：编码的位数
    vector<double> translationVec;  //转化系数数组
    unsigned int sourceMax;         //原码最大值
    bool ifMax;
    int indenpendentNum;            //自变量个数
    vector<vector<float>> Domain;   //自变量范围

        GeneticAlgorithm(vector<vector<float>> Domain, int resolution, bool ifMax) {
                this->resolution = resolution;                        //初始化参数
                this->sourceMax = (pow(2, resolution) - 1);
        this->ifMax = ifMax;
        this->indenpendentNum = Domain.size();
        this->Domain = Domain;
        for (size_t i = 0; i < this->indenpendentNum; i++)
            this->translationVec.push_back((Domain[i][1] - Domain[i][0])/sourceMax);

                init();     //初始化种群 产生编码范围内随机数 生成二进制编码

                for (size_t i = 0; i < param.maxGeneration + 1; i++)
                {
                        updateGroupFitness();   //更新种群适应度
                        calculatePropers();     //计算累积概率   用于轮盘赌
                        selectCrossGroup();     //选择交叉种群    轮盘赌
                        crossover();            //交叉  
                        mutation();             //变异
                        selectGroup();          //选择下一代种群
                        if (i % 20 == 0)
            cout << "第" << i << "代的适应度：" << getResult() << endl;
                }
                // showGroup();
        // showGroup();
        }


        void init() {   //初始化种群 随机初始路径
                srand(time(NULL));
                individual tmp;
                for (size_t i = 0; i < param.populationSize; i++)
                {
            tmp.sourceVec.clear();
            for (size_t j = 0; j < indenpendentNum; j++){
                tmp.sourceVec.emplace_back(rand() % sourceMax);
            }
            group.emplace_back(tmp);
                }
        source2code();  //将随机数转化为编码
        code2val();     //将编码解码为自变量
        }

    void source2code(){    //将随机数转化为编码
        for (size_t i = 0; i < group.size(); i++)
        {
            group[i].code.clear();
            for(size_t k = 0; k < indenpendentNum; k++){
                for (size_t j = 0; j < resolution; j++)
                    group[i].code.push_back((group[i].sourceVec[k] >> j) & 1);
            }
        }
    }

    void code2val(){//将编码解码为自变量
        for (size_t i = 0; i < group.size(); i++)
        {
            group[i].indenpendentValVec.clear();
            for (size_t j = 0; j < indenpendentNum; j++)
            {
                double tmp = 0;
                for (size_t k = 0; k < resolution; k++)
                    tmp += group[i].code[k + j*resolution] * pow(2, resolution - k - 1);
                group[i].indenpendentValVec.push_back(tmp * translationVec[j] + Domain[j][0]);
            }
        }
    }

    void code2val(individual &ind){//将编码解码为自变量
        ind.indenpendentValVec.clear();
        for (size_t i = 0; i < indenpendentNum; i++){
                double tmp = 0;
                for (size_t k = 0; k < resolution; k++)
                    tmp += ind.code[k+ i*resolution] * pow(2, resolution - k - 1);
                ind.indenpendentValVec.push_back(tmp * translationVec[i] + Domain[i][0]);
        }
        
    }

        void showGroup() {   //打印种群  用于测试
                int size = group.size();
        for (size_t i = 0; i < 10; i++)
        {
            cout << "第" << i << "个个体的编码：";
            int size = resolution * indenpendentNum;
            for (size_t j = 0; j < size; j++)
                cout << (int)group[i].code[j];
            cout << endl;

            cout << "第" << i << "个个体的自变量：";
            for (size_t j = 0; j < indenpendentNum; j++)
                cout << group[i].indenpendentValVec[j] << " ";
            cout << endl;

            cout << "第" << i << "个个体的适应度：" << group[i].fitness << endl;
            cout << "第" << i << "个个体的累积概率：" << group[i].culmulateProbability << endl;

            cout<<"------------------------------------------------------"<<endl;
        }
        
               
        }

        void updateGroupFitness() {  //更新整个种群的适应度
                for (size_t i = 0; i < param.populationSize; i++)
                        calculateFitness(group[i]);
        }

        void calculateFitness(individual &ind) {    //计算适应度
                double x = ind.indenpendentValVec[0];
        double y = ind.indenpendentValVec[1];
        ind.fitness = 6.452*(x+0.125*y)*pow(cos(x) - cos(2*y),2)/
        pow(0.8+pow((x-4.2),2)+2*pow((y-7),2),0.5) + 3.226*y;
        if (!ifMax)
                        ind.fitness = 1 / ind.fitness;
        }

        void calculatePropers() {  //计算累积概率
                group[0].culmulateProbability = group[0].fitness;
                for (size_t i = 1; i < param.populationSize; i++)
                        group[i].culmulateProbability = group[i - 1].culmulateProbability + group[i].fitness;
                for (size_t i = 0; i < param.populationSize; i++)
                        group[i].culmulateProbability /= group[param.populationSize - 1].culmulateProbability;
        }

        void selectCrossGroup() {  //选择交叉种群
                for (size_t i = 0; i < param.crossoverRate*param.populationSize; i++) {
                        double r = (double)rand() / RAND_MAX;
                        if (r < group[0].culmulateProbability) {
                                crossGroup.emplace_back(group[0]);
                                continue;
                        }
                        for (size_t j = 1; j < param.populationSize; j++) {
                                if (r >= group[j - 1].culmulateProbability && r < group[j].culmulateProbability) {
                                        crossGroup.emplace_back(group[j]);
                                        break;
                                }
                        }
                }
        }

    void crossover() {  //交叉   核心代码
        int gsize = crossGroup.size();
        for (size_t i = 0; i < gsize; i += 2) {
            int size = indenpendentNum*resolution * param.crossPercent;
            int r = rand() % (indenpendentNum*resolution-size);
            for (size_t j = r; j < r+size; j++){
                int tmp = crossGroup[i].code[j];
                crossGroup[i].code[j] = crossGroup[i + 1].code[j];
                crossGroup[i + 1].code[j] = tmp;
            }
        }
    }

    void mutation() {  //变异
        for (size_t i = 1; i < group.size(); i++) {
            if (rand() % 100 < param.mutationRate * 100) {
                int r = rand() % resolution*indenpendentNum;
                group[i].code[r] = !group[i].code[r];
            }
        }
    }

    void selectGroup() {  //选择种群
        int csize = crossGroup.size();
        for (size_t i = 0; i < csize; i++)
            {
                code2val(crossGroup[i]);
                calculateFitness(crossGroup[i]);
                group.emplace_back(crossGroup[i]);
            }
        sort(group.begin(), group.end(), compare);
        group.erase(group.begin() + param.populationSize, group.end());
        crossGroup.clear();
    }

    //比较函数 用于排序
    static bool compare(individual a, individual b) {
        return a.fitness > b.fitness;
    }

        double getResult() {  //获取结果
        if(ifMax)
            return group[0].fitness;
        else
            return 1 / group[0].fitness;
        }

};


int main() {
    //参数范围
    vector<vector<float>> Domain = { {0,10},{0,10} };
    int resolution = 16;    //编码长度
    bool ifMax = true;      //是否是最大值
        GeneticAlgorithm ga(Domain, resolution, ifMax);
}



8、代码效果
测试函数收敛迅速，因未找到合适的测试函数，未进行进一步测试。
第0代的适应度：92.1223
第20代的适应度：99.9199
第40代的适应度：99.995