電力中央研究所

報告書「電力中央研究所報告」は当研究所の研究成果を取りまとめた刊行物として、昭和28年より発行されております。 一部の報告書はPDF形式で全文をダウンロードすることができます。

※ PDFのファイルサイズが大きい場合には、ダウンロードに時間がかかる場合がございます。 ダウンロードは1回のクリックで開始しますので、ダウンロードが完了するまで、複数回のクリックはなさらないようご注意願います。

電力中央研究所 報告書(電力中央研究所報告)

報告書データベース 詳細情報


報告書番号

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.

報告書年度

1999

発行年月

2000/04

報告者

担当氏名所属

渡邊 勇

情報研究所

キーワード

和文英文
組合せ最適化 Combinatorial Optimization
メタ戦略 Meta-heuristic
ポジティブ・フィードバック Positive Feedback
エージェント Agent
周波数割当て問題 Frequency Assignment
Copyright (C) Central Research Institute of Electric Power Industry