ハイブリッド型遺伝的アルゴリズムに関する研究

組合せ的,離散的な制約条件のもとで最適化を扱う組合せ最適化は,昨今の数理計画法における中心的課題であり,実にさまざまな問題が組合せ最適化問題として扱われている.工場の長期的な生産計画や各工程のスケジューリング,VLSIのレイアウト設計,各種の配置最適化などは,その一例である.これらの問題を解くのに,離散的な数値の可能な組合せをすべて調べようとすると,組合せ的爆発を起こすため、最適解を得るのは事実上不可能である.しかし,現実の場面では,計算機資源や人的・時間的資源を考慮すると,最適解よりもむしろ近似的な解で十分な場合がほとんどである.したがって,実用的には,近似解を求める手法が有効となるが,近似解も,精度のよい解はたやすく得ることができないため,効率的な近似解法の解決が待たれている.効率的に近似解を求めるためには,いかにして無駄な探索を減らし,膨大な組合せの中から精度のよい近似解に絞り込んでいくかが,重要な課題となる.本研究では,以下に示す2種類の遺伝的アルゴリズムとラグランジュ緩和法を併用して組合せ最適化問題の近似解を求めるハイブリッド手法を提案し,ジョブショップスケジューリング問題への適用を行った.探索木の動的構成による解法ビーム探索における探索木の枝をGAによって動的に再構成しながら探索を行なう.処理順序関係の分割による解法解空間をジョブの処理順序関係で分割し,良い解を含む空間をGAで探索する.最終的な解は,列挙あるいはビーム探索で求める.以上の手法は,数値例により,従来手法に較べ性能の改善が見られることを示した.今後の課題としては,探索の過程を細かく分析することにより,GAの果たす役割を定性的に明らかにすることおよび大規模な問題へ本研究の手法を適用することにより性能評価を行うことがあげられる.

組合せ的,離散的な制約条件のもとで最適化を扱う組合せ最適化は,昨今の数理計画法における中心的課題であり,実にさまざまな問題が組合せ最適化問題として扱われている.工場の長期的な生産計画や各工程のスケジューリング,VLSIのレイアウト設計,各種の配置最適化などは,その一例である.これらの問題を解くのに,離散的な数値の可能な組合せをすべて調べようとすると,組合せ的爆発を起こすため、最適解を得るのは事実上不可能である.しかし,現実の場面では,計算機資源や人的・時間的資源を考慮すると,最適解よりもむしろ近似的な解で十分な場合がほとんどである.したがって,実用的には,近似解を求める手法が有効となるが,近似解も,精度のよい解はたやすく得ることができないため,効率的な近似解法の解決が待たれている.効率的に近似解を求めるためには,いかにして無駄な探索を減らし,膨大な組合せの中から精度のよい近似解に絞り込んでいくかが,重要な課題となる.本研究では,以下に示す2種類の遺伝的アルゴリズムとラグランジュ緩和法を併用して組合せ最適化問題の近似解を求めるハイブリッド手法を提案し,ジョブショップスケジューリング問題への適用を行った.探索木の動的構成による解法ビーム探索における探索木の枝をGAによって動的に再構成しながら探索を行なう.処理順序関係の分割による解法解空間をジョブの処理順序関係で分割し,良い解を含む空間をGAで探索する.最終的な解は,列挙あるいはビーム探索で求める.以上の手法は,数値例により,従来手法に較べ性能の改善が見られることを示した.今後の課題としては,探索の過程を細かく分析することにより,GAの果たす役割を定性的に明らかにすることおよび大規模な問題へ本研究の手法を適用することにより性能評価を行うことがあげられる.