计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2008年
1期
57-59
,共3页
禁忌算法%启发式算法%旅行商问题
禁忌算法%啟髮式算法%旅行商問題
금기산법%계발식산법%여행상문제
利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法(MTS).该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点.算法首先通过对城市分区,然后对区域连接,生成初始解;同时生成每个城市的k邻居列表,利用k邻居列表和改进的禁忌策略来突破局部最优.通过对CHN144问题及若干TSPLIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解.
利用傳統的禁忌算法的基本思想,針對TSP問題,提齣瞭一種改進的禁忌算法(MTS).該算法在初始解的生成,鄰域結構及禁忌策略方麵進行瞭大的改進,充分地利用瞭問題本身的啟髮式信息與禁忌算法的優點.算法首先通過對城市分區,然後對區域連接,生成初始解;同時生成每箇城市的k鄰居列錶,利用k鄰居列錶和改進的禁忌策略來突破跼部最優.通過對CHN144問題及若榦TSPLIB中問題的求解,結果錶明所提算法能夠以較快速度求得較好的滿意解.
이용전통적금기산법적기본사상,침대TSP문제,제출료일충개진적금기산법(MTS).해산법재초시해적생성,린역결구급금기책략방면진행료대적개진,충분지이용료문제본신적계발식신식여금기산법적우점.산법수선통과대성시분구,연후대구역련접,생성초시해;동시생성매개성시적k린거렬표,이용k린거렬표화개진적금기책략래돌파국부최우.통과대CHN144문제급약간TSPLIB중문제적구해,결과표명소제산법능구이교쾌속도구득교호적만의해.