A Memetic Decomposition-Based Multi-Objective Evolutionary Algorithm Applied to a Constrained Menu Planning Problem

Abstract

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 that fulfil all the recommendations given by nutritionists is a complex and time-consuming task; because of this, computer science has an important role in this area. This paper deals with a novel 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 contained in the plans. Particularly, this paper proposes 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 in 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 yields menu plans with lower costs, our multi-objective proposal offers menu plans with a significantly lower level of repetition of courses and food groups, with only a minor increase in cost. Furthermore, our studies demonstrate that the application of multi-objective optimisers can be used 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.

Keywords

• menu planning problem
• evolutionary algorithm
• decomposition-based multi-objective optimisation
• memetic algorithm
• iterated local search
• diversity preservation