WEKO3
アイテム
制約付きTSPを解くための局所利己的遺伝子許容動的制御GA
https://ipsj.ixsq.nii.ac.jp/records/17092
https://ipsj.ixsq.nii.ac.jp/records/170924d1b3656-289c-4bbf-9a7c-ffc5e12d9635
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM4819014.pdf (687.3 kB)
|
Copyright (c) 2007 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-12-15 | |||||||
| タイトル | ||||||||
| タイトル | 制約付きTSPを解くための局所利己的遺伝子許容動的制御GA | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Locally Selfish-gene Tolerant Dynamic Control GA to Solve Constraint TSPs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | オリジナル論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 東京電機大学情報環境学部 | ||||||||
| 著者所属 | ||||||||
| 日立ソフトウェアエンジニアリング株式会社 | ||||||||
| 著者所属 | ||||||||
| 日立ソフトウェアエンジニアリング株式会社 | ||||||||
| 著者所属 | ||||||||
| 東京電機大学情報環境学部 | ||||||||
| 著者所属 | ||||||||
| 東京電機大学情報環境学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Environment, Tokyo Denki University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hitachi Software Engineering Co., Ltd. | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hitachi Software Engineering Co., Ltd | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Environment, Tokyo Denki University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Environment, Tokyo Denki University | ||||||||
| 著者名 |
櫻井, 義尚
小野山, 隆
久保田, 仙
中村, 嘉宏
鶴田, 節夫
× 櫻井, 義尚 小野山, 隆 久保田, 仙 中村, 嘉宏 鶴田, 節夫
|
|||||||
| 著者名(英) |
Yoshitaka, Sakurai
Takashi, Onoyama
Sen, Kubota
Yoshihiro, Nakamura
Setsuo, Tsuruta
× Yoshitaka, Sakurai Takashi, Onoyama Sen, Kubota Yoshihiro, Nakamura Setsuo, Tsuruta
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | リアルタイムに配送の効率化を図る配送ルート最適化システムの実現には，時間などの制約がある数十から百都市前後の規模の巡回セールスマン問題（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秒以下で求まることを確認した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Achievement of delivery route optimization system that improves the delivery efficiency in real time requires to solve time-constraint 30-100 cities Traveling Salesman Problems (TSP) within interactive response time, with practicable optimality. To meet this requirement, a Locally Selfish-gene Tolerant Dynamic Control GA is proposed. Here, each gene of an individual satisfies only its constraints selfishly, disregarding the constraints of other genes in the same individual. Further, to some extent, even individuals that violate constraints can survive over several generations and are given the chance of improvement. Moreover, evolution is promoted by dynamically changing the degree of the tolerance and GA operations. Our experiment proved that this method provides expert-level solutions for 30-100 cities time constraint TSPs within one second. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 48, 号 SIG19(TOM19), p. 127-138, 発行日 2007-12-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
