混沌優化算法在組合優化問題中的應用

摘 要：組合優化問題一直都受到理論界和工程界的重視，此類問題的求解方法也有很多，卻各有缺點和局限性，不能滿足實際應用的需要。混沌優化算法在解決數值優化問題上具有一定的普遍性，可以很快找到全局最優解，不過組合優化問題的解不是一個數值，因此在前人研究的基礎上，提出求解組合優化問題的混沌優化算法。首先分析混沌優化，并針對組合優化問題中的TSP問題，提出一種混沌優化策略，探討在TSP問題中應用混沌優化算法的方法。結果表明了該方法的有效性。

關鍵詞：混沌優化算法；組合優化；TSP;數值優化

中圖分類號：TP18 文獻標識碼：B 文章編號：1004373X(2008)1806803

Application of Chaos Optimization Algorithm in the Solution of

Combination Optimization Problems

CHEN Shuang1，GUO Jianqin2

(1.School of Computer Science and Technology，Shandong University，Jin′an，250014，China;

2.Shandong College of Electronic Technology，Jin′an，250014，China)

Abstract：The combination optimization problems have been paid more attention in the field of theory and the engineering，there also has many solutions of this kind of problems，but actually they all have their disadvantages and limitations，so they cannot satisfy the need of the practical application.The chaos optimization algorithm has certain universality in the solution of the value optimization problems，and they can find the globally optimal solution very quickly，but the solution of the combination optimization problems is not a value，therefore this article proposes the solution of the combination optimization problems chaos optimization algorithm on the studies of the predecessors.This article first analyzes the chaos optimization，and aims at the TSP problems in the combination optimization problems，proposes one kind of strategy of the chaos optimization，and discusses application ofchaos optimization algorithm in the TSP problems，and finally it indicates that this method is effective.

Keywords：chaos optimization algorithm;combination optimization;TSP;value optimization

1 引 言

許多實際工程問題都可以轉換成組合優化問題加以解決，例如目標識別、特征點匹配、以及路徑優化，火力分配等問題。對于組合優化問題\\，通常采用神經網絡或模擬退火等方法才能進行求解。這些算法雖然具有較快的尋優速度，但通常存在易于陷入局部極小等缺點。混沌在優化計算中具有獨特的性能\\，混沌的隨機性可使優化算法具有跳出局部極小的能力，混沌的遍歷性可使優化算法到達全局最優解附近。

2 混沌優化

混沌是指在確定系統中出現的一種貌似無規則，類似隨機的現象，是存在于非線性系統中的一種較為普遍的現象。混沌并不是一片混亂，而是有著精致內在結構的一類現象，混沌是非線性動力學系統在一定條件下所表現的一種運動形式，是系統處于非平衡過程中所呈現的隨機行為；產生混沌的機制往往又是簡單的非線性，是絲毫不帶隨機因素的固定規則\\。

混沌運動具有遍歷性、隨機性、規律性等特點，混沌運動能在一定范圍內按其自身的規律不重復地遍歷所有狀態。混沌的遍歷性特點可被用來進行優化搜索且能避免陷入局部極小，因此，混沌優化搜索方法已成為一種新穎的優化技術，混沌優化就是根據其遍歷性和規律性特點采用混沌變量在一定范圍內進行搜索，促使混沌變量的搜索跳出局部極小點，最終達到全局最優點。

用混沌優化方法求解優化問題min f(x)，尋優變量x一般都有一定的取值范圍，故需構造混沌變量t與尋優變量x取值區間的映射關系。本文的混合優化算法使用x=c＋d*t映射形式。其中c，d是當混沌變量在區間(0，1)遍歷時尋優變量x均能在指定范圍內變化的常向量\\。

混沌優化方法的迭代步驟為：

Step 1 設置控制誤差ε，給定混沌初始向量t0，令k=0；

Step 2 將t0映射到x0的優化區間：x0=c+dt0，并令x*=x0，f*=f0；

