基于改進遺傳算法的多目標TSP問題研究.pdf

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

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

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