求TSP问题通用蚁群算法 C++

  • Y3_769254
    了解作者
  • 4.2MB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-26 11:33
    上传日期
自编蚁群算法 用与求解TSP问题 用vc2003打开
求TSP问题通用蚁群算法 C++.rar
内容介绍
#include<afxwin.h rel='nofollow' onclick='return false;'> #include"resource.h" #include "1.h" #include <iostream> #include <fstream> #include <math.h> #include <time.h> ;using namespace std; class MyFrame : public CFrameWnd { private: CMenu *FMenu; public: MyFrame() { Create(NULL,"aco"); FMenu = new CMenu; FMenu ->LoadMenu(IDR_MENU1); SetMenu(FMenu); } ~MyFrame() {delete FMenu;} afx_msg void OnExit() { MessageBox("EXIT"); DestroyWindow(); } afx_msg void OnOpen() { ifstream wenjian; wenjian.open("eil51.tsp"); struct city { int num; int x; int y; }cc[51]; CClientDC aDC(this); CString str; for (int i=0;i<51;i++) { wenjian>>cc[i].num>>cc[i].x>>cc[i].y; str.Format("%d",cc[i].num); aDC.TextOut(40*cc[i].x,40*cc[i].y,str); } map1.inputfile(); map1.initialmap(); map1.startsearch(); aDC.MoveTo(40*cc[besttour[0]].x,40*cc[besttour[0]].y); for (int t=1;t<51;t++) { aDC.LineTo(40*cc[besttour[t]].x,40*cc[besttour[t]].y); } str.Format("%f",shortestlength); str="shortestlength="+str; aDC.TextOut(0,0,str); } DECLARE_MESSAGE_MAP() }; BEGIN_MESSAGE_MAP(MyFrame,CFrameWnd) ON_COMMAND(ID_EXIT,OnExit) ON_COMMAND(ID_OPEN,OnOpen) END_MESSAGE_MAP() class MyApp : public CWinApp { public: BOOL InitInstance() { CFrameWnd *Frame = new MyFrame; m_pMainWnd = Frame; Frame->ShowWindow(SW_SHOW); return true; } }; MyApp a_app; void map::inputfile() { ifstream wenjian; wenjian.open("eil51.tsp"); for (int i=0;i<iCityCount;i++) { wenjian>>city[i][0]>>city[i][1]>>city[i][2]; } printf("inputfile()"); for(int t=0;t<iCityCount;t++) //printf(" %d ",city[t][2]); int j; for (int i=0;i<iCityCount;i++) { for( j=i+1; j<iCityCount; j++) { xinxisu[i][j]= xinxisu[j][i]=1; distance[i][j]=(sqrt( pow(city[i][1]-city[j][1],2 ) +pow(city[i][2]-city[j][2], 2) ) +0.5 ); distance[j][i]=distance[i][j]; //cout<< (city[i][1]-city[j][1])*(city[i][1]-city[j][1])<<endl; //cout<<(city[i][2]-city[j][2])*(city[i][2]-city[j][2]) <<endl; //cout<<((city[i][1]-city[j][1])*(city[i][1]-city[j][1])+(city[i][2]-city[j][2])*(city[i][2]-city[j][2])+5)<<endl; } distance[i][i]=0.5; xinxisu[i][i]=0.001; } //cout<<"initialmap()"; //for(int t=0;t<iCityCount;t++) //cout<<distance[3][t]<<endl; } void map::initialmap() { } void map::antsearch() { ant ant1; ant1.initial(); ant1.run(); if (ant1.length<shortestlength) {for(int t=0;t<iCityCount;t++) { besttour[t]=ant1.visited[t]; //cout<<besttour[t]<<" "<<ant1.visited[t]<<endl; } shortestlength=ant1.length; // cout<<"shortestlength"<<shortestlength<<endl; } } void map::startsearch() { for(int count=1 ;count<iItCount;count++) antsearch(); } /*void map::dispalyresult() { //printf("The shortest toure is :"); for(int t=0;t<iCityCount;t++) // printf(" %d ",besttour[t]); ofstream wenjian2; wenjian2.open("eil.tsp"); for (int i=0;i<iCityCount;i++) { wenjian2<<besttour[i]; } wenjian2<<shortestlength; } */ void ant::initial() { for (int i=0;i<iCityCount;i++) { visitsign[i]=1; visited[i]=0; } length=0; i=rand()%iCityCount; visited[0]=i; visitsign[i]=0; for (int i=0;i<iCityCount;i++) { for (int j=0;j<iCityCount;j++) {distance[i][j]=map1.distance[i][j]; xinxisu[i][j]=map1.xinxisu[i][j]; // cout<<xinxisu[i][j]<<distance[i][j]<<endl; } for (int j=0;j<3;j++) { city[i][1]=map1.city[i][j]; //printf(" %d ",city[i][j]); } } //cout<<"length="<<length<<"i="<<i<<"visited[0]="<<i<<"visitsign[i]="<<0<<endl; } void ant::run() { int citynum; for( int visitednum=1; visitednum<iCityCount;visitednum++) { //cout<<"visited[visitednum-1]"<<visited[visitednum-1]; citynum=choosenext(visited[visitednum-1]); //cout<<"choosenext"<<citynum; visited[visitednum]=citynum; visitsign[citynum]=0; length+=distance[visited[visitednum-1]][citynum]; } //cout<<endl; //cout<< "length"<<length<<endl; updatepath(); } int ant::choosenext(int city1) { double prob1[3]; prob1[0]=0; prob1[1]=0; prob1[2]=0; int probcity[3]; double prob[iCityCount]; for(int i=0;i<iCityCount;i++) { if(visitsign[i]) { prob[i]=probability(city1,i); //cout<<i<<"prob[i]"<<prob[i]<<endl; if( prob[i] rel='nofollow' onclick='return false;'>prob1[0]) { prob1[0]=prob[i]; probcity[0]=i; } else if (prob[i]>prob1[1]) { probcity[1]=i; prob1[1]=prob[i]; } else if (prob[i]>prob1[2]) { prob1[2]=prob[i]; probcity[2]=i; } } } if(prob1[1]==0||prob1[2]==0) return probcity[0]; else {int j; j=rand()%7; if(j<5) return probcity[0]; if(j=5) return probcity[1]; if(j=6) return probcity[2]; } // return probcity[0]; } double ant::probability(int city1,int city2) { return pow((1.0/distance[city1][city2]),beta)*pow((xinxisu[city1][city2]),alpha); } void ant::updatepath() { for(int i=0;i<iCityCount-1;i++) { int i1,j1; i1=visited[i]; j1=visited[i+1]; double xinxi; xinxi=rou* xinxisu[i1][j1]; xinxisu[i1][j1]=xinxi+Q/length; // xinxisu[i1][j1]+=Q/length; map1.xinxisu[i1][j1]=xinxisu[i1][j1]; //cout<< "xinxisu[i1][j1]"<<xinxisu[i1][j1]<<" "<<map1.xinxisu[i1][j1]<<endl; } }
评论
    相关推荐