報告書番号

R00014

タイトル（和文）

協調型最適化手法ACOの性能向上に向けた検討

タイトル（英文）

An Investigation for Improving the Performance of Ant Colony Optimization Algorithms

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

協調型最適化手法ACOは，大規模・複雑な問題に対する有効な最適化機構として期待されている。しかし，ACOには理論的な課題を含んだ多くの検討課題が残されている。本文では，大規模かつ複雑な組合せ最適化問題にACOを適用する上で検討すべき課題を整理し，今後重点的に取り組むべき検討課題を明らかにした。ACOを実用性の高い最適化法にするためには，(1)頑健性の確保，(2)アルゴリズムの高速化，(3)理論面の強化，(4)数値実験による性能評価，の4つの側面から検討を進める必要がある。特に，パラメータ調整，並列化による高速計算，問題構造の違いによる特性解析について重点的に検討を進める必要がある。また，最適解への収束性を中心に近年明らかになったACOの理論的側面について調査し，最適解への収束性を保証するために必要な機能やパラメータの自動制御について整理を行なった。

概要 （英文）

Ant Colony Optimization (ACO), which is a cooperative optimization metaheuristic inspired by the foraging behaviour of real ants, is a promising new approach to large-scale combinatorial optimization problems. Recently, many ACO algorithms have been proposed, but ACO metaheuristic still has some research issues to be investigated for improving the performance. In this report, we classify research issues to be tackled in order to improve the performance and identify major issues which should be investigated. In order to make ACO algorithm a practical optimization method, we need to investigate it from the viewpoint of the followings: (1)ensuring robustness, (2)reducing computation time, (3)clarification of mathematical properties, and (4)empirical analysis and validation. In particular, parameter tuning, parallelism, and characteristic analysis are crucial subjects. Based on the above classification, we also investigate some mathematical properties of ACO metaheuristic and clarify requirements for proving convergence to the optimal solution.

報告者

キーワード