報告書番号

R99007

タイトル（和文）

多数エージェントによる大規模な組合せ最適化問題の解法 -蟻の群行動を模擬した最適化手法ACOの改良-

タイトル（英文）

A Cooperative Optimization Algorithm with Multiagent for Large-scale Combinatorial Optimization

概要 （図表や脚注は「報告書全文」に掲載しております）

組合せ最適化問題の多くは現実的な計算時間で厳密解を求めることが困難であるが、最適性の保証は無くても十分精度の高い解が求まれば実用上問題がない場合が多い。このような目的に用いられる発見的解法として、蟻の採餌行動を模した最適化手法ACOが提案されている。これまでにACOは多くの組合せ最適化問題に適用され、既存の発見的解法と同精度かそれ以上の最良解を獲得している。しかし、大規模な問題では考慮すべき状態数が多くなり、次候補を選択する際の計算量が大きくなるなどの課題が残されている。本報告では、代表的な組合せ最適化問題であるグラフ彩色問題に対するACOアルゴリズムに候補集合の概念を導入し、解の探索過程で動的に変化する候補集合の計算を効率化することで高速化を図る方法について報告する。本解法を用いることで、大規模なグラフ彩色問題に対し既存のACOアルゴリズムと同精度の解をより短時間で求めることができる。

概要 （英文）

Ant Colony Optimization (ACO) is a type of cooperative optimization algorithm inspired by the foraging behavior of real ants. Recently, many ACO algorithm have been proposed to solve different types of hard combinatorial optimization problems. Graph Coloring Problem (GCP) is one of the traditional combinatorial optimization problems, and the ACO algorithm for GCP was also proposed in 1997. This ACO algorithm, however, have two drawbacks in solving large scale problems: in order to select the next vertex to be colored, (1) numerous vertices must be considered as a candidate vertex, and (2) the vertex with very low selection probability must be considered as candidate one. This report propose a new ACO algorithm for large-scale GCPs. The proposed algorithm introduces a candidate list to each vertex for reducing computation time of selecting the next vertex. The candidate list is built from pheromone intensity, and updated dynamically. The proposed algorithm is tested using a set of standard benchmark problems, and the performance is very high for large-scale GCPs.

報告者

キーワード