基于遺傳算法的TSP路徑規(guī)劃算法設(shè)計(jì)

1、基于遺傳算法的TSP路徑規(guī)劃算法設(shè)計(jì)摘要TSP問(wèn)題是一個(gè)經(jīng)典的NP難度的組合優(yōu)化問(wèn)題,遺傳算法是求解TSP問(wèn)題的有效方法之一。針對(duì)這一問(wèn)題,首先給出了基于遺傳算法求解TSP問(wèn)題的一般性流程，設(shè)計(jì)了基于遺傳算法的求解算法,包括編碼設(shè)計(jì)、適應(yīng)度函數(shù)選擇、終止條件設(shè)定、選擇算子設(shè)定、交叉算子設(shè)定以及變異算子設(shè)定等,然后設(shè)計(jì)并實(shí)現(xiàn)了基于遺傳算法的TSP問(wèn)題求解系統(tǒng), 并編制了完整的Matlab程序予以仿真實(shí)現(xiàn)。1. 引言旅行商問(wèn)題(Traveling Saleman Problem,TSP) , 又叫貨郎擔(dān)問(wèn)題, 是最基本的路線問(wèn)題, 該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā), 通過(guò)所有給定的城市之后, 最

2、后再回到原點(diǎn)的最小路徑成本。該問(wèn)題具有廣泛的應(yīng)用性, 如物流中的配送車輛調(diào)度問(wèn)題就可看成一個(gè)約束性多路旅行商問(wèn)題. 因此, 對(duì)TSP問(wèn)題求解具有一定的現(xiàn)實(shí)意義。TSP問(wèn)題屬于組合優(yōu)化問(wèn)題, 隨著問(wèn)題規(guī)模增大, 其可行解空間也急劇擴(kuò)大, 有時(shí)在當(dāng)前的計(jì)算機(jī)上用枚舉法很難甚至不能求出最優(yōu)解, 而用啟發(fā)式算法求解這類問(wèn)題的滿意解是一個(gè)很好的方式, 遺傳算法就是尋求這種滿意解的最佳工具之一。遺傳算法模擬自然進(jìn)化過(guò)程來(lái)搜索最優(yōu)解1 , 其本質(zhì)是一種高效、并行、全局搜索的方法。本文采用遺傳算法求解TSP問(wèn)題并編制Matlab程序進(jìn)行仿真試驗(yàn)。2. TSP問(wèn)題的數(shù)學(xué)模型TSP 問(wèn)題即尋找一條最短的遍歷n個(gè)城

3、市的最短路徑, 使得:取最小值, di,i+1表示兩城市i和i + 1之間的距離。3. 遺傳算法的運(yùn)行過(guò)程遺傳算法是一種 生成+ 檢測(cè) 的迭代搜索算法。其運(yùn)算流程可用圖1來(lái)表示。圖1 遺傳算法的程序4. TSP問(wèn)題的遺傳算法實(shí)現(xiàn)4.1 編碼并生成初始種群編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題, 也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵環(huán)節(jié)。求解TSP問(wèn)題時(shí), 采用所遍歷城市的順序排列來(lái)表示各個(gè)個(gè)體的編碼是最自然的編碼方法2 , 而且這種表示方法無(wú)需解碼過(guò)程, 占用的內(nèi)存空間較小。4.2 適應(yīng)度評(píng)估適應(yīng)度用來(lái)度量群體中各個(gè)體在優(yōu)化過(guò)程中達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個(gè)體被選中遺傳到下一

4、代的概率較大；而適應(yīng)度較低的個(gè)體被選中遺傳到下一代的概率相對(duì)較小一些。本文用個(gè)體所表示的循環(huán)路線的倒數(shù)來(lái)作為適應(yīng)度評(píng)估值, 路線越短,個(gè)體適應(yīng)度值越大。4.3 選擇、交叉、變異選擇操作。是從群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新種群的過(guò)程. 選擇操作以個(gè)體的適應(yīng)度評(píng)估為基礎(chǔ)。其主要目的是避免有用遺傳信息的丟失。從而提高算法的全局收斂性和計(jì)算效率。常用的選擇算子有賭輪選擇、聯(lián)賽選擇、最佳保留等。其中，最佳個(gè)體保存策略可保證迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作所破壞。它是遺傳算法收斂性的一個(gè)重要保證條件。但它也容易使得某個(gè)局部最優(yōu)個(gè)體不易被淘汰反而快速擴(kuò)散。從而使得算法的全局搜索能力不強(qiáng)。因

5、此，最佳個(gè)體保存一般要與其他選擇方法配合使用方可取得良好的效果 3 。交叉運(yùn)算產(chǎn)生子代, 子代繼承父代的基本特征。交叉算子一般包括兩個(gè)內(nèi)容: 一是對(duì)種群中的個(gè)體隨機(jī)配對(duì)并按預(yù)先設(shè)定的交叉概率來(lái)確定需要進(jìn)行交叉操作的個(gè)體對(duì); 二是設(shè)定個(gè)體的交叉點(diǎn), 并對(duì)的部分結(jié)構(gòu)進(jìn)行相互交換。交叉算子的設(shè)計(jì)與編碼方式有關(guān)。在TSP問(wèn)題中幾種有代表性的交叉算子如順序交叉、類OX交叉等, 這些交叉算子在產(chǎn)生新個(gè)體的過(guò)程中沒(méi)有目的性, 對(duì)于自然數(shù)編碼的TSP問(wèn)題, 這些交叉可能破壞親代的較優(yōu)基因, 從而使交叉算子的搜索能力大大降低。變異操作是對(duì)個(gè)體的某些基因值做變動(dòng)。變異操作的目的有兩個(gè), 一是使遺傳算法具有局部的隨

6、機(jī)搜索能力, 當(dāng)經(jīng)過(guò)交叉操作群體已接近最優(yōu)解領(lǐng)域時(shí), 利用變異算子可以加速向最優(yōu)解收斂; 二是使遺傳算法可維持群體的多樣性, 以防止早熟現(xiàn)象。變異算子的設(shè)計(jì)也與編碼方法有關(guān), 對(duì)于自然數(shù)編碼的TSP問(wèn)題, 可采用逆轉(zhuǎn)變異、對(duì)換變異和插入變異等。逆轉(zhuǎn)變異, 也稱倒位變異, 是指在個(gè)體編碼中,隨機(jī)選擇兩點(diǎn)( 兩點(diǎn)間稱為逆轉(zhuǎn)區(qū)域) , 再將這兩點(diǎn)內(nèi)的字串按反序插入到原位置中. 倒位變異考慮了原有邊的鄰接關(guān)系, 能將巡回路線上的優(yōu)良基因性能較好地遺傳到下一代, 提高尋優(yōu)速度。5. 仿真結(jié)果ans = 1.0e+003 * Columns 1 through 10 0 2.5389 2.8738 2.5

7、753 2.3181 2.1587 2.2166 3.1740 3.3711 3.5402 2.5389 0 1.0735 0.1113 0.2668 0.3950 0.4101 0.6379 0.8536 1.0550 2.8738 1.0735 0 0.9645 0.9886 1.0943 1.3827 1.2401 1.4603 1.6870 2.5753 0.1113 0.9645 0 0.2621 0.4167 0.5036 0.6247 0.8549 1.0684 2.3181 0.2668 0.9886 0.2621 0 0.1634 0.3951 0.8850 1.1109 1

8、.3182 2.1587 0.3950 1.0943 0.4167 0.1634 0 0.3386 1.0303 1.2486 1.4477 2.2166 0.4101 1.3827 0.5036 0.3951 0.3386 0 0.9841 1.1603 1.3237 3.1740 0.6379 1.2401 0.6247 0.8850 1.0303 0.9841 0 0.2434 0.4738 3.3711 0.8536 1.4603 0.8549 1.1109 1.2486 1.1603 0.2434 0 0.2321 3.5402 1.0550 1.6870 1.0684 1.3182

9、 1.4477 1.3237 0.4738 0.2321 0 1.7370 0.9102 1.2017 0.9072 0.6485 0.5226 0.7762 1.5320 1.7594 1.9651 1.3754 1.1638 1.6871 1.2041 0.9520 0.7897 0.8571 1.7987 1.9989 2.1757 1.6960 0.8690 1.5800 0.9286 0.7014 0.5419 0.5207 1.4898 1.6775 1.8444 1.2508 1.3088 1.8837 1.3595 1.1159 0.9526 0.9666 1.9354 2.1

10、246 2.2898 1.6172 2.3889 3.2394 2.4819 2.3139 2.1719 1.9794 2.8806 2.9815 3.0566 2.4930 0.3709 0.7306 0.2790 0.2683 0.4077 0.6551 0.8280 1.0700 1.2953 2.6174 0.9079 0.2670 0.8067 0.7744 0.8594 1.1683 1.2074 1.4438 1.6757 2.7576 1.1363 0.1713 1.0318 1.0127 1.0967 1.4068 1.3727 1.5998 1.8291 2.4780 0.

11、9080 0.3983 0.8158 0.7373 0.7978 1.1225 1.2776 1.5183 1.7503 2.3869 1.2635 0.6021 1.1795 1.0598 1.0803 1.4183 1.6577 1.8977 2.1298 2.7753 1.5721 0.6122 1.4735 1.4108 1.4621 1.7929 1.8416 2.0675 2.2959 3.0231 1.7323 0.6924 1.6281 1.5967 1.6639 1.9868 1.9282 2.1416 2.3642 2.1631 0.6291 0.8200 0.5824 0

12、.3776 0.3668 0.7054 1.1855 1.4246 1.6450 2.2037 1.0602 0.6812 0.9895 0.8322 0.8310 1.1694 1.5272 1.7706 2.0005 2.1160 1.3504 0.8788 1.2840 1.1120 1.0891 1.4226 1.8247 2.0679 2.2981 2.3127 1.8966 1.2085 1.8226 1.6667 1.6489 1.9822 2.3238 2.5642 2.7962 1.8765 2.0497 1.5920 1.9983 1.7924 1.7288 2.0337

13、2.5671 2.8104 3.0388 2.2144 2.2900 1.6676 2.2258 2.0448 2.0027 2.3231 2.7563 2.9985 3.2300 1.2418 1.5108 1.6359 1.5099 1.2510 1.1187 1.3239 2.1346 2.3617 2.5657 1.5610 1.7391 1.5152 1.7055 1.4734 1.3832 1.6619 2.3088 2.5492 2.7704 1.2554 2.0895 1.9493 2.0700 1.8231 1.7110 1.9499 2.6868 2.9233 3.1382

14、 Columns 11 through 20 1.7370 1.3754 1.6960 1.2508 1.6172 2.4930 2.6174 2.7576 2.4780 2.3869 0.9102 1.1638 0.8690 1.3088 2.3889 0.3709 0.9079 1.1363 0.9080 1.2635 1.2017 1.6871 1.5800 1.8837 3.2394 0.7306 0.2670 0.1713 0.3983 0.6021 0.9072 1.2041 0.9286 1.3595 2.4819 0.2790 0.8067 1.0318 0.8158 1.17

15、95 0.6485 0.9520 0.7014 1.1159 2.3139 0.2683 0.7744 1.0127 0.7373 1.0598 0.5226 0.7897 0.5419 0.9526 2.1719 0.4077 0.8594 1.0967 0.7978 1.0803 0.7762 0.8571 0.5207 0.9666 1.9794 0.6551 1.1683 1.4068 1.1225 1.4183 1.5320 1.7987 1.4898 1.9354 2.8806 0.8280 1.2074 1.3727 1.2776 1.6577 1.7594 1.9989 1.6

16、775 2.1246 2.9815 1.0700 1.4438 1.5998 1.5183 1.8977 1.9651 2.1757 1.8444 2.2898 3.0566 1.2953 1.6757 1.8291 1.7503 2.1298 0 0.4938 0.5267 0.6916 2.1051 0.7659 0.9347 1.1273 0.8100 0.9040 0.4938 0 0.3483 0.1979 1.6244 1.1556 1.4204 1.6199 1.3006 1.3844 0.5267 0.3483 0 0.4471 1.6594 0.9457 1.3230 1.5

17、470 1.2263 1.4036 0.6916 0.1979 0.4471 0 1.4362 1.3340 1.6172 1.8177 1.4982 1.5782 2.1051 1.6244 1.6594 1.4362 0 2.5778 2.9816 3.2020 2.8799 3.0067 0.7659 1.1556 0.9457 1.3340 2.5778 0 0.5406 0.7737 0.5379 0.9008 0.9347 1.4204 1.3230 1.6172 2.9816 0.5406 0 0.2386 0.1419 0.4667 1.1273 1.6199 1.5470 1

