Hopfield網(wǎng)絡(luò)求解TSP兩種改進(jìn)算法的仿真研究
加入技術(shù)交流群
首先檢查式(1)的前3項，其中，第3項僅在網(wǎng)絡(luò)輸出全為0時起約束作用，否則前2項已保證第3項成立。對前2項作如下修改：
則第3項完全可省去。將優(yōu)化目標(biāo)項寫成：本文引用地址：http://www.butianyuan.cn/article/163388.htm
或
也可滿足優(yōu)化要求。則TSP的能量函數(shù)簡化為：
下面以式(13)作為研究對象，其對應(yīng)的網(wǎng)絡(luò)連接矩陣和外部輸入分別是：
該算法可從理論上證明其有效性，仿真研究如下：取A=B=3，D=1，步長δt=0．05，對Uo=0．02和軟限幅兩種情況進(jìn)行仿真，仿真終止條件與改進(jìn)算法2相同。測試的統(tǒng)計結(jié)果如表2和圖2所示。
從測試結(jié)果可以看出，該方法獲得的最優(yōu)解的個數(shù)明顯的多于改進(jìn)算法1。軟限幅的效果明顯優(yōu)于sigmold函數(shù)的效果。但所需的收斂次數(shù)較多。這一點與改進(jìn)算法1是一致的。在使用軟限幅時獲得最優(yōu)解的概率大于95％，只是所需迭代次數(shù)稍多。
4 結(jié)束語
對兩種求解TSP的改進(jìn)算法進(jìn)行仿真研究，結(jié)果表明他們具有非常好的優(yōu)化效果，在10城市問題上可近似100％的獲得最優(yōu)解。
另外，該算法還具有對參數(shù)敏感度低的優(yōu)點。改進(jìn)算法的缺點是所需迭代次數(shù)較多。當(dāng)采用大步長迭代時，可降低收斂所需的迭代次數(shù)，但會影響優(yōu)化效果。
這種影響對Uo=0．02的情況不明顯，例如，在δt=0．5時，其優(yōu)化效果與δt=0．05時幾乎相同，所需迭代次數(shù)可降到450次左右。而對于軟限幅的情況，步長的影響就明顯了，δt= 0．5時，優(yōu)化效果與圖中Uo=0．02的情況差不多。下一步的工作擬采用變步長的方法，估計可大大降低所需的迭代次數(shù)。
評論