An Adaptive Memetic P System to Solve the 0/1 Knapsack Problem

Memetic Algorithms are traditionally composed of an evolutionary framework and one or more local search elements. However, modern generation Memetic Algorithms do not necessarily follow a pre-established scheme and are hybrid structures of various types. By following these modern trends, the present paper proposes an original and unconventional adaptive memetic structure generated by the hybridisation of a set of theoretical computational models, namely P Systems, and an evolutionary algorithm employing adaptation rules and moving operators inspired by Evolution Strategies. The resulting memetic algorithm, namely Adaptive Optimisation Spiking Neural P System (AOSNPS), is a tailored algorithm to solve optimisation problems with binary encoding. More specifically AOSNPS is composed of a family of parallel spiking neural P systems, each of them generating a binary vector representing a candidate solution on the basis of internal probability parameters and an adaptive Evolutionary Guider Algorithm that evolves the probabilities encoded in each P system. Numerical result shows that the proposed approach is effective to solve the 0/1 knapsack problem and outperforms various algorithms proposed in the literature to solve the same class of problems.