Abstract
Healthy eating is an important issue affecting a large part of the world population, so human diets are becoming increasingly popular, especially with the devastating consequences of Coronavirus Disease (Covid-19). A realistic and sustainable diet plan can help us to have a healthy eating habit since it considers most of the expectations from a diet without any restriction. In this study, the classical diet problem has been extended in terms of modelling, data sets and solution approach. Inspired by animals’ hunting strategies, it was re-modelled as a many-objective optimisation problem. In order to have realistic and applicable diet plans, cooked dishes are used. A well-known many-objective evolutionary algorithm is used to solve the diet problem. Results show that our approach can optimise specialised daily menus for different user types, depending on their preferences, age, gender and body index. Our approach can be easily adapted for users with health issues by adding new constraints and objectives. Our approach can be used individually or by dietitians as a decision support mechanism.
Keywords
Introduction
One of the global health problems causing serious consequences is malnutrition. Statistics show that undernutrition, which is mainly caused by poverty, increases the risk of death from infectious diseases. 1 Since malnutrition seriously weakens the immune system, infections result in higher mortality.2–4 Undernutrition, as a result of a dietary imbalance or restriction, stress, trauma, or as a side effect of some disease processes, results in altered immunity (both innate and adaptive immunity), impaired function, altered cellular metabolism, and muscular dysfunction.5–7 On the other hand, overnutrition, which is known to be strongly associated with the development of diabetes, hypertension, hypercholesterolemia and coronary heart disease, can affect the immune system directly or indirectly by altering the metabolic and endocrine status.8–10
Diseases that are direct or indirect consequences of malnutrition, which change the body’s immune system, cause higher mortality for infectious diseases, including the new Coronavirus Disease (Covid-19), which has become a pandemic and leaves more than 400K deaths worldwide.11,12 Therefore, we should pay attention to gain healthy eating habits and broad access to healthy foods to reduce the vulnerability to and long-term complications from COVID-19. 3 Healthy eating is not a standard diet and it refers to making changes in our eating habit to prevent serious effects of malnutrition, protect the immune system and have a healthy life in all aspects.
The daily foods we consume should maintain the balance between dietary intake and nutritional needs. Otherwise, the organism will be vulnerable to infectious diseases and will perform poorly.6,13 Dieting is a key procedure to achieve a nutritional intake balance. Unfortunately, standard human diets are generally restrictive and temporary plans for eating a special list of food to balance the body index or for medical reasons. Restricting the diet with undesirable, expensive and rare foods may damage our mental, social and economic life, which are highly connected to physical health, and need to be satisfied together. Therefore, we must consider eating affordable, available and preferred foods as a healthy eating habit.
Similar to animal’s foraging and hunting strategies 14 humans consider many objectives to be optimised while dieting. Not only the cost of the menu but also preference, availability, preparation time, diversity of the meal plan and possible more objectives have to be considered while dieting. 15
This study is designed to provide a realistic approach to model the diet problem as a many-objective healthy eating problem by adding preference and preparation time objectives. We solved it by using an existing popular many-objective evolutionary algorithm, namely Non-dominated Sorting Genetic Algorithm III (NSGA-III). 16 As far as the authors know, this is the first study that models the diet problem as a many-objective, many-constraint optimisation problem and solves it using a many-objective evolutionary algorithm. Thus, the study can have an academic impact as well as health and social impacts by helping people stay healthy through eating healthy meals. Experiments have been performed on a data set which includes a list of daily serving complete foods considering nutrients as constraints to be satisfied. Our goal is to show that modelling the problem with many objectives can result in more realistic, accurate and applicable meal plans for different user types.
Diet problem
Although the goal of the diet problem is to have and maintain a healthy life nowadays, it originally arose as a microeconomic problem to minimise cost and mostly tried to be solved by economists. During World War 2, the diet optimisation came into question for the US Army to minimise the cost of menus for soldiers which was the same as the Stigler’s diet question 17 : ‘Which quantities of 77 different foods should be consumed by a 154-pound male in order to satisfy the required limits of 9 different nutrients while minimising the cost’.
Since Stigler’s basic diet approach was based on economic concerns, it is not adequate for today’s diet expectations. Nowadays, people have many other goals beside minimising the cost of the menu, for example, preference, diversity of the meal plan, availability. As Garille and Gass 15 noted in their work, a many-objective version of the diet problem is needed to have an applicable and realistic diet approach.
Eghbali et al. 18 considered the diet problem as a multi-objective fuzzy linear programing problem with preference and cost objectives. Amin et al. 19 used a linear programing approach to solve the multi-objective diet problem by minimising saturated and trans fats, minimising sugar, maximising fibre besides minimising cost. Gumustekin et al. 20 tried to solve the single-objective diet problem by Bayesian Optimisation Algorithm (BOA), which is an Estimation of Distribution Algorithm (EDA). Porras et al. 21 tried to solve the single objective version of the diet problem by Particle Swarm Optimisation. A bi-objective version of the diet problem is studied in two works22,23 where an additional objective used to maximise the food preference besides minimising the costs. Balcı and Uyar 24 studied a bi-objective diet problem using fuzzy inference system to map many-objective diet problem into bi-objective version. Their findings are promising, but the daily meals recommended by their algorithms are poor in variety of dishes.
Foraging theory
Optimal Foraging Theory (OFT) is a popular theory in behavioural ecology literature which was first formulated in 1966 by MacArthur and Pianka. 14 OFT states that those animals having behavioural strategies to maximise their net energy intake per unit time spent while foraging are advantageous in the natural selection process. According to the OFT, animals have a degree of ability to modify their behaviours so that they receive an optimal balance of currency and constraints. The best foraging strategy (the optimal decision rule) of an animal is defined as the decision that maximises the currency under the constraints of the environment.14,25,26 Currency is usually counted in terms of net energy intake per unit time or the number of offspring produced while constraints are usually considered to include spent time, risk/safety and wasted energy.
The optimal diet model is one of the most reasonable models to the question ‘why animals often restrict themselves to a few preferred types of foods while there is a wide range of foods available’. The model predicts that foragers should ignore low profitability prey items when more profitable items are present and abundant.27–30 However, there are various factors that exist in nature that can cause animals to deviate from most profitable foods. For example, the safety of the food location (availability, the risk of being a prey to other predators, the safety of its offspring while foraging in far locations), energy/time required to prepare and consume the food. All these factors, which need to be optimised, may force the animal to select less profitable food items.26–30
Optimisation
Optimisation is a procedure of finding an optimal solution(s) for a given problem. An optimisation problem is composed of decision variables, constraint(s), and objective function(s). 31 Optimisation problems can be classified based on the number of objective functions: single- multi- and many-objective. Multi-objective optimisation problems (MOOP) have two or three objectives (usually conflict with each other), on the other hand, many-objective optimisation problems (MaOPs) involve more than three objectives. In single-objective optimisation problems, it is aimed to find an optimal solution. However, two or more objectives always arise in a set of solutions called Pareto set. A solution in the set is called Pareto optimal solution that is not dominated by any other solutions. 31
Evolutionary algorithms are effective solvers for multi/many-objective optimisation problems.31–33 Non-dominated sorting based algorithm (NSGA-III) proposed by Deb and Jain 16 is the state-of-the-art method for MaOPs. They use a set of reference points uniformly distributed across a normalised hyper-plane to handle the exponentially increasing number of non-dominated sets in the selection phase. Each solution is associated with a reference point, which ensures the diversity of the population and non-dominating Pareto set.
Methodology
Formulation of the diet problem
Like the animals, a person also considers optimising many factors/goals when dieting. Besides the cost of the diet, some other factors should also be considered during the diet, including preference, availability, preparation time of the meal and variety of meal plan.15,34 Those objectives are crucial for a person to plan a reasonable diet which does not harm but balance his/her mental, social and economic life quality. By modelling the diet problem as a many-objective optimisation problem, we can have a realistic solution approach which can lead us to healthy eating.
In this study, the diet problem is modelled as a many-objective multi-dimensional knapsack problem. Given a set of food items, the aim is to select a subset of items so that all objectives are optimised simultaneously while not exceeding knapsack capacities.35,36 Unlike knapsack problems, the diet problem has two-sided constraints; besides the upper level, the lower level of the daily nutrient requirements also must be considered. Although we modelled the diet problem as a many-objective problem, for now, we used three objectives: cost, preference, and preparation time. We can formulate the realistic diet problem as given in equation (1).
where
Solution approach
In this study, since the problem has many objectives and is open to adding new objectives, NSGA-III, the state-of-the-art many-objective algorithm, is used. In NSGA-III, binary tournament selection, partially-mapped crossover and swap mutation are used as genetic operators. 37
Each candidate solution is represented as a permutation of given items to get close to the feasible area of search space easily. On the other hand, the decision variable in the problem is binary (0/1). Therefore, the candidate solution is decoded into binary form before fitness evaluation.
To design the daily meal plan as breakfast and others (dinner and lunch) we must design the chromosome with two parts. However, we do not have any clue how to share most of the daily nutrient needs amongst meals; there are many guidelines on how to share daily Energy needs. 38 We shared the daily energy needs amongst breakfast and lunch+dinner as 3.5/10 and 6.5/10, respectively. Crossover, mutation and constraint evaluating phases are operated on each part independently, but all constraint violations are passed to the next chromosome part for overall optimisation and evaluation. Energy is the only nutrient considered for breakfast part while all nutrients are considered in the lunch+dinner part and the whole chromosome. For each part, starting with the initial position, each item is added one by one by considering the boundary constraints (see Figure 1). The lower limits for nutrient intakes must be satisfied while adding the items, but the upper limit can be exceeded. For those solutions that have exceeded some nutrients, a penalty function is applied based on the overall proportion of exceeding values over daily needs boundary.

