Leonid Solonitsyn

Faculty of computer science and technology (CST)

Department of automated control systems (ACS)

Speciality Information systems and technologies in engineering and business

Hardware optimization in logic circuits of control units

Scientific adviser: Ph.D., associate professor of ACS Svetlana Zemlyanskaya

Resume Abstract

Abstract

Contents

• 1. Theme urgency
• 2. Goal and tasks of the research
• 3. Description of the problem
• 4. Mathematical formulation of the problem
• Conclusion
• References

1. Theme urgency

The youngest pre-school educational institution, or kindergarten, is an institution for the education of children of pre-school age from 1.5 to 7 years. They, as a type of educational institution, exist in most countries and are usually the first step in the education system, if not taking into account the education received from parents. In each kindergarten, the tasks of creating a perspective and daily menu are performed. Responsibilities for performing these tasks usually lie on the shoulders of a medical worker.

Recently, in the CIS countries, they began to abandon the regular position of a nurse, one of whose duties is to draw up a perspective and daily menu according to the established standards, since in the part of kindergartens some people worked as nurses who were former managers, lawyers, and other people with non-medical qualifications, which, of course, did not affect the overall health of children positively.

As a result, the task of creating a perspective and daily menu is shifted to other people: the head of the kindergarten, the storekeeper, the cook, and so on. However, all of them are interested parties and could be guided by not only established SanPiN norms, but by what will benefit them. This applies primarily to perishable products, which are usually delivered to kindergartens once a week, such as liver, dairy products (milk and curd first), and some meat products that cannot be stored for more than 36 hours in a warehouse. For example, if the menu is compiled by storekeeper and he has one of these products in stock, and more than 36 hours have already passed since the beginning of storage, he can add a dish with it to the menu to get rid of it, which can harm children's health. That is why such interested parties should not be involved in this task. Therefore, there is a need to create an intelligent system that, based on certain parameters, will compile perspective and daily menus that will meet the norms of SanPiN.

2. Goal and tasks of the research

The purpose of the research is to increase the efficiency of the kindergarten, namely, reducing the time spent in compiling the menu and improving the diversity and nutrional balance of meal plans.

To achieve this goal it is necessary to solve the following tasks that will be performed in the sections of the master's work:

1. Examine existing methods and algorithms for compiling menus (meal plans)
2. Develop a mathematical model for compling a kindergarten meal plan, taking into account certain limitations
3. Develop a modified genetic algorithm for compiling menus (meal plans)
4. Experimentally verify the effectiveness of the algorithm

The object of the study is the process of compiling a meal plan in kindergarten.

The subject of the research is the preparation of optimal perspective and daily meal plans in kindergarten meeting the established constraints and norms of SanPiN.

3. Description of the problem

Consider the task of creating a perspective and daily menu in more detail. This task is an optimization task. The input data is a list of products from the kindergarten warehouse, the output is a perspective menu for a certain period or a daily menu.

The compilation of a perspective and daily menu in kindergarten is done by a nurse at regular intervals. The nurse compiles a perspective menu once for a certain period of time, for example, a prospective menu for two weeks. The daily menu is compiled only if the supply plan has been violated, and as a result, the warehouse lacks the necessary products to follow the previously compiled menu for the given period.

The general algorithm for compiling the daily menu can be represented as follows.:

1. Getting a list of products in stock.
2. The choice of dishes for each of the meals.
3. Checking the finished menu for compliance with established standards and requirements.
4. Paragraphs 2-3 are repeated until the desired result is achieved.

This algorithm is repeated the necessary number of times when the perspective menu is compiled for a certain number of days, and at the end, the general totals are summed up according to the plan, and the plan for the delivery of products is approved.

The described procedure is complicated by the fact that there are a large number of recipes approved for cooking in preschool child care facilities, which leads to the following problems:

• the process of compiling the menu can take a long time, because people rarely immediately select the optimal combination of dishes;
• subjectivity in the choice of dishes, since all people have their own food preferences;
• error when calculating the required number of products and summing up the menu, because when summing up, you can simply make a mistake or not notice something, and then you have to do everything anew.

