遺伝的アルゴリズムによる組合せ最適化(<小特集>自然界に学ぶアルゴリズム)

概要

論文の詳細を見る
Genetic Algorithms (GA) is a kind of optimization method which models naive evolutional process. GA has number of design elements which have great affect to its performance. This paper tries to put them in order under a context of combinatorial optimization. We classify design elements into three levels ; coding/crossover design, fitness design, and parameter tuning. We also classify performance of GA into four levels ; random search, local search, global search, and well-balanced search. We show some typical trial and error examples for each design levels with scheduling problems. For coding/crossover design, we show GA remains random search unless a crossover preserves characters in traveling salesman problems. For fitness design, we show GA remains local search when deceptive fitness prevents to grow building blocks in nurse scheduling problems. For parameter tuning, we show higher crossover rate accelerates early convergence in jobshop scheduling problems.
日本シミュレーション学会の論文
1993-03-15