18、.8177 3.2020 0.7737 0.2386 0 0.3224 0.4376 0.8100 1.3006 1.2263 1.4982 2.8799 0.5379 0.1419 0.3224 0 0.3805 0.9040 1.3844 1.4036 1.5782 3.0067 0.9008 0.4667 0.4376 0.3805 0 1.3409 1.8229 1.8315 2.0165 3.4447 1.2017 0.6683 0.4691 0.6737 0.4384 1.5815 2.0674 2.0614 2.2621 3.6865 1.3676 0.8274 0.5963 0

19、.8662 0.6850 0.4265 0.8802 0.7647 1.0734 2.4226 0.3670 0.5591 0.7829 0.4643 0.7141 0.6384 1.1253 1.1333 1.3211 2.7434 0.7197 0.4520 0.5540 0.3139 0.2703 0.7763 1.2161 1.3017 1.4004 2.8366 1.0170 0.6999 0.7207 0.5786 0.2894 1.3046 1.6903 1.8297 1.8561 3.2741 1.5478 1.1287 1.0380 1.0461 0.6666 1.2720

20、1.5302 1.7552 1.6592 3.0078 1.7459 1.4464 1.4229 1.3307 0.9936 1.5856 1.8848 2.0889 2.0219 3.3793 1.9583 1.5764 1.4969 1.4832 1.1100 0.6027 0.6012 0.8994 0.7005 2.0576 1.3528 1.3845 1.5161 1.2435 1.1524 0.8861 1.0916 1.3350 1.2166 2.5753 1.4818 1.3108 1.3616 1.1752 0.9316 1.1899 1.2340 1.5417 1.2990

21、 2.5052 1.8685 1.7407 1.7960 1.6032 1.3650 Columns 21 through 30 2.7753 3.0231 2.1631 2.2037 2.1160 2.3127 1.8765 2.2144 1.2418 1.5610 1.5721 1.7323 0.6291 1.0602 1.3504 1.8966 2.0497 2.2900 1.5108 1.7391 0.6122 0.6924 0.8200 0.6812 0.8788 1.2085 1.5920 1.6676 1.6359 1.5152 1.4735 1.6281 0.5824 0.98

22、95 1.2840 1.8226 1.9983 2.2258 1.5099 1.7055 1.4108 1.5967 0.3776 0.8322 1.1120 1.6667 1.7924 2.0448 1.2510 1.4734 1.4621 1.6639 0.3668 0.8310 1.0891 1.6489 1.7288 2.0027 1.1187 1.3832 1.7929 1.9868 0.7054 1.1694 1.4226 1.9822 2.0337 2.3231 1.3239 1.6619 1.8416 1.9282 1.1855 1.5272 1.8247 2.3238 2.5

23、671 2.7563 2.1346 2.3088 2.0675 2.1416 1.4246 1.7706 2.0679 2.5642 2.8104 2.9985 2.3617 2.5492 2.2959 2.3642 1.6450 2.0005 2.2981 2.7962 3.0388 3.2300 2.5657 2.7704 1.3409 1.5815 0.4265 0.6384 0.7763 1.3046 1.2720 1.5856 0.6027 0.8861 1.8229 2.0674 0.8802 1.1253 1.2161 1.6903 1.5302 1.8848 0.6012 1.

24、0916 1.8315 2.0614 0.7647 1.1333 1.3017 1.8297 1.7552 2.0889 0.8994 1.3350 2.0165 2.2621 1.0734 1.3211 1.4004 1.8561 1.6592 2.0219 0.7005 1.2166 3.4447 3.6865 2.4226 2.7434 2.8366 3.2741 3.0078 3.3793 2.0576 2.5753 1.2017 1.3676 0.3670 0.7197 1.0170 1.5478 1.7459 1.9583 1.3528 1.4818 0.6683 0.8274 0

25、.5591 0.4520 0.6999 1.1287 1.4464 1.5764 1.3845 1.3108 0.4691 0.5963 0.7829 0.5540 0.7207 1.0380 1.4229 1.4969 1.5161 1.3616 0.6737 0.8662 0.4643 0.3139 0.5786 1.0461 1.3307 1.4832 1.2435 1.1752 0.4384 0.6850 0.7141 0.2703 0.2894 0.6666 0.9936 1.1100 1.1524 0.9316 0 0.2518 1.1068 0.7031 0.6643 0.692

