| 講演名 | 1995/5/25 多段階交叉を用いたGAのジョブショップ問題への適用 山田 武士, 中野 良平, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 遺伝的アルゴリズム(GA)は自然淘汰と遺伝の仕組みにヒントを得た,一種の最適化手法である.GAの特徴は複数の解の集合である個体集団を用いた探索戦略と,突然変異,淘汰,そして交叉などの独特なオペレータであると言うことができる.本論文では多段階交叉(MSX)と呼ぶ新しい交叉を提案する.MSXは探索空間の距離と近傍構造を利用した交叉であり,与えられた両親から,その両者を結ぶパス上にいくつかの新たな個体を生成する.MSXの効果を調べるため,ジョプショップスケジューリング問題(JSSP)を例題とし,クリティカルパスを利用した近傍によりJSSPのためのMSXと,それを用いたGA(GA/MSX)を考案した.JSSPのベンチマークを用いた実験により,GA/MSXの優れた性能が明らかになった. |
| 抄録(英) | Genetic Algorithms (GAs) have been designed as general purpose optimization methods. GAs can be uniquely characterized by their population-based search strategies and their operators : mutation, selection and crossover. In this paper, we propose a new crossover called multi-step crossover (MSX) which utilizes a neighborhood structure and a distance in the problem space. Given parents, MSX successively generates their descendents along the path connecting the both of them. MSX was applied to the job-shop scheduling problem (JSSP) as a very high-level crossover to work on the critical path. Preliminary experiments using JSSP benchmarks showed the promising performance of a GA with the proposed MSX. |
| キーワード(和) | 遺伝的アルゴリズム / 多段階交叉 / ジョブショップスケジューリング問題 / 近傍探索 |
| キーワード(英) | Genetic Algorithms / multi-step crossover / job-shop scheduling / neighborhood search |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1995/5/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多段階交叉を用いたGAのジョブショップ問題への適用 |
| サブタイトル（和） | |
| タイトル（英） | A Genetic Algorithm with Multi-Step Crossover for Job-Shop Scheduling Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / Genetic Algorithms |
| キーワード(2)（和/英） | 多段階交叉 / multi-step crossover |
| キーワード(3)（和/英） | ジョブショップスケジューリング問題 / job-shop scheduling |
| キーワード(4)（和/英） | 近傍探索 / neighborhood search |
| 第 1 著者 氏名（和/英） | 山田 武士 / Takeshi Yamada |
| 第 1 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 第 2 著者 氏名（和/英） | 中野 良平 / Ryohei Nakano |
| 第 2 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 発表年月日 | 1995/5/25 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 75 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |