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

# 人員的名稱和來(lái)源地信息
peoplelist = [('name1','src1_place'),
       ('name2','src2_place'),
       ('name3','src3_place'),
       ('name4','src4_place'),
       ('name5','src5_place'),
       ('name6','src6_place')]
# 目的機(jī)場(chǎng)
destination='des_place'

flights={} #加載所有航班信息。
# 查詢所有的航班信息
for line in open('schedule.txt'):
  origin,dest,depart,arrive,price=line.strip().split(',') #源地址、目的地址、離開時(shí)間、到達(dá)時(shí)間、價(jià)格
  flights.setdefault((origin,dest),[])  #航班信息已起止點(diǎn)為鍵值，每個(gè)起止點(diǎn)有多個(gè)航班

  # 將航班信息添加到航班列表中
  flights[(origin,dest)].append((depart,arrive,int(price))) #按時(shí)間順序擴(kuò)展每次航班

# 將數(shù)字序列轉(zhuǎn)換為航班，打印輸出。輸入為數(shù)字序列
def printschedule(r):
  for d in range(int(len(r)/2)):
    name=peoplelist[d][0]  #人員名稱
    origin=peoplelist[d][1] #人員來(lái)源地
    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]))

# 計(jì)算某個(gè)給定時(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] #獲取人員的來(lái)源地
    outbound=flights[(origin,destination)][int(sol[2*d])] #獲取往程航班
    returnf=flights[(destination,origin)][int(sol[2*d+1])] #獲取返程航班

    # 總價(jià)格等于所有往返航班的價(jià)格之和
    totalprice+=outbound[2]
    totalprice+=returnf[2]

    # 記錄最晚到達(dá)和最早離開的時(shí)間
    if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
    if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

  # 接機(jī)服務(wù)：每個(gè)人必須在機(jī)場(chǎng)等待直到最后一個(gè)人到達(dá)位置
  # 送機(jī)服務(wù)：他們必須同時(shí)達(dá)到機(jī)場(chǎng)，并等待他們的返程航班
  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

    # 這個(gè)題解要求多付一天的汽車出租費(fèi)用么？如果是，則費(fèi)用為50美元
  if latestarrival>earliestdep: totalprice+=50

  return totalprice+totalwait

def randomoptimize(domain,costf):
  best=999999999
  bestr=None
  for i in range(0,1000):
    # 創(chuàng)建隨機(jī)解
    sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
    #計(jì)算成本值
    cost=costf(sol)

    # 與目前得到的最優(yōu)解進(jìn)行比較
    if cost<best:
      best=cost
      bestr=sol
  return sol #返回隨機(jī)最優(yōu)解

def hillclimb(domain,costf):
  # 創(chuàng)建一個(gè)隨機(jī)解
  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和末尾的時(shí)候存在問(wèn)題
      # 在每個(gè)方向上相對(duì)于原值偏離一點(diǎn)。每個(gè)方向上的偏離不相互影響
      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:]) #遠(yuǎn)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]

    # 如果沒(méi)有更好的解，則退出循環(huán)。即尋找了極低點(diǎn)
    if best==current:
      break
  return sol

def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
  # 隨機(jī)初始化值
  vec=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]

  while T>0.1:
    # 選擇一個(gè)索引值
    i=random.randint(0,len(domain)-1)

    # 選擇一個(gè)改變索引值的方向
    dir=random.randint(-step,step)

    #創(chuàng)建一個(gè)代表題解的新列表，改變其中一個(gè)值
    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] #如果漸變不超出了題解的范圍

    # 計(jì)算當(dāng)前成本與新的成本
    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

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):  #隨機(jī)產(chǎn)生50個(gè)動(dòng)物的種群
    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)秀基因者，添加變異和配對(duì)后的勝出者
    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:

        # 相互雜交。以后會(huì)遇到近親結(jié)婚的問(wèn)題
        c1=random.randint(0,topelite-1)
        c2=random.randint(0,topelite-1)
        newanimal = crossover(ranked[c1], ranked[c2])
        pop.append(newanimal)

    # 打印當(dāng)前最優(yōu)解和成本
    # print(scores[0])
  return scores[0][1] #返回最優(yōu)解

