展会信息港展会大全

请问哪一位高手有蚁群算法解决vrptw的程序代码?谢谢了!论文急
来源:互联网   发布日期:2011-10-01 19:46:43   浏览:11044次  

导读:请问哪一位高手有蚁群算法解决vrptw的程序代码?谢谢了!论文急需。。。。。...

请问哪一位高手有蚁群算法解决vrptw的程序代码?谢谢了!论文急

  • 好伟大的中国人 | 2009-06-02 17:01:44
  • //基本蚁群算法程序

    //程序在vc++6.0下面同过,对原来的做了一点修改。
    //你可以使用本代码,如果感到对你有用的话,请通知作者,作者会很高兴。
    //通讯地址:fashionxu@163.com
    //by FashionXu
    #include "stdafx.h"
    #include
    #include
    #include
    #include

    using namespace std;


    const int iAntCount=34;//蚂蚁数量
    const int iCityCount=51;//城市数量
    const int iItCount=2000;//最大跌代次数
    const double Q=100;
    const double alpha=1;
    const double beta=5;
    const double rou=0.5;

    int besttour[iCityCount];//最有路径列表

    double  rnd(int low,double uper)//获得随机数
    {

    double p=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);

    return (p);

    };


    int rnd(int uper)
    {
            return (rand()%uper);
    };

    class GInfo//tsp地图信息,包含了信息素,城市距离,和信息素变化矩阵
    {


    public:
    double m_dDeltTrial[iCityCount][iCityCount];
    double m_dTrial[iCityCount][iCityCount];
    double distance[iCityCount][iCityCount];


    };


    GInfo Map;


    class ant
    {


    private:


    int ChooseNextCity();//选择城市
    double prob[iCityCount];
    int m_iCityCount;
    int AllowedCity[iCityCount];//没有走过的城市


    public:


    void addcity(int city);
    int tabu[iCityCount];
    void Clear();
    void UpdateResult();
    double m_dLength;
    double m_dShortest;
    void move();
    ant();
    void move2last();


    };
    void ant::move2last()
    {


    int i;
    for(i=0;i《iCityCount;i++)

    if (AllowedCity[i]==1)
    {
     addcity(i);
     break;
    }


    }


    void ant::Clear()
    {
    m_dLength=0;
    int i;
    for(i=0; i〈iCityCount;i++)

    prob[i]=0;
    AllowedCity[i]=1;
    }
    i=tabu[iCityCount-1];
    m_iCityCount=0;
    addcity(i);
    }
    ant::ant()
    {
    m_dLength=m_dShortest=0;
    m_iCityCount=0;
    int i;
    for(i=0;i〈iCityCount;i++)

    AllowedCity[i]=1;
    prob[i]=0;
    }
    }
    void ant::addcity(int city)
    {
    //add city to tabu;
    tabu[m_iCityCount]=city;
    m_iCityCount++;
    AllowedCity[city]=0;
    }
    int ant::ChooseNextCity()
    {
    //Update the probability of path selection
    //select a path from tabu[m_iCityCount-1] to next


    int i;
    int j=10000;
    double temp=0;
    int curCity=tabu[m_iCityCount-1];
    for (i=0;i〈iCityCount;i++)

    if((AllowedCity[i]==1))
    {
     temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
    }
    }
    double sel=0;
    for (i=0;i〈iCityCount;i++)

    if((AllowedCity[i]==1))
    {
     prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp;
     sel+=prob[i];
    }
    else
     prob[i]=0;
    }
    double mRate=rnd(0,sel);
    double mSelect=0;

    for ( i=0;i〈iCityCount;i++)

    if((AllowedCity[i]==1))
     mSelect+=prob[i] ;
    if (mSelect>=mRate) {j=i;break;}
    }

    if (j==10000)
    {
    temp=-1;
    for (i=0;i〈iCityCount;i++)

     if((AllowedCity[i]==1))
      if (temp    {
       temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
       j=i;
      }
    }
    }

    return j;

    }
    void ant::UpdateResult()
    {
    // Update the length of tour
    int i;
    for(i=0;i〈iCityCount-1;i++)

         m_dLength+=Map.distance[tabu[i]][tabu[i+1]];
    m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]];
    }
    void ant::move()
    {
    //the ant move to next town and add town ID to tabu.
    int j;
    j=ChooseNextCity();
    addcity(j);
    }
    class project
    {
    public:

    void UpdateTrial();
    double m_dLength;
    void initmap();
    ant ants[iAntCount];
    void GetAnt();
    void StartSearch();
    project();
    };
    void project::UpdateTrial()
    {
    //calculate the changes of trial information
    int i;
    int j;

    for(i=0;i〈iAntCount;i++)
    for (j=0;j〈iCityCount-1;j++)

    {   Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength ;
     Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength;
    }
    Map.m_dDeltTrial[ants[i].tabu[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength;
    Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength;
    }
    for (i=0;i〈iCityCount;i++)

    for (j=0;j〈iCityCount;j++)

    {
     Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] );
     Map.m_dDeltTrial[i][j]=0;
    }

    }


    }
    void project::initmap()
    {
    int i;
    int j;
    for(i=0;i〈iCityCount;i++)
    for (j=0;j〈iCityCount;j++)
    {


     Map.m_dTrial[i][j]=1;
     Map.m_dDeltTrial[i][j]=0;
    }
    }
    project::project()
    {
    //initial map,read map infomation from file . et.
    initmap();
    m_dLength=10e9;


    ifstream in("eil51.tsp");

    struct city
    {
    int num;
    int x;
    int  y;
    }cc[iCityCount];

    for (int i=0;i〈iCityCount;i++)
    {
    in>>cc[i].num>>cc[i].x>>cc[i].y;
    besttour[i]=0;
    }
    int j;
    for(i=0;i〈iCityCount;i++)
    for (j=0;j〈iCityCount;j++)
    {

     {
      Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));
     }
    }


    }
    void project::GetAnt()
    {
    //randomly put ant into map
    int i=0;
    int city;
    srand( (unsigned)time( NULL ) +rand());
    for (i=0;i〈iAntCount;i++)

    {
    city=rnd(iCityCount);
    ants[i].addcity(city);
    }

    }
    void project::StartSearch()
    {
    //begin to find best solution
    int max=0;//every ant tours times
    int i;
    int j;
    double temp;
    int temptour[iCityCount];
    while ((max〈iItCount)

    {  
    for(j=0;j〈iAntCount;j++)

    {
     for (i=0;i〈iCityCount-1;i++)

    ants[j].move();
    }

     for(j=0;j〈iAntCount;j++)
    {   ants[j].move2last();
     ants[j].UpdateResult ();
    }

    //find out the best solution of the step and put it into temp
    int t;
    temp=ants[0].m_dLength;
    for (t=0;t〈iCityCount;t++)
     temptour[t]=ants[0].tabu[t];
    for(j=0;j〈iAntCount;j++)
    {
     if (temp〉ants[j].m_dLength) {
      temp=ants[j].m_dLength;
      for ( t=0;t〈iCityCount;t++)
       temptour[t]=ants[j].tabu[t];
     }
    }

    if(temp〈m_dLength){
     m_dLength=temp;
     for ( t=0;t〈iCityCount;t++)
      besttour[t]=temptour[t];
    }
    printf("%d : %f\n",max,m_dLength);
    UpdateTrial();

    for(j=0;j〈iAntCount;j++)
     ants[j].Clear();



    max++;

    }
    printf("The shortest toure is : %f\n",m_dLength);

    for ( int t=0;t〈iCityCount;t++)
    printf(" %d ",besttour[t]);

    }
    int main()
    {

    project TSP;
    TSP.GetAnt();
    TSP.StartSearch();
    return 0;
    }

    求eil51最优到了438,可以修改循环次数和其他参数。以得到更好的解。使用TSP数据的时候,将前面的一些字符串信息删除,只留下坐标数据。
  • 赞助本站

    相关热词: keywords String

    AiLab云推荐
    推荐内容
    展开

    热门栏目HotCates

    Copyright © 2010-2024 AiLab Team. 人工智能实验室 版权所有    关于我们 | 联系我们 | 广告服务 | 公司动态 | 免责声明 | 隐私条款 | 工作机会 | 展会港