|
|
#include<cmath>
|
|
|
#include<ctime>
|
|
|
#include<iostream>
|
|
|
#include<cstdlib>
|
|
|
using namespace std;
|
|
|
const int Length{ 50 };//染色体长度。使精度可以达到0.01
|
|
|
const int population_size{ 30 };//种群大小
|
|
|
const int double_size{ 2 * population_size };//方便选择函数的操作
|
|
|
const int numbers{ 3 };
|
|
|
const int trilength{ 3 * Length };//交叉函数
|
|
|
const double Error = 1e-6;
|
|
|
double coefficients[numbers][numbers];
|
|
|
double constants[numbers];
|
|
|
|
|
|
class individual;
|
|
|
class Population;
|
|
|
|
|
|
class chromosome
|
|
|
{
|
|
|
private:
|
|
|
double* Chromosome;
|
|
|
public:
|
|
|
|
|
|
friend void exchange(chromosome& c1, chromosome& c2, int j);//染色体交换
|
|
|
chromosome() {
|
|
|
Chromosome = new double[Length];
|
|
|
for (int i = 0; i < Length; ++i)
|
|
|
{
|
|
|
Chromosome[i] = rand() % 2;
|
|
|
}
|
|
|
}
|
|
|
~chromosome()
|
|
|
{
|
|
|
if (!Chromosome)
|
|
|
delete[] Chromosome;
|
|
|
}
|
|
|
double transform()
|
|
|
{
|
|
|
double x = 0;
|
|
|
for (int i = 0; i < Length - 2; ++i) {
|
|
|
x += Chromosome[Length - 1 - i] * pow(2.0, i);
|
|
|
}
|
|
|
if (Chromosome[0] == 1) x = -x; // 处理最高位的符号
|
|
|
return x * 0.000000001; // 转换到实际数值范围
|
|
|
}//转换成十进制
|
|
|
void print_chromosome()
|
|
|
{
|
|
|
for (int i{ 0 }; i < Length; ++i)
|
|
|
{
|
|
|
cout << Chromosome[i];
|
|
|
}
|
|
|
cout << '\n';
|
|
|
};
|
|
|
void print_value()
|
|
|
{
|
|
|
|
|
|
cout << transform() << '\n';
|
|
|
}
|
|
|
void copy_chromosome(const chromosome& c1)
|
|
|
{
|
|
|
delete[]Chromosome;
|
|
|
Chromosome = new double[Length];
|
|
|
for (int i{ 0 }; i < Length; ++i)
|
|
|
{
|
|
|
|
|
|
|
|
|
Chromosome[i] = c1.Chromosome[i];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
friend class individual;
|
|
|
friend class Population;
|
|
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
void exchange(chromosome& c1, chromosome& c2, int j)
|
|
|
{
|
|
|
double useless{ 0 };
|
|
|
useless = c1.Chromosome[j];
|
|
|
c1.Chromosome[j] = c2.Chromosome[j];
|
|
|
c2.Chromosome[j] = useless;
|
|
|
//cout << "第" << j + 1 << "条染色体" << endl;
|
|
|
}
|
|
|
|
|
|
|
|
|
class individual
|
|
|
{
|
|
|
private:
|
|
|
chromosome individual_chromosomes[numbers];//染色体
|
|
|
double fitness;//适应度
|
|
|
double error;//代入方程的误差
|
|
|
public:
|
|
|
|
|
|
individual();//初始化
|
|
|
~individual()
|
|
|
{
|
|
|
if (!individual_chromosomes)
|
|
|
delete[]individual_chromosomes;
|
|
|
}
|
|
|
void calculate_error()//求误差
|
|
|
{
|
|
|
double error1{ Error };
|
|
|
for (int i = 0; i < numbers; ++i)
|
|
|
{
|
|
|
double a = coefficients[i][0] * individual_chromosomes[0].transform() + coefficients[i][1] * individual_chromosomes[1].transform() + coefficients[i][2] * individual_chromosomes[2].transform();
|
|
|
error1 += pow(constants[i] - a, 2);
|
|
|
}
|
|
|
error = error1;
|
|
|
}
|
|
|
//求适应度
|
|
|
double calculate_fitness()
|
|
|
{
|
|
|
calculate_error();
|
|
|
double log = std::log(error);
|
|
|
if (log < 0)
|
|
|
{
|
|
|
fitness = 100 - pow(10, log) * 10;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
fitness = 90 - 10 * log;
|
|
|
}
|
|
|
return fitness;
|
|
|
}
|
|
|
void print_chromosomes()
|
|
|
{
|
|
|
for (int i{ 0 }; i < numbers; ++i)
|
|
|
{
|
|
|
cout << "第" << i + 1 << "条染色体为：";
|
|
|
individual_chromosomes[i].print_chromosome();
|
|
|
}
|
|
|
}
|
|
|
void print_values()
|
|
|
{
|
|
|
for (int i{ 0 }; i < numbers; ++i)
|
|
|
{
|
|
|
cout << "第" << i + 1 << "个未知数为：";
|
|
|
individual_chromosomes[i].print_value();
|
|
|
}
|
|
|
}
|
|
|
void copy_individual(const individual& i1)
|
|
|
{
|
|
|
for (int i{ 0 }; i < numbers; ++i)
|
|
|
{
|
|
|
individual_chromosomes[i].copy_chromosome(i1.individual_chromosomes[i]);
|
|
|
}
|
|
|
fitness = i1.fitness;
|
|
|
error = i1.error;
|
|
|
}
|
|
|
double get_fitness()
|
|
|
{
|
|
|
return fitness;
|
|
|
}
|
|
|
friend class Population;
|
|
|
friend void exchange(individual& i1, individual& i2);
|
|
|
};
|
|
|
|
|
|
|
|
|
individual::individual()
|
|
|
{
|
|
|
for (int i{ 0 }; i < numbers; ++i)
|
|
|
{
|
|
|
individual_chromosomes[i] = chromosome();
|
|
|
}
|
|
|
calculate_error();
|
|
|
fitness = calculate_fitness();
|
|
|
}
|
|
|
|
|
|
void exchange(individual& i1, individual& i2)
|
|
|
{
|
|
|
int max_digit = static_cast<int>(floor(sqrt(trilength)));//最多改变sqrt位
|
|
|
int digit{ max_digit };
|
|
|
while (digit > 0)
|
|
|
{
|
|
|
int i = rand() % trilength;
|
|
|
int j = i % Length;
|
|
|
i = i / Length;
|
|
|
exchange(i1.individual_chromosomes[i], i2.individual_chromosomes[i], j);
|
|
|
digit -= 1;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
class Population
|
|
|
{
|
|
|
double variation_rate;
|
|
|
double variation_degree;//变异率和最大变异幅度
|
|
|
public:
|
|
|
int selection();//选择函数
|
|
|
void produce();//繁殖函数
|
|
|
int generation;//迭代次数
|
|
|
void mutate();//变异
|
|
|
individual population[double_size + 1];//种群，2倍+1为了交叉和后续交换顺序
|
|
|
Population(int _generation = 100) : variation_rate(0.02), variation_degree(0.14), generation(_generation)
|
|
|
{
|
|
|
|
|
|
for (int i = 0; i < population_size; ++i)
|
|
|
{
|
|
|
|
|
|
population[i] = individual();
|
|
|
}
|
|
|
} // 构造函数初始化变异率和变异幅度,设置迭代次数,初始化种群
|
|
|
|
|
|
//种群初始化
|
|
|
|
|
|
void print_population()
|
|
|
{
|
|
|
for (int i{ 0 }; i < population_size; ++i)
|
|
|
{
|
|
|
cout << "第" << i + 1 << "个个体：" << endl;
|
|
|
population[i].print_chromosomes();
|
|
|
}
|
|
|
}
|
|
|
double get_max_fitness()
|
|
|
{
|
|
|
double max_fitness = population[0].fitness;
|
|
|
for (int i = 0; i < double_size + 1; ++i)
|
|
|
{
|
|
|
if (population[i].fitness > max_fitness)
|
|
|
{
|
|
|
max_fitness = population[i].fitness;
|
|
|
}
|
|
|
}
|
|
|
return max_fitness;
|
|
|
}
|
|
|
|
|
|
};
|
|
|
|
|
|
void exchange(Population& a, Population& b)
|
|
|
{
|
|
|
int times = rand() % population_size;
|
|
|
while (times > 0)
|
|
|
{
|
|
|
int i = rand() % population_size;
|
|
|
int j = (i + rand()) % population_size;
|
|
|
if (i == j)times -= 1;
|
|
|
else
|
|
|
{
|
|
|
exchange(a.population[j], b.population[j]);
|
|
|
//cout << "交换了第" << j + 1 << "个个体的" << endl;
|
|
|
a.population[j].calculate_fitness();
|
|
|
b.population[j].calculate_fitness();
|
|
|
times -= 1;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
void Population::mutate()
|
|
|
{
|
|
|
for (int i = 0; i < population_size; ++i)
|
|
|
{
|
|
|
for (int j = 0; j < numbers; ++j)
|
|
|
{
|
|
|
double random = rand() * 1.0 / RAND_MAX;//产生一个0到1之间的随机数
|
|
|
if (random < variation_rate)
|
|
|
{
|
|
|
int position = rand() % 20;
|
|
|
if (population[i].individual_chromosomes[j].Chromosome[position] == 1)
|
|
|
population[i].individual_chromosomes[j].Chromosome[position] = 0;
|
|
|
else
|
|
|
population[i].individual_chromosomes[j].Chromosome[position] = 1;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
int Population::selection()
|
|
|
{
|
|
|
double total_fitness = 0;
|
|
|
for (int i = 0; i < population_size; ++i) {
|
|
|
total_fitness += population[i].calculate_fitness();
|
|
|
}
|
|
|
|
|
|
double random = (double)rand() / RAND_MAX * total_fitness;
|
|
|
double current_sum = 0;
|
|
|
for (int i = 0; i < population_size; ++i) {
|
|
|
current_sum += population[i].calculate_fitness();
|
|
|
if (current_sum >= random)
|
|
|
{
|
|
|
return i;
|
|
|
}
|
|
|
}
|
|
|
return -1;
|
|
|
}//选择适应度最高的，给予下标
|
|
|
void Population::produce()
|
|
|
{
|
|
|
for (int i{ population_size }; i < double_size; ++i)
|
|
|
{
|
|
|
population[i].copy_individual(population[i - population_size]);
|
|
|
}
|
|
|
for (int i{ 0 }; i < population_size - 1; ++i)
|
|
|
{
|
|
|
exchange(population[i], population[i + 1]);
|
|
|
}
|
|
|
for (int i{ 0 }; i < population_size - 1; ++i)
|
|
|
{
|
|
|
if (population[i].calculate_fitness() < population[i + population_size].calculate_fitness())
|
|
|
{
|
|
|
population[double_size].copy_individual(population[i]);
|
|
|
population[i].copy_individual(population[i + population_size]);
|
|
|
population[i + population_size].copy_individual(population[double_size]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
srand(static_cast<unsigned int>(time(0)));
|
|
|
/*int a;
|
|
|
cout << "请输入迭代次数";
|
|
|
cin >> a;
|
|
|
generation = a;*/
|
|
|
for (int i = 0; i < numbers; ++i)
|
|
|
{
|
|
|
cout << "请输入第 " << i + 1 << " 个方程的系数 (用空格分隔): ";
|
|
|
for (int j = 0; j < numbers; ++j)
|
|
|
{
|
|
|
cin >> coefficients[i][j];
|
|
|
}
|
|
|
cout << "请输入第 " << i + 1 << " 个方程的常数项: ";
|
|
|
cin >> constants[i];
|
|
|
}
|
|
|
int _generation;
|
|
|
cout << "请输入迭代次数：";
|
|
|
cin >> _generation;
|
|
|
Population a(_generation);
|
|
|
a.print_population();
|
|
|
int one1 = a.selection();
|
|
|
cout << "初始值：" << endl;
|
|
|
a.population[one1].print_values();
|
|
|
int times = 0;
|
|
|
Population b;
|
|
|
while (a.get_max_fitness() < 100)
|
|
|
{
|
|
|
a.mutate();
|
|
|
a.produce();
|
|
|
if (times % 1000 == 0&×!=0)
|
|
|
{
|
|
|
cout << "这是第" << times << "迭代,最合适的解为：";
|
|
|
int one = a.selection();
|
|
|
a.population[one].print_values();
|
|
|
}
|
|
|
++times;
|
|
|
|
|
|
if (times > a.generation)
|
|
|
{
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
int one = a.selection();
|
|
|
cout << "迭代最终解为：" << endl;
|
|
|
a.print_population();
|
|
|
a.population[one].print_values();
|
|
|
}
|
