A hybrid heuristic algorithm based on Mean-Field Theory with a Simple Local Search for the Quadratic Knapsack Problem

摘要

In statistical physics, Mean-Field Theory is a probabilistic model which has three different approaches, one of them is Mean-Field variational that replaces a difficult distribution by an easier one. An optimization problem can be associated with a probability distribution that involves the structure of the problem, and is generally difficult to treat. This paper presents a novel method based on the Mean-Field Theory and a Local Search procedure to build good feasible solutions for the Quadratic Knapsack Problem. Basically, Mean-Field is used as a constructive heuristic that offers initial solutions and the quality of the solution is improved by a Local Search. To compare the performance of the proposed algorithm a Greedy constructive heuristic is implemented, and the same Local Search procedure was used. In order to test the efficiency of both algorithms, computational experiments were done on a set of benchmark instances in literature and another set is created. The experimental results show that Mean-Field like a constructive method provides similar solutions as Greedy in less time. And, incorporate them in a Local Search the response time for Mean-FIeld is less than Greedy but the quality of solutions is slightly smaller than Greedy.