Representation and decoding of solutions.
Experimental design
The daily nutrient requirements are taken from USDA Dietary Reference Intakes (DRI) documents (USDA (US Department of Agriculture) National Nutrient Database for Standard Reference Release 28 (38)). These documents contain the lower and upper boundaries for each nutrient according to personal characteristics, that is, age, body index, gender, lactation, etc. Some nutrients don’t have an upper level such as fibre and most vitamins. Due to lack of information about the amount of lean body mass which highly correlates with the basal or resting metabolic rate, energy DRI boundary has been calculated as ±15% of actual estimated energy requirement (EER).39–41
In this study, we consider a real-world data set which is obtained from the Istanbul Technical University IT department. It contains 356 dishes including breakfast foods with 23 different nutrient values based on the food portions. Each dish has cost, preparation time (including cooking time) and preference values at which the preference values are user dependent. Using a real-world data set makes our meal planning more realistic and applicable. However, the data set has some inconsistent and wrong nutrient values. To handle this inconsistency, we add some tolerance to upper and lower levels of the DRI values. The
As a result of preliminary experiments, good parameter settings for our approach were determined. All further experiments were conducted with the following parameter settings: the maximum iteration count is 1000, the mutation probability is 0.6, the crossover probability is 0.9, and the population size is 92.
To investigate the behaviour of our approach for different user groups, we designed two cases according to food preferences and age-gender combinations. In the first case, we considered non-vegetarian and ovo-lacto vegetarian users with the same age and gender (25 years old male). In the second case, a 65-year-old female and 25-year-old male users were taken into consideration. Cost, preparation time and preference values are randomly determined in the range 0–10 while preference values of meaty dishes set to 0 for the ovo-lacto vegetarian user.
Results
In this section, we present the results for the two cases. For both cases, two important nutrients, namely energy and protein are considered. Radar graphs are used to illustrate the levels of nutrient intakes of all recommended menus from one run of the algorithm for different user profiles. In radar charts, each point corresponds to one solution in the pareto front.
Figure 2 shows the level of energy and protein intakes for non-vegetarian and ovo-lacto vegetarian users. In these figures, the red and green areas indicate the non-vegetarian and ovo-lacto vegetarian users, respectively. The average protein and energy intake values for ovo-lacto vegetarians are lower than those for non-vegetarians. Without including energy-rich and protein-rich foods from the data set, vegetarian menus generally satisfy those nutrients just above low levels.