if __name__=="__main__":   #只有在執(zhí)行當(dāng)前模塊時(shí)才會(huì)運(yùn)行此函數(shù)
  print(flights)  #打印所有航班信息
  domain=[]
  for start_stop in flights:       #查詢每個(gè)起止點(diǎn)的航班個(gè)數(shù)
    domain.append((0,len(flights[start_stop])-1))  #獲取題解范圍，兩邊必區(qū)間（航班范圍的數(shù)據(jù)序列）

  # domain=[(0,9)]*(len(peoplelist)*2)
  print(domain)
  s=randomoptimize(domain,schedulecost) # 隨機(jī)搜索法，尋找最優(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)化算法。尋找使成本函數(shù)最小的題解。
import time
import random
import math
# 問(wèn)題場(chǎng)景：
# 所有乘客從不同的地方飛到同一個(gè)目的地，服務(wù)人員等待所有人到來(lái)以后將人一次性接走。
# 離開時(shí)，服務(wù)人員將人一次性帶到飛機(jī)場(chǎng)，所有乘客等待自己的航班離開。
# 要解決的問(wèn)題：
# 如何設(shè)置乘客的到來(lái)和離開航班，以及接送機(jī)的時(shí)間，使得總代價(jià)最小。
# 將題解設(shè)為數(shù)字序列。
# 數(shù)字表示某人乘坐的第幾次航班，從0開始，例如[1,4,3,2,7,3,6,3,2]表示第1個(gè)人做第2個(gè)航班來(lái)，第5個(gè)航班走，第2個(gè)人做第4個(gè)航班來(lái)，第3個(gè)航班走
# 題解相互獨(dú)立：組團(tuán)旅游問(wèn)題，舉辦會(huì)議的人員接送問(wèn)題
# 人員的名稱和來(lái)源地信息
peoplelist = [('name1','src1_place'),
       ('name2','src2_place'),
       ('name3','src3_place'),
       ('name4','src4_place'),
       ('name5','src5_place'),
       ('name6','src6_place')]
# 目的機(jī)場(chǎng)
destination='des_place'

flights={} #加載所有航班信息。
# 查詢所有的航班信息
for line in open('schedule.txt'):
  origin,dest,depart,arrive,price=line.strip().split(',') #源地址、目的地址、離開時(shí)間、到達(dá)時(shí)間、價(jià)格
  flights.setdefault((origin,dest),[])  #航班信息已起止點(diǎn)為鍵值，每個(gè)起止點(diǎn)有多個(gè)航班

  # 將航班信息添加到航班列表中
  flights[(origin,dest)].append((depart,arrive,int(price))) #按時(shí)間順序擴(kuò)展每次航班

# 將數(shù)字序列轉(zhuǎn)換為航班，打印輸出。輸入為數(shù)字序列
def printschedule(r):
  for d in range(int(len(r)/2)):
    name=peoplelist[d][0]  #人員名稱
    origin=peoplelist[d][1] #人員來(lái)源地
    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]))

# 計(jì)算某個(gè)給定時(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] #獲取人員的來(lái)源地
    outbound=flights[(origin,destination)][int(sol[2*d])] #獲取往程航班
    returnf=flights[(destination,origin)][int(sol[2*d+1])] #獲取返程航班

    # 總價(jià)格等于所有往返航班的價(jià)格之和
    totalprice+=outbound[2]
    totalprice+=returnf[2]

    # 記錄最晚到達(dá)和最早離開的時(shí)間
    if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
    if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

  # 接機(jī)服務(wù)：每個(gè)人必須在機(jī)場(chǎng)等待直到最后一個(gè)人到達(dá)位置
  # 送機(jī)服務(wù)：他們必須同時(shí)達(dá)到機(jī)場(chǎng)，并等待他們的返程航班
  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

    # 這個(gè)題解要求多付一天的汽車出租費(fèi)用么？如果是，則費(fèi)用為50美元
  if latestarrival>earliestdep: totalprice+=50

  return totalprice+totalwait

# 隨機(jī)搜索算法：隨機(jī)選擇題解，計(jì)算成本值，成本值最小的題解為確定題解。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。
def randomoptimize(domain,costf):
  best=999999999
  bestr=None
  for i in range(0,1000):
    # 創(chuàng)建隨機(jī)解
    sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
    #計(jì)算成本值
    cost=costf(sol)

    # 與目前得到的最優(yōu)解進(jìn)行比較
    if cost<best:
      best=cost
      bestr=sol
  return sol #返回隨機(jī)最優(yōu)解


