tspga.txt

使用遗传算法解决TSP问题

　　{
　　 srand(time(0));
　　 std::vector<int> temp; //选择池
　　 P vProbabilityBk; //临时保存适应度
　　 vProbabilityBk = m_vProbability;
　　 temp.reserve( ((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2 );
　　 
　　 P::iterator pos;
　　 
　　 for (int i = _GENERATION_AMOUNT; i > 0; --i)
　　 {
　　 pos = std::min_element(vProbabilityBk.begin(), vProbabilityBk.end());
　　 temp.insert( temp.end(), i, (int)(pos-vProbabilityBk.begin()) );
　　 *pos = _INFINITE; 
　　 }
　　 
　　 /**************************************************************************
　　 fnDispProbability();
　　 cout << "\ttemp\n" << std::endl; //调试用
　　 copy( temp.begin(), temp.end(), std::ostream_iterator<int>(cout," ") );
　　 cout << std::endl; //调试用
　　 **************************************************************************/
　　 #define _MIN_ELEMENT std::min_element(m_vProbability.begin(), m_vProbability.end())
　　 m_GenerationGeneBk[_GENERATION_AMOUNT-1] = m_GenerationGene[_MIN_ELEMENT - m_vProbability.begin()];
　　 
　　 int iFather; //父亲的代号
　　 int iMother; //母亲的代号
　　 T Child1, Child2; //父亲与母亲杂交出的子女的基因
　　 T::iterator tempIter;
　　 int LowBoundary;
　　 int HighBoundary;
　　 //int iChild1Probability,iChild2Probability;
　　 T fatherBk,motherBk;
　　 T::iterator V_iter;
　　 P::iterator P_iter;
　　 int iDistance;
　　 srand(time(0));
　　#ifndef _ITEMP
　　#define _ITEMP rand()%(((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2)
　　#endif
　　 for (i = 0; i < _P_GENE_MIX; ++i) //杂交_P_GENE_MIX/10次
　　 {
　　 iFather = temp[_ITEMP];
　　 do
　　 {
　　 iMother = temp[_ITEMP];
　　 }while(iMother == iFather);
　　 
　　 Child1.reserve(_CITY_AMOUNT); //初始化子女的碱基数
　　 Child2.reserve(_CITY_AMOUNT);
　　 Child1.clear();
　　 Child2.clear();
　　 
　　 LowBoundary = fnRndBoundary(0, _CITY_AMOUNT-2);
　　 HighBoundary= fnRndBoundary(LowBoundary+1, _CITY_AMOUNT-1);
　　 /**********************************************************************
　　 cout << "iMother:" << iMother << std::endl;
　　 cout << "iFather:" << iFather << std::endl;
　　 cout << "LowBoundary:" << LowBoundary << std::endl;
　　 cout << "HighBoundary:" << HighBoundary << std::endl;
　　 **********************************************************************/
　　 
　　 fatherBk = m_GenerationGene[iFather];
　　 motherBk = m_GenerationGene[iMother];
　　 std::copy (fatherBk.begin()+LowBoundary, fatherBk.begin()+HighBoundary+1, 
　　 std::back_inserter(Child1));
　　 
　　 std::copy (motherBk.begin()+LowBoundary, motherBk.begin()+HighBoundary+1,
　　 std::back_inserter(Child2));
　　 /**********************************************************************
　　 cout << "Child1:" ;
　　 for (tempIter=Child1.begin(); tempIter!=Child1.end(); ++tempIter)
　　 cout << *tempIter << " ";
　　 cout << std::endl;
　　 cout << "Child2:" ;
　　 for (tempIter=Child2.begin(); tempIter!=Child2.end(); ++tempIter)
　　 cout << *tempIter << " ";
　　 cout << std::endl;
　　 **********************************************************************/
　　 std::rotate (fatherBk.begin(), fatherBk.begin()+HighBoundary+1, fatherBk.end());
　　 std::rotate (motherBk.begin(), motherBk.begin()+HighBoundary+1, motherBk.end());
　　 /**********************************************************************
　　 cout << "fatherBk:" ;
　　 copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << std::endl;
　　 cout << "motherBk:" ;
　　 copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << std::endl;
　　 **********************************************************************/
　　 for (V_iter = m_GenerationGene[iFather].begin()+LowBoundary;
　　 V_iter != m_GenerationGene[iFather].begin()+HighBoundary+1; ++V_iter)
　　 {
　　 motherBk.erase(std::remove(motherBk.begin(), motherBk.end(), *V_iter),
　　 motherBk.end());
　　 }
　　 
　　 for (V_iter = m_GenerationGene[iMother].begin()+LowBoundary;
　　 V_iter != m_GenerationGene[iMother].begin()+HighBoundary+1; ++V_iter)
　　 {
　　 
　　 fatherBk.erase(std::remove(fatherBk.begin(), fatherBk.end(), *V_iter),
　　 fatherBk.end());
　　 }
　　 /**********************************************************************
　　 cout << "fatherBk:" ;
　　 copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << std::endl;
　　 cout << "motherBk:" ;
　　 copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << std::endl;
　　 **********************************************************************/
　　 iDistance = _CITY_AMOUNT -HighBoundary - 1;
　　 std::copy(motherBk.begin(), motherBk.begin()+iDistance, std::back_inserter(Child1));
　　 std::copy(motherBk.begin()+iDistance, motherBk.end(), std::inserter(Child1,Child1.begin()));
　　 std::copy(fatherBk.begin(), fatherBk.begin()+iDistance, std::back_inserter(Child2));
　　 std::copy(fatherBk.begin()+iDistance, fatherBk.end(), std::inserter(Child2,Child2.begin()));
　　 
　　 /**********************************************************************
　　 cout << "Child1:";
　　 copy (Child1.begin(), Child1.end(), std::ostream_iterator<int>(cout, " "));
　　 
　　 cout << "iChild1Probability:" << iChild1Probability << std::endl;
　　 cout << "Child2:" ;
　　 copy (Child2.begin(), Child2.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << "iChild2Probability:" << iChild2Probability << std::endl;
　　 **********************************************************************/
　　 /*iChild1Probability = fnEvalOne(Child1);
　　 //iChild2Probability = fnEvalOne(Child2);
　　 
　　 
　　 P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
　　 if (iChild1Probability < *P_iter)
　　 {
　　 m_GenerationGene[P_iter-m_vProbability.begin()] = Child1;
　　 *P_iter = iChild1Probability;
　　 }
　　 P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
　　 if (iChild2Probability < *P_iter)
　　 {
　　 m_GenerationGene[P_iter-m_vProbability.begin()] = Child2;
　　 *P_iter = iChild2Probability;
　　 }
　　 */
　　 m_GenerationGeneBk[2*i] = Child1;
　　 m_GenerationGeneBk[2*i+1] = Child2;
　　 } 
　　 for (i = 0; i < _GENERATION_AMOUNT; ++i)
　　 {
　　 m_GenerationGene[i] = m_GenerationGeneBk[i];
　　 }
　　 
　　 
　　 return true;
　　}
　　//测试基因的适应度
　　template <typename T, typename P>
　　bool Csga<T, P>::fnEvalAll()
　　{
　　 int i, j;
　　 m_vProbability.assign( _GENERATION_AMOUNT, 0);
　　 //cout << "\t基因适应度\n";
　　 
　　 //测试每组基因的适应性
　　 for (i = 0; i < _GENERATION_AMOUNT; ++i)
　　 {
　　 for (j = 0; j < _CITY_AMOUNT-1; ++j)
　　 {
　　 m_vProbability[i] += _P(lpCityDistance, 
　　 m_GenerationGene[i][j], m_GenerationGene[i][j+1]);
　　 }//end for (j = 0; j < _CITY_AMOUNT; ++j); 
　　 m_vProbability[i] += _P(lpCityDistance, 
　　 m_GenerationGene[i][_CITY_AMOUNT-1], m_GenerationGene[i][0]);
　　 if (m_vProbability[i] < HistoryMin)
　　 {
　　 HistoryMin = m_vProbability[i];
　　 HistoryMinWay = m_GenerationGene[i];
　　 }
　　 
　　 }//end for (int j, i = 0; i < _GENERATION_AMOUNT; ++i)
　　 //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout," "));
　　 //cout << std::endl;
　　 //m_vProbability[_GENERATION_AMOUNT-1] = fnEvalOne(m_GenerationGeneBk[_GENERATION_AMOUNT-1]);
　　 return true;
　　}
　　//测试某个基因的适应度并返回适应度
　　template <typename T, typename P>
　　int Csga<T, P>::fnEvalOne(T &Gene)
　　{
　　 int iResult = 0;
　　 
　　 for (int i = 0; i < _CITY_AMOUNT-1; ++i)
　　 {
　　 iResult += _P(lpCityDistance, Gene[i], Gene[i + 1]);
　　 }
　　 
　　 return iResult;
　　}
　　template <typename T, typename P>
　　void Csga<T, P>::fnDispProbability()
　　{
　　 
　　 /*cout << "\t个体基因序列" <<std::endl; //调试用
　　 for (int i = 0; i < _GENERATION_AMOUNT; ++i)
　　 {
　　 cout << " 个体" << i+1 << "的基因:";
　　 copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
　　 std::ostream_iterator<int>(cout," ") );
　　 if (i%2 == 1)
　　 cout << std::endl;
　　 }
　　 */
　　 cout << "\t最小开销为:"; 
　　#define _VECT_TEMP std::min_element(m_vProbability.begin(), m_vProbability.end())
　　 
　　 
　　 cout << *_VECT_TEMP << std::endl;//+_GENERATION_AMOUNT
　　 
　　 //cout << "各个方案的路程分别为:" ;
　　 //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout, " "));
　　 cout << std::endl;
　　 cout << "*******************************************************" << std::endl;
　　 
　　 
　　}
　　template <typename T, typename P>
　　void Csga<T, P>::fnDispHistoryMin()
　　{
　　 cout << "历史上最短开销为:"<< HistoryMin << " 路径为:" ;
　　 std::copy (HistoryMinWay.begin(), HistoryMinWay.end(), std::ostream_iterator<int>(cout, " ->"));
　　 cout << *HistoryMinWay.begin();
　　 cout <<std::endl;
　　}