基于改進(jìn)遺傳算法的多目標(biāo)TSP問題研究.pdf

1、TSP(Traveling salesman Problem，旅行商問題)是指給定n個城市和各城市間的距離，要求確定一條經(jīng)過各個城市當(dāng)且僅當(dāng)一次的最短路線。它是一種典型的組合優(yōu)化問題，其最優(yōu)解的求解代價是指數(shù)級的。已經(jīng)證明TSP問題是一個NP-hard問題?；谥悄軆?yōu)化算法求解TSP問題，是近年來剛剛興起的熱門課題。 然而在科學(xué)管理與經(jīng)濟(jì)決策的許多應(yīng)用領(lǐng)域中，現(xiàn)實(shí)世界存在著大量的多目標(biāo)優(yōu)化問題。對于旅行商問題(Traveling

2、 salesman Problem，Tsp)，實(shí)際中經(jīng)常要同時考慮多個目標(biāo)，如路程最短、時間最短、費(fèi)用最省、風(fēng)險最小等多方面的因素。目標(biāo)之間往往存在沖突性。如何在多個目標(biāo)中尋找一個公平、合理的解是比較復(fù)雜的問題。本文主要對遺傳算法求解多目標(biāo)TSP問題進(jìn)行了研究。 多目標(biāo)TSP是從通信、物流等應(yīng)用領(lǐng)域中提出的一類新的NP-hard的數(shù)學(xué)理論模型，它屬于演化計算的一個新的研究領(lǐng)域。與經(jīng)典的TSP相比，多目標(biāo)TSP更復(fù)雜，具有更大的挑

3、戰(zhàn)性。多目標(biāo)TSP的研究將推動一些實(shí)際問題的解決，如投資問題。投資者一般希望所投入的資金量最少，風(fēng)險最小，且獲得的收益最大。所以研究多目標(biāo)TSP具有重大的理論意義和應(yīng)用價值。 關(guān)于多目標(biāo)問題的研究在國內(nèi)外都剛起步，鑒于以上研究現(xiàn)狀，本文提出了一種多目標(biāo)遺傳算法。主要包括以下工作： 1.介紹了TSP的研究現(xiàn)狀、基本知識和遺傳算法的基礎(chǔ)理論知識。 2.介紹了作者對多目標(biāo)TSP取得的研究成果：針對傳統(tǒng)遺傳算法求解的缺陷