智能信息處理陳雙等:混沌優(yōu)化算 法在組合優(yōu)化問題中的應(yīng)用混沌優(yōu)化算法在組合優(yōu)化問題中的應(yīng)用陳雙',郭建勤”(1.山東大學計算機科學與技術(shù)學院山東 濟南250014;2. 山東電子職業(yè)技術(shù)學院山東 濟南250014)摘要:組合優(yōu)化問題一 直都受到理論界和工程界的重視，此類問題的求解方法也有很多,卻各有缺點和局限性,不能滿足實際應(yīng)用的需要。混沌優(yōu)化算法在解決數(shù)值優(yōu)化問題上具有一定的普遍性,可以很快找到全局最優(yōu)解,不過組合優(yōu)化.問題的解不是一個數(shù)值,因此在前人研究的基礎(chǔ)上,提出求解組合優(yōu)化問題的混沌優(yōu)化算法。首先分析混沌優(yōu)化,并針對組合優(yōu)化問題中的TSP問題,提出一種混沌優(yōu)化策略,探討在TSP問題中應(yīng)用混沌優(yōu)化算法的方法。結(jié)果表明了該方法的有牧性。關(guān)鍵詞:混沌優(yōu)化算法;組合優(yōu)化;TSP;教值優(yōu)化中圍分類號:TP18文獻標識碼:B文章編號:1004 - 373X(2008)18 - 068 - 03Application of Chaos Optimization Algorithm in the Solution ofCombination Optimization ProblemsCHEN Shuang' ,GUO Jianqin'(1. School of2. Shandong College of Electronice 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 theycannot satisfy the need of the practical application. The chaos optimization algorithm has certain universality in the solution ofthe value optimization problems,and they can find the globally optimal solution very quickly , but the solution of the combina-tion optimization problems is not a value, therefore this article proposes the solution of the combination optimization problemschaos optimization algorithm on the studies of the predecessors. This article first analyzes the chaos optimization,and aims atthe TSP problems in the combination optimization problems,proposes one kind of strategy of the chaos optimization, and dis-cusses application of chaos optimization algorithm in the TSP problems , and finally it indicates that this method is effective.Keywords; chaos optimization algorithm; combination optimization; TSP;value optimization的現(xiàn)象?；煦绮⒉皇且黄靵y,而是有著精致內(nèi)在結(jié)構(gòu)1引言的一類現(xiàn)象,混沌是非線性動力學系統(tǒng)在- -定條件下所許多實際工程問題都可以轉(zhuǎn)換成組合優(yōu)化問題加表現(xiàn)的一種運動形式,是系統(tǒng)處于非平衡過程中所呈現(xiàn)以解決,例如目標識別、特征點匹配、以及路徑優(yōu)化,火的隨機行為;產(chǎn)生混沌的機制往往又是簡單的非線性，力分配等問題。對于組合優(yōu)化問題[1] ,通常采用神經(jīng)網(wǎng)是絲毫不帶隨機因素的固定規(guī)則[印]。絡(luò)或模擬退火等方法才能進行求解。這些算法雖然具混沌運動具有遍歷性、隨機性、規(guī)律性等特點,混沌有較快的尋優(yōu)速度,但通常存在易于陷入局部極小等缺運動能在一定范圍內(nèi)按其自身的規(guī)律不重復(fù)地遍歷所點?；煦缭趦?yōu)化計算中具有獨特的性能[2],混沌的隨機有狀態(tài)。混沌的遍歷性特點可被用來進行優(yōu)化搜索且性可使優(yōu)化算法具有跳出局部極小的能力,混沌的遍歷能避免陷入局部極小,因此,混沌優(yōu)化搜索方法已成為性可使優(yōu)化算法到達全局最優(yōu)解附近。-種新穎的優(yōu)化技術(shù),混沌優(yōu)化就是根據(jù)其遍歷性和規(guī)律性特點采用混沌變量在一定范圍內(nèi)進行搜索,促使混2混沌優(yōu)化屯變旱終達到全局最優(yōu)點?；煦缡侵冈诖_定系統(tǒng)中出現(xiàn)的一種貌似無規(guī)則,類量xTYH中國煤化工區(qū)min j(a),尋優(yōu)變似隨機的現(xiàn)象,是存在于非線性系統(tǒng)中的一種較為普遍c N M H G需構(gòu)造混沌變量1與.尋優(yōu)變量x取值區(qū)間的映射關(guān)系。本文的混合優(yōu)化算法收稿日期:2008 -03-28使用x=c+d° t映射形式.其中c,d是當混沌變量在區(qū)8《現(xiàn)代電子技術(shù))2008年第18期總第281期上計算機應(yīng)用技術(shù)(間(0,1)遍歷時尋優(yōu)變量x均能在指定范圍內(nèi)變化的排列的計算問題,它共有二(n!) = (n- 1)!種方案.如常向量[]。混沌優(yōu)化方法的迭代步驟為:果將沿同一閉合路徑但是方向相反的方案只算為一個Step1設(shè)置控制誤差 e,給定混沌初始向量t,令方案,則窮舉法的方案數(shù)為六(n-1)!k=0;(3) TSP問題的拓展Step2將t° 映射到x°的優(yōu)化區(qū)間:x° =c+ dt°,在旅行商問題的研究中,有一類多路旅行商問題并令工”=x°,f"= f°;(Multiple Traveling Salesman Problem,MTSP)。所謂Step3用混沌變量進行迭 代搜索得出x*和f*,多路旅行商問題是指m個推銷員從同一城市(或不同如果1 f*-f-1l