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

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

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

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