TSP.rar_visual c_粒子群TSP_粒子群算法_粒子群算法 TSP_遗传算法 TSP

#include "TSPcs.h" //---------------------TestNumber----------------------------- // // checks if a given integer is already contained in a vector // of integers. //------------------------------------------------------------ bool TestNumber(const vector<int> &vec, const int &number) { for (int i=0; i<vec.size(); ++i) { if (vec[i] == number) { return true; } } return false; } int SGenome::g_nCounts=0; //////////////////////////////////////////////////////////////////////////////// //---------------------GrabPermutation---------------------- // // given an int, this function returns a vector containing // a random permutation of all the integers up to the supplied // parameter. //------------------------------------------------------------ vector<int> SGenome::GrabPermutation(int &limit) { vector<int> vecPerm; for (int i=0; i<limit; i++) { //we use limit-1 because we want ints numbered from zero int NextPossibleNumber = RandInt(0, limit-1); while(TestNumber(vecPerm, NextPossibleNumber)) { NextPossibleNumber = RandInt(0, limit-1); } vecPerm.push_back(NextPossibleNumber); } return vecPerm; } int TemplateMutate::choose(int curCity) //curCity当前走到那个城市了 { //Update the probability of path selection //select a path from tabu[m_nCityCount-1] to next int i,j=-1; double temp=0; double prob[NUM_CITIES];//概率数组 int nCout=0; double dMaxp=-1;//最大的概率 int nMaxp=-1; //先计算当前城市和没有走过的城市，两两之间的信息素的总和 for ( i=0;i<NUM_CITIES;i++) { if (m_pAllowed[i] == 1) { prob[i]=m_NormalDist[curCity][i]; if(m_bConnected[curCity][i])//是基因里的连接 { prob[i]=prob[i]*4;//概率翻倍 } temp+=prob[i]; if(prob[i]>dMaxp){ dMaxp=prob[i]; nMaxp=i; } nCout++; } } if(nCout<=0||nMaxp==-1||temp<=0) MessageBox(NULL,"计算概率出错1","",MB_OK); //计算没有走过的城市被选中的概率 /* for (i=0;i<NUM_CITIES;i++) { if (m_pAllowed[i] == 1) { prob[i]/=temp; } else { prob[i]=0; } } */ //下面的操作实际上就是遗传算法中的轮盘选择 double mRate=RandFloat()*temp; //0-1 double mSelect=0; for ( i=0;i<NUM_CITIES;i++) { if (m_pAllowed[i] == 1) { mSelect+=prob[i] ; if (mSelect>=mRate) { return i; } } } //这种情况只有在temp=0.0的时候才会出现 // if (j == -1) { MessageBox(NULL,"计算概率出错2","",MB_OK); } return j; } //选择移动方向，应用局部更新公式进行激素更新 inline void TemplateMutate::Mutate(vector<int> &chromo) { assert(NUM_CITIES==chromo.size()); //初始化基因连接距阵 memset(m_bConnected,0,sizeof(m_bConnected)); for (int j=0;j<NUM_CITIES-1;j++) //计算两两城市间的信息素 { int m=chromo[j]; int n =chromo[(j+1)]; m_bConnected[m][n]=true; m_bConnected[n][m]=true; } m_bConnected[chromo[0]][chromo[NUM_CITIES-1]]=true; m_bConnected[chromo[NUM_CITIES-1]][chromo[0]]=true; vector<int> vecTagPath; int tocity; for(int i=0;i <NUM_CITIES;i++) m_pAllowed[i]=true; int nCurCity=chromo[0]; vecTagPath.push_back(nCurCity); m_pAllowed[nCurCity]=0 ; int nCurLength=1; while(nCurLength!=NUM_CITIES) { tocity=choose(nCurCity); m_pAllowed[tocity]=false; vecTagPath.push_back(tocity); nCurCity=tocity; nCurLength++; } chromo=vecTagPath; return ; } ///////////////////////////////////////////////////////////////////////////// //-----------------------CalculatePopulationsFitness-------------------------- // // calculates the fitness of each member of the population, updates the // fittest, the worst, keeps a sum of the total fittness scores and the // average fitness score of the population (most of these stats are required // when we apply pre-selection fitness scaling. //----------------------------------------------------------------------------- void CgaControl::CalculatePopulationsFitness() { double oldRoute=m_dShortestRoute; for (int i=0; i<m_iPopSize; ++i) { double TourLength = m_pMap->GetTourLength(m_vecPopulation[i].vecCities); m_vecPopulation[i].dFitness = TourLength; if(TourLength<oldRoute) m_Split.m_nBreaks[m_vecPopulation[i].dwEvolution]++; //keep a track of the shortest route found each generation if (TourLength < m_dShortestRoute) { m_dShortestRoute = TourLength; m_vecShortestRoute=m_vecPopulation[i].vecCities; m_iFittestGenome = i; m_nShortestGen=m_vecPopulation[i].dwGeneration; } //keep a track of the worst tour each generation if (TourLength > m_dLongestRoute) { m_dLongestRoute = TourLength; } }//next chromo m_iGeneration; //Now we have calculated all the tour lengths we can assign //the fitness scores for (int i=0; i<m_iPopSize; ++i) { m_vecPopulation[i].dFitness = m_dLongestRoute - m_vecPopulation[i].dFitness; } //calculate values used in selection CalculateBestWorstAvTot(); } //-----------------------CalculateBestWorstAvTot----------------------- // // calculates the fittest and weakest genome and the average/total // fitness scores //--------------------------------------------------------------------- void CgaControl::CalculateBestWorstAvTot() { m_dTotalFitness = 0; double HighestSoFar = -9999999; double LowestSoFar = 9999999; for (int i=0; i<m_iPopSize; ++i) { //update fittest if necessary if (m_vecPopulation[i].dFitness > HighestSoFar) { HighestSoFar = m_vecPopulation[i].dFitness; m_dBestFitness = HighestSoFar; } //update worst if necessary if (m_vecPopulation[i].dFitness < LowestSoFar) { LowestSoFar = m_vecPopulation[i].dFitness; m_dWorstFitness = LowestSoFar; } m_dTotalFitness += m_vecPopulation[i].dFitness; }//next chromo m_dAverageFitness = m_dTotalFitness / m_iPopSize; //if all the fitnesses are zero the population has converged //to a grpoup of identical genomes so we should stop the run if (m_dAverageFitness == 0) { m_dSigma = 0; } } //-----------------------------FitnessScaleRank---------------------- // // This type of fitness scaling sorts the population into ascending // order of fitness and then simply assigns a fitness score based // on its position in the ladder. (so if a genome ends up last it // gets score of zero, if best then it gets a score equal to the size // of the population. //--------------------------------------------------------------------- void CgaControl::FitnessScaleRank(vector<SGenome> &pop) { //sort population into ascending order if (!m_bSorted) { sort(pop.begin(), pop.end()); m_bSorted = true; } //now assign fitness according to the genome's position on //this new fitness 'ladder' for (int i=0; i<pop.size(); i++) { pop[i].dFitness = i; } //recalculate values used in selection CalculateBestWorstAvTot(); } //----------------------------- FitnessScaleSigma ------------------------ // // Scales the fitness using sigma scaling based on the equations given // in Chapter 5 of the book. //------------------------------------------------------------------------ void CgaControl::FitnessScaleSigma(vector<SGenome> &pop) { double RunningTotal = 0; //first iterate through the population to calculate the standard //deviation for (int gen=0; gen<pop.size(); ++gen) { RunningTotal += (pop[gen].dFitness - m_dAverageFitness) * (pop[gen].dFitness - m_dAverageFitness); } double variance = RunningTotal/(double)m_iPopSize; //standard deviation is the square root of the variance m_dSigma = sqrt(variance); //now iterate through the population to reassign the fitness scores for (int gen=0; gen<pop.size(); ++gen) { double OldFitness = pop[gen].dFitness; pop[gen].dFitness = (OldFitness - m_dAverageFitness) / (2 * m_dSigma); }