Ant Algorithm with Local Search Procedure for Multiple Knapsack Problem

Multiple Knapsack Problem (MKP) is a hard combinatorial optimization problem with large application. A lot of real life and industrial problems can be defined like MKP, therefore it attracts the attention of the scientists. Exact methods and traditional numerical methods are appropriate for solving small problems or problems without hard constraints. For problems, which needs non polynomial (NP) number of calculations is better to apply so called metaheuristic methods. Metaheuristics are methodology and on their basis is constructed problem dependent algorithm. Metaheuristic methods apply some stochastic rules and it helps to find faster near optimal solution even for huge problems. Ant Colony Optimization (ACO) is a nature inspired method, which follows the real ants behavior. It is between the best methods for solving combinatorial optimization problems. Sometimes the method alone is not enough to find good solutions, especially when the problem has strong constraints. In this case, one resorts to constructing an appropriate local search procedure. The aim is to find better solutions or to fasten the search process. The solutions of the problem can be represented by binary sequence. Let us consider this binary sequence as a binary number. We will calculate the average between the best solution, represented as a binary number, and any of the current solutions. The new binary number will be the new solution after local search procedure.