其实Python智能优化算法已经提出来好几年了,包括粒子群算法PSO、遗传算法等等,曾经在上世纪包括本世纪初特别流行,这几年随着算力的提升和更高效算法的提出,其已经逐渐离开大众视野了。但是了解智能优化算法,并且使用Python实现部分算法仍旧对于我们思维能力的养成以及Python编程能力的培养不无裨益。
遗传算法
参考博客1:https://blog.csdn.net/ha_ha_ha233/article/details/91364937
参考博客2:https://blog.csdn.net/weixin_41503009/article/details/104782088
思维框架
算法实现
遗传算法代码如下:
import numpy as np
import math
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
N_GENERATIONS = 50
DNA_LEN=10
POP_SIZE=100
XBound=[-1,2]
#f(x)为需要求解的函数
def f(pop):
flist=[]
for one in pop:
flist.append(one * np.sin(10*math.pi*one) + 2)
return flist
#prese(x)为把给定的数值矩阵压缩为指定范围的列表
def press(fx,Xbound):
coeff = np.array([2**i for i in range(len(fx[0]))])
ans = np.dot(fx,coeff)/(2**(len(fx[0]))-1)
mappx = [i * (Xbound[1]-Xbound[0])+ Xbound[0] for i in ans]
return mappx
#这是根据每个点的值得到每个点的适应度
def get_fitness(fpred):
return fpred-np.min(fpred)+1e-3
#选择函数,得到新的种群矩阵
def select(pop, fitness): # nature selection wrt pop's fitness
temp=np.array(fitness)
idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
p=(temp)/(temp.sum()) )
return pop[idx]
pop=np.random.randint(low=0,high=2,size=(POP_SIZE,DNA_LEN))
save_1 = f(press(pop,XBound))
fitness=get_fitness(save_1)
select=select(pop,save_1)
print(select)
模拟退火算法
参考博客:https://blog.csdn.net/WFRainn/article/details/80303138?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161451812216780271524683%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161451812216780271524683&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-2-80303138.first_rank_v2_pc_rank_v29&utm_term=%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95Python
思维框架
算法实现
模拟退火算法代码如下:
import numpy as np
import random
import math
'''
下面几个初始化参数聪上往下分别为:求解范围的上、下界、温度降低的速率以及初始温度
'''
HIGH = 3
LOW = -3
ALF = 0.95
Temper = 50
#目标函数
def f(x):
return 11*np.sin(x) + 7 * np.cos(5*x)
#概率函数p,这里只考虑下山的情况
def p(x,x1):
return math.exp(-abs(f(x)-f(x1))/Temper)
#新解的随机产生
def new(x):
x1 = x + Temper*random.uniform(-1,1)
if (x1 <= HIGH) & (x1 >= LOW):
return x1
elif x1 < LOW:
rand = random.uniform(-1,1)
return rand * LOW + (1 - rand) * x
else:
rand = random.uniform(-1,1)
return rand * HIGH + (1 - rand) * x
def main():
global x,Temper
x=random.uniform(LOW,HIGH)
while Temper > 0.001:
for i in range(500):
x1 =new(x)
if f(x1) <= f(x):
x = x1
elif random.random() <= p(x,x1):
x = x1
else:
continue
Temper = Temper*ALF
print('最小值为:{}'.format(f(x)))
if __name__=="__main__":
main()
蚁群算法
参考博客1:https://blog.csdn.net/ACA_JSP/article/details/88362006?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161466651216780255259333%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161466651216780255259333&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v29-8-88362006.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95
参考博客2:https://blog.csdn.net/fanxin_i/article/details/80380733?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161461094416780266251736%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161461094416780266251736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-2-80380733.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95Python
参考博客3:https://blog.csdn.net/qq_38526623/article/details/105318909?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161461094416780266251736%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161461094416780266251736&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-1-105318909.first_rank_v2_pc_rank_v29&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95Python
普通蚁群算法
普通蚁群算法代码如下:
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
'''
下面是几个城市基本参数的设置
蚁群蚂蚁数量为10
'''
CHENGDU = [1,1]
SHANGHAI = [5,2]
XIAN = [2,3]
WUHAN = [3,2]
BEIJING = [4,3.5]
SHENZHEN = [3.5,0]
FUZHOU = [4.5,0.5]
CITY_LEN = 7
ANT_NUMBER = 35
MOVE_TIMES = 20
CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]
#计算两个城市间的距离
def distance(city1,city2):
temp = [i-j for i,j in zip(city1,city2)]
return (sum([x**2 for x in temp]))**(1/2)
#计算周游一圈总的长度
def total_distance(cityset):
citycopy = cityset[:]
citycopy.append(cityset[0])
dist = 0
for i in range(len(cityset)):
dist += distance(citycopy[i],citycopy[i+1])
return dist
#根据城市列表生成距离矩阵
def dist_matrix(cityset):
dist_matrix = np.zeros((CITY_LEN,CITY_LEN))
for i in range(CITY_LEN):
for j in range(CITY_LEN):
dist_matrix[i][j] = distance(cityset[i],cityset[j])
return dist_matrix
#生成初始信息素矩阵
def phe_matrix():
phe_matrix = np.diag([-5,-5,-5,-5,-5,-5,-5])
phe_matrix += 5
return phe_matrix
#求解最后的预测路径
def find_route(mat,cityset):
list1 = []
list1.append(0)
count = 0
while(True):
data = mat[count]
for item in list1:
data[item] = 0
count = max_index = np.argmax(data)
list1.append(max_index)
if(len(list1) == 7):
break
route = []
for number in list1:
route.append(cityset[number])
return route
#打印当前的路程情况
def print_plot(cityset):
x_list=[];y_list=[]
for city in cityset:
x_list.append(city[0])
y_list.append(city[1])
x_list.append(cityset[0][0])
y_list.append(cityset[0][1])
plt.plot(x_list,y_list)
plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
plt.scatter(x_list[0],y_list[0],color="red",marker="o")
plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
print('最短路径长度为:',total_distance(cityset))
#蚂蚁类,有当前位置和移动禁忌表两个元素
class ant:
def __init__(self):
self.position = np.random.randint(low=0,high=CITY_LEN)
self.Tabu_list = []
def update_Tabu(self):
if len(self.Tabu_list) >= CITY_LEN - 1:
self.Tabu_list = []
else:
self.Tabu_list.append(self.position)
def info(self):
print('当前此蚂蚁所在位置为:',self.position+1)
if len(self.Tabu_list)==0:
print('当前此蚂蚁移动禁忌表为:',self.Tabu_list)
else:
print('当前此蚂蚁移动禁忌表为:',[i+1 for i in self.Tabu_list])
def move(self,new_position):
self.update_Tabu()
self.position = new_position
#蚁群类,有蚁群蚂蚁数量和十个蚂蚁两个元素
class ants:
def __init__(self,ant_number):
self.number = ant_number
self.antss = []
for i in range(ant_number):
self.antss.append(ant())
def info(self):
for i in range(self.number):
print('蚂蚁',i+1)
self.antss[i].info()
#路径类,有距离矩阵、信息素矩阵和比值矩阵三个元素
#距离矩阵一旦生成不再改变,信息素矩阵会更新
class route_matrix:
def __init__(self,cityset):
self.dist_matrix = dist_matrix(cityset)
self.phe_matrix = phe_matrix()
for i in range(CITY_LEN):
self.dist_matrix[i][i] = 1
self.index_matrix = self.phe_matrix/self.dist_matrix
def update_index(self,pos1,pos2):
self.index_matrix[pos1][pos2] += 3.0/self.dist_matrix[pos1][pos2]
def info(self):
#print('当前路径的距离矩阵为:')
#print(self.dist_matrix)
print('当前路径的信息素矩阵为:')
print(self.phe_matrix)
print('当前路径的比值矩阵为:')
print(self.index_matrix)
#蚁群类,包含了蚂蚁和路程矩阵两个元素
class antcolony:
def __init__(self,ants,route_matrix):
self.ants = ants
self.matrix = route_matrix
def info(self):
self.ants.info()
self.matrix.info()
def move_prob(self):
prob_lists = []
for ant in self.ants.antss:
temps = self.matrix.index_matrix[ant.position][:]
prob_list = []
for temp in temps:
prob_list.append(temp)
for Tabu in ant.Tabu_list:
prob_list[Tabu] = 0
new_list = [x/sum(prob_list) for x in prob_list]
prob_lists.append(new_list)
return prob_lists
def update_matrix(self,pos1,pos2):
self.matrix.phe_matrix[pos1][pos2] += 3.0/self.matrix.dist_matrix[pos1][pos2]
self.matrix.update_index(pos1,pos2)
def wholemove(self):
if len(self.ants.antss[0].Tabu_list) < 6:
prob_lists = self.move_prob()
for i in range(ANT_NUMBER):
if len(self.ants.antss[i].Tabu_list) < 6:
idx = np.random.choice(np.arange(CITY_LEN),p=prob_lists[i])
#print(i,"的当前位置为:",self.ants.antss[i].position+1)
#print(i,'选择的下一位置为:',idx+1)
last_pos = self.ants.antss[i].position
self.ants.antss[i].move(idx)
self.update_matrix(last_pos,idx)
else:
last_pos = self.ants.antss[i].position
origin = self.ants.antss[i].Tabu_list[0]
self.ants.antss[i].move(origin)
self.update_matrix(last_pos,origin)
if __name__ == "__main__":
np.random.shuffle(CHENGSHI)
route = route_matrix(CHENGSHI)
ants = ants(ANT_NUMBER)
antcolony = antcolony(ants,route)
for count in range(MOVE_TIMES):
antcolony.wholemove()
matrix = antcolony.matrix.index_matrix
answer = find_route(matrix,CHENGSHI)
antcolony.info()
print_plot(answer)
最优-最差蚂蚁-蚁群算法
最优-最差蚂蚁策略的蚁群算法代码如下:
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
'''
下面是几个城市基本参数的设置
蚁群蚂蚁数量为10
'''
CHENGDU = [1,1]
SHANGHAI = [5,2]
XIAN = [2,3]
WUHAN = [3,2]
BEIJING = [4,3.5]
SHENZHEN = [3.5,0]
FUZHOU = [4.5,0.5]
CITY_LEN = 7
ANT_NUMBER = 35
MOVE_TIMES = 20
CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]
#计算两个城市间的距离
def distance(city1,city2):
temp = [i-j for i,j in zip(city1,city2)]
return (sum([x**2 for x in temp]))**(1/2)
#计算周游一圈总的长度
def total_distance(cityset):
citycopy = cityset[:]
citycopy.append(cityset[0])
dist = 0
for i in range(len(cityset)):
dist += distance(citycopy[i],citycopy[i+1])
return dist
#根据城市列表生成距离矩阵
def dist_matrix(cityset):
dist_matrix = np.zeros((CITY_LEN,CITY_LEN))
for i in range(CITY_LEN):
for j in range(CITY_LEN):
dist_matrix[i][j] = distance(cityset[i],cityset[j])
return dist_matrix
#根据数字列表生成的路径
def pro_route(index_list,cityset=CHENGSHI):
alter = []
for index in index_list:
alter.append(cityset[index])
return alter
#生成初始信息素矩阵
def phe_matrix():
phe_matrix = np.diag([-5,-5,-5,-5,-5,-5,-5])
phe_matrix += 5
return phe_matrix
#将路程表分解为所有相邻两个元素组成的列表
def decompose(index_list):
indexcopy = index_list[:]
indexcopy.append(index_list[0])
decom = []
for i in range(len(index_list)):
part = indexcopy[i:i+2]
decom.append(part)
return decom
#求解最后的预测路径
def find_route(mat,cityset):
list1 = []
list1.append(0)
count = 0
while(True):
data = mat[count]
for item in list1:
data[item] = 0
count = max_index = np.argmax(data)
list1.append(max_index)
if(len(list1) == 7):
break
route = []
for number in list1:
route.append(cityset[number])
return route
#打印当前的路程情况
def print_plot(cityset):
x_list=[];y_list=[]
for city in cityset:
x_list.append(city[0])
y_list.append(city[1])
x_list.append(cityset[0][0])
y_list.append(cityset[0][1])
plt.plot(x_list,y_list)
plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
plt.scatter(x_list[0],y_list[0],color="red",marker="o")
plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
print('最短路径长度为:',total_distance(cityset))
#蚂蚁类,有当前位置和移动禁忌表两个元素
class ant:
def __init__(self):
self.position = np.random.randint(low=0,high=CITY_LEN)
self.Tabu_list = []
def update_Tabu(self):
if len(self.Tabu_list) >= CITY_LEN - 1:
self.Tabu_list = []
else:
self.Tabu_list.append(self.position)
def info(self):
print('当前此蚂蚁所在位置为:',self.position+1)
if len(self.Tabu_list)==0:
print('当前此蚂蚁移动禁忌表为:',self.Tabu_list)
else:
print('当前此蚂蚁移动禁忌表为:',[i+1 for i in self.Tabu_list])
def move(self,new_position):
self.update_Tabu()
self.position = new_position
#蚁群类,有蚁群蚂蚁数量和十个蚂蚁两个元素
class ants:
def __init__(self,ant_number):
self.number = ant_number
self.antss = []
for i in range(ant_number):
self.antss.append(ant())
def info(self):
for i in range(self.number):
print('蚂蚁',i+1)
self.antss[i].info()
#路径类,有距离矩阵、信息素矩阵和比值矩阵三个元素
#距离矩阵一旦生成不再改变,信息素矩阵会更新
class route_matrix:
def __init__(self,cityset):
self.dist_matrix = dist_matrix(cityset)
self.phe_matrix = phe_matrix()
for i in range(CITY_LEN):
self.dist_matrix[i][i] = 1
self.index_matrix = self.phe_matrix/self.dist_matrix
def update_index(self,pos1,pos2,num):
if num == 2:
up = 5.0
elif num == 3:
up = 1.0
else:
up = 3.0
self.index_matrix[pos1][pos2] += up/self.dist_matrix[pos1][pos2]
def info(self):
#print('当前路径的距离矩阵为:')
#print(self.dist_matrix)
print('当前路径的信息素矩阵为:')
print(self.phe_matrix)
print('当前路径的比值矩阵为:')
print(self.index_matrix)
#蚁群类,包含了蚂蚁和路程矩阵两个元素
class antcolony:
def __init__(self,ants,route_matrix):
self.ants = ants
self.matrix = route_matrix
self.best = []
self.worst = []
def info(self):
self.ants.info()
self.matrix.info()
def move_prob(self):
prob_lists = []
for ant in self.ants.antss:
temps = self.matrix.index_matrix[ant.position][:]
prob_list = []
for temp in temps:
prob_list.append(temp)
for Tabu in ant.Tabu_list:
prob_list[Tabu] = 0
new_list = [x/sum(prob_list) for x in prob_list]
prob_lists.append(new_list)
return prob_lists
def update_matrix(self,pos1,pos2):
if [pos1,pos2] in self.best or [pos2,pos1] in self.best:
self.matrix.phe_matrix[pos1][pos2] += 5.0/self.matrix.dist_matrix[pos1][pos2]
self.matrix.update_index(pos1,pos2,2)
elif [pos1,pos2] in self.worst or [pos2,pos1] in self.worst:
self.matrix.phe_matrix[pos1][pos2] += 1.0/self.matrix.dist_matrix[pos1][pos2]
self.matrix.update_index(pos1,pos2,3)
else:
self.matrix.phe_matrix[pos1][pos2] += 3.0/self.matrix.dist_matrix[pos1][pos2]
self.matrix.update_index(pos1,pos2,1)
def wholemove(self):
if len(self.ants.antss[0].Tabu_list) < 6:
prob_lists = self.move_prob()
turn_on = 0
else:
best_list = []
turn_on = 1
for i in range(ANT_NUMBER):
if turn_on == 0:
idx = np.random.choice(np.arange(CITY_LEN),p=prob_lists[i])
#print(i,"的当前位置为:",self.ants.antss[i].position+1)
#print(i,'选择的下一位置为:',idx+1)
last_pos = self.ants.antss[i].position
self.ants.antss[i].move(idx)
self.update_matrix(last_pos,idx)
else:
sums = sum(self.ants.antss[i].Tabu_list)
self.ants.antss[i].Tabu_list.append(21-sums)
best_list.append(self.ants.antss[i].Tabu_list)
last_pos = self.ants.antss[i].position
origin = self.ants.antss[i].Tabu_list[0]
self.ants.antss[i].move(origin)
self.update_matrix(last_pos,origin)
if turn_on == 1:
dist_list = [total_distance(pro_route(i)) for i in best_list]
self.best = decompose(best_list[np.argmin(dist_list)])
self.worst = decompose(best_list[np.argmax(dist_list)])
print('当前最优为:',self.best)
print('当前最不优为:',self.worst)
if __name__ == "__main__":
np.random.shuffle(CHENGSHI)
route = route_matrix(CHENGSHI)
ants = ants(ANT_NUMBER)
antcolony = antcolony(ants,route)
for count in range(MOVE_TIMES):
antcolony.wholemove()
matrix = antcolony.matrix.index_matrix
answer = find_route(matrix,CHENGSHI)
antcolony.info()
print_plot(answer)
禁忌搜索
参考博客1:https://blog.csdn.net/adkjb/article/details/81712969
参考博客2:https://blog.csdn.net/ChinaJane163/article/details/49095085
参考博客3:https://blog.csdn.net/tyhj_sf/article/details/54235550
参考博客4:https://blog.csdn.net/weixin_42528077/article/details/86762878
思维框架
算法实现
禁忌搜索算法实现:
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()
'''
下面是几个城市基本参数的设置,N_GENERATIONS是迭代的次数
禁忌长度为2,候选集合长度为6
'''
CHENGDU = [1,1]
SHANGHAI = [5,2]
XIAN = [2,3]
WUHAN = [3,2]
BEIJING = [4,3.5]
SHENZHEN = [3.5,0]
FUZHOU = [4.5,0.5]
CITY_LEN = 7
CHENGSHI = [CHENGDU,SHANGHAI,XIAN,WUHAN,BEIJING,SHENZHEN,FUZHOU]
N_GENERATIONS = 15
Tabu_list = [10,10]
#计算两个城市间的距离
def distance(city1,city2):
temp = [i-j for i,j in zip(city1,city2)]
return (sum([x**2 for x in temp]))**(1/2)
#计算整个周游下来的总路程,即适应度函数
def total_distance(cityset):
citycopy = cityset[:]
citycopy.append(cityset[0])
dist = 0
for i in range(len(cityset)):
dist += distance(citycopy[i],citycopy[i+1])
return dist
#产生候选集合,长度为6
def alter_cityset(cityset):
alterset=[]
for i in range(CITY_LEN - 1):
citys = cityset[:]
if i != CITY_LEN - 2:
citys[1+i],citys[2+i] = citys[2+i],citys[1+i]
else:
citys[1+i],citys[1] = citys[1],citys[1+i]
alterset.append(citys)
return alterset
#计算长度为6的候选集合中各个路径对应的总路程,即计算候选的适应度函数值
def set_to_distance(altercities):
dist = []
for altercity in altercities:
dist.append(total_distance(altercity))
return dist
#打印当前的路程情况
def print_plot(cityset):
x_list=[];y_list=[]
for city in cityset:
x_list.append(city[0])
y_list.append(city[1])
x_list.append(cityset[0][0])
y_list.append(cityset[0][1])
plt.plot(x_list,y_list)
plt.scatter(x_list,y_list, linewidth=1, alpha=0.6)
plt.scatter(x_list[0],y_list[0],color="red",marker="o")
plt.scatter(x_list[1],y_list[1],color="lawngreen",marker="o")
print('最优适应度为:',total_distance(cityset))
#完成禁忌表Tabu_list的变换
def swtich_tabu(number=0):
Tabu_list.pop(0)
Tabu_list.append(number)
#找到列表中第n小元素的索引
def find_min(list1=None,n=1):
temp = list1[:];count = 0
while count < n-1:
temp[np.argmin(temp)]=np.max(temp)
count += 1
return np.argmin(temp)
#这就是循环主体部分,不断更新目前最优路径和最优适应度
def explore(chengshi,optimization,route_best):
alter = alter_cityset(chengshi)
dis = set_to_distance(alter)
min_index = np.argmin(dis)
route_be = []
if dis[min_index] < optimization:
opti = dis[min_index]
route_be = city_now = alter[min_index]
swtich_tabu(min_index)
elif min_index not in Tabu_list:
[opti,route_be] = [optimization,route_best]
city_now = alter[min_index]
swtich_tabu(min_index)
else:
min2_index = find_min(dis,2)
if min2_index not in Tabu_list:
[opti,route_be] = [optimization,route_best]
city_now = alter[min2_index]
swtich_tabu(min2_index)
else:
min3_index = find_min(dis,3)
[opti,route_be] = [optimization,route_best]
city_now = alter[min3_index]
swtich_tabu(min3_index)
return [city_now,opti,route_be]
if __name__ == "__main__":
route_now = CHENGSHI
route_best = []
np.random.shuffle(route_now)
optimization = total_distance(CHENGSHI)
print('初始适应度:',optimization)
for count in range(N_GENERATIONS):
[route_now,optimization,route_best] = explore(route_now,optimization,route_best)
print('当前最优路径是:',route_now)
print('当前最优适应度是:',optimization)
[route_now,optimization,route_best] = explore(route_now,optimization,route_best)
print_plot(route_best)