免疫算法和模擬退火算法求解TSP問題的研究.pdf

1、旅行商問題是一個經(jīng)典的組合優(yōu)化問題，也是一個NP難問題。它在實際中的應用卻非常廣泛。歷年來，人們一直努力地尋找一種既有高質(zhì)量的解，又能快速收斂的近似算法。數(shù)學發(fā)展的重要手段之一就是用新方法解決老問題。最近二十年，許多仿生計算技術悄然興起，它隨著計算機科學的發(fā)展同步成長起來。于是，這個古老問題的研究又重新注入了新的活力；由于模擬退火算法簡單易行，從而使它的應用范圍極為廣泛，并且已在眾多領域得到了實際應用，且經(jīng)常用于解決工程上的尋優(yōu)；生物免

2、疫系統(tǒng)是一個高度進化的生物系統(tǒng)，它具有高度自適應、高度分布性、自組織等特性。它能夠有效識別入侵的抗原并清除抗原，并保持機體的穩(wěn)定。人工免疫算法正是借鑒生物免疫系統(tǒng)信息處理機制的基礎上發(fā)展起來的智能信息處理技術。由于人工免疫算法具備模式識別、學習和記憶的能力，因此它成為了一種科學及工程領域中信息處理和問題求解范式，由此也開辟了計算智能研究的新領域。 本文的工作主要集中在以下幾個方面： 介紹了生物免疫的一些基本概念、系統(tǒng)組成

3、、功能及原理；簡單分析了人工免疫系統(tǒng)的研究內(nèi)容、研究現(xiàn)狀及基本理論；然后，對現(xiàn)已被提出的一些免疫算法和模擬退火算法的基本結(jié)構(gòu)和流程進行了研究和分析。 其次，在深入分析了模擬退火算法基礎上，提出一種溫度可控的求解TSP問題的模擬退火算法，通過對CHNl44以及標準的TSPLIB中不同國家的城市的數(shù)據(jù)進行測試，測試結(jié)果表明：該算法很容易收斂到問題的最優(yōu)解。 然后，在理解和掌握生物免疫系統(tǒng)的基本概念和工作原理后，針對免疫原理提