Реферат за темою випускної роботи

Зміст

1. Актуальність теми
2. Мета і задачі дослідження та заплановані результати
3. Опис задачі
4. Математична постановка задачі
Висновки
Список джерел

1. Актуальність теми

Молодший дошкільний виховний заклад, або дитячий сад, є установою для освіти дітей дошкільного віку від 1,5 до 7 років. Вони, як тип освітніх установ, існують в більшості країн і, звичайно, є першою сходинкою в системі освіти, якщо не брати до уваги освіту, отриману від батьків. В кожному дитячому саду виконуються завдання складання перспективного і щоденного меню. Обов'язки щодо виконання даних завдань, зазвичай, лежать на плечах медичного працівника.

Останнім часом в країнах СНД почали відмовлятися від штатної позиції медичної сестри, однією з обов'язків якої є складання перспективного і щоденного меню згідно з установленими нормами, так як в частині дитячих садків працювали медичними сестрами та колишні завідувачі, і юристи, і люди з іншої, не медичної, кваліфікації, що, зрозуміло, позитивно на загальне здоров'я дітей не впливало.

Внаслідок цього завдання складання перспективного і щоденного меню перекладається на інших людей: завідувача дитячим садом, комірника, кухарі і так далі. Однак, всі вони особи зацікавлені і при складанні страв можуть керуватися не тільки встановленими СанПіН, але і вибирати такі страви і їх порції, які підуть їм на користь. Це стосується в першу чергу швидкопсувних продуктів, які, зазвичай, поставляються в дитячі садки один раз в тиждень, таких як печінка, молочні продукти (молоко і сир в першу чергу), деякі м'ясні продукти, які не можна зберігати більше 36 годин на складі. Наприклад, якщо меню складає комірник і у нього на складі є один з цих продуктів, з моменту початку зберігання якого вже пройшло більше 36 годин, він може додати страву з ним в меню для позбавлення від нього, що може нашкодити здоров'ю дітей. Саме тому подібні зацікавлені особи не повинні залучатися до виконання даного завдання. Тому існує необхідність створення інтелектуальної системи, яка на основі певних параметрів буде складати перспективні і щоденні меню, які будуть відповідати нормам СанПіН.

2. Мета і задачі дослідження та заплановані результати

Метою проведених досліджень є підвищення ефективності роботи дитячого садка, а саме зменшення часу проведеного за складанням меню і поліпшення різноманітності і збалансованості планів харчування.

Для досягнення поставленої мети необхідно вирішити такі завдання, які будуть виконані в розділах магістерської роботи:

Дослідити існуючі методи і алгоритми складання меню
Розробити математичну модель складання плану харчування для дитячого саду з урахуванням обмежень
Розробити модифікований генетичний алгоритм складання плану харчування
Експериментально перевірити ефективність роботи алгоритму

Об'єктом дослідження є процес складання плану харчування в дитячому садку.

Предметом дослідження є складання оптимальних перспективних і щоденних планів харчування в дитячому садку задовольняє встановленим обмеженням і нормам СанПіН.

3. Опис задачі

Розглянемо задачу складання перспективного і щоденного меню докладніше. Дане завдання є завданням оптимізації. Вхідними даними є список продуктів зі складу дитячого садка, вихідними - перспективне меню за певний період або щоденне меню.

Складання перспективного і щоденного меню в дитячому саду виконується медсестрою в певні проміжки часу. Перспективне меню медсестра становить один раз на певний період часу, наприклад, перспективне меню на два тижні. Щоденне меню складається лише в тому випадку, якщо план поставок був порушений, і в результаті цього на складі відсутні необхідні продукти для проходження складеним раніше перспективному меню на даний період.

Загальний алгоритм складання щоденного меню можна представити таким чином:

Отримання списку наявних на складі продуктів.
Вибір страви для кожного з прийомів їжі.
Перевірка готового меню на відповідність встановленим нормам і вимогам.
Пункти 2-3 повторюються до досягнення необхідного результату.

