Solving Computationally Hard Problems by Metaheuristics

通过元启发法解决计算难题

基本信息

批准号：
10205211
负责人：
IBARAKI Toshihide
金额：
$ 6.91万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

Recently, many types of metaheuristics based on local search, e. g., simulated annealing, genetic algorithm, and tabu search, have been proposed, and successfully applied to various combinatorial optimization problems. The objective of this research is to develop powerful general-purpose algorithms for combinatorial problems arising in real applications. To achieve this purpose, we developed metaheuristics algorithms for the following problems : (a) Weighted Constraint Satisfaction Problem, (b) Generalized Assignment Problem, (c) Resource Constrained Project Scheduling Problem, (d) Set Covering Problem, (e) Cutting Stock Problem, (f) Vehicle Routing Problem, (g) Rectangle Packing Problem, and others. These problems are representative combinatorial optimization problems, and their conventional formulations are rather simple. In our research, aiming at improving the applicability of algorithms, we extended these formulations so that more practical and complicated problems can be handled.In designing algorithms, we adopted iterated local search and tabu search as the frameworks, and defined search space and neighborhoods carefully so as to attain better performance. We also incorporated some mechanisms that adaptively control program parameters during the search, which can reduce users' efforts to tune the parameters appropriately.In computational experiments, we solved many benchmark instances, and succeeded to improve the best known values for many instances. As to practical problems, our codes could also find solutions of high quality in reasonable computational time. Some codes are already being used in practical applications.

最近，许多类型的基于本地搜索的元启发法，例如。例如，模拟退火、遗传算法和禁忌搜索已经被提出，并成功应用于各种组合优化问题。本研究的目的是针对实际应用中出现的组合问题开发强大的通用算法。为了实现这一目的，我们开发了针对以下问题的元启发式算法：（a）加权约束满足问题，（b）广义分配问题，（c）资源约束项目调度问题，（d）集合覆盖问题，（e）切割库存问题，(f) 车辆路径问题，(g) 矩形包装问题等。这些问题是具有代表性的组合优化问题，其常规公式相当简单。在我们的研究中，为了提高算法的适用性，我们扩展了这些公式，以便能够处理更多实际和复杂的问题。在设计算法时，我们采用迭代局部搜索和禁忌搜索作为框架，并仔细定义搜索空间和邻域从而获得更好的性能。我们还引入了一些在搜索过程中自适应控制程序参数的机制，这可以减少用户适当调整参数的工作。在计算实验中，我们解决了许多基准实例，并成功地改进了许多实例的最佳已知值。对于实际问题，我们的代码也可以在合理的计算时间内找到高质量的解决方案。一些代码已经在实际应用中使用。