模擬退火算法的python3實現(xiàn)

imelee 2018-04-17

展開全文

import os
import sys
import math
import numpy as np
import matplotlib.pyplot as plt

sys.path.append(r'')

from random import choice,shuffle,sample,uniform
%matplotlib inline

class Point:

x = 0  # 橫坐標
y = 0  # 縱坐標

def __init__(self,x,y):
self.x = int(x)
self.y = int(y)

def printvar(self):
print ("x=%d y=%d" % (self.x,self.y))

"""
  本程序用于實現(xiàn)模擬退火算法計算
  最短路徑問題
"""

data = pd.read_csv('tspcity',header=None)
df = data.T
# len(df[0])
# df[0][0]
# df[1][0]
# df[0][1]
# df[1][1]

list = []
for i in range(len(df)):
point = Point(df[0][i],df[1][i])
list.append(point)

print(len(list))

## 計算任意兩點間的距離
num = len(list)
arr = [[ col for col in range(num)] for row in range(num)]
print(arr)
valstr = ""
for row in range(num):
for col in range(num):
      if col == row:
         arr[row][col] = 0
      else:
         p1 = list[row]
         p2 = list[col]
         arr[row][col] = round(math.sqrt(math.pow((p1.x - p2.x),2) + math.pow((p1.y - p2.y),2)),2) ### 求歐式距離，保留2位小數(shù)

## print the matrix for check

for row in range(num):
for col in range(num):
      if (col+1)%10 == 0:
         print (valstr + "\n")
         valstr = ""
      valstr += str(arr[row][col]) + ","

print ("模擬退火算法查找最短路徑：")
### 參數(shù)：最小路徑的最后一個節(jié)點和鄰域
def valSimulateAnnealSum(curnode,nextnodeList,t):

if nextnodeList == None or len(nextnodeList) < 1 :
      print ("empty")
      return 0

maxcost = sys.maxsize
retnode = 0

for node in nextnodeList:
   # print "curnode : ",curnode ," node: " ,node ," mincost : ",mincost

   t *= 0.98  ## 退火因子
   if arr[curnode][node] < maxcost :
      maxcost = arr[curnode][node]
      retnode = node
   ## 以一定的概率接受較差的解
   else:
         r = uniform(0,1)
         if arr[curnode][node] > maxcost and t > t_min and math.exp(( arr[curnode][node] - maxcost ) / t) > r:
#             print " t = " ,t , "maxcost = ", maxcost , " arr = " ,arr[curnode][node], "  exp = ",math.exp((arr[curnode][node] - maxcost)/t)  ,  " r = ",r , "t_min = " ,t_min
            retnode = node
            maxcost = arr[curnode][node]
            return (retnode,maxcost,t)

return (retnode,maxcost,t)

indexList = [ i for i in range(num)]  ### 原始的節(jié)點序列
selectedList = []  ## 選擇好的元素

### 具體思想是：從剩余的元素中隨機選擇十分之一的元素，作為鄰域。然后從鄰域中選擇一個元素作為已經(jīng)構(gòu)建好的最小路徑的下一個節(jié)點，使得該路徑
mincost = sys.maxsize###最小的花費

count = 0  ### 計數(shù)器
t = 100  ## 初始溫度
t_min = 50  ## 最小溫度
while count < num:
  count += 1
  ### 構(gòu)建一個鄰域: 如果indexList中元素個數(shù)大于10個，則取樣的個數(shù)為剩余元素個數(shù)的十分之一。否則為剩余元素個數(shù)對10的取余數(shù)
  leftItemNum = len(indexList)
#  print "leftItemNum:" ,leftItemNum
  nextnum = leftItemNum//10  if leftItemNum >= 10 else leftItemNum%10

  nextnodeList = sample(indexList,nextnum) ### 從剩余的節(jié)點中選出nextnum個節(jié)點

  if len(selectedList) == 0 :
   item = choice(nextnodeList)
   selectedList.append(item)
   indexList.remove(item)
   mincost = 0
   continue

  curnode = selectedList[len(selectedList) - 1]
  # print "nextnodeList:" ,nextnodeList
  nextnode, maxcost ,t = valSimulateAnnealSum(curnode,nextnodeList,t) ### 對待選的序列路徑求和

  ### 將返回的路徑值添加到原來的路徑值上，同時，在剩余的節(jié)點序列中，刪除nextnode節(jié)點
  mincost += maxcost
  indexList.remove(nextnode)
  selectedList.append(nextnode)

print ("最合適的路徑為：" ,selectedList)
print ("路徑節(jié)點個數(shù)：" ,len(selectedList))
print ("最小花費為：" , mincost)
print ("嘗試次數(shù):", count)

#### 畫圖 #####
plt.figure(1)
x = []
y = []
for i in selectedList :
x.append(list[i].x)
y.append(list[i].y)
plt.plot(x,y)
plt.show()
print ("x: ",x)
print ("y: " ,y)