求解旅行商問(wèn)題的微粒群算法研究.pdf

1、旅行商（TSP）問(wèn)題，是一個(gè)古老而又典型的NP-hard組合優(yōu)化問(wèn)題。該問(wèn)題的有效求解，不僅有著重要的理論和學(xué)術(shù)價(jià)值，同時(shí)對(duì)于許多實(shí)際工程應(yīng)用問(wèn)題有著重要的指導(dǎo)意義。因此，尋求高效的TSP優(yōu)化算法一直是優(yōu)化領(lǐng)域的一個(gè)熱點(diǎn)課題。微粒群算法是一種新型的群智能計(jì)算方法，算法模型簡(jiǎn)單、操作便捷，具有自組織、自適應(yīng)、自學(xué)習(xí)等智能特性，已被證明是一種求解大規(guī)模復(fù)雜問(wèn)題的有效工具，因此也是求解TSP問(wèn)題的一種智能計(jì)算方法。然而，面對(duì)復(fù)雜的離散組合優(yōu)化

2、問(wèn)題，現(xiàn)有的微粒群算法模型存在著效率低下，求解精度不高，易于早熟等缺陷。本文基于TSP優(yōu)化問(wèn)題，著重圍繞離散微粒群算法的模型設(shè)計(jì)和性能改進(jìn)，進(jìn)行以下內(nèi)容的研究： ⑴基于微粒群算法的優(yōu)化機(jī)理，分析了離散微粒群算法設(shè)計(jì)的主要方法和基本原則，進(jìn)而研究了離散微粒群算法的關(guān)鍵技術(shù)，包括離散問(wèn)題的編碼、個(gè)體微粒的評(píng)價(jià)及其主要進(jìn)化操作，為后續(xù)的研究提供技術(shù)基礎(chǔ)。 ⑵為提高離散微粒群算法的全局收斂性，提出了一種引入局部擾動(dòng)策略的改進(jìn)微粒

3、群算法。首先基于整數(shù)編碼，并結(jié)合遺傳算法中的PMX算子，對(duì)離散微粒群算法中的速度、位置及其進(jìn)化操作進(jìn)行了重新定義，其次引入微粒的活力信息來(lái)實(shí)現(xiàn)控制參數(shù)的自適應(yīng)調(diào)節(jié)，構(gòu)造局部擾動(dòng)策略以避免群體局部收斂。改進(jìn)算法被用于典型TSP測(cè)試問(wèn)題，其仿真結(jié)果表明該算法的有效性。 ⑶為提高離散微粒群算法對(duì)復(fù)雜問(wèn)題的求解能力，提出一種基于邊編碼，采用表示邊的兩城市點(diǎn)之間所有點(diǎn)依次倒置插入的微粒更新操作的改進(jìn)離散微粒群算法。并在對(duì)算法方程進(jìn)行重新定