python 寻找优化使成本函数最小的最优解的方法

今天来学习变量优化问题。寻找使成本函数最小的题解。适用于题解相互独立的情况，设计随机优化算法、爬山法、模拟退火算法、遗传算法。

优化问题的的精髓是：1、将题解转化为数字序列化，可以写出题解范围。2、成本函数能返回值

问题场景：

所有乘客从不同的地方飞到同一个目的地，服务人员等待所有人到来以后将人一次性接走。

离开时，服务人员将人一次性带到飞机场，所有乘客等待自己的航班离开。

要解决的问题：

如何设置乘客的到来和离开航班，以及接送机的时间，使得总代价最小。

将题解设为数字序列。

数字表示某人乘坐的第几次航班，从0开始，例如[1,4,3,2,7,6,2]表示第1个人做第2个航班来，第5个航班走，第2个人做第4个航班来，第3个航班走

题解相互独立：组团旅游问题，举办会议的人员接送问题

首先从网上采集航班信息，存储到schedule.txt文件中。共6个起始点，和共同的目的地。每个起止点之间包含多道航班。在txt中记录的就是起飞点、着陆点、起飞时间、着陆时间、价钱。

des_place,src6_place,6:19,8:13,239
src6_place,des_place,6:11,8:31,249
des_place,8:04,10:59,136
src6_place,7:39,10:24,219
des_place,9:31,11:43,210
src6_place,9:15,12:03,99
des_place,11:07,13:24,171
src6_place,11:08,13:07,175
des_place,12:31,14:02,234
src6_place,12:18,14:56,172
des_place,14:05,15:47,226
src6_place,13:37,15:08,250
des_place,15:07,17:21,129
src6_place,15:03,16:42,135
des_place,16:35,18:56,144
src6_place,16:51,19:09,147
des_place,18:25,20:34,205
src6_place,18:12,20:17,242
des_place,20:05,21:44,172
src6_place,22:06,261
des_place,src5_place,6:03,8:43,219
src5_place,6:05,8:32,174
des_place,7:50,10:08,164
src5_place,8:25,10:34,157
des_place,9:11,10:42,172
src5_place,9:42,11:32,169
des_place,10:33,13:11,132
src5_place,11:01,12:39,260
des_place,12:08,14:47,231
src5_place,12:44,14:17,134
des_place,14:19,17:09,190
src5_place,14:22,16:32,126
des_place,15:04,17:23,189
src5_place,15:58,18:40,173
des_place,17:06,20:00,95
src5_place,16:43,19:00,246
des_place,18:33,20:22,143
src5_place,18:48,21:45,19:32,21:25,160
src5_place,19:50,22:24,269
des_place,src4_place,6:33,9:14,172
src4_place,6:25,9:30,335
des_place,8:23,143
src4_place,7:34,9:40,324
des_place,9:25,12:46,295
src4_place,12:29,225
des_place,14:38,262
src4_place,11:28,14:40,248
des_place,12:37,15:05,170
src4_place,12:05,15:30,330
des_place,14:08,16:09,232
src4_place,14:01,17:24,338
des_place,15:23,18:49,150
src4_place,15:34,18:11,326
des_place,16:50,19:26,304
src4_place,17:07,20:04,291
des_place,18:07,21:30,355
src4_place,18:23,21:35,20:27,23:42,169
src4_place,19:53,22:21,src1_place,6:39,8:09,86
src1_place,6:17,8:26,89
des_place,10:28,149
src1_place,10:11,95
des_place,9:58,11:18,130
src1_place,9:45,11:50,74
src1_place,11:16,13:29,83
des_place,142
src1_place,12:34,15:02,109
des_place,13:39,13:40,15:37,138
des_place,15:25,16:58,62
src1_place,15:27,17:18,151
des_place,17:03,18:03,103
src1_place,17:11,18:30,108
des_place,18:24,20:49,124
src1_place,18:34,19:36,136
des_place,19:58,21:23,22:22,102
des_place,src2_place,6:09,9:49,414
src2_place,6:12,10:22,230
des_place,7:57,11:15,347
src2_place,7:53,11:37,433
des_place,13:51,229
src2_place,9:08,12:12,364
des_place,10:51,14:16,256
src2_place,10:30,14:57,290
des_place,12:20,16:34,500
src2_place,12:19,342
des_place,14:20,17:32,332
src2_place,13:54,18:02,294
des_place,15:49,20:10,497
src2_place,15:44,18:55,382
des_place,17:14,20:59,277
src2_place,16:52,20:48,448
des_place,18:44,22:42,351
src2_place,18:26,21:29,464
des_place,19:57,23:15,512
src2_place,20:07,23:27,473
des_place,src3_place,6:58,9:01,238
src3_place,6:08,8:06,224
des_place,8:19,122
src3_place,8:27,10:45,139
des_place,12:56,249
src3_place,12:14,247
des_place,10:32,13:16,139
src3_place,10:53,13:36,189
des_place,12:01,13:41,267
src3_place,14:59,149
des_place,15:33,142
src3_place,15:38,137
des_place,15:50,18:45,243
src3_place,17:25,232
des_place,16:33,18:15,253
src3_place,17:08,19:08,262
des_place,18:17,21:04,259
src3_place,18:35,20:28,204
des_place,19:46,214
src3_place,20:30,23:11,114

构建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,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

1、随机搜索算法：随机选择题解，计算成本值，成本值最小的题解为确定题解。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 #返回随机最优解

2、爬山法：对于成本函数连续的情况，题解向成本值减小的地方渐变，直到成本值不再变化。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

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!