確率学習に基づく多次元ナップザック問題解決のためのメメメティックアルゴリズム

A Memetic Algorithm Based on Probability Learning for Solving the Multidimensional Knapsack Problem.

• Zuocheng Li
• Lixin Tang
• Jiyin Liu

抄録

多次元ナップザック問題(MKP)は、実生活で多くの応用がなされているよく知られた組合せ最適化問題である。本論文では、MKPを解くための確率学習(MA/PL)に基づくメモティックアルゴリズムを提案する。本論文の主なポイントは、1)MKPの問題依存性ヒューリスティックと、2)MA/PLの新しいフレームワークである。問題依存ヒューリスティックでは、まず、MKPの特殊な構造に基づいて、各項目の利益値と重みベクトルを同時に考慮した2種類の対数効用関数(LUF)を提案する。そして、LUFを適用することで、実現不可能な解決策のための修復演算子と局所探索演算子を効果的に導くことができる。MA/PLの枠組みでは、MKPの特殊な知識を抽出するために、各項目の限界確率分布(MPD)と2つのコンジョイント項目の共同確率分布(JPD)の2つの問題依存確率分布を提案する。次に，競合学習や2値マルコフ連鎖からの発想を借りたMPDとJPDの学習規則を提案する．その後，MPDとJPDを統合してMA/PLの子孫を生成し，各項目の一変量確率情報とコンジョイント項目の依存性を十分に利用できるようにする．179個のベンチマークインスタンスを用いた実験と実生活でのケーススタディの結果から、提案するMKPの有効性と実用的な価値が実証された。

The multidimensional knapsack problem (MKP) is a well-known combinatorial optimization problem with many real-life applications. In this article, a memetic algorithm based on probability learning (MA/PL) is proposed to solve MKP. The main highlights of this article are two-fold: 1) problem-dependent heuristics for MKP and 2) a novel framework of MA/PL. For the problem-dependent heuristics, we first propose two kinds of logarithmic utility functions (LUFs) based on the special structure of MKP, in which the profit value and weight vector of each item are considered simultaneously. Then, LUFs are applied to effectively guide the repair operator for infeasible solutions and the local search operator. For the framework of MA/PL, we propose two problem-dependent probability distributions to extract the special knowledge of MKP, that is, the marginal probability distribution (MPD) of each item and the joint probability distribution (JPD) of two conjoint items. Next, learning rules for MPD and JPD, which borrow ideas from competitive learning and binary Markov chain, are proposed. Thereafter, we generate MA/PL's offspring by integrating MPD and JPD, such that the univariate probability information of each item as well as the dependency of conjoint items can be sufficiently used. Results of experiments on 179 benchmark instances and a real-life case study demonstrate the effectiveness and practical values of the proposed MKP.