[Jsprit]Jsprit学习笔记-vrp问题新解的接收策略

阈值接收器

作者实现了一个阈值接收器，SchrimpfAcceptance 下面是对这个接收器的解释 阈值接受函数： 这个概念可以描述如下：大多数问题不仅仅有一个唯一的最小值（或最大值），而是有多个局部最小值（或最大值）。为了避免在搜索开始时就陷入局部最小值，这种阈值接受函数在开始时也接受较差的解（与只接受更好解的贪婪方法相反），并随着时间的推移逐渐转变为贪婪方法。 难点： 定义（i）一个合适的初始阈值和（ii）一个描述阈值如何收敛到零的相应函数，即贪婪阈值。 初始阈值的确定： 通过在搜索空间中进行随机游走来确定初始阈值。随机游走使用特定的算法，并运行直到达到预热迭代次数。在第一次迭代或游走中，算法生成一个解，这个解是下一次游走的基础，以此类推。每个解的值都被记忆，因为初始阈值本质上是这些解值的标准差的函数。更精确地说：初始阈值 = 标准差(解的值) / 2。 具体实现阈值迭代的代码：

private double getThreshold(int iteration) { double scheduleVariable = (double) iteration / (double) maxIterations; return initialThreshold * Math.exp(-1. * Math.log(2) * scheduleVariable / alpha); }

试着通过画图来理解这个迭代 scheduleVariable 是个0,1之间的数，表示迭代的进度 alpha表示一个迭代参数 用python实现一下这个函数的图像

import numpy as np import matplotlib.pyplot as plt # 定义参数alpha和scheduleVariable的范围 alpha = 0.5 # scheduleVariable = np.linspace(0, 1, 100) # 从0到1的100个点 # 计算函数值 y = np.exp(-np.log(2) / alpha * scheduleVariable) # 绘制图像 plt.plot(scheduleVariable, y) plt.xlabel('scheduleVariable') plt.ylabel('y') plt.title('Plot of the function y = e^(-(log(2)/alpha) * scheduleVariable)') plt.grid(True) plt.show()

随着迭代次数的增加，阈值逐渐递减

新解的接收策略 public boolean acceptSolution(Collection<VehicleRoutingProblemSolution> solutions, VehicleRoutingProblemSolution newSolution) { boolean solutionAccepted = false; if (solutions.size() < solutionMemory) { solutions.add(newSolution); solutionAccepted = true; } else { VehicleRoutingProblemSolution worst = null; double threshold = getThreshold(currentIteration); for (VehicleRoutingProblemSolution solutionInMemory : solutions) { if (worst == null) worst = solutionInMemory; else if (solutionInMemory.getCost() > worst.getCost()) worst = solutionInMemory; } if (worst == null) { solutions.add(newSolution); solutionAccepted = true; } else if (newSolution.getCost() < worst.getCost() + threshold) { solutions.remove(worst); solutions.add(newSolution); solutionAccepted = true; } } return solutionAccepted; }

这段Java代码是用于决定是否接受一个新的解决方案到一个车辆路径问题（Vehicle Routing Problem, VRP）的解决方案集合中。 代码的主要逻辑如下：

定义一个布尔变量 solutionAccepted 来标识解决方案是否被接受。

检查 solutions 集合的大小是否小于 solutionMemory（一个代表解决方案记忆容量的变量）。如果是，将 newSolution 添加到集合中，并将 solutionAccepted 设置为 true。

如果 solutions 集合已满，则执行以下步骤：

定义一个变量 worst 来存储当前集合中最差的解决方案（成本最高）。通过 getThreshold 方法获取当前迭代的阈值 threshold。遍历 solutions 集合，找到成本最高的解决方案，并将其存储在 worst 变量中。检查 worst 是否为 null。如果是，这意味着集合中没有解决方案，可以将 newSolution 添加到集合中，并将 solutionAccepted 设置为 true。如果 newSolution 的成本小于 worst 的成本加上阈值 threshold，则从集合中移除 worst 解决方案，将 newSolution 添加到集合中，并将 solutionAccepted 设置为 true。

返回 solutionAccepted 变量，表示是否接受新的解决方案。

这个方法的目的是维护一个解决方案集合，只保留成本较低的解决方案，并在新解决方案的成本低于当前最差解决方案的成本加上一个阈值时更新集合。