《工程結(jié)構(gòu)反分析理論》課程設(shè)計

《工程結(jié)構(gòu)反分析理論》 1旅行商問題概述1.1旅行商問題簡介和英國數(shù)學家克克曼(T.P.Kirkman)于19世紀初提出的一個數(shù)學問題。這是一個應如何選擇巡回路徑，以使其旅行路線的總長度最短。1.2旅行商問題的研究意義合爆炸的問題,因此尋找切實可行的簡化求解方法就成為問題的關(guān)鍵。1.3旅行商問題的數(shù)學模型 (d)是由頂點i和頂點j之間的距離所組成的矩陣，旅行商問題就是求出一條通ij有頂點的全排列，隨著頂點數(shù)的增加，會產(chǎn)生組合爆炸。GVEVn}為頂點集，E={e=(i,j)|i,jj∈V，i≠j}為邊集。d(i,j∈V，i≠j)為頂點i到頂點j的距離，其中d＞0且dijijij≠∞，同時d=d(i,j∈V),則經(jīng)典TSP(ClassicalTSP,CTSP)的數(shù)學模型為：ijji(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)其中x為決策變量，x=1表示商人行走的路線包括從城市i到城市j的路徑，ijijx=0表示商人沒有選擇這條路徑。公式(1)為目標函數(shù)，求經(jīng)過所有頂點的回ij路的最小距離；公式(3)要求商人從城市i出來只有一次；公式(4)要求商人走入城市i只有一次；公式(2)-(4)限定回路上每個頂點僅有一條入邊和一條是集合K中包含圖G的全部頂點個數(shù)。公式(5)限定在回路中不出現(xiàn)子回路。模HamiltonijkV1.4旅行商問題的解法般首先想到的最原始的一種方法就是:列出一條可供選擇的路線(即對給定的城市進行排列組合),計算出每條路線的總里一條最短的路線"假設(shè)現(xiàn)在給定的4個城市分別為A、B、C和D,各城市之間的距離為己知數(shù)(如圖1所示)。我們可以通過一個組合的狀態(tài)空間圖目的不斷增大,組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急劇增長,以至達到無法計算的地步,這就是所謂的“組合爆炸問題”。。圖1城市交通圖圖2組合路徑圖2遺傳算法概述2.1遺傳算法簡介GeneticAlgorithm鑒生物界的進化規(guī)律(適者生存,優(yōu))演化而來的隨機化搜索方法"它是由美國的J.Holland教授19752.2遺傳算法的特點與其它的優(yōu)化算法相比較，遺傳算法具有以下特點：(1)遺傳算法以決策變量的編碼作為運算對象，直接對結(jié)構(gòu)對象進行操作,數(shù)連續(xù)性的限定；(3)遺傳算法同時使用多個搜索點的搜索信息，具有隱含并行性和更好的(4)遺傳算法使用搜索概率技術(shù)，能自動獲取和指導優(yōu)化的搜索空間，自2.3遺傳算法的運算過程圖3遺傳算法的運算流程3遺傳算法求解旅行商問題的研究及MATLAB程序設(shè)計TSP,其n個城市之間的距離實質(zhì)上構(gòu)成了一個n×n的矩陣，同時遺傳算法的諸多算子(如選擇、交叉、變異)，都是針對所謂染色些矩陣，比用其它高級語言更簡單、靈活、快捷。3.1初始化群體個共識：旅行的二進制表達對TSP不是最適合的。這里以城市的遍歷次序作12n群大小M。染色體長度(城市數(shù)目)為num的MATLAB程序為：3.2個體適應度計算functionlemvaluerdmatrixnum)%dmatrix表示任意兩個城市之間的的距離矩陣minopt=0;fori=1:num-1minopt=minopt+dmatrix(r(i),r(i+1));minopt=minopt+dmatrix(r(1),r(num));t3.3比例選擇操作(1)計算種群中所有個體的適應度總和；(2)計算每個個體的相對適應度大小，即各個個體在選擇操作中被選中的。中所有個體的適應度總和i個體的相對適應度大小urandsM上面的value函數(shù)成1×n的隨機矩陣.用于存iuerdmatrixnumlengthall擇的群體whilei<=M個矩陣，用于存儲被選擇的群體cgailujatheripopmj3.4交叉操作(1)以交叉概率p從中間群體中隨機地選出需要進行交叉的個體，對這些c(2)在1-(num-1)之間產(chǎn)生兩個隨機數(shù)k,l,這兩個數(shù)表示交叉點的位置；(3)對已經(jīng)配對的兩個個體，相互對應地交換第k到l位的數(shù)字。叉操作fori=1:M*pc*0.5rrandMbfloorrandM1;theratherbkfloornumrandminshumin(k,l);son的群體.對maxshumax(k,l);humaxshuhumaxshuerdeletfatherselecterdeletfahterselectnaselectfathernbselectfather義函數(shù)delet(x,y)deletxyyxfindxyn)))=[];eletxy素刪除3.5變異操作之后的群體，其操作方法為：首先在1-num之間產(chǎn)生兩個隨機數(shù)g和h,這兩個數(shù)表示變異點的位置；最后再以變異概率隨機地從群體%g,h是兩個變異點的位置foriMpmcfloorrandM)+1;g=floor(rand*num)+1;h=floor(rand*num)+1;iansoncgcgsonchian4.結(jié)果評價以16,22,24,48,70,101個城市為例,將在求解TSP問題中良好的全局搜索能力，文中以求解101個城市為例進行運算。通過運算可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加，最佳個實施過程中，M,T,p,p等參數(shù)值的設(shè)定對于問題能否找到滿意解起著非常重要的cmccmm表1遺傳算法與彈性網(wǎng)絡算法計算結(jié)果比較城城市數(shù)最優(yōu)解.1261714.3992.169遺傳算法.1271784.4004.044.253彈性網(wǎng)絡.15422274.135.557.253%生成初始群體popm=zeros(M,num);fori=1:M列functionlem=value(r,dmatrix,num)%dmatrix表示任意兩個城市之間的距離fatheronesMnum矩陣，用于存儲被選擇的群體inoptfori=1:num-1圈長歷次序求哈密頓圈長minoptminoptdmatrixri,r(i+1));minoptminoptdmatrixr),r(num));中所有個體的適應度總和iatrixnumvalue個體的相對適應度大小urandsM%生成1×n的隨機矩陣.用于存儲各iuerdmatrixnumlengthall擇的群體whilei<=Mcgailujtheripopmj操作son