Даний алгоритм повторюється необхідну кількість разів, коли перспективне меню складається на кілька днів, а в кінці підбиваються загальні підсумки за планом, і затверджується план поставки продуктів.

Описана процедура ускладнюється тим, що рецептів страв, затверджених для приготування в дошкільних дитячих установах, існує велика кількість, що призводить до виникнення наступних проблем:

процес складання меню може зайняти тривалий час, тому що людина рідко відразу вибере оптимальну комбінацію страв;
суб'єктивність при виборі страв, тому що у всіх людей є свої переваги у стравах;
похибка при розрахунку необхідної кількості продуктів і підведенні підсумків по меню, т.к. при підведенні підсумків можна просто помилитися або не помітити щось, і потім доведеться перераховувати все заново.

Ці проблеми є невід'ємною частиною будь-якого процесу, в якому бере участь людина. Однак є можливість їх практично повністю усунути при використанні автоматизованого програмного забезпечення.

4. Математична постановка задачі

Дано:

кількість дітей K;
множина продуктів на складі P;
множина їх вартості за одиницю виміру Q;
список норм для меню на день, таких як кількість калорій Cal_d, жирів Fat_d, білків Pr_d і вуглеводів Carb_d
їх можливі відхилення від норми (& Delta;Cal_d, ΔFat_d, ΔPr_d і ΔCarb_d відповідно);
множина страв B з вхідними в них продуктами R, інакше кажучи їх рецептурою;
свартість страв С_b;
Зміст калорій Сal_b, жирів Fat_b, білків Pr_b і вуглеводів Carb_b в однієї порції страви на дитину.

Потрібно знайти таку комбінацію страв (меню), яка є допустимою і найбільш оптимальною, при цьому її параметри – загальна вартість C, кількість калорій Cal, вуглеводів Carb, жирів Fat і білків Pr – повинні прагнути до заданим нормам. Допустимої є комбінація страв, для якої є продукти на складі для приготування її на К дітей, і значення її параметрів С, Cal, Fat, Pr, Carb лежать в межах відповідних норм з урахуванням допустимих відхилень:

