#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <malloc.h>
#define PMX
#define PC 0.70 //杂交率
#define PM 0.04 //变异率
#define CITY_SIZE 50 //城市数
#define POP_SIZE 1000 //种群规模
#define NEW_SIZE (POP_SIZE/2) //用于重组的个体数
#define GEN_TOTAL 10000 //总遗传代数
void Initialize(int Pop[][CITY_SIZE], int Count);
void Evaluate(int Pop[][CITY_SIZE], int EvalVal[], int Count);
void ParentSelect(int Pop[][CITY_SIZE], int EvalVal[], int Count);
void Recombine(int Pop[][CITY_SIZE], int Count);
void Mutate(int Pop[][CITY_SIZE], int Count);
int GetBestPathIndex(int EvalVal[], int Count);
void ShowBestResult(int Path[], int Len, int Gen);
void ShowPath(int Path[][CITY_SIZE], int Count);
void TSPProc();
int main(int argc, char *argv[])
{
void TSPProc();
TSPProc();
printf("\nFinish searching!");
getch();
return 0;
}
void TSPProc()
{
//使用一个整型数组表示每条路径
int Pop[POP_SIZE][CITY_SIZE];
int BestEval, BestPath[CITY_SIZE];
//对路径的评估使用整型数表示，忽略小数部分
int EvalVal[POP_SIZE];
Initialize(Pop, POP_SIZE);
Evaluate(Pop, EvalVal, POP_SIZE);
int t = GetBestPathIndex(EvalVal, POP_SIZE);
memmove(BestPath, Pop[t], sizeof(int) * CITY_SIZE);
BestEval = EvalVal[t];
ShowBestResult(BestPath, BestEval, 0);
t = 1;
while(t < GEN_TOTAL)
{
ParentSelect(Pop, EvalVal, POP_SIZE);
Recombine(Pop, POP_SIZE);
Mutate(Pop, POP_SIZE);
Evaluate(Pop, EvalVal, POP_SIZE);
printf("\rCurrent generation:%d", t);
int Index = GetBestPathIndex(EvalVal, POP_SIZE);
if(EvalVal[Index] < BestEval)
{
BestEval = EvalVal[Index];
memmove(BestPath, Pop[Index], sizeof(int) * CITY_SIZE);
printf("\r");
ShowBestResult(BestPath, BestEval, t);
}
t++;
}
}
//初始化种群
void Initialize(int Pop[][CITY_SIZE], int Count)
{
int i, j;
int Seed[CITY_SIZE];
srand(time(NULL));
for(i = 0; i < Count; i++)
{
for(j = 0; j < CITY_SIZE; j++)
Seed[j] = j;
//随机产生一条路径
for(j = 0; j < CITY_SIZE; j++)
{
int RandIdx = rand() % (CITY_SIZE - j);
Pop[i][j] = Seed[RandIdx];
Seed[RandIdx] = Seed[CITY_SIZE - j - 1];
}
}
}
//评估路径Pop，结果放入EvalVal
void Evaluate(int Pop[][CITY_SIZE], int EvalVal[], int Count)
{
static int Matrix[CITY_SIZE][CITY_SIZE];
static bool bInitMatrix;
int i, j;
char Str[256];
//先检查邻接矩阵是否已初始化
if(!bInitMatrix)
{
bool bInit = false;
FILE *pFile = fopen("d:\\tsp.txt", "r");
if(pFile)
{
bInit = true;
for(i = 0; i < CITY_SIZE; i++)
{
for(j = 0; j < CITY_SIZE; j++)
{
if(!fgets(Str, 64, pFile))
{
bInit = false;
break;
}
Matrix[i][j] = atoi(Str);
}
}
}
if(!bInit)
{
//先初始化每个城市的位置
short Locx[CITY_SIZE];
short Locy[CITY_SIZE];
for(i = 0; i < CITY_SIZE; i++)
{
Locx[i] = rand() % 500;
Locy[i] = rand() % 500;
}
//根据位置初始化城市邻接矩阵
pFile = fopen("d:\\tsp.txt", "w");
for(i = 0; i < CITY_SIZE; i++)
{
for(j = 0; j < CITY_SIZE; j++)
{
int Dx = Locx[i] - Locx[j];
int Dy = Locy[i] - Locy[j];
Matrix[i][j] = (int)sqrt(Dx * Dx + Dy * Dy);
fprintf(pFile, "%d\n", Matrix[i][j]); //保存到文件
}
}
}
fclose(pFile);
bInitMatrix = true;
}
//查邻接表获得每条路径的长度
for(i = 0; i < Count; i++)
{
int Len = 0;
//求第i条路径的长度
for(j = 0; j < CITY_SIZE - 1; j++)
Len += Matrix[Pop[i][j]][Pop[i][j+1]];
EvalVal[i] = Len;
}
}
//按轮盘的方法选择
void ParentSelect(int Pop[][CITY_SIZE], int EvalVal[], int Count)
{
int(*Buf)[CITY_SIZE] = (int (*)[CITY_SIZE])alloca(sizeof(int[CITY_SIZE]) * Count);
int *EvalBuf = (int *)alloca(sizeof(int) * Count);
//求得所有路径的总距离
int i, j, MinIdx;
double TotalLen = 0, *Ratio = (double *)alloca(sizeof(double) * Count);
for(i = 0; i < Count; i++)
TotalLen += EvalVal[i];
//计算每条路径所占比率
double Min = 1, Max = 0;
for(i = 0; i < Count; i++)
{
Ratio[i] = EvalVal[i] / TotalLen;
if(Min > Ratio[i])
{
Min = Ratio[i];
MinIdx = i;
}
if(Max < Ratio[i])
Max = Ratio[i];
}
//转换每条路径所占比率（长的路径比率大转换为短路径占大比率）
for(i = 0; i < Count; i++)
{
Ratio[i] = Max - Ratio[i] + Min;
if(i != 0)
Ratio[i] += Ratio[ i - 1];
}
Ratio[Count - 1] = 1; //纠正浮点数计算的误差导致最后的数可能不为1
bool bBestSelected = false;
srand(time(NULL));
for(i = 0; i < Count; i++)
{
double Randf = double(rand()) / double(RAND_MAX);//生成一个在0-1之间的随机数
for(j = 0; j < Count; j++)
{
if(Randf <= Ratio[j])
{
if(MinIdx == j)
bBestSelected = true;
memmove(Buf[i], Pop[j], sizeof(int) * CITY_SIZE);
EvalBuf[i] = EvalVal[j];
break;
}
}
}
//把最优解直接拷贝到下一代，保留最优
if(!bBestSelected)
{
i = rand() % Count;
memmove(Buf[i], Pop[MinIdx], sizeof(int) * CITY_SIZE);
EvalBuf[i] = EvalVal[MinIdx];
}
memmove(Pop, Buf, sizeof(int[CITY_SIZE]) * Count);
memmove(EvalVal, EvalBuf, sizeof(int) * Count);
}
//重组产生新的路径
void Recombine(int Pop[][CITY_SIZE], int Count)
{
void PMX_Cross(int Path[], int Path2[], int, int);
void OX_Cross(int Path[], int Path2[], int, int);
for(int i = 0; i < (NEW_SIZE & ~1); i += 2)
{
double Randf = double(rand()) / double(RAND_MAX);//生成一个在0-1之间的随机数
if(Randf < PC)
{
//随机选择两个体
int i = rand() % Count;
int j = rand() % Count;
//计算出交换段，随机给出起始点
int Begin = rand() % CITY_SIZE;
int End = Begin + rand() % (CITY_SIZE / 10);
if(End > CITY_SIZE)
End = CITY_SIZE - 1;
#ifdef PMX
PMX_Cross(Pop[i], Pop[j], Begin, End);
#else
OX_Cross(Pop[i], Pop[j], Begin, End);
#endif
}
}
}
void PMX_Cross(int Path[], int Path2[], int Begin, int End)
{
void DelConflict(int Path[], int Path2[], int Begin, int End, int i,
int PathNode, int Path2Node, int Couple[], int Couple2[], int &c);
//开辟空间用来记录交换的数据
int *Couple1 = (int *)alloca(sizeof(int) * (End - Begin));
int *Couple2 = (int *)alloca(sizeof(int) * (End - Begin));
int *Couple3 = (int *)alloca(sizeof(int) * (End - Begin));
int *Couple4 = (int *)alloca(sizeof(int) * (End - Begin));
for(int i = Begin, c = 0, c2 = 0; i < End; i++)
{
if(Path[i] != Path2[i])
{
int PathNode = Path[i], Path2Node = Path2[i];
//交换两条路径的第i个节点
Path[i] = Path2Node;
Path2[i] = PathNode;
DelConflict(Path, Path2, Begin, End, i, PathNode, Path2Node, Couple1, Couple2, c);
DelConflict(Path2, Path, Begin, End, i, Path2Node, PathNode, Couple3, Couple4, c2);
}
}
}
//解决第i节点交换后产生的节点号重复冲突
void DelConflict(int Path[], int Path2[], int Begin, int End, int i,
int PathNode, int Path2Node, int Couple[],
int Couple2[], int &c)
{
int j, k;
//对交换偶对作调整
for(k = 0; k < c; k++)
{
if(Couple[k] == PathNode)
{
Couple[k] = Path2Node;
break;
}
}
if(k >= c)
{
Couple[c] = Path2Node;
Couple2[c++] = PathNode;
}
for(j = Begin == 0 ? i + 1 : 0; j < CITY_SIZE; j++)
{
if(Path[j] == Path2Node)
{
//Pa