26、7 1.1655 1.1390 1.5600 1.2511 0.2518 0 1.3199 0.9432 0.9155 0.8671 1.3635 1.2823 1.8114 1.4887 1.1068 1.3199 0 0.4656 0.7358 1.2930 1.4207 1.6672 0.9915 1.1254 0.7031 0.9432 0.4656 0 0.2982 0.8368 1.0437 1.2386 0.9621 0.8615 0.6643 0.9155 0.7358 0.2982 0 0.5598 0.7531 0.9419 0.8959 0.6426 0.6927 0.8

27、671 1.2930 0.8368 0.5598 0 0.5055 0.4596 1.2295 0.7600 1.1655 1.3635 1.4207 1.0437 0.7531 0.5055 0 0.3717 0.9653 0.4428 1.1390 1.2823 1.6672 1.2386 0.9419 0.4596 0.3717 0 1.3331 0.8095 1.5600 1.8114 0.9915 0.9621 0.8959 1.2295 0.9653 1.3331 0 0.5237 1.2511 1.4887 1.1254 0.8615 0.6426 0.7600 0.4428 0

28、.8095 0.5237 0 1.6646 1.8935 1.5033 1.2894 1.0765 1.0926 0.6241 0.9610 0.6423 0.4344 Column 31 1.2554 2.0895 1.9493 2.0700 1.8231 1.7110 1.9499 2.6868 2.9233 3.1382 1.1899 1.2340 1.5417 1.2990 2.5052 1.8685 1.7407 1.7960 1.6032 1.3650 1.6646 1.8935 1.5033 1.2894 1.0765 1.0926 0.6241 0.9610 0.6423 0.

29、4344 0BestShortcut = Columns 1 through 17 29 31 30 27 28 26 25 20 21 22 18 3 17 19 24 16 8 Columns 18 through 31 9 10 2 4 5 7 6 23 11 13 12 14 15 1theMinDistance = 1.5727e+004圖2 31城市搜索圖圖3 搜索過(guò)程6. 總結(jié)本文針對(duì)TSP問(wèn)題,首先給出了基于遺傳算法求解TSP問(wèn)題的一般性流程，設(shè)計(jì)了基于遺傳算法的求解算法,包括編碼設(shè)計(jì)、適應(yīng)度函數(shù)選擇、終止條件設(shè)定、選擇算子設(shè)定、交叉算子設(shè)定以及變異算子設(shè)定等, 然后設(shè)計(jì)并實(shí)現(xiàn)

30、了基于遺傳算法的TSP問(wèn)題求解系統(tǒng), 并編制了完整的Matlab程序予以仿真實(shí)現(xiàn)。根據(jù)仿真結(jié)果可知，遺傳算法是尋求這種滿意解的最佳工具之一，是一種高效、并行、全局搜索的方法。7. 參考文獻(xiàn)1 雷英杰,等.2009 MATLAB 遺傳算法工具箱及應(yīng)用M.西安: 西安電子科技大學(xué)出版社, 8-9.2 儲(chǔ)理才. 2001 基于MATLAB 的遺傳算法程序設(shè)計(jì)及TSP問(wèn)題求解J . 集美大學(xué)學(xué)報(bào)( 自然科學(xué)版) , 6(1) : 14-19.3 郎茂祥. 2009 配送車輛優(yōu)化調(diào)度模型與算法M . 北京: 電子工業(yè)出版社,75.程序清單：31城市坐標(biāo)圖(x)程序：load(x.txt,-ascii);

31、load(y.txt,-ascii);plot(x,y,x)xlabel(X坐標(biāo)),ylabel(Y坐標(biāo));grid onCalDist程序：function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;drawTSP程序：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:City

