个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
30
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章python 寻找优化使成本函数最小的最优解的方法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
今天来学习变量优化问题。寻找使成本函数最小的题解。适用于题解相互独立的情况，设计随机优化算法、爬山法、模拟退火算法、遗传算法.
优化问题的的精髓是：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 。
最后此篇关于python 寻找优化使成本函数最小的最优解的方法的文章就讲到这里了,如果你想了解更多关于python 寻找优化使成本函数最小的最优解的方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
30
4
0
C语言sscanf()函数：从字符串中读取指定格式的数据 头文件： ?
最近，我有一个关于工作预评估的问题，即使查询了每个功能的工作原理，我也不知道如何解决。这是一个伪代码。 下面是一个名为foo()的函数，该函数将被传递一个值并返回一个值。如果将以下值传递给foo函数，
CStr 函数 返回表达式，该表达式已被转换为 String 子类型的 Variant。 CStr(expression) expression 参数是任意有效的表达式。 说明 通常，可以
CSng 函数 返回表达式，该表达式已被转换为 Single 子类型的 Variant。 CSng(expression) expression 参数是任意有效的表达式。 说明 通常，可
CreateObject 函数 创建并返回对 Automation 对象的引用。 CreateObject(servername.typename [, location]) 参数 serv
Cos 函数 返回某个角的余弦值。 Cos(number) number 参数可以是任何将某个角表示为弧度的有效数值表达式。 说明 Cos 函数取某个角并返回直角三角形两边的比值。此比值是
CLng 函数 返回表达式，此表达式已被转换为 Long 子类型的 Variant。 CLng(expression) expression 参数是任意有效的表达式。 说明 通常，您可以使
CInt 函数 返回表达式，此表达式已被转换为 Integer 子类型的 Variant。 CInt(expression) expression 参数是任意有效的表达式。 说明 通常，可
Chr 函数 返回与指定的 ANSI 字符代码相对应的字符。 Chr(charcode) charcode 参数是可以标识字符的数字。 说明 从 0 到 31 的数字表示标准的不可打印的
CDbl 函数 返回表达式，此表达式已被转换为 Double 子类型的 Variant。 CDbl(expression) expression 参数是任意有效的表达式。 说明 通常，您可
CDate 函数 返回表达式，此表达式已被转换为 Date 子类型的 Variant。 CDate(date) date 参数是任意有效的日期表达式。 说明 IsDate 函数用于判断 d
CCur 函数 返回表达式，此表达式已被转换为 Currency 子类型的 Variant。 CCur(expression) expression 参数是任意有效的表达式。 说明 通常，
CByte 函数 返回表达式，此表达式已被转换为 Byte 子类型的 Variant。 CByte(expression) expression 参数是任意有效的表达式。 说明 通常，可以
CBool 函数 返回表达式，此表达式已转换为 Boolean 子类型的 Variant。 CBool(expression) expression 是任意有效的表达式。 说明 如果 ex
Atn 函数 返回数值的反正切值。 Atn(number) number 参数可以是任意有效的数值表达式。 说明 Atn 函数计算直角三角形两个边的比值 (number) 并返回对应角的弧
Asc 函数 返回与字符串的第一个字母对应的 ANSI 字符代码。 Asc(string) string 参数是任意有效的字符串表达式。如果 string 参数未包含字符，则将发生运行时错误。
Array 函数 返回包含数组的 Variant。 Array(arglist) arglist 参数是赋给包含在 Variant 中的数组元素的值的列表（用逗号分隔）。如果没有指定此参数，则
Abs 函数 返回数字的绝对值。 Abs(number) number 参数可以是任意有效的数值表达式。如果 number 包含 Null，则返回 Null；如果是未初始化变量，则返回 0。
FormatPercent 函数 返回表达式，此表达式已被格式化为尾随有 % 符号的百分比（乘以 100 ）。 FormatPercent(expression[,NumDigitsAfterD
FormatNumber 函数 返回表达式，此表达式已被格式化为数值。 FormatNumber( expression [,NumDigitsAfterDecimal [,Inc
我是一名优秀的程序员,十分优秀！