Evolutionary game algorithm for multiple knapsack problem
Ye Kyeong Jun, Liu Xiande, Lu Han · 2004
In this paper, we propose a novel algorithm for optimizing multiple knapsack problem based on game theory. The proposed algorithm maps the search space and objective function of multiple knapsack problem to the strategy profile space and utility function of noncooperative game respectively, and achieves the optimization objective through a three-phase equilibrium process of rational game agents. In this article, we present the definition and detailed description of the proposed algorithm, and give the proof on its global convergence property. The efficiency of the proposed algorithm has been verified by the simulation test and the comparison with genetic algorithms.