その他(学会発表)

基本情報

氏名 丹羽 啓一
氏名(カナ) ニワ ケイイチ
氏名(英語) Niwa Keiichi

著書,学術論文等の名称

遺伝的アルゴリズムとBendersの分割法による混合0-1計画法

単著・共著の別

共同

発行又は発表の年月

1997/08

発行予定

 

発行所,発表雑誌等又は発表学会等の名称

第2回ファジィORミニシンポジウム講演論文集

巻・号

 

掲載ページ

57~62

概要

現実の意思決定状況には,実数変数と0-1変数を同時に扱う混合0-1計画問題として定式化される場合も少なくなく,実際の問題例として施設配置問題が考えられる.混合0-1計画問題に対しては,従来から様々な解法が提案され,適用されてきたが,未だに実用的な解法が確立されていないのが現状である.現在までに提案された解法の中で最も有効な解法は分枝限定法と考えられる.分枝限定法は,混合0-1計画問題の制約を連続緩和することで得られる連続緩和問題に対して線形計画法を適用し,得られた解をもとに解空間を分割し (分枝操作),解の有界情報を用いて枝切りを行い探索数を減少させる (限定操作) という二つの操作を繰り返し,最終的に原問題の最適解を得るというアルゴリズムである.しかしながら,分枝限定法の問題点としては,問題の規模が増大したとき,探索数を減少させるために用いている限定操作において良い有界条件が得られなければ,有効な時間内に最適解を得ることが困難であるという点が挙げられる.そこで,本研究においては,混合0-1計画問題に対してBendersの分割法を用いることで原問題を線形計画問題と0-1計画問題に分割し,その各々の問題に対して有効な解法を適用することによって混合0-1計画問題の解法を提案する.その際に,近年,0-1計画問題に対する近似解法としてその有効性が報告されている遺伝的アルゴリズムを用いることとする.提案手法の実行可能性と有効性を検証するために分枝限定法と提案手法を用いて数値実験を行い,それぞれの手法を用いることで得られた解の精度および最適解を得るまでにかかったCPU時間の比較を行った.