Step 3 用混沌變量進行迭代搜索得出xk和fk，如果|fk－fk－1|<ε，則x*=xk，f*=fk，結束。否則轉Setp 4;

Step 4 令k=k+l，轉Step 3。

混沌優化方法求解組合優化問題的基本思想是：首先研究組合優化問題解的空間的特點，產生初始解；再利用混沌變量產生新的解或對初始解，進行混沌擾動，求新解的適應值，得到目前最優解；經過多次迭代，求出全局最優值。在組合優化過程中，混沌優化算法不必像隨機搜索方法那樣根據某種概率轉移來擺脫局部極小，混沌優化搜索不存在局部極小，用混沌二次載波搜索的優化方法能很好地求解無約束優化問題。

3 混沌優化算法在TSP問題上的應用

旅行商問題\\（Traveling Salesman Problem，TSP）是圖論中有代表性的組合優化問題，已經被證明有NP完全計算復雜性，并且許多實際問題都可以轉化為旅行商問題。

例如：鐵路運營、管道鋪設、線路的選擇、計算機網絡的拓撲結構、郵遞員送信和火炬接力等。因此，該問題高效的全局優化算法的研究，一直被科技界和工程界所高度重視。

3.1 TSP問題描述及其計算復雜度

（1） TSP問題描述

問題描述：給定n個城市的集合{1，2，…，n}及城市之間環游的花費C_ij(1≤i≤n，1≤j≤n，i≠j)，需要找到1條經過每個城市1次且回到起點的最小花費的環游\\。

對于大規模TSP，可以進行分區分層研究，即把大規模問題分為若干層次和區域，每區用己有的有效算法求解，然后把通一層次各的各區視為又一個TSP進行優化，再用相應算法處理各區的連接，如此逐層處理以渴求得到大規模問題的次優解。

（2） TSP問題計算復雜度

如果采用最簡單的窮舉發來解決此問題，需要把所有的路徑方案的長度都求出來，從中選擇一個最短的。則由組合數學理論可知，這是一個n個城市沿閉合路徑排列的計算問題，它共有1n(n!)=(n－1)！種方案。如果將沿同一閉合路徑但是方向相反的方案只算為一個方案，則窮舉法的方案數為12(n－1)！

（3） TSP問題的拓展

在旅行商問題的研究中，有一類多路旅行商問題(Multiple Traveling Salesman Problem，MTSP)。所謂多路旅行商問題是指m個推銷員從同一城市(或不同城市)出發，分別走一條旅行線路，使得每個城市都有且僅有1個推銷員走過(出發城市除外)，且總路徑最短。

多路旅行商問題的研究將對運籌學、鐵路運輸規劃的研究，對于加速推動運輸線代化有一定的促進意義。

對于TSP問題，也有一些啟發式算法，如最鄰近搜索、截面搜索、凸包分析、自適應方法等。這些算法都有一定的效果，特別是對平面上的TSP問題，可以利用其位置信息、三角不等式或幾何特性來減小算法的復雜度，但對一般的TSP問題，即只有距離信息而無位置信息或不滿足三角不等式的不可度量的大規模TSP，還沒有有效的算法。

3.2 用混沌優化算法解決TSP問題的流程

（1） 將一個TSP問題映射成為一個混沌優化系統可以用以下步驟完成：

將TSP問題的每一條可能路徑用1個換位矩陣表示，并給出相應的距離表示式；

將TSP問題的換位矩陣集合與由n個神經元陣列相對應；每一條路經所對應的換位陣的個元素與相應的神經元穩態輸出對應；

找出一個反映TSP約束優化問題的能量函數；

求出使能量函數取最小值的神經網絡連接權值矩陣和偏置參數。

這樣由上述步驟設計的神經網絡可用于相應的TSP問題的求解，網絡的穩態輸出就是TSP問題的局部優化解，同時它也是相應能量函數的最小點。網絡的搜索時間即是穩定態的時間，計算過程就是網絡動力學過程。

