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

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

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

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