DASE 7113 · 课程精讲

Frank–Wolfe交通分配

按输入、计算、输出的顺序理解,再逐句对照老师代码。

打开老师的完整代码 · Moodle 原页

三条路耗时为ci(xi)=ai+bixi2,其中a=(4,25,50)、b=(1,1,1)。总流量为10。势函数是f(x)=∑i[aixi+bixi3/3],其梯度就是当前路线耗时。

  1. 初始平均分配x=(10/3,10/3,10/3),总量为10。
  2. 每轮计算耗时,选择当前最快的路,把LP子问题流量y全部放到那条路。
  3. 方向为d=y−x,gap为−cTd。
  4. 再按x←x+αd混合更新,保持非负且总量10。

原代码第50行固定α=0.01,实际只画一条曲线;第54行却写了三个策略名的图例,应把图例改为 ['fixed step size 0.01']。它并没有执行三种策略的外层循环。

原样运行10000轮后,最终流量约(6.01589,3.98411,0),路线耗时约(40.19093,40.87313,50)。最后记录的gap约3.23967、势函数约217.31544;记录发生在该轮更新之前。固定步长会在均衡附近摆动,不能把某一轮偶然很小的gap当成持续收敛。

解析均衡为(6.05,3.95,0):两条已用路耗时相等,均为40.6025;第三路基础耗时50,更慢。对应势函数为217.30833。

要试递减步长,把第50行改为 alpha = 1/(k+2);要试精确线搜索,把它改为 alpha = minimize_scalar(lambda t: f(x+t*d), bounds=(0,1), method='bounded').x。要画多条对比线,每种策略都要重新设置同一个起点并各跑完整循环。

另附的三种步长练习程序已经把重新初始化和回溯条件写全。本次一万轮后,递减、精确、回溯的gap仍约为0.045、0.057、0.029;每种方法在这个问题上都有继续改进空间,不能只凭“精确”二字断定它一定最快。

从均分流量跟算第一轮。10/3 的平方为 100/9,所以三个成本约为 15.111,36.111,61.111。第 1 路最便宜,线性子问题取 y=(10,0,0)。用 x+0.01(y−x) 更新,第一项是 10/3+0.01(20/3)=3.4,后两项都是 10/3−0.01(10/3)=3.3,总量还是 10。此轮 gap 为 (10/3)(15.111+36.111+61.111)−10(15.111)≈223.333。

从上到下读

逐句讲解

左侧行号与保存的代码文件一致。空行用于分段。

行原代码这一行在做什么
1#!/usr/bin/env python3脚本启动声明,方便支持此方式的系统用Python3运行;Windows直接用Python打开也可。
2# -*- coding: utf-8 -*-声明源文件编码为UTF-8。
5import numpy as np导入NumPy,供向量、求和和最小值位置计算使用。
6from scipy.optimize import linprog, minimize_scalar导入LP和一维求解器;这份固定步长版本没有调用它们,后续改线搜索可用minimize_scalar。
7import matplotlib.pyplot as plt导入绘图接口。
10demand = 10总出行需求demand设为10。
11path_number = 3路线数量path_number设为3。
14a = np.array([4, 25, 50])三条路线的无拥堵基础耗时a为4、25、50。
15b = np.array([1, 1, 1])三条路拥堵平方项系数b都为1。
18f = lambda x: np.sum(a * x + b * x ** 3 / 3)定义势函数,对每条路计算a_i*x_i+b_i*x_i³/3再求和;求导后得到路线耗时。
19k_max = 10000最多执行10000轮;原代码没有按gap自动提前停止。
22plt.figure(figsize=(8, 5), dpi=500)创建8×5绘图窗口。
25Iter = list()创建空列表Iter,保存轮号。
26Gap = list()创建空列表Gap,保存对应的最优性gap。
27x = np.ones(path_number)先生成三个1作为初始权重。
28x = x / np.sum(x) * demand除以总和3再乘需求10,得到均匀可行起点(10/3,10/3,10/3)。
33for k in range(k_max):主循环k依次取0至9999。
36 f_val = f(x)计算当前势函数值f_val,用于打印观察。
37 c = a + b * x ** 2计算当前三条路线耗时c=a+b*x²,也就是势函数梯度。
39 y = np.zeros(path_number)建立三个零,准备写LP子问题的解y。
40 y[np.argmin(c)] = demandargmin(c)找最快路线的编号,再把该路的流量设为全部需求10,其余仍为0。
42 d = y - x从当前点指向LP解的位移d=y−x。
44 gap = -np.dot(c, y - x)dot求内积,取负得到Frank–Wolfe gap;gap为零表示凸问题已满足最优性条件。
45 print(f_val, gap)打印本轮更新前的势函数与gap。
47 Iter.append(k)保存当前轮号。
48 Gap.append(gap)保存当前gap,供最后画曲线。
50 alpha = 0.01实际使用固定步长0.01;想改为其他策略,应从这一行替换选步长逻辑。
51 x += alpha * d按x←x+alpha*d更新。因为步长在0到1之间,新点是两个可行点的凸组合。
52plt.plot(Iter, Gap)循环结束后,画出已保存的唯一一条gap曲线。
54plt.legend(['decreasing step size', 'exact line search', 'inexact line search'])设置图例文字,但原程序只有一条线,三个策略名与实际不符;此处应改成一个固定步长标签。
55plt.yscale('log')纵轴改为对数刻度,便于观察gap跨多个数量级的变化。
运行结果

代码画出的图

Frank–Wolfe交通分配运行结果