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