書評II

2000年 01月 01日 書評II 玉置　久（神戸大学） 著者 : Dirk C. Mattfeld 書名 : Evolutionay Search and the Job Shop 出版 : Physica-Verlag Heidelberg, 1996 本書は，ジョブショップ・スケジューリング問題に対する進化型計算の適用方法を議論したものである．まず，ジョブショップ問題について，選択グラフ表現やアクティブ・スケジュール生成法などを含め， 2章で詳しく説明されている．その後，3章で局所探索(ローカルサーチ)法の紹介， 4章で進化型計算アルゴリズムの一般的解説がなされている．続く 5章～8章では，著者の研究成果 (本書は学位論文をベースとしたものである) を中心に， ジョブショップ問題に対する遺伝アルゴリズムの構成法が議論されている．そこでは，探索空間の設計や適応度の景観といった， 一般に遺伝アルゴリズムを適用する際に重要であると考えられるポイントについてもきちんと説明・議論されている．計算実験については，この分野でポピュラーな Muth & Thompson 10×10 などのベンチマーク問題が例題として選ばれているが，最後の 9章で，実世界の問題へ適用する場合の難しさ等についても触れられている． ジョブショップ問題に限定する形で進化型計算の適用法をテーマとしているという点において，本書は他に類を見ないものであり，(本書が出版された時点での) 格好の State-of-the-art を示していると考えられる．ただ，1995 年以降，特に日本で遺伝アルゴリズムのジョブショップ問題への応用に関する研究が盛んになったが，これらの成果について触れられていないのが残念である． しかしながら，単に遺伝アルゴリズムの適用法を紹介するというものではなく，上述のように探索空間の構成やその特徴の評価なども試みられているという点において，現時点でもなお，遺伝アルゴリズムのみならず最適値探索法(局所探索法)を構成する際の指針になり得る内容が含まれているものと思われる．また，ジョブショップ問題 (2章) や局所探索法 (3章) についての記述も，簡潔ながら的を得たものであり， (少しオーオーバかもしれないが) この部分だけでも読む価値があるのではなかろうか． 最後に，本書の目次を以下に記しておく． Introduction Production Planning Production Scheduling Heuristic Search Overview of the Thesis Job Shop Scheduling Representation of the JSP Schedule Generation Techniques Enumeration Methods Local Search Techniques Neighborhood Definitions Local Hill Climbing Local Search Extensions Evolutionary Algorithms The Evolutionary Metaphor Adaptation in Epistatic Domains Genetic Hybrids Perspectives on Adaptive Scheduling Configuring the Solution Space Properties of the Search Space Summary of Perspectives Population Flow in Adaptive Scheduling Genetic Algorithm Template Inheritance Management Population Management Applying Adaptive Scheduling Adaptation of Structured Populations Finite and Structured Populations Inheritance of Attitudes A Computational Study Survey of the GA-Approaches Benchmark Study Conclusions and Outlook (152 pages, 142 references)