命题： 来自不同地方的人们去同一个地方，需要安排他们的飞机行程，希望同一天在纽约会面，同时在同一天返回。要求总成本最小。
航班样例数据如下：
起点，终点，起飞时间，到达时间，价格 LGA,OMA,6:19,8:13,239 OMA,LGA,6:11,8:31,249 LGA,OMA,8:04,10:59,136 OMA,LGA,7:39,10:24,219 LGA,OMA,9:31,11:43,210 OMA,LGA,9:15,12:03,99 LGA,OMA,11:07,13:24,171 OMA,LGA,11:08,13:07,175 LGA,OMA,12:31,14:02,234 OMA,LGA,12:18,14:56,172 LGA,OMA,14:05,15:47,226 OMA,LGA,13:37,15:08,250 LGA,OMA,15:07,17:21,129 OMA,LGA,15:03,16:42,135 LGA,OMA,16:35,18:56,144 OMA,LGA,16:51,19:09,147 LGA,OMA,18:25,20:34,205 OMA,LGA,18:12,20:17,242 LGA,OMA,20:05,21:44,172 OMA,LGA,20:05,22:06,261 ……..
import time import random import numpy as np #创建每个人对应的出发城市 people = [('Seymour', 'BOS'), ('Franny', 'DAL'), ('Zooey', 'CAK'), ('Walt', 'MIA'), ('Buddy', 'ORD'), ('Les', 'OMA')] # 定义目的地 destination = 'LGA' #定义一个函数解析原始数据txt文件 flights = {} def extract_file(filename): flights = {} for line in open(filename): origin, dest, depart, arrive, price = line.strip().split(',') flights.setdefault((origin, dest), []) flights[(origin, dest)].append((depart, arrive, int(price))) return flights flights = extract_file('schedule.txt') list(flights.keys())[0]Out[277]: (‘LGA’, ‘DAL’)
[python3不支持字典索引，先转成list] (http://blog.csdn.net/a070220106/article/details/9089379)
#定义一个方便获取分钟数的函数 def getminutes(t): x = time.strptime(t, '%H:%M') return x[3] * 60 + x[4] #定义打印出题解对应的人员航班信息的函数 def printschedule(r): for d in range(int(len(r) / 2)): name = people[d][0] origin = people[d][1] out = flights[(origin, destination)][(r[d])] ret = flights[(destination, origin)][(r[d + 1])] print('ss %5s-%5s $%3s %5s-%5s $%3s' % (name, origin, out[0], out[1], out[2], ret[0], ret[1], ret[2]))s = [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3] printschedule(s)
Seymour BOS 8:04-10:11 9512:08−14:05 95 12 : 08 − 14 : 05 142 Franny DAL 12:19-15:25 34210:51−14:16 342 10 : 51 − 14 : 16 256 Zooey CAK 10:53-13:36 1899:58−12:56 189 9 : 58 − 12 : 56 249 Walt MIA 9:15-12:29 22516:50−19:26 225 16 : 50 − 19 : 26 304 Buddy ORD 16:43-19:00 24610:33−13:11 246 10 : 33 − 13 : 11 132 Les OMA 11:08-13:07 17515:07−17:21 175 15 : 07 − 17 : 21 129
# 定义成本函数（是优化问题的核心） def costf(sol): totalprice = 0 latestarrival = 0 earliestdep = 24 * 60 for d in range(int(len(sol) / 2)): # Get the inbound and outbound flights origin = people[d][1] #print('origin', origin) outbound = flights[(origin, destination)][(sol[d])] #print('outbound', outbound) returnf = flights[(destination, origin)][(sol[d + 1])] #print('returnf', returnf) # Total price is the price of all outbound and return flights totalprice += outbound[2] totalprice += returnf[2] # Track the latest arrival and earliest departure if latestarrival < getminutes(outbound[1]): latestarrival = getminutes(outbound[1]) if earliestdep > getminutes(returnf[0]): earliestdep = getminutes(returnf[0]) # Every person must wait at the airport until the latest person arrives. # They also must arrive at the same time and wait for their flights. totalwait = 0 for d in range(int(len(sol) / 2)): origin = people[d][1] outbound = flights[(origin, destination)][(sol[d])] returnf = flights[(destination, origin)][(sol[d + 1])] totalwait += latestarrival - getminutes(outbound[1]) totalwait += getminutes(returnf[0]) - earliestdep # Does this solution require an extra day of car rental? That'll be $50! if latestarrival > earliestdep: totalprice += 50 return totalprice + totalwait # 定义遗传算法 def geneticoptimize(domain, costf, popsize=50, step=1 , mutprob=0.2, elite=0.2, maxiter=100): #popsize:种群大小 #step: 变异步长（一个种群中的单个DNA变异的步长） #mutprob:种群的新成员由变异而非交叉得来的概率 #elite:种群中被认为是最优解且被允许传入下一代的部分 #maxiter: 需要运行多少代就停止 # 定义变异参数 def mutate(vec): i = random.randint(0, len(domain) - 1) if random.random() < 0.5 and vec[i] > domain[i][0]: return vec[0:i] + [vec[i] - step] + vec[i + 1:] elif vec[i] < domain[i][1]: 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:] # 创建随机初始种群(50个不同的种群) pop = [] for i in range(popsize): vec = [random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))] pop.append(vec) #每一代胜出的个数（这里定义了20%的上一代优胜者会进入下一代） topelite = int(elite * popsize) # 主循环 for i in range(100): #range(maxiter) scores = [(costf(v), v) for v in pop] #计算50个初始种群每个的成本及排列方式 scores.sort() #按照成本从小到大排序 ranked = [v for (s, v) in scores] #从纯粹的胜出者开始 pop = ranked[0:topelite] #只保留20%的初始种群 # 添加变异和配对后的胜出者 while len(pop) < popsize: if random.random() < mutprob: #random.random()产生0-1之间的一个随机数 #当这个随机数小于变异概率系数0.2的时候，开始变异 #也就意味着有20%的几率是突变 #变异（基因在未配对之前突变） c = random.randint(0, topelite)#指定那个位置的基因发生突变 pop.append(mutate(ranked[c])) #添加突变的种群到被选中的纯粹胜出的10个种群中 else: # 配对（2个初始纯粹胜出的种群配对） #这里有机会c1与c2是相同的 c1 = random.randint(0, topelite) c2 = random.randint(0, topelite) pop.append(crossover(ranked[c1], ranked[c2])) # 打印当前最佳的最小成本函数 print(scores[0][0]) #返回成本函数对应的解列表 return scores[0][1]标准的题解数据格式应该是一个长度为12的一元列表 e.g: sol = [8, 0, 3, 5, 4, 8, 5, 4, 8, 9, 4, 1] 定义一个与原始题解相同长度的二元列表，这样子定义的目的是每天都有往返10趟航班，每个人往返都可以从这10趟航班中任意选择，有利创造出任意的初始种题解 domain = [(0, 9)] * len(people) * 2
[(0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9)]
1，创建初始种群pop ：创建50个初始种群的题解
for i in range(popsize): vec = [random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))] pop.append(vec)pop Out[301]: [[0, 5, 6, 6, 6, 4, 7, 2, 3, 6, 7, 6], [8, 9, 3, 1, 1, 8, 2, 7, 4, 2, 5, 8], [0, 2, 0, 5, 4, 4, 8, 4, 1, 4, 0, 3], [4, 6, 3, 5, 3, 6, 7, 5, 9, 4, 5, 9], [4, 5, 6, 6, 5, 2, 8, 6, 5, 9, 9, 8], [0, 9, 9, 8, 9, 1, 8, 8, 5, 1, 7, 7], [2, 4, 8, 2, 5, 4, 8, 0, 0, 4, 8, 1], [7, 8, 8, 7, 9, 5, 9, 5, 5, 5, 0, 9], [0, 6, 1, 0, 5, 5, 5, 9, 0, 1, 6, 0], [3, 8, 1, 7, 7, 5, 3, 0, 7, 7, 4, 5], [4, 4, 9, 3, 2, 9, 7, 8, 6, 2, 0, 2], [4, 9, 4, 8, 5, 9, 0, 6, 9, 8, 8, 5], [9, 6, 6, 1, 2, 1, 4, 8, 8, 1, 5, 1], [9, 9, 9, 9, 0, 8, 0, 1, 1, 8, 5, 7], [7, 2, 7, 6, 5, 0, 8, 8, 1, 8, 1, 1], [0, 6, 5, 9, 2, 7, 0, 8, 7, 0, 9, 7], [1, 3, 4, 9, 8, 2, 9, 1, 0, 8, 2, 3], [4, 3, 4, 9, 7, 2, 4, 7, 0, 7, 2, 2], [8, 6, 6, 1, 8, 7, 6, 5, 8, 5, 2, 9], [1, 8, 0, 1, 8, 1, 4, 5, 0, 4, 9, 1], [1, 0, 2, 3, 0, 1, 4, 0, 1, 6, 2, 2], [8, 1, 9, 0, 7, 9, 1, 2, 4, 2, 9, 3], [4, 7, 8, 4, 6, 8, 8, 4, 5, 4, 5, 7], [7, 1, 1, 0, 7, 2, 0, 0, 9, 6, 5, 5], [0, 5, 4, 8, 9, 9, 9, 3, 4, 9, 7, 1], [0, 9, 9, 4, 6, 8, 3, 8, 7, 1, 2, 2], [6, 2, 3, 7, 3, 7, 5, 7, 4, 9, 5, 4], [3, 4, 8, 7, 8, 6, 9, 4, 8, 2, 2, 6], [4, 6, 8, 8, 7, 7, 1, 6, 0, 7, 5, 5], [7, 3, 6, 0, 4, 9, 3, 5, 8, 7, 7, 7], [5, 9, 9, 8, 1, 1, 1, 0, 0, 3, 9, 4], [5, 8, 8, 9, 8, 6, 8, 8, 8, 1, 6, 5], [6, 0, 7, 5, 9, 9, 1, 6, 7, 6, 4, 8], [8, 7, 4, 8, 3, 9, 2, 9, 8, 7, 1, 7], [9, 9, 2, 8, 6, 6, 3, 8, 8, 9, 8, 2], [1, 4, 6, 5, 9, 5, 6, 5, 3, 6, 4, 7], [1, 8, 3, 7, 3, 3, 3, 6, 7, 9, 6, 3], [8, 3, 2, 9, 2, 5, 0, 7, 4, 0, 9, 8], [8, 3, 0, 0, 5, 2, 3, 4, 9, 4, 6, 5], [5, 0, 1, 3, 8, 8, 6, 9, 5, 0, 8, 9], [1, 4, 3, 3, 3, 0, 5, 2, 9, 5, 7, 4], [2, 4, 0, 2, 4, 8, 5, 5, 7, 0, 3, 9], [0, 7, 5, 5, 1, 0, 2, 4, 7, 8, 0, 7], [5, 4, 4, 4, 5, 7, 7, 7, 2, 8, 4, 9], [3, 5, 4, 1, 7, 2, 5, 1, 4, 8, 5, 7], [4, 9, 8, 8, 0, 0, 1, 5, 5, 9, 1, 2], [3, 1, 0, 5, 7, 9, 4, 4, 0, 2, 9, 1], [8, 8, 3, 5, 1, 7, 7, 9, 1, 8, 8, 1], [5, 9, 6, 7, 6, 9, 9, 0, 4, 7, 7, 9], [8, 0, 3, 5, 4, 8, 5, 4, 8, 9, 4, 1]]
2，topelite， 对初始种群排序，选择前20%的初始种群作为下一代 通过选拔后，第二代只剩下了10个种群 for i in range(100): #range(maxiter) scores = [(costf(v), v) for v in pop] #计算50个初始种群每个的成本及排列方式 scores.sort() #按照成本从小到大排序 ranked = [v for (s, v) in scores] #从纯粹的胜出者开始 pop = ranked[0:topelite] #只保留20%的初始种群`pop #10个种群 Out[453]: Out[453]: [[6, 2, 2, 1, 5, 2, 6, 5, 9, 8, 3, 5], [6, 8, 5, 6, 5, 7, 4, 3, 5, 7, 1, 2], [3, 3, 5, 6, 3, 5, 7, 4, 4, 3, 7, 0], [0, 6, 3, 4, 4, 5, 4, 2, 9, 4, 6, 7], [9, 9, 8, 7, 8, 5, 6, 3, 9, 1, 5, 5], [8, 4, 4, 3, 3, 3, 9, 6, 5, 5, 6, 6], [2, 0, 5, 4, 5, 6, 2, 0, 8, 8, 7, 3], [8, 3, 7, 6, 5, 1, 2, 9, 4, 2, 3, 8], [2, 6, 2, 5, 7, 3, 8, 9, 1, 9, 9, 6], [5, 8, 5, 7, 7, 4, 8, 5, 4, 3, 9, 2]]
3，在第二代种群的基础上进行变异（这里定义了20%的机会突变）或者配对，迭代100次，每次迭代要么发生变异，要么配对，变异或者配对。每次迭代总会保留初始种群（这里是50）的20%的个体进入下一代，然后继续有20%的几率突变，或者80%的几率配对。达到设定的迭代次数后，选择成本函数最小的一个题解，算法停止。第一次迭代的时候，会从50个随机初始种群中产生10个种群，然后突变一个或者配对产生一个，第二代总共11个种群时候的pop变量： （这里出来的结果显示是突变还是配对？） 观察最后的一个结果就是突变或者配对产生新的一个后代，它跟倒数第三个前面一段类似，后面一段跟顺数第四个一样，所以是配对了的） Out[459]: [[6, 2, 2, 1, 5, 2, 6, 5, 9, 8, 3, 5], [6, 8, 5, 6, 5, 7, 4, 3, 5, 7, 1, 2], [3, 3, 5, 6, 3, 5, 7, 4, 4, 3, 7, 0], [0, 6, 3, 4, 4, 5, 4, 2, 9, 4, 6, 7], [9, 9, 8, 7, 8, 5, 6, 3, 9, 1, 5, 5], [8, 4, 4, 3, 3, 3, 9, 6, 5, 5, 6, 6], [2, 0, 5, 4, 5, 6, 2, 0, 8, 8, 7, 3], [8, 3, 7, 6, 5, 1, 2, 9, 4, 2, 3, 8], [2, 6, 2, 5, 7, 3, 8, 9, 1, 9, 9, 6], [5, 8, 5, 7, 7, 4, 8, 5, 4, 3, 9, 2], [2, 6, 2, 5, 7, 3, 4, 2, 9, 4, 6, 7]]
11个种群对应的成本函数排序
scores Out[462]: [(4802, [6, 2, 2, 1, 5, 2, 6, 5, 9, 8, 3, 5]), (4931, [6, 8, 5, 6, 5, 7, 4, 3, 5, 7, 1, 2]), (4952, [3, 3, 5, 6, 3, 5, 7, 4, 4, 3, 7, 0]), (5019, [0, 6, 3, 4, 4, 5, 4, 2, 9, 4, 6, 7]), (5098, [9, 9, 8, 7, 8, 5, 6, 3, 9, 1, 5, 5]), (5151, [8, 4, 4, 3, 3, 3, 9, 6, 5, 5, 6, 6]), (5194, [2, 6, 2, 5, 7, 3, 4, 2, 9, 4, 6, 7]), (5223, [2, 0, 5, 4, 5, 6, 2, 0, 8, 8, 7, 3]), (5423, [8, 3, 7, 6, 5, 1, 2, 9, 4, 2, 3, 8]), (5519, [2, 6, 2, 5, 7, 3, 8, 9, 1, 9, 9, 6]), (5709, [5, 8, 5, 7, 7, 4, 8, 5, 4, 3, 9, 2])]
经过对此迭代后，每次总保留10个pop进行变异或者配对，迭代完成后，返回成本最小的一个结果作为最终输出。 最终的题解以及最小的成本在迭代12次就得到了。。
s = geneticoptimize(domain, costf) [5, 3, 5, 3, 4, 3, 3, 0, 0, 0, 0, 0] #题解 4288 3901 3646 3646 3646 3490 3337 3303 2994 2994 2994 2912 2912 2912 2912 2912 2912 2912 2912 2912 2912 2912 2912
