求解旅行商問題的微粒群算法研究.pdf

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

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

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