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

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

基本信息

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

项目摘要

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

项目成果

期刊论文数量(28)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
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 代理的新蚂蚁系统算法”《经济评论》,小樽商业大学。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Parallel Tabu Search for Graph Multi-Partitioning Problem
图多分区问题的并行禁忌搜索
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.:“本地搜索相关景观的概率分析”《经济评论》,小樽商业大学。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
加地太一: "グラフ分割問題の解構造とAR(1)モデル"2002年度オペレーションズ・リサーチ学会秋季研究発表会. 34-35 (2002)
Taichi Kaji:“图划分问题的解决方案结构和 AR(1) 模型”2002 年运筹学会秋季会议 34-35 (2002)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
AR(1)プロセスを用いたLocal Searchに対する確率的解析
使用 AR(1) 过程进行本地搜索的随机分析
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

KAJI Taichi其他文献

KAJI Taichi的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('KAJI Taichi', 18)}}的其他基金

Elucidation of the mystery of metaheuristics and its application
元启发学奥秘的阐释及其应用
  • 批准号:
    23510153
  • 财政年份:
    2011
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Probabilistic Analysis of Meta-heuristics Algorithm from theViewpoint of Theoretical Approach
理论方法视角下元启发式算法的概率分析
  • 批准号:
    17510113
  • 财政年份:
    2005
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了