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

Dorigo提出的蚁群算法思想非常独特。然而，标准类型的蚂蚁系统算法不能获得更好的解决方案，随机图。因此，我们利用信息素设计新的智能体，采用基于集约化和多样化的策略，如禁忌搜索，以达到更好的解决方案。由于蚁群算法不依赖于邻域，本文尝试将基于邻域的方法应用到蚁群算法中，以提高解的质量。并利用上述新的智能体实现了并行蚂蚁系统算法，以减少计算时间。此外，我们提出了如何在并行算法造成的困难，另一个元算法已经克服了使用代理技术。最后，我们讨论了这些元概率论的特点，试图建立一个模型，为广泛的组合优化问题的理论概率分析。我们认为，有可能使这一模式适用于许多问题。在这里，我们引入AR（1）模型来数值近似各种邻域，并制定了一个概率模型，它计算的平均情况下的成本的解决方案找到的本地搜索和所需的步骤数。我们使用这种概率分析来讨论元启发式算法的特征。

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.