講演情報
[N-1-03]集合差分進化の多次元ナップサック問題への適用
◎國永 優人1、前田 道治1 (1. 福岡工業大学大学院工学研究科)
キーワード：
多次元ナップサック問題、組合せ最適化問題、メタヒューリスティクス、集合差分進化
多次元ナップサック問題（MKP）は，制約の下で利益を最大化する組合せ最適化問題であり，NP困難問題に分類される．そのため，大規模問題に対してはメタヒューリスティクスを用いた解法が数多く提案されている．しかし，従来手法では探索の停滞や局所解への収束が課題となる場合がある．そこで本研究では，MKPに対する集合差分進化を提案し，探索性能の向上を図る．提案手法では，個体間の差分情報を利用した突然変異操作を行い，生成された集合に対して交叉演算を適用することで空間を探索する．数値実験の結果，本手法は複数のベンチマーク問題において，従来手法であるDPSO，Ant AlgorithmおよびSCLPSOを上回る性能を示した．以上より，本手法の有効性を確認した．