最新計(jì)算智能課程設(shè)計(jì)粒子群優(yōu)化算法求解旅行商問(wèn)題matlab實(shí)現(xiàn)免費(fèi)下載(編輯修改稿)
2025-04-21 03:50 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 。6. 停止準(zhǔn)則一般使用最大迭代次數(shù)或可以接受的滿意解作為停止準(zhǔn)則。7. 粒子空間的初始化較好地選擇粒子的初始化空間，將大大縮短收斂時(shí)間。這是問(wèn)題依賴的。3. 粒子群算法求解旅行商問(wèn)題的流程粒子群優(yōu)化算法雖然成功地應(yīng)用于連續(xù)優(yōu)化的問(wèn)題中，而在離散上的研究和應(yīng)用還很少，尤其是用PSO解決TSP問(wèn)題是一個(gè)新的研究方向[2]。最初的PSO是用來(lái)解決連續(xù)空間的問(wèn)題的，為了適合求解TSP問(wèn)題，人們對(duì)算法進(jìn)行了各種改進(jìn)。本文采用王嵐[3]重新定義PSO的運(yùn)算符號(hào)和規(guī)則，引入交換子和交換序的概念，構(gòu)造一種特殊的PSO用于求解TSP的方法。先對(duì)這種改進(jìn)的PSO進(jìn)行簡(jiǎn)略介紹：定義1 設(shè)n個(gè)城市的TSP問(wèn)題的解序列為S=（ai），i=1,2，…，（i 1，i2）為交換解S中的點(diǎn)ai1和ai2，則S’=S+ SO（i 1，i2）為解S經(jīng)算子SO（i 1，i2）操作后的新解，這里為符號(hào)“+”賦予了新的含義.例1 有一個(gè)有5個(gè)城市的TSP問(wèn)題，其解為S=（1,3,5,2,4），交換算子為SO（1，2），則S’=S+SO(1,2)=(1,3,5,2,4)+SO(1,2)=(3,1,5,2,4).定義2 一個(gè)或多個(gè)交換子的有序隊(duì)列就是交換序，記作SS。其中，SS=（SO1，SO2，…，SOn），SO1，SO2，…，SOn是交換子，它們之間的順序是有意義的。交換序作用于一個(gè)TSP解上意味著這個(gè)交換序中的所有交換子依次作用于該解上，即S’=S+SS=S+（SO1，SO2，…，SOn）=[(S+SO1)+SO2]+…+SOn.定義3 不同的交換序作用于同一解上可能產(chǎn)生相同的新解，所有有相同效果的交換序的集合稱為交換序的等價(jià)集。定義4 若干個(gè)交換序可以合并成一個(gè)新的交換序，定義為兩個(gè)交換序的合并算子。例2 設(shè)兩個(gè)交換序SS1和SS2按先后順序作用于解S上，得到新解S’。假設(shè)另外有一個(gè)交換序SS’作用于同一解上，能夠得到相同的解S’，可定義SS’=SS1+SS2。SS’和SS1+SS2屬于同一等價(jià)集。一般來(lái)說(shuō)，SS’不唯一。定義5 在交換序等價(jià)集中，擁有最少交換子的序稱為該等價(jià)集的基本交換序。可按如下方法構(gòu)造一個(gè)基本交換序。設(shè)給定兩個(gè)解路徑A和B，需要構(gòu)造一個(gè)基本交換序SS，使得B+SS=A。A：（1,2,3,4,5）； B：（2,3,1,5,4）可以看出，A(1)=B(3)=1，所以第一個(gè)交換子是SO（1,3），B1=B+SO（1,3），得到B 1（1,3,2,5,4）；A(2)=B1(3)=2，所以第二個(gè)交換子是SO（2,3），B2=B1+SO（2,3），得到B 2=（1,2,3,5,4）；同理，第三個(gè)交換子是SO（4,5），得到B3=B2+SO（4,5）=A。這樣就得到一個(gè)基本交換序：SS=AB=（SO（1,3），SO（2,3），SO（4,5））?；綪SO算法中的速度算式在基于以上交換子和交換序的概念下各符號(hào)有了新的定義。其中、仍為學(xué)習(xí)因子，、仍為 [0,1]內(nèi) 的隨機(jī)數(shù)；表示基本交換序以的概率保留，表示基本交換序以的概率保留。由此可以看出的值越大，保留的交換子就越多，的影響就越大；同理，的值越大， 的影響也就越大。這也正是學(xué)習(xí)因子的含義所在。求解TSP的PSO算法步驟描述如下：（1）. 初始化粒子群，即給群體中每一個(gè)粒子賦一個(gè)隨機(jī)的初始解和交換序；（2）
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1