用遗传算法解决旅行商问题.txt

旅行商问题

　　　　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[i].mark;
　　　　　　for(j = 0; j < CM_CHILDREN_NUM; j++)
　　　　　　{
　　　　　　　　Variant(comm[i], 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 CString 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[i], ptmp, num, 20);
　　　　　　　　　　　　pClass->Mark(comm[i]);
　　　　　　　　　　　　totalMark += comm[i].mark;
　　　　　　　　　　　　if(maxMark < comm[i].mark)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　maxMark = comm[i].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[i].killRate = int(10000.0 * comm[i].mark / totalMark);
　　　　　　totalBullet += comm[i].killRate;
　　　　}
　　　　while(indNum > CM_SEED_NUM)
　　　　{
　　　　　　bullet = rand() % totalBullet;
　　　　　　for(i = 1; i < indNum; i++)
　　　　　　{
　　　　　　　　if(bullet <= comm[i].killRate)
　　　　　　　　{
　　　　　　　　　　// 命中
　　　　　　　　　　totalBullet -= comm[i].killRate;
　　　　　　　　　　tgene.index = comm[indNum - 1].index;
　　　　　　　　　　tgene.mark = comm[indNum - 1].mark;
　　　　　　　　　　tgene.killRate = comm[indNum - 1].killRate;
　　　　　　　　　　comm[indNum - 1].index = comm[i].index;
　　　　　　　　　　comm[indNum - 1].mark = comm[i].mark;
　　　　　　　　　　comm[indNum - 1].killRate = comm[i].killRate;
　　　　　　　　　　comm[i].index = tgene.index;
　　　　　　　　　　comm[i].mark = tgene.mark;
　　　　　　　　　　comm[i].killRate = tgene.killRate;
　　　　　　　　　　indNum--;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　bullet -= comm[i].killRate;
　　　　　　　　}
　　　　　　}
　　　　}
　　　　pClass->m_i64GenNum++;
　　　　tnow = CTime::GetCurrentTime();
　　　　pClass->m_tsTimeUsed = tnow - tstart;
　　}
　　// 释放空间
　　for(i = 0; i < commSize; i++)
　　{
　　　　delete [] comm[i].index;
　　　　comm[i].index = NULL;
　　}
　　delete [] comm;
　　comm = NULL;

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

　　return 0;   // thread completed successfully
}