A Novel Memetic Algorithm with Explicit Control of Diversity for the Menu Planning Problem

Menu planning is a complex task that involves finding a combination of menu items by taking into account several kinds of features, such as nutritional and economical, among others. In order to deal with the menu planning as an optimization problem, these features are transformed into constraints and objectives. Several variants of this problem have been defined and metaheuristics have been significantly successful solving them. In the last years, Memetic Algorithms (MAS) with explicit control of diversity have lead the attainment of high-quality solutions in several combinatorial problems. The main aim of this paper is to show that these types of methods are also viable for the menu planning problem. Specifically, a simple problem formulation based on transforming the menu planning into a single-objective constrained optimization problem is used. An MA that incorporates the use of iterated local search and a novel crossover operator is designed. The importance of incorporating an explicit control of diversity is studied. This is performed by using several well-known strategies to control the diversity, as well as a recently devised proposal. Results show that, for solving this problem in a robust way, the incorporation of explicit control of diversity and ad-hoc operators is mandatory.