Inhibition of Modeling-dependent Search Bias in Ant Colony Optimization

IPSJ

Bibliographic Information

Other Title
  • アントコロニー最適化におけるモデル化に依存する探索バイアスの抑制

Search this article

Description

本論文ではアントコロニー最適化（Ant Colony Optimization: ACO）における，探索バイアスを抑制するフェロモン量更新ルールを提案する．ACOは自然界の蟻が行う食料採集行動に着想を得たメタヒューリスティクスであり，様々な組合せ最適化問題において高い性能を示している．ACOの探索傾向には，解の生成確率を決定するフェロモンパラメータのモデル化と解の生成に用いる処理手順に依存したバイアスが生じることがあり，性能低下を引き起こす場合がある．バイアスを抑制する方法としては，フェロモンパラメータの設計を改善する方法とフェロモン量を更新するルールを改善する方法の2つが考えられるが，本論文では更新ルールを改善する方法について検討する．ジョブショップスケジューリング問題を用いて提案手法の性能評価を行った結果，提案する更新ルールは探索バイアスを抑制することができ，従来の更新ルールに比べ高い探索性能を示すことが分かった．

This paper proposes a novel pheromone update rule which inhibits a search bias in Ant Colony Optimization (ACO). The ACO is a meta-heuristics which has been inspired by the foraging behavior of real ant colonies, and it shows better accuracy than the other methods in the various combinatorial optimization problems. The search process in ACO is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time. There are two approaches to inhibiting this bias. One is to improve the pheromone model and the solution construction process, and the other is to improve the process of the pheromone update which is dealt with in this paper. The proposed update rule is evaluated by its application to job shop scheduling problems. Experimental results show that the proposed rule can inhibit the harmful bias and outperforms previous pheromone update rules.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top