模拟退⽕和遗传算法解决TSP问题
数据集介绍
采⽤数据集FRI26
来⾃标准数据集，共有26个城市，最优解为933：
图1：数据矩阵
图2：数据集介绍
算法介绍
模拟退⽕
介绍：酸类
模拟退⽕是⼀种通⽤概率算法，常⽤来在⼀定时间内寻在⼀个很⼤搜寻空间中的近似最优解。
迭代过程：
迭代过程是模拟退⽕算法的核⼼步骤，分为新解的产⽣和接受新解两部分： 1. 由⼀个产⽣函数从当前解产⽣⼀个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变 换即可产⽣新解的⽅法，如对构成新解的全部或部分元素进⾏置换、互换等，注意到产⽣新解的变换⽅法决定了当前新解的邻域结构，因⽽对冷却进度表的选取有⼀定的影响。
2. 计算与新解所对应的⽬标函数差。因为⽬标函数差仅由变换部分产⽣，所以⽬标函数差的计算最好按增量计算。事实表明，对⼤多数
应⽤⽽⾔，这是计算⽬标函数差的最快⽅法。
3. 判断新解是否被接受，判断的依据是⼀个接受准则，最常⽤的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，
否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
4. 当新解被确定接受时，⽤新解代替当前解，这只需将当前解中对应于产⽣新解时的变换部分予以实现，同时修正⽬标函数值即可。此
时，当前解实现了⼀次迭代。可在此基础上开始下⼀轮试验。⽽当新解被判定为舍弃时，则在原当前解的基础上继续下⼀轮试验。
实现代码：
// 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//"; 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()
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次，取平均值：
图3：模拟退⽕结果
路面遗传算法
介绍：
遗传算法是计算数学中⽤于解决最优化的搜索算法，是进化算法的⼀种。进化算法最初是借鉴了进化⽣物学中的⼀些现象⽽发展起来的，这些现象包括遗传、突变、⾃然选择以及杂交等。
实现代码：
#include <stdio.h>
#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 // 变异概率
第29次中国互联网络发展状况统计报告
#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//"; 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;
px事件
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;
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议