遗传算法解决旅行商问题

下面是程序的主要核心代码：
// 变异函数
inline void Variant(GENE & gsource, GENE & gdest, int * ptemp, int size, int varate)
{
static int i;
static int j, k, l, n, m;
static int tmp;
memcpy(gdest.index, gsource.index, sizeof(int) * size);
for(i = 0; i < varate; i++)
{
switch(rand() % 2)
{
case 0:
// 逆序变异
{
j = rand() % size;
k = rand() % size;
if(j == k)
{
k = (k + 1) % size;
}
if(j > k)
{
k += size;
for(l = j; l < j + k - l; l++)
{
n = (j + k - l) % size;
m = l % size;
tmp = gdest.index[m];
gdest.index[m] = gdest.index[n];
gdest.index[n] = tmp;
}
}
else
{
for(l = j; l < j + k - l; l++)
{
tmp = gdest.index[l];
gdest.index[l] = gdest.index[j + k - l];
gdest.index[j + k - l] = tmp;
}
}
}
break;
case 1:
// 转移变异
{
j = rand() % size;
k = 1;//rand() % ((size >> 4) + 1);
if(k == 0)
{
k = 1;
}
l = rand() % (size - k) + 1;
n = (j + k) % size + l > size ? size - (j + k) % size : l;
memcpy(ptemp, gdest.index + (j + k) % size, n * sizeof(int));
if(n < l)
{
memcpy(ptemp + n, gdest.index, (l - n) * sizeof(int));
}
n = j + k > size ? size - j : k;
memcpy(ptemp + l, gdest.index + j, n * sizeof(int));
if(n < k)
{
memcpy(ptemp + l + n, gdest.index, (k - n) * sizeof(int));
}
m = k + l;
n = j + m > size ? size - j :m;
memcpy(gdest.index + j, ptemp, n * sizeof(int));
if(n < m)
{
memc

py(gdest.index, ptemp + n, (m - n) * sizeof(int));
}
}
break;
default:
break;
}
}
}