32、Num-1plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g); hold on;endplot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);title(num2str(CityNum),

33、城市TSP);if f=0 text(500,230,第 ,int2str(p), 步, 最短距離為 ,num2str(bsf);else text(500,230,最終搜索結(jié)果：最短距離 ,num2str(bsf);endhold off;pause(0.05);genetic_algorithm程序：function gaTSPCityNum=31;dislist,Clist=tsp(CityNum);inn=100; %初始種群大小gnmax=200; %最大代數(shù)pc=0.8; %交叉概率pm=0.8; %變異概率%產(chǎn)生初始種群for i=1:inn s(i,:)=randperm(Ci

34、tyNum);endf,p=objf(s,dislist);gn=1;while gngnmax+1 for j=1:2:inn seln=sel(s,p); %選擇操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:); scnew(j+1,:)=scro(2,:); smnew(j,:)=mut(scnew(j,:),pm); %變異操作 smnew(j+1,:)=mut(scnew(j+1,:),pm); end s=smnew; %產(chǎn)生了新的種群 f,p=objf(s,dislist); %計(jì)算新種群的適應(yīng)度 %記錄當(dāng)前代最好和平均的適應(yīng)度

35、 fmax,nmax=max(f); ymean(gn)=1000/mean(f); ymax(gn)=1000/fmax; %記錄當(dāng)前代的最佳個(gè)體 x=s(nmax,:); drawTSP(Clist,x,ymax(gn),gn,0); gn=gn+1; pause;endgn=gn-1;figure(2);plot(ymax,r); hold on;plot(ymean,b);grid;title(搜索過(guò)程);legend(最優(yōu)解,平均解);end%-%計(jì)算適應(yīng)度函數(shù)function f,p=objf(s,dislist);inn=size(s,1); %讀取種群大小for i=1:inn

36、 f(i)=CalDist(dislist,s(i,:); %計(jì)算函數(shù)值，即適應(yīng)度endf=1000./f;%計(jì)算選擇概率fsum=0;for i=1:inn fsum=fsum+f(i)15;endfor i=1:inn ps(i)=f(i)15/fsum;end%計(jì)算累積概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;end%-function pcc=pro(pc);test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n); end%-%“選擇”操作

37、function seln=sel(s,p);inn=size(p,1);%從種群中選擇兩個(gè)個(gè)體for i=1:2 r=rand; %產(chǎn)生一個(gè)隨機(jī)數(shù) prand=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %選中個(gè)體的序號(hào)endend%-%“交叉”操作function scro=cro(s,seln,pc);bn=size(s,2);pcc=pro(pc); %根據(jù)交叉概率決定是否進(jìn)行交叉操作，1則是，0則否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);if pcc=1 c1=round(rand

38、*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交叉位 c2=round(rand*(bn-2)+1; chb1=min(c1,c2); chb2=max(c1,c2); middle=scro(1,chb1+1:chb2); scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2); scro(2,chb1+1:chb2)=middle; for i=1:chb1 while find(scro(1,chb1+1:chb2)=scro(1,i) zhi=find(scro(1,chb1+1:chb2)=scro(1,i); y=scro(2,chb1+zhi);

39、 scro(1,i)=y; end while find(scro(2,chb1+1:chb2)=scro(2,i) zhi=find(scro(2,chb1+1:chb2)=scro(2,i); y=scro(1,chb1+zhi); scro(2,i)=y; end end for i=chb2+1:bn while find(scro(1,1:chb2)=scro(1,i) zhi=find(scro(1,1:chb2)=scro(1,i); y=scro(2,zhi); scro(1,i)=y; end while find(scro(2,1:chb2)=scro(2,i) zhi=f

40、ind(scro(2,1:chb2)=scro(2,i); y=scro(1,zhi); scro(2,i)=y; end endendend%-%“變異”操作function snnew=mut(snew,pm);bn=size(snew,2);snnew=snew;pmm=pro(pm); %根據(jù)變異概率決定是否進(jìn)行變異操作，1則是，0則否if pmm=1 c1=round(rand*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)變異位 c2=round(rand*(bn-2)+1; chb1=min(c1,c2); chb2=max(c1,c2); x=snew(chb1+1:c

41、hb2); snnew(chb1+1:chb2)=fliplr(x);endendtabu_search程序：clear;CityNum=31;dislist,Clist=tsp(CityNum);Tlist=zeros(CityNum);%禁忌表(tabu list)cl=100;%保留前cl個(gè)最好候選解bsf=Inf;tl=50; %禁忌長(zhǎng)度(tabu length)l1=200;%候選解(candidate),不大于n*(n-1)/2(全部領(lǐng)域解個(gè)數(shù))S0=randperm(CityNum);S=S0;BSF=S0;Si=zeros(l1,CityNum);StopL=200; %終止步數(shù)p=1;clf;figure(1);while (pCityNum*(CityNum)/2 disp(候選解個(gè)數(shù),不大于n*(n-1)/2(全部領(lǐng)域解個(gè)數(shù))！ 系統(tǒng)自動(dòng)退出！); l1=(CityNum*(CityNum)/2).5; break; end ArrS(p)=CalDist(dislist,S); i=1; A=zeros(l1,2); while i=l1 M=CityNum*rand(1,2); M=ceil(M); if M(1)=M(2) m1=max(M(1),M(2);m2=min(M(1),M(2);