混沌優(yōu)化算法在組合優(yōu)化問(wèn)題中的應用

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