基于多目標方法的旅行商問題復雜度研究.pdf

1、NP-hard組合優(yōu)化問題一直都是備受關注的問題，越來越多的啟發(fā)式算法被提出來解決這些問題，針對某一類組合優(yōu)化問題，這里有很多種啟發(fā)式算法可以選擇，因此算法選擇問題成為現(xiàn)在研究的熱點。本文旨在研究在解決旅行商問題時是否選擇2-opt算法，給定一個旅行商問題實例，只需要借助它的特征，就能預測其對于2-opt算法的復雜度，如果對于2-opt算法的復雜度較低，那么可以選擇2-opt算法來解決它，相反就需要選擇其它算法來解決它。
　　在現(xiàn)

2、有的文獻中，主要有兩種評價旅行商問題實例對于2-opt算法復雜度的方法。一種是根據2-opt算法解決旅行商問題實例的效率，該方法認為2-opt算法在處理簡單旅行商問題實例時效率較高，相反在困難實例上效率較低，另一種是根據2-opt算法解決旅行商問題實例時得到的解的質量，該方法提出2-opt解決簡單旅行商問題實例時得到的解的質量是較好的，而在解決困難實例時得到的解的質量較差。
　　現(xiàn)有的方法都是利用遺傳算法演化生成困難和簡單的旅行商

3、問題實例，然后通過比較這兩類實例特征的差異，去分析特征與實例復雜度之間的關系，然而本文實驗表明這兩種評價旅行商問題實例對于2-opt算法復雜度的方法是有沖突的。為了解決這個沖突，本文綜合考慮了這兩個目標，并采用NSGA-Ⅱ算法以及MOEA/D算法多目標去演化得到簡單和困難的旅行商問題實例，然后提取特征去分析實例特征與實例復雜度的關系。實驗結果表明多目標方法能夠發(fā)現(xiàn)不同于單目標發(fā)現(xiàn)的特征與實例復雜度之間的關系，并且利用多目標方法發(fā)現(xiàn)的特征