制約付きTSPを解くための局所利己的遺伝子許容動的制御GA

概要

論文の詳細を見る
リアルタイムに配送の効率化を図る配送ルート最適化システムの実現には,時間などの制約がある数十から百都市前後の規模の巡回セールスマン問題(TSP)を対話応答時間である数秒以内に解き,しかも専門家レベルの最適解を得ることが要求される.この要求を満たすために,局所利己的遺伝子許容型GA (Locally Selfish-gene Tolerant Genetic Algorithms, LST-GA)に加え,これに動的制御の概念を取り入れた局所利己的遺伝子許容動的制御GA (Locally Selfish-gene Tolerant Dynamic Control Genetic Algorithms, LSTDC-GA)を提案した.この手法では,1つの個体の染色体を構成する個々の遺伝子は同じ個体内の他の遺伝子の制約を無視して局所的利己的にその遺伝子の制約だけを満たす.こうして,制約違反を起こした個体をある程度許容し,改善の機会を与える.またこの許容度合いであるペナルティ係数を環境変数である突然変異率などと同期させて動的に制御することにより進化を促進させる.時間制約が存在する数十から百都市前後の規模のTSPにおいて最大誤差が20%以下の解が,実験では1秒以下で求まることを確認した.
一般社団法人情報処理学会の論文
2007-12-15