人工智能TSP中国旅行家问题求解.docx
- 文档编号:18493957
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:11
- 大小:110.11KB
人工智能TSP中国旅行家问题求解.docx
《人工智能TSP中国旅行家问题求解.docx》由会员分享,可在线阅读,更多相关《人工智能TSP中国旅行家问题求解.docx(11页珍藏版)》请在冰点文库上搜索。
人工智能TSP中国旅行家问题求解
《人工智能导论》实验报告之一
基于TSP遗传算法的旅行家问题求解
专业班级:
姓名:
学号:
电子信箱:
手机号码:
提交日期:
2012-05-31
指导老师:
实验成绩:
一、实验目的:
旅行商问题是一个经典的优化组合问题,它可以扩展到很多问题,如电路布线、输油管路铺设等,但是,由于TSP问题的可行解数目与城市数目N是成指数型增长的,是一个NP难问题,因而一般只能近似求解,遗传算法(GA)是求解该问题的较有效的方法之一,当然还有如粒子群算法,蚁群算法,神经网络算法等优化算法也可以进行求解。
遗传算法是美国学者Holland根据自然界“物竞天择,适者生存”现象而提出的一种随机搜索算法,本文采用C/C++语言来实现遗传算法解决TSP问题
二、实验内容:
旅行商问题可以具体描述为:
已知n个城市之间的相互距离,现有一个推销员从某一个城市出发,必须遍访这n个城市,并且每个城市只能访问一次,最后又必须返回到出发城市,如何安排他对这些城市的访问次序,可使其旅行路线的总长度最短。
用图论术语来表示,就是有一个图g=(v,e),其中v是定点5,e是边集,设d=(dij)是有顶点i和顶点j之间的距离所组成的距离矩阵,旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离的回路。
若对与城市v={v1,v2,v3…vn}的一个访问顺序为t=(t1,t2,t3…,tn),其中ti∈v(i=1,2,..n),且记tn+1=t1,则旅行上问题的数学模型为式1:
(1)
三、实验环境:
软件环境:
WindowsXP,MicrosoftVisualStudioC++6.0,Notepad
硬件环境:
PC机,2.0GHZ主频,2G内存
四、算法流程
4.1遗传算法
遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题,它需要对算法所产生的每个染色体进行评价,并基于适应度值来选择染色体,使适应性好的染色体有更多的繁殖机会,在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始种群;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作,经过遗产操作后的个体集合形成下一代新的种群,对这个新的种群进行下一轮的进化。
4.2遗传算法的过程
1.初始化群体。
2.计算群体上每个个体的适应度值
3.由个体适应度值所决定的某个规则选择将进入下一代个体。
4.按概率Pc进行交叉操作。
5.按概率Pm进行变异操作。
6.没有满足某种停止条件,则转第2步,否则进入第7步。
7.输出种群中适应度值最优的染色体作为问题的满意解或最优界。
停止条件有两种:
一是完成了预先给定的进化代数则停止;二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。
图1:
遗传算法过程框图
五、关键源码:
//ChinaDlg.cpp中部分代码:
//China45Dlg.cpp:
implementationfile//CChina45DlgdialogCChina45Dlg:
:
CChina45Dlg(CWnd*pParent/*=NULL*/):
CDialog(CChina45Dlg:
:
IDD,pParent){//{{AFX_DATA_INIT(CChina45Dlg)m_GALen=45;m_nGroupSize=100;m_GACrossProb=0.6;m_GAVariProb=0.03;m_GANum=100;m_CurGANum=0;m_MiniCost=0.0;m_CrossNum=0;m_VariNum=0;m_GAFitness=0.0;//}}AFX_DATA_INIT//NotethatLoadIcondoesnotrequireasubsequentDestroyIconinWin32m_hIcon=AfxGetApp()->LoadIcon(IDR_MAINFRAME);m_bIsGA=false;for(inti=0;i : OnPaint(){if(IsIconic()){CPaintDCdc(this);//devicecontextforpaintingSendMessage(WM_ICONERASEBKGND,(WPARAM)dc.GetSafeHdc(),0);//CentericoninclientrectangleintcxIcon=GetSystemMetrics(SM_CXICON);intcyIcon=GetSystemMetrics(SM_CYICON);CRectrect;GetClientRect(&rect);intx=(rect.Width()-cxIcon+1)/2;inty=(rect.Height()-cyIcon+1)/2;//Drawtheicondc.DrawIcon(x,y,m_hIcon);}else{if(! m_bIsGA){CPenPen;CDC*pDC=GetDC();CRectRectClient,Workarea;GetClientRect(RectClient);Workarea.left=RectClient.left+140;Workarea.bottom=RectClient.bottom-30;Workarea.right=Workarea.left+290;Workarea.top=Workarea.bottom-270;pDC->Rectangle(Workarea);pDC->SetBkColor(0x00FFFFFF);intpx=Workarea.left;intpy=Workarea.bottom+20;pDC->SetTextColor(0x00F08080);for(inti=0;i : OnPaint();}}//产生随机整数intCChina45Dlg: : RandomInt(intlow,inthigh){intresult;result=rand();returnresult%(high-low+1)+low;}//屏幕显示函数voidCChina45Dlg: : DrawNetwork(){CPenPen;CDC*pDC=GetDC();CRectRectClient,Workarea;GetClientRect(RectClient);Workarea.left=RectClient.left+140;Workarea.bottom=RectClient.bottom-30;Workarea.right=Workarea.left+290;Workarea.top=Workarea.bottom-270;pDC->Rectangle(Workarea);pDC->SetBkColor(0x00FFFFFF);intpx=Workarea.left;intpy=Workarea.bottom+20;pDC->SetTextColor(0x00F08080);for(inti=0;i : ExecGA(intk,PopNode*pop){doubleTotalF=0;//取得基因算法所需参数UpdateData(TRUE);//根据群体规模和交叉概率计算出交叉个体个数m_CrossNum=(int)m_nGroupSize*m_GACrossProb/2;m_VariNum=(int)m_nGroupSize*m_GAVariProb;PopNode*oldpop,*newpop;oldpop=newPopNode[m_nGroupSize];newpop=newPopNode[m_nGroupSize+m_CrossNum*2+m_VariNum];//已进行过基因算法标志m_bIsGA=true;if(m_nGroupSize ",MB_OK|MB_ICONINFORMATION,NULL);return;}if(k<=100){//形成初始基因序列for(inti=0;i =r2)oldpop[i].Varite(r1,r2);}}elsefor(inti=0;i =maxpos)oldpop[i].SwapNode(&oldpop[maxpos]);}m_CurGANum=gen;//查找当前一代中的最小费用个体m_MiniCost=oldpop[0].cost;m_pop.CopyNode(&oldpop[0]);m_GAFitness=m_pop.fit;//AfxMessageBox("显示数据");UpdateData(false);UpdateWindow();//绘制图形DrawNetwork();//继承所有父代基因for(i=0;i =maxpos)newpop[i].SwapNode(&newpop[maxpos]);}//产生新一代群体for(i=0;i //PopNode.cpp //PopNode.cpp: implementationofthePopNodeclass. //Construction/Destruction PopNode: : PopNode(): cost(MAXCOST),fit(0) { chrom=newint[MAXCHROM]; path=newint[MAXCHROM]; for(inti=0;i } PopNode: : ~PopNode() { deletechrom;deletepath; } //交换两条基因 voidPopNode: : SwapNode(PopNode*pop) { PopNodetemp; temp.CopyNode(this);CopyNode(pop); pop->CopyNode(&temp); } //交叉两条基因 voidPopNode: : CrossTwo(PopNode*pop,intnPos) { inttmpPath[MAXCHROM]; for(inti=1;i inttemp=chrom[i]; chrom[i]=pop->chrom[i];pop->chrom[i]=temp; } tmpPath[0]=0;for(i=1;i //重新整理pop基因城市位置和路径关系 for(i=1;i { //取得第i城市在路径中位置 intm=pop->chrom[i]; //临时路径置入当前城市i while(tmpPath[m]! =MAXCHROM) { m=(m+1)%MAXCHROM;if(m==0)m=1; } tmpPath[m]=i; } for(i=1;i { pop->path[i]=tmpPath[i];pop->chrom[tmpPath[i]]=i; } //重新整理this基因城市位置和路径关系 tmpPath[0]=0;for(i=1;i for(i=1;i { //取得第i城市在路径中位置 intm=chrom[i]; //临时路径置入当前城市i while(tmpPath[m]! =MAXCHROM) { m=(m+1)%MAXCHROM;if(m==0)m=1; } tmpPath[m]=i; } for(i=1;i { path[i]=tmpPath[i];chrom[tmpPath[i]]=i; } } //变异操作定义 voidPopNode: : Varite(intnPos1,intnPos2) { inttemp=path[chrom[nPos1]]; path[chrom[nPos1]]=path[chrom[nPos2]]; path[chrom[nPos2]]=temp; temp=chrom[nPos1]; chrom[nPos1]=chrom[nPos2]; chrom[nPos2]=temp; } //计算代价 doublePopNode: : CalcCost(double*distance) { cost=0; for(inti=0;i cost+=distance[path[i]*MAXCHROM+path[i+1]]; cost+=distance[path[MAXCHROM-1]*MAXCHROM+path[0]]; returncost; } //复制对象 voidPopNode: : CopyNode(PopNode*pop) { for(inti=0;i { chrom[i]=pop->chrom[i];path[i]=pop->path[i]; } cost=pop->cost;fit=pop->fit; } 六、屏幕截图: 设置不同的参数获得的不同的结果图: 七、结果分析: 根据实验结果进行了分析,遗传算法是一种智能优化算法,它的实现有些关键点,一是串的编码方式,本质就是问题编码,串长度及编码形式对算法收敛影响极大;二是适应函数的确定,这是选择的基础;三是自身参数的设定,其中重要的是群体大小,最大迭代次数,交叉概率和变异概率,通过实验我们可以看到最大迭代次数对问题求解的精度有影响,交叉概率和变异概率的设定对问题的收敛速度和求解精度都有极大的影响,目前很多研究都是根据具体的领域问题,改进交叉算子,变异算子,寻找最优的参数设定来提高算法收敛速度和保证最优解的得到,对算子的改进和参数值的设定这是将来的研究工作。 八、参考网页及文献: 参考网页:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 TSP 中国 旅行 问题 求解