Dissecting OLMS membrane algorithms: understanding the role of communication and evolutionary operators in optimization strategies

Abstract Metaheuristics are general-purpose optimization techniques designed to explore the solution space of complex problems, balancing between exploration and exploitation, trying to escape local optima. Some techniques are inspired by natural processes, such as simulated annealing, particle swarm optimization, or genetic algorithms. Membrane computing, a computational paradigm based on the behavior and the structure of living cells, has proved capable in solving computationally hard problems in an efficient way. From the intersection of both fields, the framework of membrane algorithms embeds metaheuristics as a way to evolve objects in a membrane system. A thorough study of this framework is presented in this work, deeply analyzing the mutual influence of a variety of strategies of membrane and genetic algorithms, enhancing their synergy in searching for optimal solutions. Specifically, this paper assesses the impact of aspects, such as communication rules, genetic operators or number of membranes, among others. All strategies are compared using well-known problems as Traveling Salesman Problem and Graph Coloring Problem, taken as a benchmark. The results show the best solutions are dependent on the specific problem addressed and the genetic algorithm used but, overall, a distributive send-in strategy is ideal for specializing membranes, allowing some to focus on exploration of the state space and others on exploitation of good solutions.