权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Approach of Hybrid Ant Agents and Probabilistic Analysis for Combinatorial Optimization Problems

混合蚂蚁代理方法和组合优化问题的概率分析

基本信息

批准号：
14580466
负责人：
KAJI Taichi
金额：
$ 2.18万
依托单位：
Otaru University of Commerce
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580466/
关键词：
Traveling Salesman Problem Ant System Algorithm Agent Tabu Search Pheromone Probabilistic Analysis

项目摘要

The idea of ant system algorithm proposed by Dorigo is very unique. However, the standard type of the ant system algorithm cannot obtain better solutions for random graphs. So, we design new agent by using pheromone based on intensification and diversification strategy, such as the tabu search is applied, in order to reach better solutions. We attempt to apply approach based on neighborhood to the ant system algorithm in terms of improving quality of solutions because the ant system algorithm does not depend on neighborhood. And, parallel ant system algorithm by above-mentioned new agents is implemented to reduce computational time. Furthermore, we present how the difficulty caused in parallel algorithm for another meta-heuristics has been overcome using agent technology. Finally we discuss the characteristics of these meta-heuristics attempting to construct a model which gives theoretical probabilistic analysis for wide class of combinatorial optimization problem. We consider that it is possible to adapt this model to many problems. Here, we introduce AR(1) model to numerically approximate various kinds of neighborhood, and formulate a probabilistic model, which compute the average-case of the costs of the solutions found by local search and the required number of steps. We discuss the characteristics of meta-heuristics using this probabilistic analysis.

Dorigo提出的蚂蚁系统算法思想是非常独特的。然而，对于随机图，标准类型的蚂蚁系统算法不能得到更好的解。因此，我们利用信息素的集约化和多样化策略来设计新的agent，如禁忌搜索，以达到更好的解决方案。由于蚂蚁系统算法不依赖于邻域，因此我们尝试将基于邻域的方法应用于蚂蚁系统算法，以提高解的质量。并利用上述新型智能体实现并行蚂蚁系统算法，以减少计算时间。此外，我们还介绍了如何使用代理技术克服另一种元启发式并行算法所带来的困难。最后，我们讨论了这些元启发式方法的特点，试图建立一个模型，为广泛的组合优化问题提供理论概率分析。我们认为这种模式有可能适用于许多问题。在此，我们引入AR(1)模型对各种邻域进行数值逼近，并建立了一个概率模型，计算了局部搜索得到的解的平均代价和所需的步数。我们用这种概率分析来讨论元启发式的特点。