Last active
August 26, 2021 05:47
-
-
Save ywzhang909/378b596c430b57de69a5d737c6cf78be to your computer and use it in GitHub Desktop.
Tuba Search#algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import numpy as np | |
dulChange = False | |
coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0], | |
[880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0], | |
[1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0], | |
[725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0], | |
[300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0], | |
[1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0], | |
[420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0], | |
[685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0], | |
[475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0], | |
[830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0], | |
[1340.0, 725.0], [1740.0, 245.0]]) | |
def getdistmat(coordinates): | |
num = coordinates.shape[0] | |
distmat = np.zeros((52, 52)) | |
for i in range(num): | |
for j in range(i, num): | |
distmat[i][j] = distmat[j][i] = np.linalg.norm(coordinates[i] - coordinates[j]) | |
return distmat | |
def initpara(): | |
alpha = 0.99 | |
t = (1, 100) | |
markovlen = 10000 | |
return alpha, t, markovlen | |
num = coordinates.shape[0] | |
distmat = getdistmat(coordinates) | |
solutionnew = np.arange(num) # 0-51 | |
valuenew = 9999999999999 | |
solutioncurrent = solutionnew.copy() | |
valuecurrent = 9999999999999 | |
solutionbest = solutionnew.copy() | |
valuebest = 9999999999999 | |
alpha, t2, markovlen = initpara() | |
t = t2[1] | |
result = [] # 记录迭代过程中的最优解 | |
while t > t2[0]: | |
for i in np.arange(markovlen): | |
# print t, i | |
# 下面的两交换和三角换是两种扰动方式,用于产生新解 | |
if dulChange: # 两交换 | |
# np.random.rand()产生[0, 1)区间的均匀随机数 | |
while True: # 产生两个不同的随机数 | |
loc1 = np.int(np.ceil(np.random.rand() * (num - 1))) | |
loc2 = np.int(np.ceil(np.random.rand() * (num - 1))) | |
if loc1 != loc2: | |
break | |
solutionnew[loc1], solutionnew[loc2] = solutionnew[loc2], solutionnew[loc1] | |
else: # 三交换 | |
while True: | |
loc1 = np.int(np.ceil(np.random.rand() * (num - 1))) | |
loc2 = np.int(np.ceil(np.random.rand() * (num - 1))) | |
loc3 = np.int(np.ceil(np.random.rand() * (num - 1))) | |
if ((loc1 != loc2) & (loc2 != loc3) & (loc1 != loc3)): | |
break | |
# 下面的三个判断语句使得loc1<loc2<loc3 | |
if loc1 > loc2: | |
loc1, loc2 = loc2, loc1 | |
if loc2 > loc3: | |
loc2, loc3 = loc3, loc2 | |
if loc1 > loc2: | |
loc1, loc2 = loc2, loc1 | |
# 下面的三行代码将[loc1,loc2)区间的数据插入到loc3之后 | |
tmplist = solutionnew[loc1:loc2].copy() | |
solutionnew[loc1:loc3 - loc2 + 1 + loc1] = solutionnew[loc2:loc3 + 1].copy() | |
solutionnew[loc3 - loc2 + 1 + loc1:loc3 + 1] = tmplist.copy() | |
valuenew = 0 | |
for i in range(num - 1): | |
valuenew += distmat[solutionnew[i]][solutionnew[i + 1]] | |
valuenew += distmat[solutionnew[0]][solutionnew[51]] | |
if valuenew < valuecurrent: # 接受该解 | |
# 更新solutioncurrent 和solutionbest | |
valuecurrent = valuenew | |
solutioncurrent = solutionnew.copy() | |
if valuenew < valuebest: | |
valuebest = valuenew | |
solutionbest = solutionnew.copy() | |
else: # 按一定的概率接受该解 | |
if np.random.rand() < np.exp(-(valuenew - valuecurrent) / t): | |
valuecurrent = valuenew | |
solutioncurrent = solutionnew.copy() | |
else: | |
solutionnew = solutioncurrent.copy() | |
t = alpha * t | |
result.append(valuebest) | |
fopen = open('save1','w+') | |
fopen.write(result) | |
fopen.close() | |
import matplotlib.pyplot as plt | |
plt.figure() | |
plt.plot(np.array(result)) | |
plt.xlabel('t') | |
plt.ylabel('value') | |
plt.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment