ファジー目標を考慮した大規模多目的多次元0-1ナップサック問題に対する分解手続きを含む遺伝的アルゴリズムの改良

概要

論文の詳細を見る
0-1ナップサック問題に対しては, 問題が小規模であれば, 分枝限定法や動的計画法の適用により厳密な最適解が求められる. しかし, 問題の規模が大きくなるにつれて, これらの方法においては計算量が指数的に増大するため, 厳密な最適解を求めることはきわめて困難になる. そこで, 準最適解を求めるためのさまざまな近似アルゴリズムが提案されてきている. 大規模0-1ナップサック問題に対しては, 問題の特殊構造を利用して効率的に解を導出するための方法として3重構造文字列を用いた分解手続きを含む遺伝的アルゴリズムによる解法を筆者らは提案してきている. しかし, この遺伝的アルゴリズムでは, 遺伝的アルゴリズムにおける個体空間の一つの個体Sを問題の解空間の一つの解xに対応させるデコーデイングの際に,制約条件しか考慮されていないので, 目的関数をも考慮することにより探索効率の向上が期待できる. そこで, 本論文では,間題の制約のみならず目的関数をも考慮するために, 連続緩和問題の解の情報に基づく個体表現を用いた分解手続きを含む遺伝的アルゴリズムを提案する.
社団法人電子情報通信学会の論文
1999-03-25