按输入、计算、输出的顺序理解,再逐句对照老师代码。
三条路耗时为,其中、。总流量为10。势函数是,其梯度就是当前路线耗时。
原代码第50行固定,实际只画一条曲线;第54行却写了三个策略名的图例,应把图例改为 ['fixed step size 0.01']。它并没有执行三种策略的外层循环。
原样运行10000轮后,最终流量约,路线耗时约。最后记录的gap约3.23967、势函数约217.31544;记录发生在该轮更新之前。固定步长会在均衡附近摆动,不能把某一轮偶然很小的gap当成持续收敛。
解析均衡为:两条已用路耗时相等,均为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;每种方法在这个问题上都有继续改进空间,不能只凭“精确”二字断定它一定最快。
从均分流量跟算第一轮。 的平方为 ,所以三个成本约为 。第 1 路最便宜,线性子问题取 。用 更新,第一项是 ,后两项都是 ,总量还是 10。此轮 gap 为 。
左侧行号与保存的代码文件一致。空行用于分段。
| 行 | 原代码 | 这一行在做什么 |
|---|---|---|
| 1 | #!/usr/bin/env python3 | 脚本启动声明,方便支持此方式的系统用Python3运行;Windows直接用Python打开也可。 |
| 2 | # -*- coding: utf-8 -*- | 声明源文件编码为UTF-8。 |
| 5 | import numpy as np | 导入NumPy,供向量、求和和最小值位置计算使用。 |
| 6 | from scipy.optimize import linprog, minimize_scalar | 导入LP和一维求解器;这份固定步长版本没有调用它们,后续改线搜索可用minimize_scalar。 |
| 7 | import matplotlib.pyplot as plt | 导入绘图接口。 |
| 10 | demand = 10 | 总出行需求demand设为10。 |
| 11 | path_number = 3 | 路线数量path_number设为3。 |
| 14 | a = np.array([4, 25, 50]) | 三条路线的无拥堵基础耗时a为4、25、50。 |
| 15 | b = np.array([1, 1, 1]) | 三条路拥堵平方项系数b都为1。 |
| 18 | f = lambda x: np.sum(a * x + b * x ** 3 / 3) | 定义势函数,对每条路计算a_i*x_i+b_i*x_i³/3再求和;求导后得到路线耗时。 |
| 19 | k_max = 10000 | 最多执行10000轮;原代码没有按gap自动提前停止。 |
| 22 | plt.figure(figsize=(8, 5), dpi=500) | 创建8×5绘图窗口。 |
| 25 | Iter = list() | 创建空列表Iter,保存轮号。 |
| 26 | Gap = list() | 创建空列表Gap,保存对应的最优性gap。 |
| 27 | x = np.ones(path_number) | 先生成三个1作为初始权重。 |
| 28 | x = x / np.sum(x) * demand | 除以总和3再乘需求10,得到均匀可行起点(10/3,10/3,10/3)。 |
| 33 | for 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)] = demand | argmin(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之间,新点是两个可行点的凸组合。 |
| 52 | plt.plot(Iter, Gap) | 循环结束后,画出已保存的唯一一条gap曲线。 |
| 54 | plt.legend(['decreasing step size', 'exact line search', 'inexact line search']) | 设置图例文字,但原程序只有一条线,三个策略名与实际不符;此处应改成一个固定步长标签。 |
| 55 | plt.yscale('log') | 纵轴改为对数刻度,便于观察gap跨多个数量级的变化。 |