tsp.cpp

C语言实现的遗传算法解TSP问题（旅行商问题）

#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)
    {
      //Path2Node在Path的交换段的内找到，暂不作处理
      //否则，需要把该处的节点换成相应的值      
      if(j < Begin || j >= End)
      {
        int Val = Couple2[k]; 
        for(int a = 0; a < c;)
        {
          if(Couple[a] == Val)
          {
            Val = Couple2[a];
            a = 0; //回溯查找对应值
          }
          else
            a++;
        }
        Path[j] = Val;
      }
      break;
    }

    //对查找范围作调整，忽略交叉起点到当前位置之间的位
    if(j == Begin - 1)
      j = i;
  }
}

void OX_Cross(int Path[], int Path2[], int Begin, int End)
{
  void OX_CrossIml(int Path[], int Path2[], int Begin, int End, int NewPath[]);
  int NewPath[CITY_SIZE], NewPath2[CITY_SIZE];
  OX_CrossIml(Path, Path2, Begin, End, NewPath);
  OX_CrossIml(Path2, Path, Begin, End, NewPath2);
  memmove(Path, NewPath, sizeof(int) * CITY_SIZE);
  memmove(Path2, NewPath2, sizeof(int) * CITY_SIZE);
}

void OX_CrossIml(int Path[], int Path2[], int Begin, int End, int New[])
{
  int Buf[CITY_SIZE];
  memmove(Buf, Path + End, sizeof(int) * (CITY_SIZE - End));
  memmove(Buf + (CITY_SIZE - End), Path, sizeof(int) * End);
  for(int i = 0, j = 0; i < CITY_SIZE; i++)
  {    
    if(i < Begin || i >= End)
    {
      for(; j < CITY_SIZE; j++)
      {
        int k;
        for(k = Begin; k < End; k++)
        {
          if(Path2[k] == Buf[j])
            break;
        }
        if(k >= End)
          break;
      }
      New[i] = Buf[j++];
    }
    else
      New[i] = Path2[i];
  }
}

void Mutate(int Pop[][CITY_SIZE], int Count)
{
  for(int i = 0; i < Count; i++)
  {
    double Randf = double(rand()) / double(RAND_MAX);//生成一个在0-1之间的随机数
    if(Randf <= PM)
    {//前后倒序
      int c = rand() % CITY_SIZE;
      int j = rand() % CITY_SIZE;
      if(c > j)
      {
        int t = c;
        c = j;
        j = t;
      }

      for(; c < j; c++, j--)
      {
        int Num = Pop[i][c];
        Pop[i][c] = Pop[i][j];
        Pop[i][j] = Num;
      }
    }
  }
}

int GetBestPathIndex(int EvalVal[], int Count)
{
  int Min = EvalVal[0], MinIdx = 0;
  for(int i = 1; i < Count; i++)
  {
    if(Min > EvalVal[i])
    {
      Min = EvalVal[i];
      MinIdx = i;
    }
  }
  return MinIdx;
}

void ShowBestResult(int Path[], int Len, int Gen)
{
  printf("Generation Number %d, shortest path (%d):\n", Gen, Len);
  ShowPath((int(*)[CITY_SIZE])Path, 1);
}

void ShowPath(int Path[][CITY_SIZE], int Count)
{
  for(int j = 0; j < Count; j++)
  {
    for(int i = 0; i < CITY_SIZE - 1; i++)
      printf("%d-", Path[j][i]);
    printf("%d\n", Path[j][CITY_SIZE - 1]);
  }
  printf("\n");
}