遗传算法-求函数最优解
例题1：求目标函数Max{1-x2},-1<=x<=1，要求二进制编码，精确度为10-3。
遗传算法的实现，流程如下：
1.初始化种群：随机生成一定数量的染色体，每个染色体由一定数量的基因组成，每个基因的值为0或1。
2.评估种群：对于每个染色体，计算其适应度，即目标函数的值。
3.选择：根据染色体的适应度，选择一定数量的染色体作为下一代的父代。
4.交叉：对于每一对父代，以一定的概率进行交叉操作，生成一个新的子代。
5.变异：对于每个子代，以一定的概率进行变异操作，改变其中的一个或多个基因的值。
6.生成下一代种群：将父代和子代合并，得到下一代种群。
重复2-6步，直到达到停止条件（例如达到最大迭代次数或找到满足要求的解）。
解：在本题中，目标函数为f(x) = Max{1-x2},-1<=x<=1，其中x为染色体所代表的实数值。每个基因的值为0或1，表示实数值在二进制下的某一位。染色体的适应度为目标函数的值即f(x)。在每一代中，选择操作使用了轮盘赌选择，交叉操作使用了单点交叉，变异操作使用了单点变异。
参数配置
- POPULATION_SIZE：种群大小，即每一代中包含的个体数量，这里设置为100。
- CHROMOSOME_LENGTH：染色体长度，即每个个体的基因数量，这里设置为10。
- MUTATION_RATE：变异率，即每个基因发生变异的概率，这里设置为0.1。
- CROSSOVER_RATE：交叉率，即两个个体进行交叉的概率，这里设置为0.9。
- MAX_GENERATIONS：最大迭代次数，即算法运行的最大代数，这里设置为1000。
- PRECISION：精度，即当个体的适应度达到1.0时，算法停止运行，这里设置为0.001。
初始化种群
void initialize_population(vector<Chromosome>& population) {
for (int i = 0; i < POPULATION_SIZE; i++) {
Chromosome chromosome;
for (int j = 0; j < CHROMOSOME_LENGTH; j++) {
chromosome.genes.push_back(dis2(gen) < 0.5 ? 0 : 1);
}
population.push_back(chromosome);
}
}
评估种群
double decode(vector<int> genes) {
double x = 0.0;
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
x += genes[i] * pow(2, CHROMOSOME_LENGTH - i - 1);
}
return -1.0 + 2.0 * x / (pow(2, CHROMOSOME_LENGTH) - 1);
}
double fitness(vector<int> genes) {
double x = decode(genes);
return 1.0 - x * x;
}
void evaluate(vector<Chromosome>& population) {
for (int i = 0; i < POPULATION_SIZE; i++) {
population[i].fitness = fitness(population[i].genes);
}
}
选择
void sort_population(vector<Chromosome>& population) {
sort(population.begin(), population.end(), compare);
}
bool compare(Chromosome a, Chromosome b) {
return a.fitness > b.fitness;
}
交叉
vector<int> crossover(vector<int> parent1, vector<int> parent2) {
vector<int> child;
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
child.push_back(dis2(gen) < CROSSOVER_RATE ? parent1[i] : parent2[i]);
}
return child;
}
变异
void mutate(vector<int>& genes) {
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
if (dis2(gen) < MUTATION_RATE) {
genes[i] = 1 - genes[i];
}
}
}
生成下一代种群
void next_generation(vector<Chromosome>& population) {
vector<Chromosome> new_population;
for (int i = 0; i < POPULATION_SIZE; i++) {
vector<int> parent1_genes = population[i].genes;
vector<int> parent2_genes = population[dis(gen)].genes;
vector<int> child_genes = crossover(parent1_genes, parent2_genes);
mutate(child_genes);
Chromosome child;
child.genes = child_genes;
new_population.push_back(child);
}
evaluate(new_population);
sort_population(new_population);
population = new_population;
}
停止条件
for (int i = 0; i < MAX_GENERATIONS; i++) {
if (population[0].fitness >= 1.0 - PRECISION) {
break;
}
next_generation(population);
}
程序结果
最优解：x = 0.000977517,f(x) = 0.999999
完整代码
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;
const int POPULATION_SIZE = 100;
const int CHROMOSOME_LENGTH = 10;
const double MUTATION_RATE = 0.1;
const double CROSSOVER_RATE = 0.9;
const int MAX_GENERATIONS = 1000;
const double PRECISION = 0.001;
random_device rd;
mt19937 gen(rd());
uniform_real_distribution<> dis(-1.0, 1.0);
uniform_real_distribution<> dis2(0.0, 1.0);
struct Chromosome {
vector<int> genes;
double fitness;
};
double decode(vector<int> genes) {
double x = 0.0;
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
x += genes[i] * pow(2, CHROMOSOME_LENGTH - i - 1);
}
return -1.0 + 2.0 * x / (pow(2, CHROMOSOME_LENGTH) - 1);
}
double fitness(vector<int> genes) {
double x = decode(genes);
return 1.0 - x * x;
}
void evaluate(vector<Chromosome>& population) {
for (int i = 0; i < POPULATION_SIZE; i++) {
population[i].fitness = fitness(population[i].genes);
}
}
bool compare(Chromosome a, Chromosome b) {
return a.fitness > b.fitness;
}
void sort_population(vector<Chromosome>& population) {
sort(population.begin(), population.end(), compare);
}
void initialize_population(vector<Chromosome>& population) {
for (int i = 0; i < POPULATION_SIZE; i++) {
Chromosome chromosome;
for (int j = 0; j < CHROMOSOME_LENGTH; j++) {
chromosome.genes.push_back(dis2(gen) < 0.5 ? 0 : 1);
}
population.push_back(chromosome);
}
}
vector<int> crossover(vector<int> parent1, vector<int> parent2) {
vector<int> child;
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
child.push_back(dis2(gen) < CROSSOVER_RATE ? parent1[i] : parent2[i]);
}
return child;
}
void mutate(vector<int>& genes) {
for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
if (dis2(gen) < MUTATION_RATE) {
genes[i] = 1 - genes[i];
}
}
}
void next_generation(vector<Chromosome>& population) {
vector<Chromosome> new_population;
for (int i = 0; i < POPULATION_SIZE; i++) {
vector<int> parent1_genes = population[i].genes;
vector<int> parent2_genes = population[dis(gen)].genes;
vector<int> child_genes = crossover(parent1_genes, parent2_genes);
mutate(child_genes);
Chromosome child;
child.genes = child_genes;
new_population.push_back(child);
}
evaluate(new_population);
sort_population(new_population);
population = new_population;
}
int main() {
vector<Chromosome> population;
initialize_population(population);
evaluate(population);
sort_population(population);
for (int i = 0; i < MAX_GENERATIONS; i++) {
if (population[0].fitness >= 1.0 - PRECISION) {
break;
}
next_generation(population);
}
cout << "最优解: x = " << decode(population[0].genes) << ", f(x) = " << population[0].fitness << endl;
return 0;
}