TSP问题；Simulated Annealing算法

TSP问题之Simulated Annealing算法

• 算法思想
• Python代码
• 例题

算法思想

设连通图G的顶点数为N，带权邻接矩阵为D_{n\times n}。将模拟退火算法应用到TSP问题，首先要构造一个目标函数： \min f(x) = \sum_{i,j}(x_{ij}\times d_{ij}), 其中x_{ij}=0,1，且要满足约束条件： \sum_j x_{ij}=1,\ i=1,2,...,N, \sum_i x_{ij}=1,\ j=1,2,...,N, x_{kk} \neq 0,\ k=1,2,...,N.
一个解X=(x_{ij})_{n \times n}即代表一个可行的H圈。算法的一个应用难点在于如何在一个给定的H圈的基础上随机搜索得到另一个H圈（当然这也意味着搜索得到的结果要在可行域内）。对于这个问题里X的每一个元素都是离散型变量，且取值只有0和1两种，设一个H圈为H_0:=[h_1,h_2,...,h_N]，一个简单的搜索规则如下是：随机抽取H_0中的两个点h_i,\ h_j并交换其顺序，则得到了一个新的H圈$H_1:=[h_1,h_2,...,h_{i-1},h_{j},h_{i+1},...,h_{j-1},h_{i},h_{j+1},..