These problems are an integral part of any process in which a person participates. However, it is possible to almost completely eliminate them when using automated software.

4. Mathematical formulation of the problem

Given:

• amount of children K;
• set of products in stock P;
• set of their price per unit Q;
• list of norms for the menu for the day, such as calories Cal_d, fats Fat_d, proteins Pr_d and carbohydrates Carb_d
• their possible deviations from the norm (ΔCal_d, ΔFat_d, ΔPr_d and ΔCarb_d respectively);
• set of dishes B with their products R, in other words their recipe;
• set of prices for dishes C_b;
• content of calories Cal_b, fats Fat_b, proteins Pr_b and carbohydrates Carb_b in one dish per child.

It is required to find such a combination of dishes (menu) that is permissible and most optimal, while its parameters – total price C, calories Cal, carbohydrates Carb, fats Fat, and proteins Pr – should aim to given norms. Permissable is a combination of dishes for which there are products in stock for cooking it for K children, and the values of its parameters C, Cal, Fat, Pr, Carb are within given norms, taking into account the permissible deviations:

The most optimal is the combination of dishes, which is permissible, and the parameters C, Cal, Pr, Fat and Carb of which are as close as possible to the specified norms.

The constraints in this problem are:

• The amount of product in the combination of dishes p_i must not exceed the quantity of the product in stock P_i, i = 1, ..., n.
• The amount of calories in the combination of dishes Cal must be close to norm Cal_d with an error ΔCal_d.
• Similar constraints exist for price C, fats Fat, proteins Pr and carbohydrates Carb

Taking into account the above indicated, the following objective function was compiled:

where

• G_i(X) – function to calculate how close the X parameter is to its optimal value;
  
• g_i – priority parameter of the corresponding parameter

The priority is usually equal for all parameters (i.e., equal to 1), but sometimes it can be different if, for example, it is necessary to restore the balance of proteins-fats-carbohydrates, which was disturbed in past days

Since it is important for us that all the parameters lie in the intervals that we set, a conditional function was created that performs this task and depending on the proximity to the desired values, the value of that function changes for the better:

where

• ub – upper bound of the parameter X;
• lb – lower bound of the parameter X;
• ia – ideal (target) value of the parameter X;
• w – the ratio of the current amount of the parameter X to ub, ia or lb, depending on the current function, for example, w_ia means that this is the ratio of the current value of the parameter X to the ideal value;
• d – function value for a parameter by default, you can change it for each parameter separately, in order to manage the parameter evaluation

On this basis, the formalized mathematical formulation of the problem is as follows:

where

• $p_{\mathrm{i}}=\sum _{j=1}^n{R}_{\mathrm{ji}}$ – the amount of product p_i spent per child;
• Cal = 9Fat + 4Carb + 4Pr – formula for calculating the number of calories in the menu plan;
• $\mathrm{Carb}=\sum _{j=1}^n{\mathrm{Carb}}_{b_{\mathrm{j}}}$ – formula for calculating the amount of carbohydrates in the menu plan;
• $\mathrm{Pr}=\sum _{j=1}^n{\mathrm{Pr}}_{b_{\mathrm{j}}}$ – formula for calculating the amount of proteins in the menu plan;
• $\mathrm{Fat}=\sum _{j=1}^n{\mathrm{Fat}}_{b_{\mathrm{j}}}$ – formula for calculating the amount of fats in the menu plan;
• $C=\sum _{j=1}^n{C}_{b_{\mathrm{j}}}$ – formula for calculating cost of the menu plan.

However, this mathematical model does not reflect the following conditions and limitations, which must also be taken into account when drawing up the menu and taken into account when implementing algorithms:

1. A variety of dishes. Meals can be repeated only once ν days, since children from 1 to 7 years old are required variety in food.
2. It is undesirable to combine some dishes and products in one meal, as they can lead to undesirable and harmful consequences for the child's body, or simply cause the child to not eat.
3. The priorities of dishes. Some meals include perishable products, such as liver or milk, that need to be realized as soon as possible. Therefore, a possible menu with them should be of higher priority than without them.
4. The period for which menu is compiled. This condition is applicable only when a perspective menu is made. Usually, when preparing a perspective menu for D days, products in stock are counted only on the first day, and for the remaining D-1 days it is not included, as future deliveries will be planned for these days.

