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

Dong, Jianping; Rong, Haina; Neri, Ferrante; Yang, Qiang; Zhu, Ming; Zhang, Gexiang

Abstract

© 2020 IEEE. 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.

Citation

Dong, J., Rong, H., Neri, F., Yang, Q., Zhu, M., & Zhang, G. (2020). An Adaptive Memetic P System to Solve the 0/1 Knapsack Problem. In Proceedings of the 2020 IEEE Congress on Evolutionary Computation (1-8). https://doi.org/10.1109/CEC48606.2020.9185841

• Conference Name: 2020 IEEE Congress on Evolutionary Computation (CEC)
• Conference Location: Glasgow, United Kingdom
• Start Date: Jul 19, 2020
• End Date: Jul 24, 2020
• Acceptance Date: Mar 20, 2020
• Online Publication Date: Sep 3, 2020
• Publication Date: 2020-07
• Deposit Date: Apr 2, 2020
• Publicly Available Date: Apr 8, 2020
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 1-8
• Book Title: Proceedings of the 2020 IEEE Congress on Evolutionary Computation
• ISBN: 978-1-7281-6930-9
• DOI: https://doi.org/10.1109/CEC48606.2020.9185841
• Keywords: Index Terms-Memetic Algorithms; P Systems; Membrane Computing; Evolutionary Algorithms; Knapsack Problem
• Public URL: https://nottingham-repository.worktribe.com/output/4243356
• Publisher URL: https://ieeexplore.ieee.org/document/9185841
• Related Public URLs: https://wcci2020.org/
• Additional Information: © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.