- 著者
-
仙石 浩明
吉原 郁夫
今川 徹三
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
- 巻号頁・発行日
- vol.1995, no.66, pp.19-26, 1995-07-19
- 参考文献数
- 4
- 被引用文献数
-
3
遺伝的アルゴリズム()は、探索が大域的、制約条件の変化に柔軟、などの長所があり、開発・保守工数を削減できるが、遺伝子コーディング法、交差方法などを問題毎に考案しなければならない。一方、従来から広く用いられてきたヒューリスティック探索法は、人手で解かれていたような問題を解く場合は、容易にアルゴリズムを作ることができる。しかし実問題に適用するには、より詳細な知識を組み込むなどのチューンアップが必須であり、開発・保守工数がかかるという短所がある。そこで、ヒューリスティック探索において探索木の分枝選択に優先順位を定め、この優先順位をGAで最適化する手法を提案する。本提案手法をバス仕業ダイヤ作成システムに応用し、実用上十分な仕業ダイヤ作成が可能となった。本システムは実際にダイヤ改正で使われた。Genetic Algorithms (GAs) have advantages in ability to search globally and flexibly, but we have to design the gene coding and the crossover method depending on each problem. On the other hand heuristic search algorithms are easy to develop and have been widely used to solve the problems, which have been conventionally solved manually, but for practical applications, we have to tune up the algorithms, for example, adding knowledge in detail, adjusting parameters, and so on. In this paper, we present a method using GA as an optimizer of the heuristic search. In our method, GA tunes the priorities of choosing branches in search tree, with which heuristic search algorithm can find optimal solutions. We apply our method to bus drivers scheduling systems. It can generate enough practical schedules, and is already used for revising drivers schedules.