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提出的蚂蚁系统算法的想法非常独特。但是，ANT系统算法的标准类型无法为随机图获得更好的解决方案。因此，我们通过基于强化和多元化策略（例如禁忌搜索）使用信息素来设计新代理，以达到更好的解决方案。我们试图在提高解决方案质量方面基于邻里的方法将方法应用于蚂蚁系统算法，因为蚂蚁系统算法不取决于邻域。并且，实施了上述新代理的平行蚂蚁系统算法以减少计算时间。此外，我们介绍了使用代理技术克服了另一种元脑化算法的并行算法引起的难度。最后，我们讨论了这些元数据的特征，试图构建一个模型，该模型为广泛的组合优化问题提供了理论概率分析。我们认为可以使该模型适应许多问题。在这里，我们将AR（1）模型介绍给数值近似于各种邻域，并制定了一个概率模型，该模型计算了通过本地搜索和所需步骤数量数量的求解解决方案成本的平均值。我们使用这种概率分析讨论了元毛术的特征。

项目成果

Kaji, T.: "New Ant System Algorithm by Ant-Tabu Agents"The Economic Review, Otaru University of Commerce. Vol.53,No.2,3. 143-163 (2002)

Kaji, T.：“Ant-Tabu 代理的新蚂蚁系统算法”《经济评论》，小樽商业大学。

Parallel Tabu Search for Graph Multi-Partitioning Problem

图多分区问题的并行禁忌搜索

• 发表时间: 2003
• 期刊: The Economic Review, Otaru University of Commerce Vol.53, No.4
• 作者: Kaji;T.
• 通讯作者: T.

Kaji, T.: "A Probabilistic Analysis on the Correlated Landscape for Local Search"The Economic Review, Otaru University of Commerce. Vol.54, No.2,3. 165-177 (2003)

Kaji, T.：“本地搜索相关景观的概率分析”《经济评论》，小樽商业大学。

加地太一: "グラフ分割問題の解構造とAR(1)モデル"2002年度オペレーションズ・リサーチ学会秋季研究発表会. 34-35 (2002)

Taichi Kaji：“图划分问题的解决方案结构和 AR(1) 模型”2002 年运筹学会秋季会议 34-35 (2002)。

Kaji, T.: "Parallel Tabu Search for Graph Multi-Partitioning Problem"The Economic Review, Otaru University of Commerce. Vol.53, No.4. 121-136 (2003)

Kaji, T.：“图多分区问题的并行禁忌搜索”《经济评论》，小樽商业大学。