# 爬山法：對(duì)于成本函數(shù)連續(xù)的情況，題解向成本值減小的地方漸變，直到成本值不再變化。domain為題解范圍（可選航班范圍），costf為成本函數(shù)。
# 在只有一個(gè)極低點(diǎn)時(shí)最有效。可以采用隨機(jī)重復(fù)爬山法優(yōu)化
def hillclimb(domain,costf):
  # 創(chuàng)建一個(gè)隨機(jī)解
  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和末尾的時(shí)候存在問(wèn)題
      # 在每個(gè)方向上相對(duì)于原值偏離一點(diǎn)。每個(gè)方向上的偏離不相互影響
      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:]) #遠(yuǎn)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]

    # 如果沒(méi)有更好的解，則退出循環(huán)。即尋找了極低點(diǎn)
    if best==current:
      break
  return sol

# 模擬退火算法：概率性接收更優(yōu)解（更差解），時(shí)間越久，概率越大（越低）。
def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
  # 隨機(jī)初始化值
  vec=[float(random.randint(domain[i][0],domain[i][1])) for i in range(len(domain))]
  while T>0.1:
    # 選擇一個(gè)索引值
    i=random.randint(0,len(domain)-1)

    # 選擇一個(gè)改變索引值的方向
    dir=random.randint(-step,step)

    #創(chuàng)建一個(gè)代表題解的新列表，改變其中一個(gè)值
    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] #如果漸變不超出了題解的范圍

    # 計(jì)算當(dāng)前成本與新的成本
    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運(yùn)行多少代
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):  #隨機(jī)產(chǎn)生50個(gè)動(dòng)物的種群
    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)秀基因者，添加變異和配對(duì)后的勝出者
    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:

        # 相互雜交。以后會(huì)遇到近親結(jié)婚的問(wèn)題
        c1=random.randint(0,topelite-1)
        c2=random.randint(0,topelite-1)
        newanimal = crossover(ranked[c1], ranked[c2])
        pop.append(newanimal)

    # 打印當(dāng)前最優(yōu)解和成本
    # print(scores[0])
  return scores[0][1] #返回最優(yōu)解

if __name__=="__main__":   #只有在執(zhí)行當(dāng)前模塊時(shí)才會(huì)運(yùn)行此函數(shù)
  print(flights)  #打印所有航班信息
  domain=[]
  for start_stop in flights:       #查詢每個(gè)起止點(diǎn)的航班個(gè)數(shù)
    domain.append((0,len(flights[start_stop])-1))  #獲取題解范圍，兩邊必區(qū)間（航班范圍的數(shù)據(jù)序列）

  # domain=[(0,9)]*(len(peoplelist)*2)
  print(domain)
  s=randomoptimize(domain,schedulecost) # 隨機(jī)搜索法，尋找最優(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)航班信息

# 利用之前設(shè)計(jì)好的優(yōu)化算法，解決涉及偏好的優(yōu)化問(wèn)題。1、將題解轉(zhuǎn)化為數(shù)字序列化，可以寫出題解范圍。2、成本函數(shù)能返回值
import random
import math
import optimization

# 場(chǎng)景：每個(gè)房間有兩個(gè)床位，每個(gè)學(xué)生有自己首選房間和次選房間（只選房間，不選床位）。將所有學(xué)生安排到所有房間
# 目標(biāo)：在盡量滿足學(xué)生的選擇的情況下，為學(xué)生安排宿舍

# 將題解轉(zhuǎn)化為數(shù)字間沒(méi)有聯(lián)系的數(shù)字序列?？梢宰屆總€(gè)數(shù)字代表可選床位的第幾個(gè)，索引從0開始
# 例如：[0,2,1,1,1,2,0,1]表示第1個(gè)人選可選床位的第1個(gè)，第2個(gè)人選剩余可選床位的第3個(gè)床位，第3個(gè)人選剩余可選床位的第2個(gè)。。。

# 代表宿舍，每個(gè)宿舍有兩個(gè)床位。5個(gè)房間
dorms=['Zeus','Athena','Hercules','Bacchus','Pluto']

# 代表學(xué)生及其首選房間和次選房間。10個(gè)人
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)]  題解范圍。因?yàn)榍懊孢x擇了一個(gè)，后面的可選范圍就會(huì)變少
domain=[(0,(len(dorms)*2)-i-1) for i in range(0,len(dorms)*2)]  #題解的可選范圍


