|
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 # 橫坐標(biāo) y = 0 # 縱坐標(biāo) 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)) """ 本程序用于實(shí)現(xiàn)模擬退火算法計(jì)算 最短路徑問(wè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)) ## 計(jì)算任意兩點(diǎn)間的距離 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ù)：最小路徑的最后一個(gè)節(jié)點(diǎn)和鄰域 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é)點(diǎn)序列 selectedList = [] ## 選擇好的元素 ### 具體思想是： 從剩余的元素中隨機(jī)選擇十分之一的元素，作為鄰域。然后從鄰域中選擇一個(gè)元素作為已經(jīng)構(gòu)建好的最小路徑的下一個(gè)節(jié)點(diǎn)，使得該路徑 mincost = sys.maxsize###最小的花費(fèi) count = 0 ### 計(jì)數(shù)器 t = 100 ## 初始溫度 t_min = 50 ## 最小溫度 while count < num: count += 1 ### 構(gòu)建一個(gè)鄰域: 如果indexList中元素個(gè)數(shù)大于10個(gè)，則取樣的個(gè)數(shù)為剩余元素個(gè)數(shù)的十分之一。否則為剩余元素個(gè)數(shù)對(duì)10的取余數(shù) leftItemNum = len(indexList) # print "leftItemNum:" ,leftItemNum nextnum = leftItemNum//10 if leftItemNum >= 10 else leftItemNum%10 nextnodeList = sample(indexList,nextnum) ### 從剩余的節(jié)點(diǎn)中選出nextnum個(gè)節(jié)點(diǎn) 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) ### 對(duì)待選的序列路徑求和 ### 將返回的路徑值添加到原來(lái)的路徑值上，同時(shí)，在剩余的節(jié)點(diǎn)序列中，刪除nextnode節(jié)點(diǎn) mincost += maxcost indexList.remove(nextnode) selectedList.append(nextnode) print ("最合適的路徑為：" ,selectedList) print ("路徑節(jié)點(diǎn)個(gè)數(shù)：" ,len(selectedList)) print ("最小花費(fèi)為：" , mincost) print ("嘗試次數(shù):", count) #### 畫(huà)圖 ##### 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) |
|
|
來(lái)自： imelee > 《python 算法》