// 辅助线程
UINT CCityMap::ThreadProc( LPVOID pParam )
{
CCityMap * pClass = (CCityMap *)pParam;
if(pClass->m_iCityNum <= 1)
{
return 0;
}
srand((UINT)time(NULL));
pClass->m_bCompute = true;
pClass->ReadSetting();
static int i, j;
static GENE tgene;
static int bullet;
static int totalBullet;
static int maxCountdown = CM_JUMP_COUNTDOWN_INIT;
// 分配空间
int num = pClass->m_iCityNum;
int * ptmp = new int[num];
int commSize = CM_SEED_NUM * (1 + CM_CHILDREN_NUM);
GENE * comm = new GENE[commSize];
for(i = 0; i < commSize; i++)
{
comm.index = new int [num];
comm.mark = 0.0;
}
// 生成初始群落
CTime tstart = CTime::GetCurrentTime();
CTime tnow;
pClass->m_i64GenNum = 1;
pClass->m_iJumpCount = 0;
memcpy(comm[0].index, pClass->m_piBestIndex, sizeof(int) * num);
pClass->Mark(comm[0]);
pClass->QuadrangleOptimise(comm[0]);
pClass->m_dBestMark = comm[0].mark;
pClass->m_i64BestGen = pClass->m_i64GenNum;
double maxMark = comm[0].mark;
int maxIndex = 0;
double totalMark = maxMark;
pClass->m_iJumpCountdown = CM_JUMP_COUNTDOWN_INIT;
for(i = 1; i < CM_SEED_NUM; i++)
{
Variant(comm[0], comm, ptmp, num, pClass->m_iJumpCountdown);
pClass->Mark(comm);
totalMark += comm.mark;
if(maxMark < comm.mark)
{
maxMark = comm.mark;
maxIndex = i;
}
}
// 移动最优基因
if(maxIndex != 0)
{
tgene.index = comm[0].index;
tgene.mark = comm[0].mark;
comm[0].index = comm[maxIndex].index;
comm[0].mark = comm[maxIndex].mark;
comm[maxIndex].index = tgene.index;
comm[maxIndex].mark = tgene.mark;
maxIndex = 0;
pClass->QuadrangleOptimise(comm[0]);
maxMark = comm[0].mark;
memcpy(pClass->m_piBestIndex, comm[0].index, sizeof(int) * num);
pClass->m_dBestMark = maxMark;
pClass->m_i64BestGen = pClass->m_i64GenNum;
}
int indNum = CM_SEED_NUM;
pClass->m_dAVGMark = (totalMark) / indNum;
pClass->m_pMaxTrendLine->Clear();
pClass->m_pAVGTrendLine->Clear();
pClass->m_pMaxTrendLine->AddValue(maxMark);
pClass->m_pAVGTrendLine->AddValue(pClass->m_dAVGMark);
// 开始进化
while(!pClass->m_bKillMsg)
{
totalMark = 0.0;
// 变异
for(i = 0; i < CM_SEED_NUM; i++)
{
totalMark +=

comm.mark;
for(j = 0; j < CM_CHILDREN_NUM; j++)
{
Variant(comm, comm[indNum], ptmp, num, 1);
pClass->Mark(comm[indNum]);
totalMark += comm[indNum].mark;
if(maxMark < comm[indNum].mark)
{
maxMark = comm[indNum].mark;
maxIndex = indNum;
}
indNum++;
}
}
pClass->m_dAVGMark = (totalMark) / indNum;
pClass->m_pAVGTrendLine->AddValue(pClass->m_dAVGMark);
pClass->m_pMaxTrendLine->AddValue(maxMark);
// 移动最优基因
if(maxIndex != 0)
{
tgene.index = comm[0].index;
tgene.mark = comm[0].mark;
comm[0].index = comm[maxIndex].index;
comm[0].mark = comm[maxIndex].mark;
comm[maxIndex].index = tgene.index;
comm[maxIndex].mark = tgene.mark;
maxIndex = 0;
if(maxMark > pClass->m_dBestMark)
{
memcpy(pClass->m_piBestIndex, comm[0].index, sizeof(int) * num);
pClass->m_dBestMark = maxMark;
pClass->m_i64BestGen = pClass->m_i64GenNum;
}
int forcastCountdown = int((maxCountdown - pClass->m_iJumpCountdown) * CM_JUMP_COUNTDOWN_INC);
if(forcastCountdown > maxCountdown)
{
maxCountdown = forcastCountdown;
}
pClass->m_iJumpCountdown = maxCountdown;
}
else
{
pClass->m_iJumpCountdown--;
if(pClass->m_iJumpCountdown <= 0)
{
pClass->QuadrangleOptimise(comm[0]);
if(maxMark < comm[0].mark)
{
pClass->m_iJumpCountdown = maxCountdown;
maxMark = comm[0].mark;
if(maxMark > pClass->m_dBestMark)
{
memcpy(pClass->m_piBestIndex, comm[0].index, sizeof(int) * num);
pClass->m_dBestMark = maxMark;
pClass->m_i64BestGen = pClass->m_i64GenNum;
}
}
else
{
if(CM_IMG_LOG)
{
// 保存当前屏幕图像为文件,作为日志
pClass->m_iJumpCountdown = maxCountdown;
static CS

tring fileName;
fileName.Format("%03d.bmp", pClass->m_iJumpCount);
pClass->SaveAsImage(fileName);
}
srand((UINT)time(NULL));
maxCountdown = CM_JUMP_COUNTDOWN_INIT;
pClass->m_iJumpCountdown = maxCountdown;
// 已经陷入局部最优，灾变
pClass->m_iJumpCount++;
Variant(comm[0], comm[0], ptmp, num, 20);
pClass->Mark(comm[0]);
maxMark = comm[0].mark;
for(i = 1; i < CM_SEED_NUM; i++)
{
Variant(comm[0], comm, ptmp, num, 20);
pClass->Mark(comm);
totalMark += comm.mark;
if(maxMark < comm.mark)
{
maxMark = comm.mark;
maxIndex = i;
}
}
// 移动最优基因
if(maxIndex != 0)
{
tgene.index = comm[0].index;
tgene.mark = comm[0].mark;
comm[0].index = comm[maxIndex].index;
comm[0].mark = comm[maxIndex].mark;
comm[maxIndex].index = tgene.index;
comm[maxIndex].mark = tgene.mark;
maxIndex = 0;
}
indNum = CM_SEED_NUM;
}
}
}
// 轮盘赌
totalMark -= comm[0].mark;
totalBullet = 0;
for(i = 1; i < indNum; i++)
{
comm.killRate = int(10000.0 * comm.mark / totalMark);
totalBullet += comm.killRate;
}
while(indNum > CM_SEED_NUM)
{
bullet = rand() % totalBullet;
for(i = 1; i < indNum; i++)
{
if(bullet <= comm.killRate)
{
// 命中
totalBullet -= comm.killRate;
tgene.index = comm[indNum - 1].index;
tgene.mark = comm[indNum - 1].mark;
tgene.killRate = comm[indNum - 1].killRate;
comm[indNum - 1].index = comm.index;

comm[indNum - 1].mark = comm.mark;
comm[indNum - 1].killRate = comm.killRate;
comm.index = tgene.index;
comm.mark = tgene.mark;
comm.killRate = tgene.killRate;
indNum--;
break;
}
else
{
bullet -= comm.killRate;
}
}
}
pClass->m_i64GenNum++;
tnow = CTime::GetCurrentTime();
pClass->m_tsTimeUsed = tnow - tstart;
}
// 释放空间
for(i = 0; i < commSize; i++)
{
delete [] comm.index;
comm.index = NULL;
}
delete [] comm;
comm = NULL;

tgene.index = NULL;
pClass->m_bCompute = false;

return 0; // thread completed successfully
}