当前位置:   article > 正文

遗传算法解决多元函数优化问题(C++实现)_用遗传算法工具箱或编程实现遗传算法求解下面的 函数优化问题: f(x,y)=sin(3πx)c

用遗传算法工具箱或编程实现遗传算法求解下面的 函数优化问题: f(x,y)=sin(3πx)c

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

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);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236

8、代码效果

测试函数收敛迅速,因未找到合适的测试函数,未进行进一步测试。
第0代的适应度:92.1223
第20代的适应度:99.9199
第40代的适应度:99.995

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/798224
推荐阅读
相关标签
  

闽ICP备14008679号