桂傳志

摘 要：混沌是非線性系統(tǒng)所產(chǎn)生的類似隨機(jī)的運(yùn)動(dòng)，研究表明混沌序列具有隨機(jī)性、遍歷性等特點(diǎn)。由于混沌序列的隨機(jī)性、遍歷性等特點(diǎn)，可將其應(yīng)用在TSP問題的應(yīng)用上。多數(shù)文章產(chǎn)生混沌序列采用Logistic映射，由于Logistic映射所產(chǎn)生的混沌序列很不均勻，該文采用邏輯自映射來(lái)產(chǎn)生混沌序列，大大提高了優(yōu)化運(yùn)算的時(shí)間。

關(guān)鍵詞：混沌 優(yōu)化算法 TSP問題 Logistic映射

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2016）07（c）-0074-02

TSP問題即旅行商問題，它求解的是旅行者經(jīng)過N個(gè)城市且僅一次并回到原處總的最小行程。該文章通過邏輯自映射所產(chǎn)生的混沌序列來(lái)編程求解20個(gè)城市的TSP問題，得到了TSP問題的最優(yōu)解。

自李兵等將混沌序列引入優(yōu)化算法，成功地解決了優(yōu)化算法收斂于局部極值的問題，優(yōu)化算法取得了較大的進(jìn)展。近年來(lái)，利用混沌序列進(jìn)行優(yōu)化搜索的研究也取得了一定的成就。為提高搜索效率，張彤等提出變尺度混沌優(yōu)化算法，通過變尺度不斷地縮小搜索范圍，提高了搜索精度，加快了搜索速度。高鷹等把混沌優(yōu)化算法思想引入粒子群算法，通過對(duì)粒子群進(jìn)行尋優(yōu)，從而使粒子群的進(jìn)化速度加快。文章在前人的研究基礎(chǔ)上，將混沌優(yōu)化算法應(yīng)用于解決TSP問題。

1 混沌序列

混沌序列具有遍歷性、隨機(jī)性、“規(guī)律性”等特點(diǎn)，是對(duì)初始值敏感的一種復(fù)雜序列。由于混沌序列的遍歷性，使得混沌搜索可以跳出局部最優(yōu)點(diǎn)，從而達(dá)到全局最優(yōu)點(diǎn)。混沌序列的產(chǎn)生方法有Logestic映射、立方映射、邏輯自映射等方法。其表達(dá)式分別如下：

2 不同映射產(chǎn)生的混沌序列比較

對(duì)于Logestic映射，對(duì)隨機(jī)取一初值，，Logestic映射所產(chǎn)生的混沌序列具有很好的遍歷性，但是在用Logestic映射尋優(yōu)的過程中，因?yàn)長(zhǎng)ogestic映射所產(chǎn)生的混沌序列具有遍歷性不均勻的特點(diǎn)，使得尋優(yōu)速度比較緩慢。

而立方映射和邏輯自映射所產(chǎn)生的混沌序列也具有很好的遍歷性，立方映射、邏輯自映射所產(chǎn)生的混沌序列的遍歷性要更加均勻，從而使得尋優(yōu)的速度加快。各種映射所產(chǎn)生的混沌序列如圖1所示。

衡量混沌性質(zhì)的一個(gè)重要指標(biāo)是李亞普諾夫指數(shù)，從李亞普諾夫指數(shù)也可以看出Logestic映射的混沌特性較其他映射更不明顯。通過實(shí)驗(yàn)的方法得到各種映射所產(chǎn)生的混沌序列的均勻性是不一樣的，其分布情況見表1。

3 TSP問題概述

TSP問題，即Travelling Salesman Problem，又被稱為推銷員問題，是數(shù)學(xué)領(lǐng)域中著名的N-P問題之一。假設(shè)有一個(gè)旅行商要去拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能經(jīng)過一次而且必須經(jīng)過一次，并且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得到的路徑路程為所有路徑之中的最小值。

建立TSP問題解決模型的方法很多，文中采用矩陣的方法。在表2的方陣中，ABCDE表示城市名稱，矩陣的值為0表示在旅行時(shí)，兩個(gè)城市沒有直接經(jīng)過；矩陣的值為1表示在旅行時(shí)，兩個(gè)城市直接經(jīng)過。為保證旅行過程中，每個(gè)城市僅經(jīng)過一次，則要求矩陣的每行每列有且僅有一個(gè)1，其余均為0。表示經(jīng)過的城市路徑為A-E-D-C-B-A。

第二步：選擇兩個(gè)混沌序列初值（不相等），即和，其值不相等，且在（-1，1）范圍之內(nèi)。

第三步：將表示TSP問題的矩陣轉(zhuǎn)化為單位陣，求出此時(shí)的TSP問題的解，將其設(shè)為最優(yōu)解。

第四步：利用邏輯自映射函數(shù)產(chǎn)生兩個(gè)混沌序列。并將其乘以城市數(shù)，然后取整，得到i和j。若i和j相等，重復(fù)第四步。

第五步：將表示TSP問題的矩陣的i和j行進(jìn)行交換操作。

第六步：計(jì)算此時(shí)的解，如果則。

第七步：達(dá)到循環(huán)次數(shù)，結(jié)束；否則，返回第四步。

4 仿真結(jié)果

文章采用電腦隨機(jī)產(chǎn)生20城市坐標(biāo)，然后對(duì)這20城市進(jìn)行TSP問題求解。這20城市的其坐標(biāo)值為：16，65；11，100；68，2；58，10；10，80；28，5；30，38；30，95；98，40；28，16；41，41；71，33；63，21；19，58；8，46；91，26；79，38；29，92；63，63；43，10。

通過仿真，求得結(jié)果如圖2，其最短路徑的距離為561.37。

參考文獻(xiàn)

[1] 李兵，蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用，1997，14（4）：613-615.

[2] 張彤，王宏偉，王子才.變尺度混沌優(yōu)化方法及其應(yīng)用[J].控制與決策，1999，14（3）：285-288.

[3] 高鷹，謝勝利.混沌粒子群優(yōu)化算法[J].計(jì)算機(jī)科學(xué)，2004， 31（8）：13-15.

[4] 洪蕾.粒子群及人工魚群算法優(yōu)化研究[J].軟件，2014（8）：83-86.