# -*- coding: utf-8 -*- # Filename : Boltzmann.py import operator from numpy import * import copy import matplotlib.pyplot as plt class BoltzmannNet(object): def __init__(self): self.dataMat = [] self.MAX_ITER = 2000 self.T0 = 1000 self.Lambda = 0.97 self.iteration = 0 self.dist = [] self.pathindx = [] self.bestdist = 0 self.bestpath = [] # 加载数据文件 def loadDataSet(self, fileName): numFeat = len(open(fileName).readline().split('\t')) - 1 dataMat = []; fr = open(fileName) for line in fr.readlines(): lineArr = [] curLine = line.strip().split('\t') lineArr.append(float(curLine[0])); lineArr.append(float(curLine[1])); dataMat.append(lineArr) self.dataMat = mat(dataMat) def distEclud(self, matA, matB): # 计算矩阵各向量之间的距离--欧氏距离 ma, na = shape(matA); mb, nb = shape(matB); rtnmat = zeros((ma, nb)) for i in range(ma): for j in range(nb): rtnmat[i, j] = linalg.norm(matA[i, :] - matB[:, j].T) return rtnmat # 计算路径长度 def pathLen(self, dist, path): N = len(path) plen = 0; for i in range(0, N - 1): # 长度为N的向量，包含从1-N的整数 plen += dist[path[i], path[i + 1]] plen += dist[path[0], path[N - 1]] return plen # 路径交换函数 def changePath(self, old_path): N = len(old_path) if random.rand() < 0.25: # 产生两个位置，并交换 chpos = floor(random.rand(1, 2) * N).tolist()[0] new_path = copy.deepcopy(old_path) new_path[int(chpos[0])] = old_path[int(chpos[1])] new_path[int(chpos[1])] = old_path[int(chpos[0])] else: # 产生三个位置，交换a-b和b-c段 d = ceil(random.rand(1, 3) * N).tolist()[0]; d.sort() # 随机生成路径 a = int(d[0]); b = int(d[1]); c = int(d[2]) if a != b and b != c: new_path = copy.deepcopy(old_path) new_path[a:c - 1] = old_path[b - 1:c - 1] + old_path[a:b - 1] else: new_path = self.changePath(old_path) return new_path # 玻尔兹曼函数 def boltzmann(self, newl, oldl, T): return exp(-(newl - oldl) / T) # 初始化网络 def initBMNet(self, m, n, distMat): # 构造一个初始可行解 self.pathindx = list(range(m)) random.shuffle(self.pathindx); # 随机生成每个路径 self.dist.append(self.pathLen(distMat, self.pathindx)) # 每个路径对应的距离 return self.T0, self.pathindx, m # 训练样本 def train(self): [m, n] = shape(self.dataMat) distMat = self.distEclud(self.dataMat, self.dataMat.T) # 转换为邻接矩阵（距离矩阵） # T:当前温度，curpath当前路径索引 MAX_M内循环最大迭代次数 [T, curpath, MAX_M] = self.initBMNet(m, n, distMat) step = 0; # 初始化外循环迭代 while step <= self.MAX_ITER: # 外循环 m = 0; # 内循环计数器 while m <= MAX_M: # 内循环 curdist = self.pathLen(distMat, curpath) # 计算当前路径距离 newpath = self.changePath(curpath) # 产生新路径 newdist = self.pathLen(distMat, newpath) # 计算新路径距离 if (curdist > newdist): # 如果新路径优于原路径，选择新路径作为下一状态 curpath = newpath self.pathindx.append(curpath) self.dist.append(newdist) self.iteration += 1 else: # 如果新路径比原路径差，则执行随机操作 if random.rand() < self.boltzmann(newdist, curdist, T): curpath = newpath self.pathindx.append(curpath) self.dist.append(newdist) self.iteration += 1 m += 1 step += 1 T = T * self.Lambda # 降温 # 计算最优值 self.bestdist = min(self.dist) indxes = argmin(self.dist) self.bestpath = self.pathindx[indxes] # 绘制路径 def drawPath(self, plt, color='b'): m, n = shape(self.dataMat) px = (self.dataMat[self.bestpath, 0]).tolist() py = (self.dataMat[self.bestpath, 1]).tolist() px.append(px[0]); py.append(py[0]) plt.plot(px, py, color) # 绘制散点 def drawScatter(self, plt): px = (self.dataMat[:, 0]).tolist() py = (self.dataMat[:, 1]).tolist() plt.scatter(px, py, c='green', marker='o', s=60) i = 65 for x, y in zip(px, py): plt.annotate(str(chr(i)), xy=(x[0] + 40, y[0]), color='black') i += 1 # 绘制趋势线 def TrendLine(self, plt, color='b'): plt.plot(range(len(self.dist)), self.dist, color) bmNet = BoltzmannNet() bmNet.loadDataSet(r"D:\Boltzmann\dataSet25.txt") bmNet.train() bmNet.drawScatter(plt) bmNet.drawPath(plt) plt.show() #绘制误差算法收敛曲线 plt.show()
