| 講演名 | 1996/5/24 局所探索機能を組み込んだ交叉を用いたGAスケジューリング 山田 武士, 中野 良平, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では、先に提案した多段階交叉(MSX)と局所探索法を統合した交叉である局所探索交叉法(MSXF)を提案する。一般にMSXFは、探索空間の近傍構造と距離を利用し、両親のうちの一方を初期値として、もう一方の親との距離が近い解を優先させながら、現在の解をその近傍中の優秀な解で確率的に置き換える。この操作を、現在の解ともう一方の親との距離が十分小さくなるまで繰り返した後、得られた最も優秀な解を子供として採用する。クリティカルブロックを利用した近傍と、スケジュール間の距離を利用したMSXFを交叉法とするGA(GA/MSXF)をジョブショップスケジューリング問題(JSSP)のべンチマーク問題に適用したところ、その優れた性能が明らかになった。 |
| 抄録(英) | In this paper, multi-step crossover (MSX) and a local search method are unified into a single operator called MSXF. MSXF utilizes a neighborhood structure and a distance measure in the search space. In MSXF, a solution, initially set to be one of the parents, is stochastically replaced by a relatively good solution in the neighborhood, where the replacement is biased toward the other parent. This process is repeated until reaching the other parent, and the best solution generated in the process is selected as an offspring. Using job-shop scheduling problem (JSSP) benchmarks, MSXF was evaluated in a GA framework as a high-level crossover working on the critical path of a schedule. Experiments showed the promising performance of MSXF/GA. |
| キーワード(和) | 遺伝的アルゴリズム / 多段階交叉 / 近傍探索交叉 / ジョブショップスケジューリング問題 / 近傍探索 |
| キーワード(英) | Genetic Algorithms / multi-step crossover / job-shop scheduling / neighborhood search |
| 資料番号 | AI96-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1996/5/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 局所探索機能を組み込んだ交叉を用いたGAスケジューリング |
| サブタイトル（和） | |
| タイトル（英） | Scheduling by Genetic Local Search with Multi-Step Crossover |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / Genetic Algorithms |
| キーワード(2)（和/英） | 多段階交叉 / multi-step crossover |
| キーワード(3)（和/英） | 近傍探索交叉 / job-shop scheduling |
| キーワード(4)（和/英） | ジョブショップスケジューリング問題 / neighborhood search |
| キーワード(5)（和/英） | 近傍探索 |
| 第 1 著者 氏名（和/英） | 山田 武士 / Takeshi YAMADA |
| 第 1 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 第 2 著者 氏名（和/英） | 中野 良平 / Ryohei NAKANO |
| 第 2 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 発表年月日 | 1996/5/24 |
| 資料番号 | AI96-2 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 77 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |