求解幾類復(fù)雜優(yōu)化問題的進(jìn)化算法.pdf

1、作為一種重要的優(yōu)化算法,進(jìn)化算法是借鑒生物進(jìn)化機制形成的一種隨機搜索算法.因不需目標(biāo)函數(shù)的可微信息,又有隱并行性,故用于求解一些傳統(tǒng)優(yōu)化算法難解決的問題.旅行商問題(TSP)正是經(jīng)典的NP-hard組合優(yōu)化問題之一,許多實際問題經(jīng)過簡化均可建模為TSP,因此,具有全局收斂性的遺傳算法成為人們解決TSP的主要方法之一.本文首先提出了一個新的求解TSP的進(jìn)化算法,設(shè)計了一種簡單的整數(shù)編碼方式,使得路徑與某整數(shù)一一對應(yīng),優(yōu)點是每個個體都可行,

2、運算量少,便于設(shè)計遺傳算子;其次,量子遺傳算法(QIGA)利用其高效的搜索能力和較好維持種群多樣性的能力被運用到許多難求解的優(yōu)化問題,因此,深入研究QIGA是必要的.本文通過引入新的可控旋轉(zhuǎn)門操作及終止條件來進(jìn)一步改善QIGA的性能.改進(jìn)的QIGA不僅可以有效地跳出局部最優(yōu)解,而且保持了解的質(zhì)量與運行時間的一種平衡;再次,借助前面的工作,提出了一種求解TSP的新的QIGA,利用幾率幅值編碼,使得種群規(guī)模只有常規(guī)遺傳算法的1/10~1/5