基于多目標(biāo)方法的旅行商問題復(fù)雜度研究.pdf

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

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

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