• PUDN用户
    了解作者
  • Visual C++
    开发工具
  • 19KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 58
    下载次数
  • 2010-04-13 21:09
    上传日期
使用蚁群算法编写的C++环境下的旅行商(TSP)经典问题的解决方法
TSP.zip
  • StdAfx.h
    1.2KB
  • TSP_AS.CPP
    5KB
  • TSP_ACS.CPP
    5.2KB
  • TSP_Generic.cpp
    2.6KB
  • TSP_Ant.h
    1.3KB
  • TSP.cpp
    1.2KB
  • TSP_data.cpp
    2.7KB
  • TSP_node.cpp
    1011B
  • TSP_node.h
    887B
  • TSP_ACS.H
    1.9KB
  • TSP_MMAS.H
    1.9KB
  • Resource.h
    495B
  • TSP_Ant.cpp
    11KB
  • TSP_AS.H
    1.7KB
  • TSP_MMAS.CPP
    5.7KB
  • TSP.h
    315B
  • StdAfx.cpp
    290B
  • TSP_Generic.h
    1KB
  • TSP_DATA.H
    1.1KB
内容介绍
/////////////////////////////////////////////////////////// // This virsion is AntSystem 1.0 // author: zhaochaoqing ChongQing University // //the author can be contacted at: // Email: zh_iostream@126.com // //////////////////////////////////////////////////////////// // // TSP_Ant.h :interface for TPS_Ant class //////////////////////////////////////////////////////////// #include"stdafx.h" #include "TSP.h" #include "TSP_Ant.h" #include "TSP_node.h" #include"TSP_ACS.h" #include"TSP_MMAS.h" #include "TSP_Generic.h" #include "TSP_AS.h" #ifdef _DEBUG #undef THIS_FILE static char THIS_FILE[]=__FILE__; #define new DEBUG_NEW #endif TSP_Ant::TSP_Ant(/*int nID, */int nHomeID) { // m_nID = nID; m_nHomeID = nHomeID; m_nTourLength = 0; } TSP_Ant::TSP_Ant(const TSP_Ant & ant) //拷贝构造 { // m_nID = ant.nID; m_nHomeID = ant.m_nHomeID; m_nTourLength = ant.m_nTourLength; // copy the tour? //TDO : necessary? } CList<int, int>* TSP_Ant::GetTour() { return & m_lTour; } TSP_Ant::~TSP_Ant() { m_lTour.RemoveAll(); } const TSP_Ant & TSP_Ant::operator=(const TSP_Ant & ant) { // m_nID = ant.nID; m_nHomeID = ant.m_nHomeID; m_nTourLength = ant.m_nTourLength; // copy the tour? //TDO : necessary? return *this; } void TSP_Ant::SetHome(int nHome) { m_nHomeID = nHome; } void TSP_Ant::GlobalUpdate(TSP_AS *pAS) { POSITION pos = m_lTour.GetHeadPosition(); int nodei = m_lTour.GetNext(pos); int nodefirst = nodei, nodej; while (pos != NULL) { nodej = m_lTour.GetNext(pos); // global pheromone update rule pAS->SetTauAt(nodei, nodej, pAS->GetTauAt(nodei, nodej) + pAS->GetQ()/m_nTourLength); // symmetric case pAS->SetTauAt(nodej, nodei, pAS->GetTauAt(nodei, nodej)); nodei = nodej; } // last to first尾结点接首结点; pAS->SetTauAt(nodej, nodefirst, pAS->GetTauAt(nodej, nodefirst) + pAS->GetQ()/m_nTourLength); // symmetric case pAS->SetTauAt(nodefirst, nodej, pAS->GetTauAt(nodej, nodefirst)); } double TSP_Ant::BuildTour(TSP_AS *pAS) { // reset tour info m_lTour.RemoveAll(); m_nTourLength = 0; // add home city first m_lTour.AddTail(m_nHomeID); int i = m_nHomeID; int j = -1; POSITION posJ = NULL; // create a tabu list storing cities not yet visited CList<int, int> lToVisit; int node = -1; for (int city=0; city < pAS->GetDim(); city++) { if (city != m_nHomeID) { lToVisit.AddTail(city); } } while (!lToVisit.IsEmpty()) { // find the sum over all remaining nodes double dSum = 0; POSITION pos = NULL; int u = 0; pos = lToVisit.GetHeadPosition(); while (pos != NULL) { u = lToVisit.GetNext(pos); dSum += pow(pAS->GetTauAt(i, u), (double)pAS->GetAlpha()) * pow(pAS->GetVisAt(i, u),(double)pAS->GetBeta()); } // probability matrix int nVisitSize = lToVisit.GetCount(); double* aProbs = new double[nVisitSize]; // calculate accumulated probabilities pos = lToVisit.GetHeadPosition(); int nIdx = 0; double dCurSum = 0.0; while (pos != NULL) { u = lToVisit.GetNext(pos); //返回的是连标中pos所指的元素并将pos指向下一个元素, //调用GetNext后pos的值就改变了 double dRatio = (pow(pAS->GetTauAt(i, u),(double)pAS->GetAlpha()) * pow(pAS->GetVisAt(i, u),(double)pAS->GetBeta())) / dSum; dCurSum += dRatio; aProbs[nIdx] = dCurSum; nIdx++; } double dProb = rand() / (RAND_MAX+1.0); for (nIdx = 0; nIdx < nVisitSize; nIdx++) { // go from the back since the probs are larger there // stop if we have low enough double dMyProb = aProbs[nIdx]; if (dProb <= (dMyProb+0.00001)) { posJ = lToVisit.FindIndex(nIdx); // we want the last one that was above j = lToVisit.GetAt(posJ); break; } } if ((j==i) || (j==-1)) // means take the largest { posJ = lToVisit.FindIndex(nVisitSize-1); // we want the last one that was above j = lToVisit.GetAt(posJ); } // now we add the new node to the tour and remove from unvisited list m_lTour.AddTail(lToVisit.GetAt(posJ)); lToVisit.RemoveAt(posJ); i = j; // cleanup delete[] aProbs; } // we finished calculating the tour, now find its length POSITION pos = m_lTour.GetHeadPosition(); int nodei = m_lTour.GetNext(pos); int nodefirst = nodei; int nodej = -1; while (pos != NULL) { nodej = m_lTour.GetNext(pos); m_nTourLength += pAS->GetDistAt(nodei, nodej); nodei = nodej; } // last to first; m_nTourLength += pAS->GetDistAt(nodej, nodefirst); return m_nTourLength; } double TSP_Ant::BuildTour(TSP_ACS * pACS) { // first try - no candidate lists // reset tour info m_lTour.RemoveAll(); m_nTourLength = 0.0; // add home city first m_lTour.AddTail(m_nHomeID); int i = m_nHomeID; int j = -1; POSITION posJ = NULL; // create a tabu list storing cities not yet visited CList<int, int> lToVisit; int node = -1; for (int city=0; city<pACS->GetDim(); city++) { if (city != m_nHomeID) { lToVisit.AddTail(city); } } while (!lToVisit.IsEmpty()) { // Choose which formula to follow double dQ = (rand() % 101) / 100.0; if (dQ <= pACS->GetQ0()) { double dMax = -1.0; int nMaxCity = -1; POSITION posMaxCity = NULL; POSITION pos = lToVisit.GetHeadPosition();// 返回的是链表头元素的位置 POSITION posPrev = pos; int u = 0; double dArg = 0.0; while (pos != NULL) { u = lToVisit.GetNext(pos);//返回的是连标中pos所指的元素并将pos指向下一个元素 // 调用GetNext后pos的值就改变了 dArg = pACS->GetTauAt(i, u) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta()); if (dArg > dMax) { dMax = dArg; nMaxCity = u; posMaxCity = posPrev; } posPrev = pos; } // we now know the next city to visit j = nMaxCity; posJ = posMaxCity; } else { // find the sum over all remaining nodes double dSum = 0; POSITION pos = NULL; int u = 0; pos = lToVisit.GetHeadPosition(); while (pos != NULL) { u = lToVisit.GetNext(pos); dSum += pow(pACS->GetTauAt(i, u),(double)pACS->GetAlpha()) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta()); } // probability matrix // CArray<double,double> aProbs; // aProbs.SetSize(lToVisit.GetCount()); int nVisitSize = lToVisit.GetCount(); double* aProbs = new double[nVisitSize]; // calculate accumulated probabilities pos = lToVisit.GetHeadPosition(); int nIdx = 0; double dCurSum = 0.0; while (pos != NULL) { u = lToVisit.GetNext(pos); double dRatio = (pow(pACS->GetTauAt(i, u),(double)pACS->GetAlpha ()) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta()))/dSum; dCurSum += dRatio; // aProbs.SetAt(nIdx, dCurSum); aProbs[nIdx] = dCurSum; nIdx++; } // find the desired next node double dProb = rand() / (RAND_MAX+1.0); // for (nIdx = 0; nIdx < aProbs.GetSize(); nIdx++) for (nIdx = 0; nIdx < nVisitSize; nIdx++) { // double dMyProb = aProbs.GetAt(nIdx); double dMyProb = aProbs[nIdx]+0.000001; if (dProb <= dMyProb) { posJ = lToVisit.FindIndex(nIdx); // we want the last one that was above j = lToVisit.GetAt(posJ); break; } } if ((j==i) || (j==-1)) // means take the largest { posJ = lToVisit.FindIndex(nVisitSize-1); // we want the last one that was above j = lToVisit.GetAt(posJ); } delete[] aProbs; } // now we add the new node to the tour m_lTour.AddTail(lToVisit.GetAt(posJ)); lToVisit.RemoveAt(posJ); //remove from unvisited list // do local update of pheremones pACS->SetTauAt(i, j, (1 - pACS->GetRho()) * pACS->GetTauAt(i,j) + pACS->GetRho() * pACS->GetTau0()); // symmetric case // if (pACS->
评论
    相关推荐