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