A Memetic Decomposition-based Multi-objective Evolutionary Algorithm applied to a Constrained Menu Planning Problem
Work submitted to: Special Issue 'Evolutionary Computation 2020' - Mathematics
- Alejandro Marrero --- @amarrerod
- Eduardo Segredo --- @esegredo
- Coromoto León --- @cleon
- Carlos Segura --- @carlossegurag
Encouraging healthy and balanced diet plans is one of the most important action points for governments around the world. Generating healthy, balanced and inexpensive menu plans fulfilling all the recommendations given by nutritionists is a complex and time-consuming task, and therefore, computer science has an important role in this area.
This paper deals with a constrained multi-objective formulation of the menu planning problem specially designed for school canteens that considers the minimisation of the cost and the minimisation of the level of repetition of the specific courses and food groups that the plans consist of. Particularly, a multi-objective memetic approach based on the well-known Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D). A crossover operator specifically designed for this problem is included into the approach. Moreover, an ad-hoc Iterated Local Search (ILS) is considered for the improvement phase. As a result, our proposal is referred to as ILS-MOEA/D.
A wide experimental comparison against a recently proposed single-objective memetic scheme, which includes explicit mechanisms to promote diversity in the decision variable space, is provided. The experimental assessment shows that, even though the single-objective approach obtains menu plans with lower costs, our multi-objective proposal attains menu plans with a significantly lower level of repetition of courses and food groups, with just a slight increase on the cost.
Furthermore, our studies demonstrate that the application of multi-objective optimisers allows to implicitly promote diversity not only in the objective function space, but also in the decision variable space.
Consequently, in contrast to the single-objective optimiser, there was no need to include an explicit strategy to manage the diversity in the decision space in the case of the multi-objective approach.