TSP问题的遗传算法实现

admin1

※全局常量：
const int city_num = 10;//城市的数量，即基因的个数
const int Population_num = 100;//群体规模
double pc = 0.8;//交叉概率
double pm = 0.3;//变异概率
double dis[city_num][city_num];//城市间的距离矩阵
※自定义类型：
struct City { //城市
int label;//城市编号
int x;//该城市在坐标轴x上的位置
int y;//该城市在坐标轴y上的位置
};
※函数：
//计算两个城市之间的距离
double distance_two_city(const City& city1, const City& city2)
//返回当前路径的总长度
double distance_all_city(vector& vec)
//初始化
void init（）
//显示当前的最短路径
void show_path(vector& city)
//选择(采用联赛选择及精英保存策略)
void BettingWheelSelection()
//单点交叉并消除冲突
void Mating()
//变异
void Variation()






#include<iostream>
#include<vector>
#include<fstream>
#include<random>
#include<map>
#include<time.h>
using namespace std;

const int city_num = 10;//城市的数量，即基因的个数
const int Population_num = 100;//群体规模
double pc = 0.8;//交叉概率
double pm = 0.3;//变异概率
double dis[city_num][city_num];//城市间的距离矩阵
//城市的编号及位置
struct City {
        int label;//城市编号
        int x;//该城市在坐标轴x上的位置
        int y;//该城市在坐标轴y上的位置
};
vector<vector<City>> Pop;//种群，即所有个体的集合
//计算两个城市之间的距离
double distance_two_city(const City& city1, const City& city2)
{
        return sqrt(pow((city1.x - city2.x), 2) + pow((city1.y - city2.y), 2));//用欧式距离进行计算
}
//返回当前路径的总长度
double distance_all_city(vector<City>& vec)
{
        double sum = 0;
        int size = vec.size();//城市的数量
        for (int i = 1; i < size; ++i)
                sum += dis[vec[i].label][vec[i - 1].label];
        sum += dis[vec[size - 1].label][vec[0].label];
        return sum;
}
//初始化
void init()
{
        ifstream fin;//读文件对象
        fin.open("city.txt");//打开文件
        vector<City> city;//存放城市的数据
        for (int i = 0; i < city_num; ++i)//从文件中读入各城市的编号及位置坐标
        {
                City temp;
                fin >> temp.label;
                fin >> temp.x;
                fin >> temp.y;
                city.push_back(temp);
        }
        fin.close();
        for (int i = 0; i < city_num; ++i)//计算城市之间的距离
                for (int j = 0; j < city_num; ++j)
                        dis[i][j] = dis[j][i] = distance_two_city(city[i], city[j]);
        srand((unsigned)time(NULL));
        for (int i = 0; i < Population_num; ++i)//随机产生100个个体
        {
                vector<City> temp = city;
                for (int j = 0; j < 10; ++j)
                        swap(temp[j], temp[rand() % city_num]);
                Pop.push_back(temp);//将该个体加入到种群中
        }
}
//显示当前的最短路径
void show_path(vector<City>& city)
{
        cout << "path:";
        for (int i = 0; i < city_num; ++i)
                cout << city[i].label << ' ';
        cout << city[0].label << endl;
        cout << endl;
}
//选择(采用联赛选择及精英保存策略)
void BettingWheelSelection()
{
        vector<vector<City>> temp;
        map<double, int> bigmap;//用于排序，找出最短距离的路径（默认升序排序）
        for (int i = 0; i < Population_num; ++i)
                bigmap[distance_all_city(Pop[i])] = i;
        int better_fit, worse_fit;
        better_fit = (*bigmap.begin()).second;//当前适应度最好的个体
        worse_fit = (*(--bigmap.end())).second;//当前适应度最差的个体
        double sum;//当前最优路径的距离
        sum = (*bigmap.begin()).first;
        cout << "min-road:" << sum << endl;
        show_path(Pop[better_fit]);//输出该最优路径
        temp.push_back(Pop[better_fit]);//将最好的个体复制两份到新的种群中
        temp.push_back(Pop[better_fit]);
        int M = 3;//精英选择策略中随机选择的个体数
        srand((unsigned)time(NULL));
        for (int i = 0; i < Population_num - 2; ++i)//用联赛选择剩余的个体数
        {
                int fit = INT_MAX;//当前所选个体集合中的最高适应度
                int loc;//适应度最好的个体
                for (int j = 0; j < M; ++j)//从city_num-2个个体中随机选择M个个体
                {
                        int pos = rand() % Population_num;
                        while (pos == better_fit || pos == worse_fit)//该个体不能是当前种群中适应度最高或最差的个体
                                pos = rand() % Population_num;
                        if (distance_all_city(Pop[pos]) < fit)//判断当前个体是否适应度最优的个体
                        {
                                fit = distance_all_city(Pop[pos]);
                                loc = pos;
                        }
                }
                temp.push_back(Pop[loc]);//用联赛选择策略选择了一个个体，将它加入新的种群中
        }
        Pop = temp;//产生新的种群
}
//单点交叉并消除冲突
void Mating()
{
        vector<City> temp1, temp2;
        int pos = 7;//发生交叉的起始位置（交叉区域：从该位置到末尾）
        srand((unsigned)time(NULL));
        for (int i = 0; i < 48; ++i)
        {
                double rand_rate = rand() / (float)RAND_MAX;
                if (rand_rate < pc)//如果当前的概率小于交叉的概率则进行交叉
                {
                        temp1 = Pop[i + 2];//个体1
                        temp1[pos] = Pop[99 - i][pos];//交叉
                        temp1[pos + 1] = Pop[99 - i][pos + 1];
                        temp1[pos + 2] = Pop[99 - i][pos + 2];
                        int z = 0;//消除冲突
                        for (int j = 0; j < pos; ++j)
                        {
                                while (Pop[i + 2][z].label == temp1[pos].label || Pop[i + 2][z].label == temp1[pos + 1].label ||
                                        Pop[i + 2][z].label == temp1[pos + 2].label)
                                        ++z;
                                temp1[j] = Pop[i + 2][z];
                                ++z;
                        }
                        temp2 = Pop[99 - i];//个体2
                        temp2[pos] = Pop[i + 2][pos];//交叉
                        temp2[pos + 1] = Pop[i + 2][pos + 1];
                        temp2[pos + 2] = Pop[i + 2][pos + 2];
                        z = 0;//消除冲突
                        for (int j = 0; j < pos; ++j)
                        {
                                while (Pop[99 - i][z].label == temp2[pos].label || Pop[99 - i][z].label == temp2[pos + 1].label ||
                                        Pop[99 - i][z].label == temp2[pos + 2].label)
                                        ++z;
                                temp2[j] = Pop[99 - i][z];
                                ++z;
                        }
                        Pop[i + 2] = temp1;//完成交叉
                        Pop[99 - i] = temp2;
                }
        }
}
//变异
void Variation()
{
        srand((unsigned)time(NULL));
        for (int i = 2; i < Population_num; ++i)
        {
                double rand_rate = rand() / (float)RAND_MAX;
                if (rand_rate < pm)//如果当前概率小于变异概率则进行变异
                {
                        for (int j = 0; j < 5; ++j)//随机选择5个基因进行变异
                        {
                                int pos1 = rand() % city_num;//随机选择变异的位置
                                int pos2 = rand() % city_num;
                                swap(Pop[i][pos1], Pop[i][pos2]);
                        }
                }
        }
}

int main()
{
        const int gen_max = 30;//最大迭代数
        init();
        for (int i = 0; i < gen_max; ++i)
        {
                cout << "Generation " << i + 1 << endl;
                BettingWheelSelection();
                Mating();
                Variation();
        }
}