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

關鍵詞：混沌優(yōu)化算法；組合優(yōu)化；TSP;數(shù)值優(yōu)化

中圖分類號：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 引 言

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

2 混沌優(yōu)化

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

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

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

混沌優(yōu)化方法的迭代步驟為：

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

Step 2 將t0映射到x0的優(yōu)化區(qū)間：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。

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

3 混沌優(yōu)化算法在TSP問題上的應用

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

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

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

（1） TSP問題描述

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

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

（2） TSP問題計算復雜度

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

（3） TSP問題的拓展

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

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

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

3.2 用混沌優(yōu)化算法解決TSP問題的流程

（1） 將一個TSP問題映射成為一個混沌優(yōu)化系統(tǒng)可以用以下步驟完成：

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

將TSP問題的換位矩陣集合與由n個神經(jīng)元陣列相對應；每一條路經(jīng)所對應的換位陣的個元素與相應的神經(jīng)元穩(wěn)態(tài)輸出對應；

找出一個反映TSP約束優(yōu)化問題的能量函數(shù)；

求出使能量函數(shù)取最小值的神經(jīng)網(wǎng)絡連接權值矩陣和偏置參數(shù)。

這樣由上述步驟設計的神經(jīng)網(wǎng)絡可用于相應的TSP問題的求解，網(wǎng)絡的穩(wěn)態(tài)輸出就是TSP問題的局部優(yōu)化解，同時它也是相應能量函數(shù)的最小點。網(wǎng)絡的搜索時間即是穩(wěn)定態(tài)的時間，計算過程就是網(wǎng)絡動力學過程。

（2） 用混沌優(yōu)化求解TSP算法步驟如下：

給定TSP的城市數(shù)目和城市坐標，從tsp.dat文件中讀入數(shù)據(jù)，其中包括城市數(shù)目n，城市坐標{C₁(x，y)，C₂(x，y)，…，C_n(x，y)}，（這里(x，y)代表實際的二維地理坐標）；然后初始化一個n×n規(guī)模的混沌網(wǎng)絡，包括輸入矩陣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的隨機初值矩陣；

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

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

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

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

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

4 結 語

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

參 考 文 獻

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

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

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

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

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

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

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

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

［9］何國光，朱萍，曹志彤，等.混沌神經(jīng)網(wǎng)絡的Lyapunov指數(shù)與混沌區(qū)域［J］.浙江大學學報：理學版，2004，31（4）：387390.

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

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

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

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