今天来学习变量优化问题。寻找使成本函数最小的题解。适用于题解相互独立的情况，设计随机优化算法、爬山法、模拟退火算法、遗传算法。
优化问题的的精髓是：1、将题解转化为数字序列化，可以写出题解范围。2、成本函数能返回值
问题场景：
所有乘客从不同的地方飞到同一个目的地，服务人员等待所有人到来以后将人一次性接走。
离开时，服务人员将人一次性带到飞机场，所有乘客等待自己的航班离开。
要解决的问题：
如何设置乘客的到来和离开航班，以及接送机的时间，使得总代价最小。
将题解设为数字序列。
数字表示某人乘坐的第几次航班，从0开始，例如[1,4,3,2,7,3,6,3,2]表示第1个人做第2个航班来，第5个航班走，第2个人做第4个航班来，第3个航班走
题解相互独立：组团旅游问题，举办会议的人员接送问题
首先从网上采集航班信息，存储到schedule.txt文件中。共6个起始点，和共同的目的地。每个起止点之间包含多道航班。在txt中记录的就是起飞点、着陆点、起飞时间、着陆时间、价钱。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
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
|
构建6名游客的航班信息
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# 人员的名称和来源地信息
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))) #按时间顺序扩展每次航班
|
为了实现优化，我们将题解转变为数字序列，为了理解更加方便的理解数字序列代表的含义。实现一个函数，接受数字序列，打印输出航班信息。
|
1
2
3
4
5
6
7
8
|
# 将数字序列转换为航班，打印输出。输入为数字序列
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]))
|
此场景我们要解决的问题就是寻找使花费最小的每位游客应该乘坐的往返航班。
我们定义一个成本函数代表我们需要花费的资金。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# 计算某个给定时间在一天中的分钟数
def getminutes(t):
x = time.strptime(t, '%H:%M')
return x[3] * 60 + x[4]
# 成本函数。输入为数字序列
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为成本函数。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(0,1000):
# 创建随机解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
#计算成本值
cost=costf(sol)
# 与目前得到的最优解进行比较
if cost<best:
best=cost
bestr=sol
return sol #返回随机最优解
|
2、爬山法：对于成本函数连续的情况，题解向成本值减小的地方渐变，直到成本值不再变化。domain为题解范围（可选航班范围），costf为成本函数。在只有一个极低点时最有效。可以采用随机重复爬山法优化。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def hillclimb(domain,costf):
# 创建一个随机解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
# 主循环
while 1:
# 创建相邻解的列表
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偏移
# 在相邻解中寻找最优解
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# 如果没有更好的解，则退出循环。即寻找了极低点
if best==current:
break
return sol
|
3、模拟退火算法：概率性接收更优解（更差解），时间越久，概率越大（越低）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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)
#创建一个代表题解的新列表，改变其中一个值
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)
# 它是更好的解么？或者是趋向最优解的可能的临界解么
if (eb<ea or random.random()<p):
vec=vecb
# 降低温度
T=T*cool
return vec
|
4、遗传算法：基因杂交（交叉）或基因变异。domain题解范围，costf成本函数，popsize种群大小，step变异基因量，mutprob变异比例，elite优秀基因者的比例，maxiter运行多少代。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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:]
# 构建初始种群
pop=[]
for i in range(popsize): #随机产生50个动物的种群
vec=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
pop.append(vec)
# 每一代有多少胜出者？
topelite=int(elite*popsize)
# 主循环
for i in range(maxiter):
scores=[(costf(v),v) for v in pop]
scores.sort()
ranked=[v for (s,v) in scores]
# 在种群中选出优胜者
pop=ranked[0:topelite]
# 为优秀基因者，添加变异和配对后的胜出者
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:
# 相互杂交。以后会遇到近亲结婚的问题
c1=random.randint(0,topelite-1)
c2=random.randint(0,topelite-1)
newanimal = crossover(ranked[c1], ranked[c2])
pop.append(newanimal)
# 打印当前最优解和成本
# print(scores[0])
return scores[0][1] #返回最优解
|
测试程序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
if __name__=="__main__": #只有在执行当前模块时才会运行此函数
print(flights) #打印所有航班信息
domain=[]
for start_stop in flights: #查询每个起止点的航班个数
domain.append((0,len(flights[start_stop])-1)) #获取题解范围，两边必区间（航班范围的数据序列）
# domain=[(0,9)]*(len(peoplelist)*2)
print(domain)
s=randomoptimize(domain,schedulecost) # 随机搜索法，寻找最优题解
print(s)
printschedule(s) #打印最优航班信息
s = hillclimb(domain, schedulecost) # 爬山法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
s = annealingoptimize(domain, schedulecost) # 模拟退火算法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
s = geneticoptimize(domain, schedulecost) # 遗传算法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
|
全部代码optimization.py
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
# 优化算法。寻找使成本函数最小的题解。
import time
import random
import math
# 问题场景：
# 所有乘客从不同的地方飞到同一个目的地，服务人员等待所有人到来以后将人一次性接走。
# 离开时，服务人员将人一次性带到飞机场，所有乘客等待自己的航班离开。
# 要解决的问题：
# 如何设置乘客的到来和离开航班，以及接送机的时间，使得总代价最小。
# 将题解设为数字序列。
# 数字表示某人乘坐的第几次航班，从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))) #按时间顺序扩展每次航班
# 将数字序列转换为航班，打印输出。输入为数字序列
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]))
# 计算某个给定时间在一天中的分钟数
def getminutes(t):
x = time.strptime(t, '%H:%M')
return x[3] * 60 + x[4]
# 成本函数。输入为数字序列
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为成本函数。
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(0,1000):
# 创建随机解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
#计算成本值
cost=costf(sol)
# 与目前得到的最优解进行比较
if cost<best:
best=cost
bestr=sol
return sol #返回随机最优解
# 爬山法：对于成本函数连续的情况，题解向成本值减小的地方渐变，直到成本值不再变化。domain为题解范围（可选航班范围），costf为成本函数。
# 在只有一个极低点时最有效。可以采用随机重复爬山法优化
def hillclimb(domain,costf):
# 创建一个随机解
sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
# 主循环
while 1:
# 创建相邻解的列表
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偏移
# 在相邻解中寻找最优解
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# 如果没有更好的解，则退出循环。即寻找了极低点
if best==current:
break
return sol
# 模拟退火算法：概率性接收更优解（更差解），时间越久，概率越大（越低）。
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)
#创建一个代表题解的新列表，改变其中一个值
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)
# 它是更好的解么？或者是趋向最优解的可能的临界解么
if (eb<ea or random.random()<p):
vec=vecb
# 降低温度
T=T*cool
return vec
# 遗传算法：基因杂交（交叉）或基因变异。domain题解范围，costf成本函数，popsize种群大小，step变异基因量，mutprob变异比例，elite优秀基因者的比例，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:]
# 构建初始种群
pop=[]
for i in range(popsize): #随机产生50个动物的种群
vec=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]
pop.append(vec)
# 每一代有多少胜出者？
topelite=int(elite*popsize)
# 主循环
for i in range(maxiter):
scores=[(costf(v),v) for v in pop]
scores.sort()
ranked=[v for (s,v) in scores]
# 在种群中选出优胜者
pop=ranked[0:topelite]
# 为优秀基因者，添加变异和配对后的胜出者
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:
# 相互杂交。以后会遇到近亲结婚的问题
c1=random.randint(0,topelite-1)
c2=random.randint(0,topelite-1)
newanimal = crossover(ranked[c1], ranked[c2])
pop.append(newanimal)
# 打印当前最优解和成本
# print(scores[0])
return scores[0][1] #返回最优解
if __name__=="__main__": #只有在执行当前模块时才会运行此函数
print(flights) #打印所有航班信息
domain=[]
for start_stop in flights: #查询每个起止点的航班个数
domain.append((0,len(flights[start_stop])-1)) #获取题解范围，两边必区间（航班范围的数据序列）
# domain=[(0,9)]*(len(peoplelist)*2)
print(domain)
s=randomoptimize(domain,schedulecost) # 随机搜索法，寻找最优题解
print(s)
printschedule(s) #打印最优航班信息
s = hillclimb(domain, schedulecost) # 爬山法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
s = annealingoptimize(domain, schedulecost) # 模拟退火算法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
s = geneticoptimize(domain, schedulecost) # 遗传算法，寻找最优题解
print(s)
printschedule(s) # 打印最优航班信息
|
使用优化算法解决房间住宿问题
场景：每个房间有两个床位，每个学生有自己首选房间和次选房间（只选房间，不选床位）。将所有学生安排到所有房间
目标：在尽量满足学生的选择的情况下，为学生安排宿舍。
将题解转化为数字间皆有联系的数字序列。可以让每个数字代表可选床位的第几个，索引从0开始
例如：[0,2,1,1,1,2,0,1]表示第1个人选可选床位的第1个，第2个人选剩余可选床位的第3个床位，第3个人选剩余可选床位的第2个。。。
测试代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
# 利用之前设计好的优化算法，解决涉及偏好的优化问题。1、将题解转化为数字序列化，可以写出题解范围。2、成本函数能返回值
import random
import math
import optimization
# 场景：每个房间有两个床位，每个学生有自己首选房间和次选房间（只选房间，不选床位）。将所有学生安排到所有房间
# 目标：在尽量满足学生的选择的情况下，为学生安排宿舍
# 将题解转化为数字间没有联系的数字序列。可以让每个数字代表可选床位的第几个，索引从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)
# 删除该槽，这样后面的数字列表才能正确翻译成“剩余床位”
del slots[x]
# 成本函数：
def dormcost(vec):
cost=0
# 创建一个槽序列
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__": #只有在执行当前模块时才会运行此函数
print(domain)
s = optimization.randomoptimize(domain, dormcost) # 随机搜索法，寻找最优题解
print(s)
printsolution(s) # 打印最优解代表的含义
s = optimization.hillclimb(domain, dormcost) # 爬山法，寻找最优题解
print(s)
printsolution(s) # 打印最优解代表的含义
s = optimization.annealingoptimize(domain, dormcost) # 模拟退火算法，寻找最优题解
print(s)
printsolution(s) # 打印最优解代表的含义
s = optimization.geneticoptimize(domain, dormcost) # 遗传算法，寻找最优题解
print(s)
printsolution(s) # 打印最优解代表的含义
|
使用优化算法解决绘制关系网问题
场景：在绘制关系网图中，每个人在图中都有位置x，y坐标，在有关联的两个人中间添加连线。
目标：是所有连线的交叉数最少
将题解转化为数字间没有联系的数字序列。可以让每个数字代表人物在图形中的位置x，y
例如：[200,120,250,230..]表示第1个人坐标为200,120，第2个人坐标为250,230…
测试代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
# 将优化算法应用到绘制关系网图中，使得交叉线最少
import math
import optimization
# 场景：在绘制关系网图中，每个人在图中都有位置x，y坐标，在有关联的两个人中间添加连线。
# 目标：是所有连线的交叉数最少
# 将题解转化为数字间没有联系的数字序列。可以让每个数字代表人物在图形中的位置x，y
# 例如：[200,120,250,230..]表示第1个人坐标为200,120，第2个人坐标为250,230...
# 关系网中涉及的人员
people=['Charlie','Augustus','Veruca','Violet','Mike','Joe','Willy','Miranda']
# 关联关系
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')]
# 计算交叉线，作为成本函数
def crosscount(v):
# 将数字序列转化为一个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就是两条交叉线的分数值。
# line where they cross
ua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den
ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den
# 如果两条线的分数值介于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)):
# 获取两个节点的位置
(x1,y1),(x2,y2)=loc[people[i]],loc[people[j]]
# 获取两节点之间的距离
dist=math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
# 对间距小于50个像素的节点进行判罚
if dist<50:
total+=(1.0-(dist/50.0))
return total
#画图，绘制网络
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__": #只有在执行当前模块时才会运行此函数
print(domain)
s = optimization.randomoptimize(domain, crosscount) # 随机搜索法，寻找最优题解
print(s)
drawnetwork(s) # 绘制关系网
s = optimization.hillclimb(domain, crosscount) # 爬山法，寻找最优题解
print(s)
drawnetwork(s) # 绘制关系网
s = optimization.annealingoptimize(domain, crosscount) # 模拟退火算法，寻找最优题解
print(s)
drawnetwork(s) # 绘制关系网
s = optimization.geneticoptimize(domain, crosscount) # 遗传算法，寻找最优题解
print(s)
drawnetwork(s) # 绘制关系网
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/luanpeng825485697/article/details/78765923