求解TSP問題的遺傳算法的改進和并行化研究.pdf

1、旅行商問題(Travel salesman problem,TSP)是一個具有廣泛應用價值和重要理論意義的組合優(yōu)化難題,目前被廣泛地應用到工業(yè)、農業(yè)、國防、商業(yè),特別是交通等領域,引起了數學、物理、計算機等諸多研究者的關注,而用遺傳算法解決TSP問題成為當前研究熱點問題之一。
　　 用遺傳算法求解TSP問題的基本思想是在一個大的空間范圍內搜索和產生較優(yōu)個體,這就產生了巨大時間復雜度和空間復雜度,而且收斂速度也受到巨大的影響。本文

2、針對算法中這兩個缺陷,用以下兩種方法解決:一是用并行化以加速遺傳算法的求解速度和加快收斂速度；二是提高算法搜索空間的能力。
　　 首先,針對遺傳算法中初始化種群操作的不確定性,提出一種基于經典遺傳算法的初始化種群的方法。該方法按照隨機搜索和啟發(fā)式搜索相結合的方式,保證對空間搜索能力和種群中個體收斂速度。實驗證明,該方法比傳統(tǒng)遺傳算法空間搜索能力更好,用以解決TSP問題得到的解更優(yōu)。
　　 其次,針對傳統(tǒng)并行遺傳算法通信時

3、間較大,提出一種改進并行遺傳算法模型。該模型通過主處理器接收從處理器中部分較優(yōu)解作為初始化種群的部分個體,然后再進行遺傳操作；減少了經典算法中每次迭代的通信時間,并通過遷移較優(yōu)解確保了算法的收斂性并加速了最優(yōu)解的產生。
　　 最后,在改進遺傳算法基礎上,設計三種并行遺傳算法求解TSP問題。該實驗基于主從式模型、粗粒度模型、改進模型,利用實驗室機群環(huán)境,利用消息傳遞接口(Message Passing Interrace,MPI)