求解TSP問題的化學反應優(yōu)化算法研究.pdf

1、在日常生活中、工程設(shè)計中，面臨著許多優(yōu)化問題，優(yōu)化問題是當前計算機科學的一個研究熱點。當問題的規(guī)模較小時，很容易得到問題的精確解，但是當問題的規(guī)模很大時，可以采用人工智能法方法求解最優(yōu)解，化學反應優(yōu)化算法是近年新提出來的擁有較好性能的智能算法中的一種。
　　本文以TSP問題為研究對象，CRO算法為解決TSP問題的智能算法框架，實驗了四個分子操作算子以適應TSP問題的求解并進行了優(yōu)化。本文系統(tǒng)地對CRO算法進行了概括，并詳細地介紹了

2、CRO算法的分子模型、分子屬性、分子的基本操作、基本思想和算法流程。本文根據(jù)CRO算法的流程，首先進行了分子集合的初始化，并針對第一次初始化操作分子采樣不明朗的缺點，使用了隨機方向法初始化分子集合，達到了生成擁有更多信息的分子集合的實驗要求。其次確定了CRO算法中的參數(shù)配置，申明了CRO算法中的函數(shù)。在接下來的步驟中，對于撞墻反應，給出了一個優(yōu)化后的撞墻反應步驟，彌補了原撞墻反應收斂不足的缺陷;對于分解反應，給出了一個保留原分子結(jié)構(gòu)的分

3、解反應步驟;對于交換反應，給出了一個繼承原分子部分結(jié)構(gòu)的新交換反應步驟，相對于原反應更易于獲得最優(yōu)解;對于合成反應，提出了一個基于節(jié)點旋轉(zhuǎn)的新合成反應步驟，該步驟更加傾向于局部搜索。
　　通過第一次實驗，證明了CRO算法相對于經(jīng)典的GA算法，在解對稱TSP問題時具有更高的效率，但是不明顯。通過第二次實驗，證明了對四個基本反應步驟進行優(yōu)化后的CRO算法，在解TSP問題時能夠提供顯著的加速比。當TSP節(jié)點在500個以內(nèi)時，TSP問題的