（2） 用混沌優化求解TSP算法步驟如下：

給定TSP的城市數目和城市坐標，從tsp.dat文件中讀入數據，其中包括城市數目n，城市坐標{C₁(x，y)，C₂(x，y)，…，C_n(x，y)}，（這里(x，y)代表實際的二維地理坐標）；然后初始化一個n×n規模的混沌網絡，包括輸入矩陣y_ij和輸出矩陣xij；

歸一化城市坐標{C₁(x，y)，C₂(x，y)，…C_n(x，y)}，為{c1(x，y)，c₂(x，y)，…，c_n(x，y)}，，再計算歸一化后的距離矩陣d_ij。用隨機化方法給y_ij(0)賦一個n×n的隨機初值矩陣；

通過設定混沌衰減參數終止值zend，可以求得混沌神經網絡最終收斂需要的周期數，計算方法為：Cycle(tend)=log1－β(z(tend)/z0)；

如果Cycle=1，計算xij(0)：計算本周期能量函數；否則，計算dE/dx；再計算本周期y_ij(t+1)，xij(t+1)和本周期能量函數E；

迭代從1：Cycle，判斷如果n

具有大量并行計算能力的神經網絡，在硬件中采用時，能夠很快找到最優解。而且，計算時間不取決于問題的復雜度，而是取決于網絡的內部反饋連接。

對于不同城市數目的TSP問題，應盡量將參數z0和β調整到一個合適的范圍內。例如，對于城市數目比較大的TSP問題，z0的設定也相對大一點，因為由于神經網絡階數越多，參與計算的神經元數目越多，由于狀態空間的搜索區域比較大，而這時不應性自衰減因子若太小，造成的擾動和混沌態就會過小，從而降低混沌遍歷搜索的效果；β的值稍微小一點，是為了有利于進行比較細的搜索。

4 結 語

混合優化算法是一種具有全局收斂性且收斂速度快的算法，它具有的許多優點。混沌優化對于連續變量的優化是有效的，其優化原理具有普遍性，能夠更有效地尋找到全局最優解。

參 考 文 獻

［1］劉傳文.基于Hopfield神經網絡的遙感圖像超分辨率識別算法［J］.武漢理工大學學報，2005，29(6)：970973.

［2］張國鋼，耿英三，王建華.基于蟻群并行算法的電氣接線路徑優化及仿真［J］.系統仿真學報，2003，15(8)：1 0911 094.

［3］高海昌，馮博琴，朱利.智能優化算法求解TSP問題［J］.控制與決策，2006，21(3)：241247.

［4］徐耀群，劉健.一種混沌神經網絡及其在旅行商問題中的應用\\.中國控制與決策學術年會論文集\\，2004.

［5］王凌.智能優化算法及其應用［M］.北京：清華大學出版社，2001.

［6］梁瑞鑫，鄭德玲.基于區間套混沌搜索的混合優化方法［J］.北京科技大學學報，2002，24(3)：342344.

［7］尤勇，王孫安，盛萬興.新型混沌優化方法的研究及應用［J］.西安交通大學學報，2003，37(1)：6972.

［8］王麗俠.混沌優化算法及在0/1背包問題中的應用［J］.儀器儀表學報，2006（S3）：580581.

［9］何國光，朱萍，曹志彤，等.混沌神經網絡的Lyapunov指數與混沌區域［J］.浙江大學學報：理學版，2004，31（4）：387390.

［10］胡志坤，桂衛華，彭小奇.混沌梯度組合優化算法\\.控制與決策，2004，19（12）：1 3371 340.

作者簡介 陳 雙 女，1975年出生，山東大學計算機科學與技術學院。主要研究方向為計算機原理及應用。

郭建勤 女，1974年出生，山東省電子職業技術學院電子系，講師。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文