All of these conditions and limitations are important to the menu development process and were taken into account when creating models of algorithms for the implementation of the system.

Conclusion

At this stage of the master's work, an analysis was made of the process of preparing meal plans in kindergartens. A mathematical formulation of the problem was done. Also, the basic algorithms that solved this problem were analyzed.

The ACO, although it is a powerful tool for a certain class of problems, has a significant drawback in this type of tasks – with more strong constraints, the speed of the algorithm starts to decrease significantly.[3,6]

The Computational Nutrition algorithm looks quite promising, because according to tests from the authors of the method, it allows you to find valid solutions almost always, but it has the same drawback as ACO in this type of problem – the stronger the constraints, the slower the algorithm.[5]

The genetic algorithm among all considered algorithms is the most flexible, since allows you to examine dozens and hundreds of possible options, and does not examine them one by one. [1-2,7] Therefore, to solve the problem, it was decided to use a modified genetic algorithm, which will make it possible to obtain optimal solutions, taking into account the specifics of making meal plans in kindergartens.

In the future, software implementation of the modified genetic algorithm will be developed and experimental determination of the optimal parameters of said implementation will be done to achieve its maximum performance.

At the time of writing this abstract the master's work is not completed yet. Expected completion date – May 2018. The full text of the work and materials on the topic can be obtained from the author or his scientific adviser after the specified date.

References

1. Catalan-Salgado E-A, Zagal-Flores R., Torres-Fernandez Y., Paz-Nieves A. A Diet Generator Using Genetic Algorithms // Research in Computer Science (2014) (75):71-77 [Electronic resource] [Link]
2. Gaál B., Vassányi I., Kozmann G. A novel artificial intelligence method for weekly dietary menu planning // Methods Archive 44.5 (2005): 655-664 [Electronic resource] [Link]
3. Rusin M., Zaitseva E. Hierarchical heterogeneous ant colony optimization // Computer Science and Information Systems (FedCSIS), 2012 Federated Conference on. IEEE, 2012. [Electronic resource] [Link]
4. Sundmark N. Design and implementation of a constraint satisfaction algorithm for meal planning. – 2005. [Electronic resource] [Link]
5. Pikes T., Adams R. Computational Nutrition: An Algorithm to Generate a Diet Plan to Meet Specific Nutritional Requirements // E-Health Telecommunication Systems and Networks, 5 (2016), 31-38. doi: 10.4236/etsn.2016.52004. [Electronic resource] [Link]
6. Dorigo M., Stützle T. Ant Colony Optimization: Overview and Recent Advances. M. Gendreau and Y. Potvin, editors, Handbook of Metaheuristics, 2nd edition. Vol. 146 in International Series in Operations Research & Management Science, pp. 227-263. Springer, Verlag, New York, 2010.
7. Скобцов Ю. А. Основы эволюционных вычислений. – Донецк: ДонНТУ, 2008. – 326 с. – ISBN 978-966-377-056-6.
8. Солоницын Л.П., Землянская С.Ю. Гримута А.В., Смирнов И.В. Интеллектуальная система составления перспективного и ежедневного меню в условиях младшего дошкольного воспитательного учреждения // Материалы IX Международной научно-технической конференции «Информатика, управляющие системы, математическое и компьютерное моделирование» (ИУСМКМ-2018). – Донецк: ДонНТУ, 2018. – с. 46-51 [Electronic resource] [Link]
9. Комарцова Л.Г. Подход к построению параллельного генетического алгоритма // Материалы международной научно-технической конференции студентов, аспирантов и молодых ученых. – МГТУ им. Н.Э. Баумана (Калужский филиал). – 2011. [Electronic resource] [Link]
10. Скаков Е.С. Метод поиска с запретами для оптимизационных задач // Новое слово в науке и практике: гипотезы и апробация результатов исследований: тр. 15-й Междунар. конф., Новосибирск, 23 января 2015 г., 2015. С. 155-171 [Electronic resource] [Link]