|
|
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <cstdlib>
using namespace std;
const double FITCHANGE = 500; //适应度常数
class GeneticAlgorithm {
public:
struct parameters {
int populationSize = 1000; //种群大小
int maxGeneration = 200; //最大迭代次数
double mutationRate = 0.05; //变异概率
double crossoverRate = 0.4; //交叉概率
int tournamentSize = 200; //选择种群大小
float crossPercent = 0.2; //交叉百分比
} param;
struct individual {
double fitness; //适应度
double culmulateProbability;//累积概率
vector<int> path; //路径
};
vector<individual> group; //种群
vector<individual> crossGroup; //交叉种群
int length; //路径长度
vector<vector<float>> points;
GeneticAlgorithm(vector<vector<float>> &points){
this->points = points;
this->length = points.size();
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();
}
void init(){ //初始化种群 随机初始路径
vector<int> tmp;
individual tmpIn{0,0,tmp};
for (size_t i = 1; i <= length; i++)//1-n的数组
tmp.push_back(i);
for(int i = 0; i < param.populationSize; i++){
random_shuffle(tmp.begin()+1,tmp.end());//随机排列
tmpIn.path = tmp;
group.emplace_back(tmpIn);
}
srand(time(NULL));
}
void showGroup(){ //打印种群 用于测试
int size = group.size();
for (size_t j = 0; j < size; j++){
cout << "fit:" << group[j].fitness << " prop:"<< group[j].culmulateProbability << " path:";
for (size_t i = 0; i < length; i++)
cout<<group[j].path[i]<<" ";
cout<<endl;
}
cout<<"-------------------------------------"<<endl;
for (size_t i = 0; i < crossGroup.size(); i++)
{
cout << "fit:" << crossGroup[i].fitness << " prop:"<< crossGroup[i].culmulateProbability << " path:";
for (size_t j = 0; j < length; j++)
cout<<crossGroup[i].path[j]<<" ";
cout<<endl;
}
cout<<"-------------------------------------"<<endl;
}
void updateGroupFitness(){ //更新整个种群的适应度
for (size_t i = 0; i < param.populationSize; i++)
calculateFitness(group[i]);
}
void calculateFitness(individual &ind){ //计算适应度
float res = 0;
for (size_t i = 0; i < length-1; i++)
res += getDistance(ind.path[i], ind.path[i+1]);
res += getDistance(ind.path[0],ind.path[length-1]);
ind.fitness = FITCHANGE/res;
}
float getDistance(int p1, int p2){ //计算欧式距离
float disX = points[p2-1][0] - points[p1-1][0];
float disY = points[p2-1][1] - points[p1-1][1];
return pow((disX*disX+disY*disY),0.5);
}
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(){ //交叉 核心代码
vector<bool> isCrossed(param.populationSize,false); //记录是否交叉过
int crossNum = length*param.crossPercent;//交叉个数
for (size_t i = 0; i < crossGroup.size()-2; i+=2){
int r = rand()%(length - crossNum - 1) + 1; //交叉起点
for (size_t j = r; j < r + crossNum; j++)
isCrossed[crossGroup[i].path[j]] = true; //记录交叉过的片段
int p = 0; //记录交叉点
for (size_t j = 0; j < length; j++){ //交叉替换到Gi
if(!isCrossed[crossGroup[i+1].path[j]]){
if(p < r)
crossGroup[i].path[p] = crossGroup[i+1].path[j];
else
crossGroup[i].path[p+crossNum] = crossGroup[i+1].path[j];
p++;
}
}
isCrossed.assign(length,false); //重置
// calculateFitness(crossGroup[i]);//计算适应度
group.emplace_back(crossGroup[i]);//添加到种群
}
}
void mutation(){ //变异
for (size_t i = 1; i < group.size(); i++){
if(rand()%100 < param.mutationRate*100){
int r1 = rand()%length;
int r2 = rand()%length;
int tmp = group[i].path[r1];
group[i].path[r1] = group[i].path[r2];
group[i].path[r2] = tmp;
calculateFitness(group[i]); //更新适应度
}
}
}
void selectGroup(){ //选择种群
sort(group.begin(),group.end(),compare);
group.erase(group.begin()+param.populationSize,group.end());
}
//比较函数 用于排序
static bool compare(individual a, individual b){
return a.fitness > b.fitness;
}
double getResult(){ //获取最优路径
return FITCHANGE/group[0].fitness;
}
};
float getDistance(vector<vector<float>> &points ,int p1, int p2){ //计算欧式距离
float disX = points[p2][0] - points[p1][0];
float disY = points[p2][1] - points[p1][1];
return pow((disX*disX+disY*disY),0.5);
}
float getBestResult(vector<vector<float>> &points){ //随机搜索最优路径 用于对比
srand(time(NULL));
vector<vector<float>> pointsCopy = points;
float res = 999999;
int length = points.size();
for (size_t i = 0; i < 10000000; i++)
{
float now = 0;
random_shuffle(pointsCopy.begin()+1,pointsCopy.end());
for (size_t j = 0; j < length-1; j++)
now += getDistance(pointsCopy,j , j+1);
now += getDistance(pointsCopy,0,length-1);
res = min(res, now);
}
return res;
}
int main() {
vector<vector<float>> city = {{114.46,39.92}, {117.2,39.13}, {121.48,31.22},
{106.54,29.59}, {91.11,29.97}, {87.68,43.77}, {106.27,38.47}, {111.65,40.82},
{108.33,22.84}, {126.63,45.75}, {125.35,43.88}, {123.38,41.8}, {114.48,38.03},
{112.53,37.87}, {101.74,36.56}, {117,36.65}, {113.6,34.76}, {118.78,32.04},
{117.27,31.86}, {120.19,30.26}, {119.3,26.08}, {115.89,28.68}, {113,28.21},
{114.31,30.52}, {113.23,23.16}, {121.5,25.05}, {110.35,20.02}, {103.73,36.03},
{108.95,34.27}, {104.06,30.67}, {106.71,26.57}, {102.73,25.04}, {114.1,22.2},
{113.33,22.13}};
GeneticAlgorithm ob(city);
// cout<<getBestResult(city)<<endl;
}
void selectGroup(){ //选择种群
sort(group.begin(),group.end(),compare);
group.erase(group.begin()+param.populationSize,group.end());
crossGroup.clear();
} |
|
发表于 2024-6-22 09:46:18