\{\begin{matrix} C = C_{d} \pm {ΔC}_{d} \\ Cal = {Cal}_{d} \pm {ΔCal}_{d} \\ Fat = {Fat}_{d} \pm {ΔFat}_{d} \\ \Pr = \Pr_{d} \pm {ΔPr}_{d} \\ Carb = {Carb}_{d} \pm {ΔCarb}_{d} \end{matrix}

Найбільш оптимальною є комбінація страв, яка допустима, і параметри C, Cal, Pr, Fat і Carb якої максимально близькі до заданим нормам.

Обмеженнями в даній задачі служать:

Кількість продукту в комбінації блюд p_i не повинно перевищувати кількість продукту на складі P_i, i = 1, …, n.
Кількість калорій в комбінації блюд Cal має бути близько до норми Cal _d з похибкою в ΔCal_d.
Аналогічні обмеження існують для вартості С, кількості жирів Fat, білків Pr і вуглеводів Carb

З урахуванням наведених вище позначень була складена наступна цільова функція:

F = g_{1} \times G_{1} (C) + g_{2} \times G_{2} (Cal) + g_{3} \times G_{3} (Carb) + g_{4} \times G_{4} (Fat) + g_{5} \times G_{5} (Pr),

где

G_i(X) – функція для розрахунку того, наскільки параметр Х близький до свого оптимального значення;
g_i – коефіцієнт пріоритету відповідного параметра

Пріоритет зазвичай у всіх параметрів рівний, але іноді може відрізнятися, якщо, наприклад, необхідно відновити баланс білків-жирів-вуглеводів, який був порушений в минулі дні.

Так як нам важливо, щоб всі параметри лежали в встановлених нами проміжках, і в залежності від близькості до бажаних значень змінювалося і значення цільової функції в кращу сторону, то була складена умовна функція, яка виконує це завдання:

G_{i} (X)  = \{\begin{matrix} w_{>ub} - d_{>ub}, \infty \geq X > ub \\ w_{<ub} - d_{<ub}, ub \geq X > ia \\ w_{ia} + d_{>lb}, ia \geq X > lb \\ w_{>lb} - d_{<lb}, lb \geq X > 0 \end{matrix},

де

ub – верхня межа параметра Х;
lb – нижня межа параметра Х;
ia – ідеальне (цільове) значення параметра X;
w – відношення поточної кількості параметра Х до ub, ia або lb, в залежності від поточної функції, наприклад, w_ia значить, що це відношення поточного значення параметра Х до ідеального значення;
d – значення функції для параметра за замовчуванням, можна змінювати його для кожного параметра окремо, для того щоб управляти оцінкою параметра

Виходячи з цього, формалізована математична постановка виглядає наступним чином:

F = g_{1} \times G_{1} (C) + g_{2} \times G_{2} (Cal) + g_{3} \times G_{3} (Carb) + g_{4} \times G_{4} (Fat) + g_{5} \times G_{5} (Pr) \to \max

\{\begin{matrix} K \times p_{i} \leq P_{i}, i = 1,2,...,n; \\ {Cal}_{d} - {ΔCal}_{d} \leq Cal \leq {Cal}_{d} + {ΔCal}_{d} \\ {Carb}_{d} - {ΔCarb}_{d} \leq Carb \leq {Carb}_{d} + {ΔCarb}_{d} \\ \Pr_{d} - {ΔPr}_{d} \leq \Pr \leq \Pr_{d} + {ΔPr}_{d} \\ {Fat}_{d} - {ΔFat}_{d} \leq Fat \leq {Fat}_{d} + {ΔFat}_{d} \\ C_{d} - {ΔC}_{d} \leq C \leq C_{d} + {ΔC}_{d} \\ p_{i} \geq 0 i = 1,2,...,n; \\ K, Cal, Carb, Pr, Fat, C < 0 \end{matrix}

де

$p_{i} = \sum_{j = 1}^{n} R_{ji}$ – витрачається кількість продукту p_i на одну дитину;
Cal = 9Fat + 4Carb + 4Pr – формула для розрахунку кількості калорій в плані меню;
$Carb = \sum_{j = 1}^{n} {Carb}_{b_{j}}$ – формула для розрахунку кількості вуглеводів в плані меню;
$\Pr = \sum_{j = 1}^{n} \Pr_{b_{j}}$ – формула для розрахунку кількості білків в плані меню;
$Fat = \sum_{j = 1}^{n} {Fat}_{b_{j}}$ – формула для розрахунку кількості жирів в плані меню;
$C = \sum_{j = 1}^{n} C_{b_{j}}$ – формула для розрахунку вартості плану меню.

Однак, дана математична модель не відображає наступні умови і обмеження, які також необхідно враховувати при складанні меню і брати до уваги при реалізації алгоритмів:

Різноманітність страв. Страви можуть повторюватися лише раз в ν днів, так як дітям від 1 року до 7 років потрібно різноманітність в їжі.
Деякі страви і продукти небажано поєднувати в одному прийомі їжі, так як вони можуть призвести до небажаних і шкідливих наслідків для організму дитини, або просто викликати у дитини небажання є.
Пріоритети страв. Частина страв включає в себе швидкопсувні продукти, такі як печінка або молоко, які необхідно реалізувати якомога швидше. Тому можливе меню з ними має бути більш пріоритетним, ніж без них.
Період, на який складається перспективне меню. Ця умова може бути застосовано лише тоді, коли складається перспективне меню. Зазвичай при складанні перспективного меню на D днів продукти на складі враховуються лише в перший день, а на решту D-1 дні воно складається без їх урахування, так як на ці дні будуть плануватися майбутні поставки.

Всі ці умови і обмеження є важливими для процесу складання меню і були прийняті до уваги при складанні моделей алгоритмів для реалізації системи.

Висновки

На даному етапі виконання магістерської роботи був проведений аналіз процесу складання планів харчування в дитячих садах. Була сформульована математична постановка поставленого завдання. Також, було проаналізовано основні алгоритми, якими вирішувалася подібна цій завдання.

Мурашиний алгоритм, хоча і є потужним засобом для певного класу задач, в даному типі завдань має істотний недолік – при більш жорстких обмеженнях алгоритм починає істотно сповільнити свою роботу.[3,6]

Алгоритм Computational Nutrition виглядає досить перспективно, тому що згідно з тестами від авторів методу він дозволяє знаходити валідниє рішення практично завжди, але володіє тим же самим недоліком що і мурашиний в даному типі завдань – чим жорсткіше обмеження, тим більше сповільнюється робота алгоритму.[5]

Генетичний алгоритм є серед всіх розглянутих алгоритмів найбільш гнучким, тому що дозволяє розглядати десятки і сотні можливих варіантів, а не розглядає їх переходячи від одного до іншого. [1-2,7] Тому для вирішення поставленого завдання був вирішено використовувати модифікований генетичний алгоритм, який дозволить отримувати оптимальні рішення з урахуванням специфіки складання планів харчування в дитячих садах.

Надалі, передбачається програмна реалізація розробляється модифікованого генетичного алгоритму та експериментальне знаходження оптимальних параметрів самого генетичного алгоритму для досягнення його максимальної швидкодії.

На момент написання даного реферату магістерська робота ще не завершена. Очікувана дата завершення – травень 2018 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Список джерел

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 [Електронний ресурс] [Посилання]
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 [Електронний ресурс] [Посилання]
Rusin M., Zaitseva E. Hierarchical heterogeneous ant colony optimization // Computer Science and Information Systems (FedCSIS), 2012 Federated Conference on. IEEE, 2012. [Електронний ресурс] [Посилання]
Sundmark N. Design and implementation of a constraint satisfaction algorithm for meal planning. – 2005. [Електронний ресурс] [Посилання]
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. [Електронний ресурс] [Посилання]
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.
Скобцов Ю. А. Основы эволюционных вычислений. – Донецк: ДонНТУ, 2008. – 326 с. – ISBN 978-966-377-056-6.
Солоницын Л.П., Землянская С.Ю. Гримута А.В., Смирнов И.В. Интеллектуальная система составления перспективного и ежедневного меню в условиях младшего дошкольного воспитательного учреждения // Материалы IX Международной научно-технической конференции «Информатика, управляющие системы, математическое и компьютерное моделирование» (ИУСМКМ-2018). – Донецк: ДонНТУ, 2018. – с. 46-51 [Електронний ресурс] [Посилання]
Комарцова Л.Г. Подход к построению параллельного генетического алгоритма // Материалы международной научно-технической конференции студентов, аспирантов и молодых ученых. – МГТУ им. Н.Э. Баумана (Калужский филиал). – 2011. [Електронний ресурс] [Посилання]
Скаков Е.С. Метод поиска с запретами для оптимизационных задач // Новое слово в науке и практике: гипотезы и апробация результатов исследований: тр. 15-й Междунар. конф., Новосибирск, 23 января 2015 г., 2015. С. 155-171 [Електронний ресурс] [Посилання]

Солоніцин Леонід Павлович

Факультет комп'ютерних наук та технологій

Кафедра автоматизованих систем управління

Спеціальність Інформаційні системи та технології в техніці та бізнесі

Інтелектуальна система складання перспективного і щоденного меню в умовах молодшого дошкільного виховного закладу

Науковий керівник: к.т.н., доц. Землянська Світлана Юріївна