報告書番号

R01004

タイトル（和文）

パラメータフリー遺伝的アルゴリズムの組合せ最適化問題への適用性評価

タイトル（英文）

Empirical Evaluation of the Parameter-free Genetic Algorithm for Combinatorial Optimization Problems

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

澤井らによって提案されているパラメータフリー遺伝的アルゴリズム(PfGA)は従来遺伝的アルゴリズム(GA)で必須の集団の大きさ，交叉率，突然変異率などのパラメータを持たず，問題毎のパラメータのチューニングが不要であることから，実用的価値が高い。しかし，関数最適化への適用結果の報告はあるが，組合せ最適化問題への適用についての報告はない。組合せ最適化問題の適用方式の検討結果として，周波数割当問題(FAP)への適用結果と，計算時間が制限された条件下で高性能を発揮する，ジョブショップスケジューリング問題(JSSP)への適用結果を報告する。提案する2つの解法は，問題を最適順列を発見する形に定式化し，ランダムキーを用いて順列を表現することでPfGAの特質を活用した算法となっている。標準的なベンチマーク問題への適用結果から，PfGAはFAP，JSSPに対しても高い性能を示すことを示す。

概要 （英文）

The parameter-free GA (PfGA) proposed by Sawai et al. is not only simple and robust, but also does not need to set almost all genetic parameters in advance that need to be set in other GAs. The performance of PfGA is high for functional optimization problems of 5- or 10-dimensions, but its performance for combinatorial optimization problems which search space is larger than the functional optimization has not been investigated.This paper reports the results of empirical evaluation of PfGA for combinatorial optimization problems. The first problem is fixed channel assignment problem (FCAP), and the second one is the job-shop sheduling problem (JSP) where the total number of search points is limited,.The ramdom keys representation of permutation is combined with the PfGA, and the PfGA is extended for real-coded version for the two problems. Simulation results show that the performance of PfGA and parallel distributed PfGA for FCAP, and JSP is as good as of functional optimization problems.

報告者

キーワード