基于k_means的改進(jìn)粒子群算法求解TSP問(wèn)題_易云飛
旅行商問(wèn)題(Traveling Salesman Problem,簡(jiǎn)稱 TSP)是一個(gè) 典型的 NP 完全問(wèn)題。問(wèn)題描述:給定 N 個(gè)城市和兩兩城市之見(jiàn) 的距離,求一條訪問(wèn)各個(gè)城市且僅訪問(wèn)一次的最短路線。雖其數(shù) 學(xué)描述很簡(jiǎn)單, 卻無(wú)法找到一個(gè)確定的算法在多項(xiàng)式時(shí)間內(nèi)求 解旅行商問(wèn)題。 粒子群算法(Particle Swarm Optimization,簡(jiǎn)稱 PSO)由美國(guó) 社會(huì)心理學(xué)家 James Kennedy 和電氣工程師 Russell Eberhart 于 1995 年提出的一種全局優(yōu)化算法,該算法是一種基于群體智能 的優(yōu)化算法, 它是受鳥(niǎo)群和魚(yú)群群體運(yùn)動(dòng)的行為方式啟發(fā)而得 到的。該算法的基本思想來(lái)源于對(duì)鳥(niǎo)群簡(jiǎn)化社會(huì)模型的研究及 行為模擬,其中的每個(gè)個(gè)體充分利用群體的與自身的智能,不斷 地調(diào)整學(xué)習(xí),最終得到滿意解。在 PSO 算法中,每個(gè)備選解是搜 索空間中的一個(gè)粒子, 每個(gè)粒子根據(jù)它自身的經(jīng)驗(yàn)和粒子群的 最佳經(jīng)驗(yàn),在問(wèn)題空間中向更好的位置飛行,如此循環(huán)搜索直到 發(fā)現(xiàn)最優(yōu)解。該算法在連續(xù)優(yōu)化問(wèn)題的運(yùn)用中取得了較好的效 果,但較少用于 TSP 等組合優(yōu)化問(wèn)題的求解。