我想知道超启发式和元启发式之间的区别是什么,以及它们的主要应用是什么。哪些问题适合通过超启发式解决?
什么是超启发式,它们与元启发式有何不同?
TL:DR:超启发式是元启发式,适用于解决同类优化问题,但(原则上)为非专家从业者提供“快速原型设计”方法。在实践中,流行的方法存在问题,激发了对“白盒”超启发式的新兴观点。
更详细地说:
Metaheuristics 是用于搜索可能解决方案的巨大空间以找到“高质量”解决方案的方法。流行的元启发式算法包括模拟退火、禁忌搜索、遗传算法等。
元启发式和超启发式之间的本质区别在于增加了一个搜索间接级别:非正式地,超启发式可以描述为“用于搜索启发式空间的启发式”。因此,只要适当定义要搜索的“启发式空间”的性质,就可以将任何元启发式用作超启发式。
因此,超启发式的应用领域与元启发式相同。它们的适用性(相对于元启发式)是一种“快速原型工具”:最初的动机是允许非专家从业者将元启发式应用于他们特定的优化问题(例如“旅行推销员(TSP)加上时间窗加上 bin-包装”),而不需要高度具体的问题领域的专业知识。当时的想法是,这可以通过以下方式完成:
- 允许从业者仅实施非常简单(有效、随机)的启发式方法来转换潜在的解决方案。例如,对于 TSP:“交换两个随机城市”而不是(比如说)更复杂的Lin-Kernighan启发式。
- 通过以智能方式组合/排序它们来获得有效的结果(尽管使用了这些简单的启发式方法),通常是通过采用某种形式的学习机制。
超启发式可以被描述为“选择性的”或“生成的”,具体取决于启发式是(分别)排序还是组合。因此,生成式超启发式算法经常使用诸如遗传编程之类的方法来组合原始启发式算法,因此通常由从业者定制以解决特定问题。例如,关于生成超启发式的原始论文使用学习分类器系统来结合启发式进行装箱。因为生成方法是针对特定问题的,所以下面的评论不适用于它们。
相比之下,选择性超启发式的最初动机是研究人员将能够创建一个超启发式求解器,然后仅使用简单的随机启发式算法就可以在看不见的问题域中很好地工作。
传统上实现这一点的方式是通过引入“超启发式域屏障”(参见下图),据称可以通过阻止求解器了解其所在的域来实现跨问题域的通用性。它正在运行。相反,它将通过仅对可用启发式列表中的不透明整数索引进行操作来解决问题(例如,以“多臂强盗问题”的方式)。
在实践中,这种“领域盲”方法并没有产生足够质量的解决方案。为了在任何地方都能获得与特定问题元启发式算法相媲美的结果,超启发式研究人员不得不实施复杂的特定问题启发式算法,从而未能实现快速原型设计的目标。
原则上仍然可以创建一个能够泛化到新问题域的选择性超启发式求解器,但这变得更加困难,因为上述域障碍概念意味着只有非常有限的特征集可用于交叉-领域学习(例如,以流行的选择性超启发式框架为例)。
最近对“白盒”超启发式的研究观点提倡使用声明性、功能丰富的方法来描述问题域。这种方法有许多声称的优点:
- 从业者现在不再需要实施启发式方法,而是简单地指定问题域。
- 它消除了领域障碍,将超启发式置于与问题特定元启发式相同的“知情”状态。
- 对于白盒问题的描述,臭名昭著的“没有免费午餐”定理(本质上说,考虑到所有黑盒问题的空间,具有无限退火时间表的模拟退火平均与任何其他方法一样好)没有更长时间适用。
免责声明:我在这个研究领域工作,因此不可能从答案中消除所有个人偏见。