模拟退火和遗传算法解决TSP问题
模拟退火和遗传算法解决TSP问题
数据集介绍
- 采用数据集FRI26
来自标准数据集，共有26个城市，最优解为933：
数据下载链接
算法介绍
模拟退火
介绍：
模拟退火是一种通用概率算法，常用来在一定时间内寻找在一个很大搜寻空间中的近似最优解。
迭代过程：
迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：
- 由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
- 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
- 判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
- 当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
实现代码：
// tsp_sa.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fstream>
#include <iostream>
#include <assert.h>
#include <math.h>
using namespace std;
#define T0 50000.0 //初始化温度
#define Tk (1e-8) //终止温度
#define d 0.98 // 退火系数
#define L 1000 // 每个温度时的迭代次数，即链长
#define N 26 // 城市数量
#define TESTTIME 30 //测试次数
int solution[N]; // 用于存放一个解
int map[N][N]; //记录地图数据
const char* filepath = "C://Users//56989//Desktop//dataset.txt";
ifstream infile;
//读取数据
void readData()
{
infile.open(filepath);
assert(infile.is_open()); //若失败,则输出错误消息,并终止程序运行
for (int i = 0; i < 26; i++)
{
for (int j = 0; j < 26; j++)
{
infile >> map[i][j];
}
}
}
// 计算路径长度
int pathLen(int * arr)
{
int totlen = 0;
for (int i = 0; i < N-1; i++)
{
totlen += map[arr[i]][arr[i + 1]];
}
totlen += map[arr[N-1]][arr[0]]; //回到出发城市
return totlen;
}
// 初始化函数
void initSolution()
{
for (int i = 0; i<N; i++)
solution[i] = i; // 初始化一个解
}
// 产生一个新解
// 此处采用随机交叉两个位置的方式产生新的解
void genAnotherSolu()
{
double r1 = ((double)rand()) / (RAND_MAX + 1.0);
double r2 = ((double)rand()) / (RAND_MAX + 1.0);
int pos1 = (int)(N*r1); //第一个交叉点的位置
int pos2 = (int)(N*r2);
int temp = solution[pos1];
solution[pos1] = solution[pos2];
solution[pos2] = temp; // 交换两个点
}
// 主函数
int main(void)
{
readData(); //读取数据
printf("读数据完成\n\n");
srand((unsigned)time(NULL));
time_t start, finish; //计算时间
start = clock(); //开始计算时间
int tempsolu[N]; //保留原来的解
int tempLen = 0;
double aveLen = 0.0; //平均长度
for (int testtime = 1; testtime <= TESTTIME; testtime++)
{
double T;
T = T0; //初始温度
initSolution(); //初始化一个解
int soluLen = pathLen(solution);
while (T > Tk)
{
//printf("进入.\n");
for (int i = 1; i <= L; i++)
{
memcpy(tempsolu, solution, N * sizeof(int)); // 复制数组，保留原来的解
genAnotherSolu(); // 产生新解
tempLen = pathLen(tempsolu);
soluLen = pathLen(solution);
int dif = soluLen - tempLen;
if (dif >= 0)//原来的解更好
{
double ran = ((double)rand()) / (RAND_MAX);
if (exp(-dif / T) <= ran) // 保留原来的解
{
memcpy(solution, tempsolu, N * sizeof(int));
}
}
}
T = T * d; // 降温
}
aveLen += pathLen(solution);
printf("第%d次计算完成，所得路径长度为: %d\n", testtime, pathLen(solution));
}
aveLen = aveLen / 30;
finish = clock();
double duration = ((double)(finish - start)) / CLOCKS_PER_SEC; // 计算时间
printf("程序运行耗时:%lf秒.\n", duration);
printf("重复30次，求得的最优路径平均值为：%2f.\n", aveLen);
/*
printf("模拟退火算法\n");
printf("路径如下：\n");
for (int i = 0; i<N ; i++) // 输出路径
{
printf("%d ", solution[i]);
}
printf("\n最优路径长度为:%d\n", pathLen(solution));
*/
return 0;
}
实验结果：
计算30次，取平均值：
遗传算法
介绍：
遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
实现代码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <fstream>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
#define MAXGENS 500 // 最大进化代数
#define POPSIZE 100 // 种群数目
#define PXOVER 0.6 // 交叉概率
#define PMUTATION 0.1 // 变异概率
#define N 26 // 染色体长度(这里即为城市个数)
#define TESTTIME 30 //测试次数
int pop[POPSIZE][N]; // 种群
int fitness[POPSIZE];
int globalBest[N]; // 最佳路线
int bestFitness = 0x7FFFFFFF; // 最短路径长度
int map[N][N]; //记录地图数据
const char* filepath = "C://Users//56989//Desktop//dataset.txt";
ifstream infile;
//读取数据
void readData()
{
infile.open(filepath);
assert(infile.is_open()); //若失败,则输出错误消息,并终止程序运行
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
infile >> map[i][j];
}
}
infile.close();
}
// 种群初始化
void init()
{
int num = 0;
while (num < POPSIZE)
{
for (int i = 0; i<POPSIZE; i++)
for (int j = 0; j<N; j++)
pop[i][j] = j;
num++;
for (int i = 0; i<N - 1; i++)
{
for (int j = i + 1; j<N; j++)
{
int temp = pop[num][i];
pop[num][i] = pop[num][j];
pop[num][j] = temp; // 交换第num个个体的第i个元素和第j个元素
num++;
if (num >= POPSIZE)
break;
}
if (num >= POPSIZE)
break;
}
while (num < POPSIZE)
{
double r1 = ((double)rand()) / (RAND_MAX + 1.0);
double r2 = ((double)rand()) / (RAND_MAX + 1.0);
int p1 = (int)(N*r1); // 位置1
int p2 = (int)(N*r2); // 位置2
int temp = pop[num][p1];
pop[num][p1] = pop[num][p2];
pop[num][p2] = temp; // 交换基因位置
num++;
}
}
// for (int i = 0; i<POPSIZE; i++)
// {
// for (int j = 0; j<N; j++)
// {
// pop[i][j] = j;
// }
// random_shuffle(pop[i], pop[i] + N);
// }
}
int findMin()
{
int mindis = fitness[0];
int minindex = 0;
for (int i = 1; i<POPSIZE; i++)
{
if (fitness[i] < mindis)
{
mindis = fitness[i];
minindex = i;
}
}
return minindex;
}
// 计算路径长度
double pathLen(int * arr)
{
int totlen = 0;
for (int i = 0; i < N - 1; i++)
{
totlen += map[arr[i]][arr[i + 1]];
}
totlen += map[arr[N - 1]][arr[0]]; //回到出发城市
return totlen;
}
// 选择操作
void select()
{
double pick;
int choice_arr[POPSIZE][N];
double fit_pro[POPSIZE];
double sum = 0;
double fit[POPSIZE]; // 适应度函数数组(距离的倒数)
for (int j = 0; j<POPSIZE; j++)
{
fit[j] = 1.0 / fitness[j];
sum += fit[j];
}
for (int j = 0; j<POPSIZE; j++)
{
fit_pro[j] = fit[j] / sum; // 概率数组
}
// 开始轮盘赌
for (int i = 0; i<POPSIZE; i++)
{
pick = ((double)rand()) / RAND_MAX; // 0到1之间的随机数
for (int j = 0; j<POPSIZE; j++)
{
pick = pick - fit_pro[j];
if (pick <= 0)
{
for (int k = 0; k<N; k++)
choice_arr[i][k] = pop[j][k]; // 选中一个个体
break;
}
}
}
for (int i = 0; i<POPSIZE; i++)
{
for (int j = 0; j<N; j++)
pop[i][j] = choice_arr[i][j];
}
}
//交叉操作
void crossover()
{
double pick;
double pick1, pick2;
int choice1, choice2;
int pos1, pos2;
int temp;
int conflict1[N]; // 冲突位置
int conflict2[N];
int num1, num2;
int index1, index2;
int move = 0; // 当前移动的位置
while (move<N - 1)
{
pick = ((double)rand()) / RAND_MAX; // 用于决定是否进行交叉操作
if (pick > PXOVER)
{
move += 2;
continue; // 本次不进行交叉
}
// 采用部分映射杂交
choice1 = move; // 用于选取杂交的两个父代
choice2 = move + 1; // 注意避免下标越界
pick1 = ((double)rand()) / (RAND_MAX + 1.0);
pick2 = ((double)rand()) / (RAND_MAX + 1.0);
pos1 = (int)(pick1*N); // 用于确定两个杂交点的位置
pos2 = (int)(pick2*N);
while (pos1 > N - 2 || pos1 < 1)
{
pick1 = ((double)rand()) / (RAND_MAX + 1.0);
pos1 = (int)(pick1*N);
}
while (pos2 > N - 2 || pos2 < 1)
{
pick2 = ((double)rand()) / (RAND_MAX + 1.0);
pos2 = (int)(pick2*N);
}
if (pos1 > pos2)
{
temp = pos1;
pos1 = pos2;
pos2 = temp; // 交换pos1和pos2的位置
}
for (int j = pos1; j <= pos2; j++)
{
temp = pop[choice1][j];
pop[choice1][j] = pop[choice2][j];
pop[choice2][j] = temp; // 逐个交换顺序
}
num1 = 0;
num2 = 0;
if (pos1 > 0 && pos2 < N - 1)
{
for (int j = 0; j <= pos1 - 1; j++)
{
for (int k = pos1; k <= pos2; k++)
{
if (pop[choice1][j] == pop[choice1][k])
{
conflict1[num1] = j;
num1++;
}
if (pop[choice2][j] == pop[choice2][k])
{
conflict2[num2] = j;
num2++;
}
}
}
for (int j = pos2 + 1; j<N; j++)
{
for (int k = pos1; k <= pos2; k++)
{
if (pop[choice1][j] == pop[choice1][k])
{
conflict1[num1] = j;
num1++;
}
if (pop[choice2][j] == pop[choice2][k])
{
conflict2[num2] = j;
num2++;
}
}
}
}
if ((num1 == num2) && num1 > 0)
{
for (int j = 0; j<num1; j++)
{
index1 = conflict1[j];
index2 = conflict2[j];
temp = pop[choice1][index1]; // 交换冲突的位置
pop[choice1][index1] = pop[choice2][index2];
pop[choice2][index2] = temp;
}
}
move += 2;
}
}
// 变异操作
// 变异策略采取随机选取两个点，将其对换位置
void mutation()
{
double pick, pick1, pick2;
int pos1, pos2, temp;
for (int i = 0; i<POPSIZE; i++)
{
pick = ((double)rand()) / RAND_MAX; // 用于判断是否进行变异操作
if (pick > PMUTATION)
continue;
pick1 = ((double)rand()) / (RAND_MAX + 1.0);
pick2 = ((double)rand()) / (RAND_MAX + 1.0);
pos1 = (int)(pick1*N); // 选取进行变异的位置
pos2 = (int)(pick2*N);
while (pos1 > N - 1)
{
pick1 = ((double)rand()) / (RAND_MAX + 1.0);
pos1 = (int)(pick1*N);
}
while (pos2 > N - 1)
{
pick2 = ((double)rand()) / (RAND_MAX + 1.0);
pos2 = (int)(pick2*N);
}
temp = pop[i][pos1];
pop[i][pos1] = pop[i][pos2];
pop[i][pos2] = temp;
}
}
//精英更新
void elitist()
{
int best, worst;
int bestIndex, worstIndex;
best = fitness[0];
worst = fitness[0];
bestIndex = 0;
worstIndex = 0;
//找出最好和最坏
for (int i = 0; i < POPSIZE; i++)
{
if (fitness[i] < best)
{
best = fitness[i];
bestIndex = i;
}
else if (fitness[i] > worst)
{
worst = fitness[i];
worstIndex = i;
}
}
//要不更新最好
if (best < bestFitness)
{
for (int i = 0; i < N; i++)
{
globalBest[i] = pop[bestIndex][i];
}
bestFitness = best;
}
else//要不更新最坏
{
for (int i = 0; i < N; i++)
{
pop[worstIndex][i] = globalBest[i];
}
fitness[worstIndex] = bestFitness;
}
}
int main(void)
{
readData();
time_t start, finish;
start = clock();
double aveLen = 0.0;
int timeTime = 0;
while (timeTime < TESTTIME)
{
srand((unsigned)time(NULL)); // 初始化随机数种子
init();
//更新fitness
for (int j = 0; j<POPSIZE; j++)
{
fitness[j] = pathLen(pop[j]);
}
int minindex = findMin();
for (int j = 0; j<N; j++)
globalBest[j] = pop[minindex][j]; // 最短路径序列
bestFitness = fitness[minindex];
for (int i = 0; i<MAXGENS; i++)
{
select(); // 选择
crossover(); //交叉
mutation(); //变异
for (int j = 0; j<POPSIZE; j++)
fitness[j] = pathLen(pop[j]); // 距离数组
elitist(); //添加一个精英选择
minindex = findMin();
if (fitness[minindex] < bestFitness)
{
bestFitness = fitness[minindex]; // 更新最短路径
for (int j = 0; j<N; j++)
globalBest[j] = pop[minindex][j]; // 更新全局最短路径序列
}
}
timeTime++;
aveLen += bestFitness;
printf("第%d次计算，最短路径长度为:%d\n", timeTime, bestFitness);
}
finish = clock(); // 计算结束
double duration = ((double)(finish - start)) / CLOCKS_PER_SEC; // 计算耗时
printf("遗传算法\n");
/*
for (int i = 0; i < N; i++)
{
cout << globalBest[i] << " ";
}
cout << endl;
printf("最短路径长度为:%d\n", bestFitness);
*/
printf("程序平均耗时为:%lf秒.\n", duration/TESTTIME);
printf("平均结果为：%2f\n", aveLen / 30);
return 0;
}
遗传算法结果：
走过的坑：
- 遗传算法收敛特别慢。我所实现的版本经过了多次！多次！的改良。才勉强达到模拟退火的水平。不然效果特别差。
- 遗传算法的初始化对最终结果有较大的影响，这点和模拟退火有很大的不同。
- 遗传算法实现难度大于模拟退火。整个过程耗费了本人很多很多时间!
两者对比：
- 两者结果其实类似。无论从时间上还是从结果上。
- 其实遗传算法要次于模拟退火。一是遗传算法很依赖初始解，这给构造带来了极大的挑战。二是遗传算法收敛特别慢，容易陷入局部最优。
- 遗传算法的交叉算子，选择算子有多种并且实现相对复杂，并且需要调的参数比模拟退火多。针对简单问题时，不建议使用遗传算法。
代码下载：
包括sa的源码、GA源码以及数据集
有不足之处请多指教 ????
数据集来源：
http://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
http://people.sc.fsu.edu/~jburkardt/datasets/tsp/fri26_d.txt
模拟退火博客：
https://www.cnblogs.com/lyrichu/p/6688459.html
https://www.cnblogs.com/flashhu/p/8884132.html
https://www.cnblogs.com/rvalue/p/8678318.html
TSP介绍：
https://baike.baidu.com/item/TSP问题/840008?fr=aladdin
GA:
https://www.cnblogs.com/lyrichu/p/6152928.html
https://blog.****.net/greedystar/article/details/80343841#五、源代码