# 打印輸出題解。輸入為題解序列
def printsolution(vec):
 slots=[]
 # 為每個(gè)宿舍鍵兩個(gè)槽
 for i in range(len(dorms)): slots+=[i,i]

 # 遍歷每一名學(xué)生的安置情況
 for i in range(len(vec)):
  x=int(vec[i])

  # 從剩余槽中選擇
  dorm=dorms[slots[x]]
  # 輸出學(xué)生及其被分配的宿舍
  print(prefs[i][0],dorm)
  # 刪除該槽，這樣后面的數(shù)字列表才能正確翻譯成“剩余床位”
  del slots[x]

# 成本函數(shù)：
def dormcost(vec):
 cost=0
 # 創(chuàng)建一個(gè)槽序列
 slots=[0,0,1,1,2,2,3,3,4,4]

 # 遍歷每一名學(xué)生
 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í)行當(dāng)前模塊時(shí)才會(huì)運(yùn)行此函數(shù)
  print(domain)
  s = optimization.randomoptimize(domain, dormcost) # 隨機(jī)搜索法，尋找最優(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)化算法應(yīng)用到繪制關(guān)系網(wǎng)圖中，使得交叉線最少
import math
import optimization
# 場(chǎng)景：在繪制關(guān)系網(wǎng)圖中，每個(gè)人在圖中都有位置x，y坐標(biāo)，在有關(guān)聯(lián)的兩個(gè)人中間添加連線。
# 目標(biāo)：是所有連線的交叉數(shù)最少
# 將題解轉(zhuǎn)化為數(shù)字間沒(méi)有聯(lián)系的數(shù)字序列?？梢宰屆總€(gè)數(shù)字代表人物在圖形中的位置x，y
# 例如：[200,120,250,230..]表示第1個(gè)人坐標(biāo)為200,120，第2個(gè)人坐標(biāo)為250,230...
# 關(guān)系網(wǎng)中涉及的人員
people=['Charlie','Augustus','Veruca','Violet','Mike','Joe','Willy','Miranda']

# 關(guān)聯(lián)關(guā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')]

# 計(jì)算交叉線，作為成本函數(shù)
def crosscount(v):
 # 將數(shù)字序列轉(zhuǎn)化為一個(gè)person:(x,y)的字典
 loc=dict([(people[i],(v[i*2],v[i*2+1])) for i in range(0,len(people))])
 total=0

 # 遍歷每一對(duì)連線
 for i in range(len(links)):
  for j in range(i+1,len(links)):

   # 獲取坐標(biāo)位置
   (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就是兩條交叉線的分?jǐn)?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

   # 如果兩條線的分?jǐn)?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)):
    # 獲取兩個(gè)節(jié)點(diǎn)的位置
    (x1,y1),(x2,y2)=loc[people[i]],loc[people[j]]

    # 獲取兩節(jié)點(diǎn)之間的距離
    dist=math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
    # 對(duì)間距小于50個(gè)像素的節(jié)點(diǎn)進(jìn)行判罰
    if dist<50:
     total+=(1.0-(dist/50.0))

 return total
#畫圖，繪制網(wǎng)絡(luò)
from PIL import Image,ImageDraw

def drawnetwork(sol):
 # 建立image對(duì)象
 img=Image.new('RGB',(400,400),(255,255,255))
 draw=ImageDraw.Draw(img)

 # 建立標(biāo)識(shí)位置信息的字典
 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) #設(shè)定題解范圍
if __name__=="__main__":   #只有在執(zhí)行當(dāng)前模塊時(shí)才會(huì)運(yùn)行此函數(shù)
  print(domain)
  s = optimization.randomoptimize(domain, crosscount) # 隨機(jī)搜索法，尋找最優(yōu)題解
  print(s)
  drawnetwork(s) # 繪制關(guān)系網(wǎng)
  s = optimization.hillclimb(domain, crosscount) # 爬山法，尋找最優(yōu)題解
  print(s)
  drawnetwork(s) # 繪制關(guān)系網(wǎng)
  s = optimization.annealingoptimize(domain, crosscount) # 模擬退火算法，尋找最優(yōu)題解
  print(s)
  drawnetwork(s) # 繪制關(guān)系網(wǎng)
  s = optimization.geneticoptimize(domain, crosscount) # 遺傳算法，尋找最優(yōu)題解
  print(s)
  drawnetwork(s) # 繪制關(guān)系網(wǎng)