“““
@author:?zll
description：
迭代局部搜索算法求解TSP
“““

import?random
import?time
import?math
import?copy

max_iterations?=?10
max_no_improve?=?10
CITY_SIZE?=?52?#城市數量

#?柏林52城算例
city?=?[
[?565575?][?25185?][?345750?][?945685?][?845655?]
[?880660?][?25230?][?5251000?][?5801175?][?6501130?]
[?1605620?][?1220580?][?1465200?][?15305?]
[?845680?][?725370?][?145665?]
[?415635?][?510875?][?560365?][?300465?][?520585?][?480415?]
[?835625?][?975580?][?1215245?][?1320315?][?1250400?][?660180?]
[?410250?][?420555?][?575665?][?11501160?][?700580?][?685595?]
[?685610?][?770610?][?795645?][?720635?][?760650?][?475960?]
[?95260?][?875920?][?700500?][?555815?][?830485?][?117065?]
[?830610?][?605625?][?595360?][?1340725?][?1740245?]
	];

#優化值
Delta?=?[?[0?for?i?in?range（CITY_SIZE）]?for?j?in?range（CITY_SIZE）?]


class?Solution:
	def?__init__（self）:
		self.cost?=?0
		self.route?=?[]
	
	def?copy（self）:
		solution?=?Solution（）
		solution.cost?=?self.cost
		solution.route?=?copy.deepcopy（self.route）
		return?solution


def?ILS（）:

	#計算路徑總長度
	def?cost_total（city_list）:
		cost?=?0
		for?i?in?range（CITY_SIZE?-?1）:
			cost?+=?distance_2city（city_list[i]?city_list[i?+?1]）
		cost?+=?distance_2city（city_list[CITY_SIZE?-?1]?city_list[0]）
		return?cost


	#計算兩個城市間距離
	def?distance_2city?（c1?c2）:
		dis?=?math.sqrt（（city[c1][0]?-?city[c2][0]）?**?2?+?（city[c1][1]?-?city[c2][1]）?**?2）
		return?dis


	#本地局部搜索，找出局部最優解，邊界條件?max_no_improve
	def?local_search（best_solution）:

		#顛倒數組中下標begin到end的元素位置
		def?swap_element（city_list?begin?end）:
			while??begin?				temp?=?city_list[begin]
				city_list[begin]?=?city_list[end]
				city_list[end]?=?temp
				begin?+=?1
				end?-=?1

		#鄰域動作?反轉index_i?<->?index_j?間的元素
		def?two_opt_swap（cities_route?index_i?index_j）:
			new_cities_route?=?copy.deepcopy（cities_route）
			swap_element（new_cities_route?index_i?index_j）
			return?new_cities_route

		#?計算鄰域操作優化值?
		def?calc_delta（i?k?city_list）:
			‘‘‘
????????????????以下計算說明：
????????????????對于每個方案，翻轉以后沒必要再次重新計算總距離
????????????????只需要在翻轉的頭尾做個小小處理

????????????????比如：
????????????????有城市序列???1-2-3-4-5?總距離?=?d12?+?d23?+?d34?+?d45?+?d51?=?A
????????????????翻轉后的序列?1-4-3-2-5?總距離?=?d14?+?d43?+?d32?+?d25?+?d51?=?B
????????????????由于?dij?與?dji是一樣的，所以B也可以表示成?B?=?A?-?d12?-?d45?+?d14?+?d25
????????????????下面的優化就是基于這種原理
			‘‘‘

			delta?=?0

			if?i?==?0?and?k?==?CITY_SIZE?-?1?:
				delta?=?0
			else?:
				i2?=?（i?-?1?+?CITY_SIZE）?%?CITY_SIZE
				k2?=?（k?+?1）?%?CITY_SIZE?
				delta?=?0?
				-?distance_2city（city_list[i2]?city_list[i]）?
				+?distance_2city（city_list[i2]?city_list[k]）?
				-?distance_2city（city_list[k]?city_list[k2]）?
				+?distance_2city（city_list[i]?city_list[k2]）?

			return?delta

		#?更新Delta?
		def?Update（i?k?route）?:
			‘‘‘
		小編注：這是一個計算每次領域動作后路徑長度改變值的小優化，在測試中我們暫時

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????7738??2020-11-27?13:02??python?tsp\ILS?TSP.py
?????文件????????2479??2020-11-27?13:02??python?tsp\SA?TSP.py
?????文件????????6965??2020-11-27?13:02??python?tsp\TS?TSP.py