Energy and protein satisfaction levels of all menus for a non-vegetarian and an ovo-lacto vegetarian user.
On the other hand, Figure 3 provides the level of energy and protein intakes for two users with different genders and ages, respectively. In these figures, the red and green areas indicate a 65-year-old female and a 25-year-old male user, respectively. Since the nutritional requirements are different, the average protein and energy intake values for the 65-year-old female individual are satisfied at lower values than those for the 25-year-old male individual.

Energy and protein satisfaction levels of all menus for a 65-year-old female and a 25-year-old male user.
We also provide the contribution of each dish in a selected menu to objective functions by using a radar chart. Figure 4 shows the radar charts for a non-vegetarian user and an ovo-lacto vegetarian user. In these charts, the green, red and blue regions indicate preference, cost, and preparation time, respectively. Additionally, each point indicates each dish in the given menu. The green region should be as large as possible since the preference of users should be maximised. On the other hand, the red and blue regions should be as small as possible.

Contribution of each dish to objective functions: (a) non-vegetarian user and (b) ovo-lacto vegetarian user.
Discussion
Based on the experimental results, our algorithm can offer optimised menus to different types of users taking into consideration the daily lower and upper bounds for nutrient intakes according to user specifications such as gender, age and body index. All solutions satisfy the lower and upper DRI levels (with ε values) of nutrients for the user while all objectives are optimised. Based on the results from this study about user types and preferences, the DRI levels change while DRI satisfaction levels and recommended menus change accordingly. Instead of foods with meat, substitution foods are included in ovo-lacto vegetarian menus. Therefore, energy and protein nutrients are satisfied close to the lower bounds for ovo-lacto users while they are satisfied at various levels between lower and upper bounds for non-vegetarian users. These results show the effect of the preference objective. In the recommended menu given in Figure 4, most dishes are dishes that the user likes. Additionally, this menu has low cost and short preparation time.
Our healthy eating tool provides people with a menu of dishes by considering many aspects such as minimum cost, short preparation time, palatability and nutritional requirements. Optimising a diet with many aspects makes the diet as a healthy eating plan. However, it is hard to schedule such a diet by hand or other approaches. Therefore, our approach can be used as a reliable, automated, computer-based meal planner individually or by dietitians as a decision support mechanism. Dietitians can use it as a helper tool to provide personalised diet menus to their patients. On the other hand, the widespread use of such a tool can make an impactful contribution to public health against infectious diseases and other malnutrition-based diseases while altering poverty-malnutrition trade-off in favour of the people by sufficient and cheap menu plans.
In the experimental part, we used a real-world dataset which contains the breakfast foods and the complete recipes (like soup, salad) instead of individual food items (like carrot). Therefore, our healthy eating tool provides more realistic, accessible and applicable meal plans for different user types. Additionally, our dataset contains the dishes mostly from dishes which people in Turkey are familiar with. Since our tool is compatible with other datasets, it can be easily applied to the public health nutrition system in other countries, by replacing the dataset with dishes from their own regional cuisines.
This work differs from most of similar previous works22–24 with modelling, diversity of the daily menu and dataset. The diversity of the menu is one of the biggest problems with previous works. In this work, the daily menu is divided into breakfast and lunch+dinner by which the menu is forced to have breakfast dishes and have higher diversity. Instead of general food datasets, a real world dataset with complete dishes is used which make our approach more realistic and applicable compared with previous works.22,23 Despite being multi-objective, Amin’s study 19 is far different from our approach in terms of objectives and modelling. They tried to minimise harmful ingredients while our approach is a many objective optimisation approach with nutrient satisfaction.
Conclusion and future directions
In this study, the diet problem was modelled as a many-objective optimisation problem inspired from optimal foraging theory. A well-known many-objective evolutionary algorithm was applied to the problem. Permutation representation, constraint handling techniques and proper genetic operators were considered as part of our approach. A real-world data set was used in the experiments.
Our approach can provide pleasant menus for different user types all around the world with satisfying nutritional requirements. It should be noted that our approach is basically for healthy people who want to stay healthy with currently used DRI standard values. However, it can be adapted for users with health issues easily by adding proper constraint(s) and altered DRI values. Although we used three objectives in the model, other possible objectives such as maximising the number of food groups in a menu or minimising carbon footprint of the menu can be considered. As a future study, we plan to add new objectives to our approach (e.g. maximising food diversity by maximising food groups) and to solve the problem with other MOEAs to find the most suitable algorithm based on the number of objectives. Since it is important to optimise each meal in a balanced way based on energy sharing, we plan to split the daily meal plan as breakfast, lunch, dinner and snacks which will also contribute to the diversity of the meal plan. On the other hand, it is important to balance the daily energy gain from protein, carbohydrate and fat where each needs to have a specific contribution which needs to be considered in the healthy diet approach.
Footnotes
Author contribution
CT, BK and SU were responsible for the study conception and design. CT, BK and SU were responsible for the collection, analysis, interpretation of the data and contributed to the writing of the manuscript. CT had overall responsibility for the final content. All authors critically reviewed the manuscript and approved the final version submitted for publication.
Transparency
The lead author affirms that this manuscript is an honest, accurate, and transparent account of the study being reported. The lead author affirms that no important aspects of the study have been omitted.
Declaration of conflicting interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.
Funding
The author(s) received no financial support for the research, authorship, and/or publication of this article.
