algorithm - 解决装箱问题的模拟退火算法

Question

我正在研究关于 Bin Packing 的问题。我目前已经以遗传编程的方式实现了这个问题。但是当我针对这个问题研究Simulated Annealing Algorithm时，我并不是很了解。

这个问题是否有任何好的链接或代码/伪代码。

Answer 1

首先让我们定义问题

打包一套N = {1, 2, …, n} 项目，每个都有大小t_i, i =1, 2,…, n, 放入相同的容器中，每个容器的容量为 C在不违反容量限制的情况下最小化箱数

所以退火算法的主要大纲将包括:

• 使用首次拟合递减程序构造初始解
• 计算并为项目分配权重以根据到各个箱子的包装解决方案
• 通过在所有箱子对之间交换项目来执行本地搜索
• 根据之前的结果进行重新加权优化运行
• 根据冷却计划减少重量变形

现在重要的是对装箱问题进行邻域搜索:

• 从当前的解决方案中，通过在垃圾箱之间交换项目来获得下一个解决方案具有以下目标函数(Fleszar 和 Hindi 2002)

• 交换计划交换两个箱子之间的项目，然后进行交换(1,0)，交换(1,1)，交换(1,2)，交换(2,2) 对于所有的 bin 对。
• 交换 (1,0)

- 然后只评估目标函数值的变化

• 交换 (1,1)，然后交换 (1,2)，例如:

这应该给你一个开始。