python 尋找優(yōu)化使成本函數(shù)最小的最優(yōu)解的方法
更新時間：2017年12月28日 10:41:37 作者：欒鵬
這篇文章主要介紹了python 尋找優(yōu)化使成本函數(shù)最小的最優(yōu)解的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
今天來學習變量優(yōu)化問題。尋找使成本函數(shù)最小的題解。適用于題解相互獨立的情況，設計隨機優(yōu)化算法、爬山法、模擬退火算法、遺傳算法。
優(yōu)化問題的的精髓是：1、將題解轉(zhuǎn)化為數(shù)字序列化，可以寫出題解范圍。2、成本函數(shù)能返回值
問題場景：
所有乘客從不同的地方飛到同一個目的地，服務人員等待所有人到來以后將人一次性接走。
離開時，服務人員將人一次性帶到飛機場，所有乘客等待自己的航班離開。
要解決的問題：
如何設置乘客的到來和離開航班，以及接送機的時間，使得總代價最小。
將題解設為數(shù)字序列。
數(shù)字表示某人乘坐的第幾次航班，從0開始，例如[1,4,3,2,7,3,6,3,2]表示第1個人做第2個航班來，第5個航班走，第2個人做第4個航班來，第3個航班走
題解相互獨立：組團旅游問題，舉辦會議的人員接送問題
首先從網(wǎng)上采集航班信息，存儲到schedule.txt文件中。共6個起始點，和共同的目的地。每個起止點之間包含多道航班。在txt中記錄的就是起飛點、著陸點、起飛時間、著陸時間、價錢。
des_place,src6_place,6:19,8:13,239 src6_place,des_place,6:11,8:31,249 des_place,src6_place,8:04,10:59,136 src6_place,des_place,7:39,10:24,219 des_place,src6_place,9:31,11:43,210 src6_place,des_place,9:15,12:03,99 des_place,src6_place,11:07,13:24,171 src6_place,des_place,11:08,13:07,175 des_place,src6_place,12:31,14:02,234 src6_place,des_place,12:18,14:56,172 des_place,src6_place,14:05,15:47,226 src6_place,des_place,13:37,15:08,250 des_place,src6_place,15:07,17:21,129 src6_place,des_place,15:03,16:42,135 des_place,src6_place,16:35,18:56,144 src6_place,des_place,16:51,19:09,147 des_place,src6_place,18:25,20:34,205 src6_place,des_place,18:12,20:17,242 des_place,src6_place,20:05,21:44,172 src6_place,des_place,20:05,22:06,261 des_place,src5_place,6:03,8:43,219 src5_place,des_place,6:05,8:32,174 des_place,src5_place,7:50,10:08,164 src5_place,des_place,8:25,10:34,157 des_place,src5_place,9:11,10:42,172 src5_place,des_place,9:42,11:32,169 des_place,src5_place,10:33,13:11,132 src5_place,des_place,11:01,12:39,260 des_place,src5_place,12:08,14:47,231 src5_place,des_place,12:44,14:17,134 des_place,src5_place,14:19,17:09,190 src5_place,des_place,14:22,16:32,126 des_place,src5_place,15:04,17:23,189 src5_place,des_place,15:58,18:40,173 des_place,src5_place,17:06,20:00,95 src5_place,des_place,16:43,19:00,246 des_place,src5_place,18:33,20:22,143 src5_place,des_place,18:48,21:45,246 des_place,src5_place,19:32,21:25,160 src5_place,des_place,19:50,22:24,269 des_place,src4_place,6:33,9:14,172 src4_place,des_place,6:25,9:30,335 des_place,src4_place,8:23,11:07,143 src4_place,des_place,7:34,9:40,324 des_place,src4_place,9:25,12:46,295 src4_place,des_place,9:15,12:29,225 des_place,src4_place,11:08,14:38,262 src4_place,des_place,11:28,14:40,248 des_place,src4_place,12:37,15:05,170 src4_place,des_place,12:05,15:30,330 des_place,src4_place,14:08,16:09,232 src4_place,des_place,14:01,17:24,338 des_place,src4_place,15:23,18:49,150 src4_place,des_place,15:34,18:11,326 des_place,src4_place,16:50,19:26,304 src4_place,des_place,17:07,20:04,291 des_place,src4_place,18:07,21:30,355 src4_place,des_place,18:23,21:35,134 des_place,src4_place,20:27,23:42,169 src4_place,des_place,19:53,22:21,173 des_place,src1_place,6:39,8:09,86 src1_place,des_place,6:17,8:26,89 des_place,src1_place,8:23,10:28,149 src1_place,des_place,8:04,10:11,95 des_place,src1_place,9:58,11:18,130 src1_place,des_place,9:45,11:50,172 des_place,src1_place,10:33,12:03,74 src1_place,des_place,11:16,13:29,83 des_place,src1_place,12:08,14:05,142 src1_place,des_place,12:34,15:02,109 des_place,src1_place,13:39,15:30,74 src1_place,des_place,13:40,15:37,138 des_place,src1_place,15:25,16:58,62 src1_place,des_place,15:27,17:18,151 des_place,src1_place,17:03,18:03,103 src1_place,des_place,17:11,18:30,108 des_place,src1_place,18:24,20:49,124 src1_place,des_place,18:34,19:36,136 des_place,src1_place,19:58,21:23,142 src1_place,des_place,20:17,22:22,102 des_place,src2_place,6:09,9:49,414 src2_place,des_place,6:12,10:22,230 des_place,src2_place,7:57,11:15,347 src2_place,des_place,7:53,11:37,433 des_place,src2_place,9:49,13:51,229 src2_place,des_place,9:08,12:12,364 des_place,src2_place,10:51,14:16,256 src2_place,des_place,10:30,14:57,290 des_place,src2_place,12:20,16:34,500 src2_place,des_place,12:19,15:25,342 des_place,src2_place,14:20,17:32,332 src2_place,des_place,13:54,18:02,294 des_place,src2_place,15:49,20:10,497 src2_place,des_place,15:44,18:55,382 des_place,src2_place,17:14,20:59,277 src2_place,des_place,16:52,20:48,448 des_place,src2_place,18:44,22:42,351 src2_place,des_place,18:26,21:29,464 des_place,src2_place,19:57,23:15,512 src2_place,des_place,20:07,23:27,473 des_place,src3_place,6:58,9:01,238 src3_place,des_place,6:08,8:06,224 des_place,src3_place,8:19,11:16,122 src3_place,des_place,8:27,10:45,139 des_place,src3_place,9:58,12:56,249 src3_place,des_place,9:15,12:14,247 des_place,src3_place,10:32,13:16,139 src3_place,des_place,10:53,13:36,189 des_place,src3_place,12:01,13:41,267 src3_place,des_place,12:08,14:59,149 des_place,src3_place,13:37,15:33,142 src3_place,des_place,13:40,15:38,137 des_place,src3_place,15:50,18:45,243 src3_place,des_place,15:23,17:25,232 des_place,src3_place,16:33,18:15,253 src3_place,des_place,17:08,19:08,262 des_place,src3_place,18:17,21:04,259 src3_place,des_place,18:35,20:28,204 des_place,src3_place,19:46,21:45,214 src3_place,des_place,20:30,23:11,114
構(gòu)建6名游客的航班信息
# 人員的名稱和來源地信息
peoplelist = [('name1','src1_place'),
('name2','src2_place'),
('name3','src3_place'),
('name4','src4_place'),
('name5','src5_place'),
('name6','src6_place')]
# 目的機場
destination='des_place'
flights={} #加載所有航班信息。
# 查詢所有的航班信息
for line in open('schedule.txt'):
origin,dest,depart,arrive,price=line.strip().split(',') #源地址、目的地址、離開時間、到達時間、價格
flights.setdefault((origin,dest),[]) #航班信息已起止點為鍵值，每個起止點有多個航班
# 將航班信息添加到航班列表中
flights[(origin,dest)].append((depart,arrive,int(price))) #按時間順序擴展每次航班
為了實現(xiàn)優(yōu)化，我們將題解轉(zhuǎn)變?yōu)閿?shù)字序列，為了理解更加方便的理解數(shù)字序列代表的含義。實現(xiàn)一個函數(shù)，接受數(shù)字序列，打印輸出航班信息。
# 將數(shù)字序列轉(zhuǎn)換為航班，打印輸出。輸入為數(shù)字序列
def printschedule(r):
for d in range(int(len(r)/2)):
name=peoplelist[d][0] #人員名稱
origin=peoplelist[d][1] #人員來源地
out=flights[(origin,destination)][int(r[2*d])] #往程航班
ret=flights[(destination,origin)][int(r[2*d+1])] #返程航班
print('%10s %10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2]))
此場景我們要解決的問題就是尋找使花費最小的每位游客應該乘坐的往返航班。
我們定義一個成本函數(shù)代表我們需要花費的資金。
# 計算某個給定時間在一天中的分鐘數(shù)
def getminutes(t):
x = time.strptime(t, '%H:%M')
return x[3] * 60 + x[4]
# 成本函數(shù)。輸入為數(shù)字序列
def schedulecost(sol):
totalprice=0
latestarrival=0
earliestdep=24*60
for d in range(int(len(sol)/2)):
# 得到往返航班
origin=peoplelist[d][1] #獲取人員的來源地
outbound=flights[(origin,destination)][int(sol[2*d])] #獲取往程航班
returnf=flights[(destination,origin)][int(sol[2*d+1])] #獲取返程航班
# 總價格等于所有往返航班的價格之和
totalprice+=outbound[2]
totalprice+=returnf[2]
# 記錄最晚到達和最早離開的時間
if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])
# 接機服務：每個人必須在機場等待直到最后一個人到達位置
# 送機服務：他們必須同時達到機場，并等待他們的返程航班
totalwait=0
for d in range(int(len(sol)/2)):
origin=peoplelist[d][1]
outbound=flights[(origin,destination)][int(sol[2*d])]
returnf=flights[(destination,origin)][int(sol[2*d+1])]
totalwait+=latestarrival-getminutes(outbound[1])
totalwait+=getminutes(returnf[0])-earliestdep
# 這個題解要求多付一天的汽車出租費用么？如果是，則費用為50美元
if latestarrival>earliestdep: totalprice+=50
return totalprice+totalwait
1、隨機搜索算法：隨機選擇題解，計算成本值，成本值最小的題解為確定題解。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(0,1000):
# 創(chuàng)建隨機解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
#計算成本值
cost=costf(sol)
# 與目前得到的最優(yōu)解進行比較
if cost<best:
best=cost
bestr=sol
return sol #返回隨機最優(yōu)解
2、爬山法：對于成本函數(shù)連續(xù)的情況，題解向成本值減小的地方漸變，直到成本值不再變化。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。在只有一個極低點時最有效?？梢圆捎秒S機重復爬山法優(yōu)化。
def hillclimb(domain,costf):
# 創(chuàng)建一個隨機解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
# 主循環(huán)
while 1:
# 創(chuàng)建相鄰解的列表
neighbors=[]
for j in range(len(domain)): #在j等于0和末尾的時候存在問題
# 在每個方向上相對于原值偏離一點。每個方向上的偏離不相互影響
if sol[j]>domain[j][0]:
neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:]) #向近0偏移
if sol[j]<domain[j][1]:
neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:]) #遠0偏移
# 在相鄰解中尋找最優(yōu)解
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# 如果沒有更好的解，則退出循環(huán)。即尋找了極低點
if best==current:
break
return sol
3、模擬退火算法：概率性接收更優(yōu)解（更差解），時間越久，概率越大（越低）。
def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
# 隨機初始化值
vec=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]
while T>0.1:
# 選擇一個索引值
i=random.randint(0,len(domain)-1)
# 選擇一個改變索引值的方向
dir=random.randint(-step,step)
#創(chuàng)建一個代表題解的新列表，改變其中一個值
vecb=vec[:]
vecb[i]+=dir
if vecb[i]<domain[i][0]: vecb[i]=domain[i][0] #如果漸變不超出了題解的范圍
elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1] #如果漸變不超出了題解的范圍
# 計算當前成本與新的成本
ea=costf(vec)
eb=costf(vecb)
p=pow(math.e,(-eb-ea)/T)
# 它是更好的解么？或者是趨向最優(yōu)解的可能的臨界解么
if (eb<ea or random.random()<p):
vec=vecb
# 降低溫度
T=T*cool
return vec
4、遺傳算法：基因雜交（交叉）或基因變異。domain題解范圍，costf成本函數(shù)，popsize種群大小，step變異基因量，mutprob變異比例，elite優(yōu)秀基因者的比例，maxiter運行多少代。
def geneticoptimize(domain,costf,popsize=50,step=1,mutprob=0.2,elite=0.2,maxiter=100):
# 變異操作，存在變異失敗的情況
def mutate(vec):
i=random.randint(0,len(domain)-1)
if random.random()<0.5 and vec[i]>=domain[i][0]+step:
return vec[0:i]+[vec[i]-step]+vec[i+1:]
elif vec[i]<=domain[i][1]-step:
return vec[0:i]+[vec[i]+step]+vec[i+1:]
# 雜交操作（交叉）
def crossover(r1,r2):
i=random.randint(1,len(domain)-2)
return r1[0:i]+r2[i:]
# 構(gòu)建初始種群
pop=[]
for i in range(popsize): #隨機產(chǎn)生50個動物的種群
vec=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
pop.append(vec)
# 每一代有多少勝出者？
topelite=int(elite*popsize)
# 主循環(huán)
for i in range(maxiter):
scores=[(costf(v),v) for v in pop]
scores.sort()
ranked=[v for (s,v) in scores]
# 在種群中選出優(yōu)勝者
pop=ranked[0:topelite]
# 為優(yōu)秀基因者，添加變異和配對后的勝出者
while len(pop)<popsize:
if random.random()<mutprob: #變異所占的比例
# 變異
c=random.randint(0,topelite-1)
newanimal = mutate(ranked[c])
if newanimal!=None: #有可能存在變異死亡者
pop.append(newanimal)
else:
# 相互雜交。以后會遇到近親結(jié)婚的問題
c1=random.randint(0,topelite-1)
c2=random.randint(0,topelite-1)
newanimal = crossover(ranked[c1], ranked[c2])
pop.append(newanimal)
# 打印當前最優(yōu)解和成本
# print(scores[0])
return scores[0][1] #返回最優(yōu)解
測試程序
if __name__=="__main__": #只有在執(zhí)行當前模塊時才會運行此函數(shù)
print(flights) #打印所有航班信息
domain=[]
for start_stop in flights: #查詢每個起止點的航班個數(shù)
domain.append((0,len(flights[start_stop])-1)) #獲取題解范圍，兩邊必區(qū)間（航班范圍的數(shù)據(jù)序列）
# domain=[(0,9)]*(len(peoplelist)*2)
print(domain)
s=randomoptimize(domain,schedulecost) # 隨機搜索法，尋找最優(yōu)題解
print(s)
printschedule(s) #打印最優(yōu)航班信息
s = hillclimb(domain, schedulecost) # 爬山法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
s = annealingoptimize(domain, schedulecost) # 模擬退火算法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
s = geneticoptimize(domain, schedulecost) # 遺傳算法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
全部代碼optimization.py
# 優(yōu)化算法。尋找使成本函數(shù)最小的題解。
import time
import random
import math
# 問題場景：
# 所有乘客從不同的地方飛到同一個目的地，服務人員等待所有人到來以后將人一次性接走。
# 離開時，服務人員將人一次性帶到飛機場，所有乘客等待自己的航班離開。
# 要解決的問題：
# 如何設置乘客的到來和離開航班，以及接送機的時間，使得總代價最小。
# 將題解設為數(shù)字序列。
# 數(shù)字表示某人乘坐的第幾次航班，從0開始，例如[1,4,3,2,7,3,6,3,2]表示第1個人做第2個航班來，第5個航班走，第2個人做第4個航班來，第3個航班走
# 題解相互獨立：組團旅游問題，舉辦會議的人員接送問題
# 人員的名稱和來源地信息
peoplelist = [('name1','src1_place'),
('name2','src2_place'),
('name3','src3_place'),
('name4','src4_place'),
('name5','src5_place'),
('name6','src6_place')]
# 目的機場
destination='des_place'
flights={} #加載所有航班信息。
# 查詢所有的航班信息
for line in open('schedule.txt'):
origin,dest,depart,arrive,price=line.strip().split(',') #源地址、目的地址、離開時間、到達時間、價格
flights.setdefault((origin,dest),[]) #航班信息已起止點為鍵值，每個起止點有多個航班
# 將航班信息添加到航班列表中
flights[(origin,dest)].append((depart,arrive,int(price))) #按時間順序擴展每次航班
# 將數(shù)字序列轉(zhuǎn)換為航班，打印輸出。輸入為數(shù)字序列
def printschedule(r):
for d in range(int(len(r)/2)):
name=peoplelist[d][0] #人員名稱
origin=peoplelist[d][1] #人員來源地
out=flights[(origin,destination)][int(r[2*d])] #往程航班
ret=flights[(destination,origin)][int(r[2*d+1])] #返程航班
print('%10s %10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2]))
# 計算某個給定時間在一天中的分鐘數(shù)
def getminutes(t):
x = time.strptime(t, '%H:%M')
return x[3] * 60 + x[4]
# 成本函數(shù)。輸入為數(shù)字序列
def schedulecost(sol):
totalprice=0
latestarrival=0
earliestdep=24*60
for d in range(int(len(sol)/2)):
# 得到往返航班
origin=peoplelist[d][1] #獲取人員的來源地
outbound=flights[(origin,destination)][int(sol[2*d])] #獲取往程航班
returnf=flights[(destination,origin)][int(sol[2*d+1])] #獲取返程航班
# 總價格等于所有往返航班的價格之和
totalprice+=outbound[2]
totalprice+=returnf[2]
# 記錄最晚到達和最早離開的時間
if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])
# 接機服務：每個人必須在機場等待直到最后一個人到達位置
# 送機服務：他們必須同時達到機場，并等待他們的返程航班
totalwait=0
for d in range(int(len(sol)/2)):
origin=peoplelist[d][1]
outbound=flights[(origin,destination)][int(sol[2*d])]
returnf=flights[(destination,origin)][int(sol[2*d+1])]
totalwait+=latestarrival-getminutes(outbound[1])
totalwait+=getminutes(returnf[0])-earliestdep
# 這個題解要求多付一天的汽車出租費用么？如果是，則費用為50美元
if latestarrival>earliestdep: totalprice+=50
return totalprice+totalwait
# 隨機搜索算法：隨機選擇題解，計算成本值，成本值最小的題解為確定題解。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(0,1000):
# 創(chuàng)建隨機解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
#計算成本值
cost=costf(sol)
# 與目前得到的最優(yōu)解進行比較
if cost<best:
best=cost
bestr=sol
return sol #返回隨機最優(yōu)解
# 爬山法：對于成本函數(shù)連續(xù)的情況，題解向成本值減小的地方漸變，直到成本值不再變化。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。
# 在只有一個極低點時最有效?？梢圆捎秒S機重復爬山法優(yōu)化
def hillclimb(domain,costf):
# 創(chuàng)建一個隨機解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
# 主循環(huán)
while 1:
# 創(chuàng)建相鄰解的列表
neighbors=[]
for j in range(len(domain)): #在j等于0和末尾的時候存在問題
# 在每個方向上相對于原值偏離一點。每個方向上的偏離不相互影響
if sol[j]>domain[j][0]:
neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:]) #向近0偏移
if sol[j]<domain[j][1]:
neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:]) #遠0偏移
# 在相鄰解中尋找最優(yōu)解
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# 如果沒有更好的解，則退出循環(huán)。即尋找了極低點
if best==current:
break
return sol
# 模擬退火算法：概率性接收更優(yōu)解（更差解），時間越久，概率越大（越低）。
def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
# 隨機初始化值
vec=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]
while T>0.1:
# 選擇一個索引值
i=random.randint(0,len(domain)-1)
# 選擇一個改變索引值的方向
dir=random.randint(-step,step)
#創(chuàng)建一個代表題解的新列表，改變其中一個值
vecb=vec[:]
vecb[i]+=dir
if vecb[i]<domain[i][0]: vecb[i]=domain[i][0] #如果漸變不超出了題解的范圍
elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1] #如果漸變不超出了題解的范圍
# 計算當前成本與新的成本
ea=costf(vec)
eb=costf(vecb)
p=pow(math.e,(-eb-ea)/T)
# 它是更好的解么？或者是趨向最優(yōu)解的可能的臨界解么
if (eb<ea or random.random()<p):
vec=vecb
# 降低溫度
T=T*cool
return vec
# 遺傳算法：基因雜交（交叉）或基因變異。domain題解范圍，costf成本函數(shù)，popsize種群大小，step變異基因量，mutprob變異比例，elite優(yōu)秀基因者的比例，maxiter運行多少代
def geneticoptimize(domain,costf,popsize=50,step=1,mutprob=0.2,elite=0.2,maxiter=100):
# 變異操作，存在變異失敗的情況
def mutate(vec):
i=random.randint(0,len(domain)-1)
if random.random()<0.5 and vec[i]>=domain[i][0]+step:
return vec[0:i]+[vec[i]-step]+vec[i+1:]
elif vec[i]<=domain[i][1]-step:
return vec[0:i]+[vec[i]+step]+vec[i+1:]
# 雜交操作（交叉）
def crossover(r1,r2):
i=random.randint(1,len(domain)-2)
return r1[0:i]+r2[i:]
# 構(gòu)建初始種群
pop=[]
for i in range(popsize): #隨機產(chǎn)生50個動物的種群
vec=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
pop.append(vec)
# 每一代有多少勝出者？
topelite=int(elite*popsize)
# 主循環(huán)
for i in range(maxiter):
scores=[(costf(v),v) for v in pop]
scores.sort()
ranked=[v for (s,v) in scores]
# 在種群中選出優(yōu)勝者
pop=ranked[0:topelite]
# 為優(yōu)秀基因者，添加變異和配對后的勝出者
while len(pop)<popsize:
if random.random()<mutprob: #變異所占的比例
# 變異
c=random.randint(0,topelite-1)
newanimal = mutate(ranked[c])
if newanimal!=None: #有可能存在變異死亡者
pop.append(newanimal)
else:
# 相互雜交。以后會遇到近親結(jié)婚的問題
c1=random.randint(0,topelite-1)
c2=random.randint(0,topelite-1)
newanimal = crossover(ranked[c1], ranked[c2])
pop.append(newanimal)
# 打印當前最優(yōu)解和成本
# print(scores[0])
return scores[0][1] #返回最優(yōu)解
if __name__=="__main__": #只有在執(zhí)行當前模塊時才會運行此函數(shù)
print(flights) #打印所有航班信息
domain=[]
for start_stop in flights: #查詢每個起止點的航班個數(shù)
domain.append((0,len(flights[start_stop])-1)) #獲取題解范圍，兩邊必區(qū)間（航班范圍的數(shù)據(jù)序列）
# domain=[(0,9)]*(len(peoplelist)*2)
print(domain)
s=randomoptimize(domain,schedulecost) # 隨機搜索法，尋找最優(yōu)題解
print(s)
printschedule(s) #打印最優(yōu)航班信息
s = hillclimb(domain, schedulecost) # 爬山法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
s = annealingoptimize(domain, schedulecost) # 模擬退火算法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
s = geneticoptimize(domain, schedulecost) # 遺傳算法，尋找最優(yōu)題解
print(s)
printschedule(s) # 打印最優(yōu)航班信息
使用優(yōu)化算法解決房間住宿問題
場景：每個房間有兩個床位，每個學生有自己首選房間和次選房間（只選房間，不選床位）。將所有學生安排到所有房間
目標：在盡量滿足學生的選擇的情況下，為學生安排宿舍。
將題解轉(zhuǎn)化為數(shù)字間皆有聯(lián)系的數(shù)字序列?？梢宰屆總€數(shù)字代表可選床位的第幾個，索引從0開始
例如：[0,2,1,1,1,2,0,1]表示第1個人選可選床位的第1個，第2個人選剩余可選床位的第3個床位，第3個人選剩余可選床位的第2個。。。
測試代碼
# 利用之前設計好的優(yōu)化算法，解決涉及偏好的優(yōu)化問題。1、將題解轉(zhuǎn)化為數(shù)字序列化，可以寫出題解范圍。2、成本函數(shù)能返回值
import random
import math
import optimization
# 場景：每個房間有兩個床位，每個學生有自己首選房間和次選房間（只選房間，不選床位）。將所有學生安排到所有房間
# 目標：在盡量滿足學生的選擇的情況下，為學生安排宿舍
# 將題解轉(zhuǎn)化為數(shù)字間沒有聯(lián)系的數(shù)字序列?？梢宰屆總€數(shù)字代表可選床位的第幾個，索引從0開始
# 例如：[0,2,1,1,1,2,0,1]表示第1個人選可選床位的第1個，第2個人選剩余可選床位的第3個床位，第3個人選剩余可選床位的第2個。。。
# 代表宿舍，每個宿舍有兩個床位。5個房間
dorms=['Zeus','Athena','Hercules','Bacchus','Pluto']
# 代表學生及其首選房間和次選房間。10個人
prefs=[('Toby', ('Bacchus', 'Hercules')),
('Steve', ('Zeus', 'Pluto')),
('Karen', ('Athena', 'Zeus')),
('Sarah', ('Zeus', 'Pluto')),
('Dave', ('Athena', 'Bacchus')),
('Jeff', ('Hercules', 'Pluto')),
('Fred', ('Pluto', 'Athena')),
('Suzie', ('Bacchus', 'Hercules')),
('Laura', ('Bacchus', 'Hercules')),
('James', ('Hercules', 'Athena'))]
# [(0,9),(0,8),(0,7),(0,6),...,(0,0)] 題解范圍。因為前面選擇了一個，后面的可選范圍就會變少
domain=[(0,(len(dorms)*2)-i-1) for i in range(0,len(dorms)*2)] #題解的可選范圍
# 打印輸出題解。輸入為題解序列
def printsolution(vec):
slots=[]
# 為每個宿舍鍵兩個槽
for i in range(len(dorms)): slots+=[i,i]
# 遍歷每一名學生的安置情況
for i in range(len(vec)):
x=int(vec[i])
# 從剩余槽中選擇
dorm=dorms[slots[x]]
# 輸出學生及其被分配的宿舍
print(prefs[i][0],dorm)
# 刪除該槽，這樣后面的數(shù)字列表才能正確翻譯成“剩余床位”
del slots[x]
# 成本函數(shù)：
def dormcost(vec):
cost=0
# 創(chuàng)建一個槽序列
slots=[0,0,1,1,2,2,3,3,4,4]
# 遍歷每一名學生
for i in range(len(vec)):
x=int(vec[i])
dorm=dorms[slots[x]]
pref=prefs[i][1]
# 首選成本值為0，次選成本值為1
if pref[0]==dorm: cost+=0
elif pref[1]==dorm: cost+=1
else: cost+=3
# 不在選擇之列則成本值為3
# 刪除選中的槽
del slots[x]
return cost
if __name__=="__main__": #只有在執(zhí)行當前模塊時才會運行此函數(shù)
print(domain)
s = optimization.randomoptimize(domain, dormcost) # 隨機搜索法，尋找最優(yōu)題解
print(s)
printsolution(s) # 打印最優(yōu)解代表的含義
s = optimization.hillclimb(domain, dormcost) # 爬山法，尋找最優(yōu)題解
print(s)
printsolution(s) # 打印最優(yōu)解代表的含義
s = optimization.annealingoptimize(domain, dormcost) # 模擬退火算法，尋找最優(yōu)題解
print(s)
printsolution(s) # 打印最優(yōu)解代表的含義
s = optimization.geneticoptimize(domain, dormcost) # 遺傳算法，尋找最優(yōu)題解
print(s)
printsolution(s) # 打印最優(yōu)解代表的含義
使用優(yōu)化算法解決繪制關系網(wǎng)問題
場景：在繪制關系網(wǎng)圖中，每個人在圖中都有位置x，y坐標，在有關聯(lián)的兩個人中間添加連線。
目標：是所有連線的交叉數(shù)最少
將題解轉(zhuǎn)化為數(shù)字間沒有聯(lián)系的數(shù)字序列。可以讓每個數(shù)字代表人物在圖形中的位置x，y
例如：[200,120,250,230..]表示第1個人坐標為200,120，第2個人坐標為250,230…
測試代碼
# 將優(yōu)化算法應用到繪制關系網(wǎng)圖中，使得交叉線最少
import math
import optimization
# 場景：在繪制關系網(wǎng)圖中，每個人在圖中都有位置x，y坐標，在有關聯(lián)的兩個人中間添加連線。
# 目標：是所有連線的交叉數(shù)最少
# 將題解轉(zhuǎn)化為數(shù)字間沒有聯(lián)系的數(shù)字序列?？梢宰屆總€數(shù)字代表人物在圖形中的位置x，y
# 例如：[200,120,250,230..]表示第1個人坐標為200,120，第2個人坐標為250,230...
# 關系網(wǎng)中涉及的人員
people=['Charlie','Augustus','Veruca','Violet','Mike','Joe','Willy','Miranda']
# 關聯(lián)關系
links=[('Augustus', 'Willy'),
('Mike', 'Joe'),
('Miranda', 'Mike'),
('Violet', 'Augustus'),
('Miranda', 'Willy'),
('Charlie', 'Mike'),
('Veruca', 'Joe'),
('Miranda', 'Augustus'),
('Willy', 'Augustus'),
('Joe', 'Charlie'),
('Veruca', 'Augustus'),
('Miranda', 'Joe')]
# 計算交叉線，作為成本函數(shù)
def crosscount(v):
# 將數(shù)字序列轉(zhuǎn)化為一個person:(x,y)的字典
loc=dict([(people[i],(v[i*2],v[i*2+1])) for i in range(0,len(people))])
total=0
# 遍歷每一對連線
for i in range(len(links)):
for j in range(i+1,len(links)):
# 獲取坐標位置
(x1,y1),(x2,y2)=loc[links[i][0]],loc[links[i][1]]
(x3,y3),(x4,y4)=loc[links[j][0]],loc[links[j][1]]
den=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
# 如果兩線平行，則den==0。兩條線是線段，不是直線
if den==0: continue
# 否則，ua與ub就是兩條交叉線的分數(shù)值。
# line where they cross
ua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den
ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den
# 如果兩條線的分數(shù)值介于0和1之間，則兩線彼此交叉
if ua>0 and ua<1 and ub>0 and ub<1:
total+=1
for i in range(len(people)):
for j in range(i+1,len(people)):
# 獲取兩個節(jié)點的位置
(x1,y1),(x2,y2)=loc[people[i]],loc[people[j]]
# 獲取兩節(jié)點之間的距離
dist=math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
# 對間距小于50個像素的節(jié)點進行判罰
if dist<50:
total+=(1.0-(dist/50.0))
return total
#畫圖，繪制網(wǎng)絡
from PIL import Image,ImageDraw
def drawnetwork(sol):
# 建立image對象
img=Image.new('RGB',(400,400),(255,255,255))
draw=ImageDraw.Draw(img)
# 建立標識位置信息的字典
pos=dict([(people[i],(sol[i*2],sol[i*2+1])) for i in range(0,len(people))])
for (a,b) in links:
draw.line((pos[a],pos[b]),fill=(255,0,0))
for n,p in pos.items():
draw.text(p,n,(0,0,0))
img.show()
domain=[(10,370)]*(len(people)*2) #設定題解范圍
if __name__=="__main__": #只有在執(zhí)行當前模塊時才會運行此函數(shù)
print(domain)
s = optimization.randomoptimize(domain, crosscount) # 隨機搜索法，尋找最優(yōu)題解
print(s)
drawnetwork(s) # 繪制關系網(wǎng)
s = optimization.hillclimb(domain, crosscount) # 爬山法，尋找最優(yōu)題解
print(s)
drawnetwork(s) # 繪制關系網(wǎng)
s = optimization.annealingoptimize(domain, crosscount) # 模擬退火算法，尋找最優(yōu)題解
print(s)
drawnetwork(s) # 繪制關系網(wǎng)
s = optimization.geneticoptimize(domain, crosscount) # 遺傳算法，尋找最優(yōu)題解
print(s)
drawnetwork(s) # 繪制關系網(wǎng)
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了Python讀取GSMap數(shù)據(jù)的問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
這篇文章主要介紹了PyTorch預訓練Bert模型的示例，幫助大家更好的進行機器學習，訓練模型，感興趣的朋友可以了解下2020-11-11
PyTorch實現(xiàn)重寫/改寫Dataset并載入Dataloader
這篇文章主要介紹了PyTorch實現(xiàn)重寫/改寫Dataset并載入Dataloader，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-07-07
這篇文章主要為大家介紹了Python實現(xiàn)管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
盤點20個Python數(shù)據(jù)科學庫神器打造數(shù)據(jù)魔法世界
數(shù)據(jù)科學家和分析師常常使用?Python?來處理數(shù)據(jù)、進行分析和可視化,Python生態(tài)系統(tǒng)中有許多庫,但有一些庫是數(shù)據(jù)科學家日常工作中必不可少的,本文將深入介紹20個重要的Python?庫,包括示例代碼和用例2024-01-01
Python實現(xiàn)采用進度條實時顯示處理進度的方法
這篇文章主要介紹了Python實現(xiàn)采用進度條實時顯示處理進度的方法,涉及Python數(shù)學運算結(jié)合時間函數(shù)顯示進度效果的相關操作技巧,需要的朋友可以參考下2017-12-12
手把手教你將Flask應用封裝成Docker服務的實現(xiàn)
這篇文章主要介紹了手把手教你將Flask應用封裝成Docker服務，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
這篇文章主要介紹了Python如何使用input函數(shù)獲取輸入,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
本文主要介紹了python遞歸算法，包含無限遞歸,正常遞歸,階乘等，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2024-02-02
這篇文章主要介紹了Pytorch 實現(xiàn)變量類型轉(zhuǎn)換操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05