Преди в тази поредица:

здравословни

Храни на Бащата

Баща ми е интересен човек.

От време на време той подбира здравна тенденция и/или цел за отслабване, която би накарала челюстите на много хора да паднат. Например, веднъж бяхме на 5-дневно пътуване с раници с дължина 50 мили в Гранд Тетонс и баща ми донасяше по един такъв на ден за вечеря и имаше остатъци от витамини за останалата част от прехраната си. Останалите планирахме за около 3000 калории на ден. Той е изпробвал диетите с високо съдържание на мазнини и без мазнини, както и доста други. Той се занимава със загуба на тегло, но също така и с по-дълъг живот, така че освен всичко друго, той има ограничение на калориите.

Наскоро той ме помоли да му помогна да оптимизира диетата си. Той описа схема, която изпълняваше на ръка, за да минимизира броя на калориите, които консумира на ден, като същевременно поддържа минималните хранителни вещества, изисквани от препоръките на FDA. Той имаше електронна таблица с хранителните вещества за всяка храна и електронна таблица с ограниченията за всяко хранително вещество. Искаше да излезе с колекция от ястия (или просто да хвърли цялата храна в блендер) с вкус в рамките на разума, но отговарящ на тези критерии.

По същество той решаваше линейна програма на ръка, приблизително възможно най-добре, с няколкостотин променливи! След като ме попита дали има „някакъв вид математика“, която да му помогне да автоматизира трудоемките си усилия, реших да му помогна. В края на краищата изминаха повече от три години, откакто обещах на читателите си, че ще прилагам линейно програмиране, за да оптимизирам диета (макар че тя беше оптимизирана за разходи, а не за калории).

Въпреки че никога не надхвърляше това, което линейното програмиране може да обработи, доста бързо заявките на баща ми се специализираха извън това, което би заинтересувало читателя. Може би това е естеството на математическите консултации, но изглежда, че когато дадете на някого това, което той иска, той осъзнава, че не е това, което е искал.

Но основните идеи все още са достатъчно актуални. Моето решение е стотина реда python за настройка на входа, използвайки инструментите за изследване на операциите с отворен код на Google като основно решение. Отказ от отговорност: Работя за Google, но не работя в екипа, който е написал този инструмент. Също така нищо в тази публикация не представя възгледите на моя работодател. Това съм само аз и мащабът на този проблем така или иначе е смешен за Google.

Така че тази публикация е наполовина урок, показващ как да се използва обвивката на python or-tools (това е само донякъде документирано), и наполовина показва реалистичен случай на използване за линейно програмиране.

Не позволявайте обаче тази публикация да ви разубеди от убеждението, че линейното програмиране е полезно освен диетата. Хората използват линейно програмиране, за да решават всякакви интересни проблеми. Ето няколко, на които попаднах само през последните няколко седмици:

  • Факторинг на големи матрици
  • Решаване на игри с нулева сума
  • Оптимално настаняване на гости на сватба (Технически те използват цяло число програмиране, което или инструменти могат да направят)

И това дори не е да споменем повсеместните приложения в оперативните изследвания (мрежови потоци, оптимизация на производството, икономика), на които разчита всяка голяма компания. Приложенията изглеждат безкрайни!

Както обикновено, целият код и данни, които използваме при създаването на тази публикация, са достъпни на страницата на Github на този блог.

Актуализация 2018-01-01: С този код баща ми беше изпробвал няколко нежелани техники за готвене: вземете всички съставки и ги хвърлете в омлет или ги смесете в смути. Нещо при готвенето на храната променя хранителното съдържание, така че той твърди, че е трябвало да ги яде повече или по-малко сурови. Получените „ястия“ бяха толкова неприятни, че изглежда се отказа от техниките за оптимизация в този пост. Изглежда крайният край на компромиса за вкус/здраве не е там, където той иска да бъде. Това предполага открит проблем: намерете добър начин да моделирате (или да се опрете на данни) кои храни са вкусни заедно и в какви количества. Човек би могъл да се поучи от корпуса от рецепти, въпреки че си представям, че това може да стигне толкова далеч само за леко приготвени съставки. Но с хипотетични ограничения като „наказвайте/предпочитайте тези храни да бъдат в едно и също хранене“, може да се направи количествена оценка на компромиса за вкус/здраве по начин, който прави баща ми щастлив. Наличието на лесен начин за плъзгане по скалата (а не просто наивно оптимизиране) също би било полезно.

Опреснител

Ако си спомняте как работят линейните програми, можете спокойно да пропуснете този раздел.

Като опресняване, нека да очертаем как да моделираме проблема с храненето като линейна програма и да припомним основните обозначения. Променливите са храна на стъпки от 100 грама. Може да бъде и количеството консумиран грах, месо от омари и др. Всички променливи, разбира се, трябва да са неотрицателни. Целта е да се сведе до минимум общият брой консумирани калории. Ако е количеството калории в 100g консервиран грах, тогава човек би платил в калории, допринесени от грах. Ако имаме различни променливи, тогава целевата функция е линейната комбинация

Използваме получер текст, за да представим вектора. По същия начин ще представлява векторът на разходите за храни. Както сме виждали много пъти, можем компактно да запишем горната сума като вътрешен продукт .

И накрая, ние изискваме количеството на всяко хранително вещество, комбинирано в нещата, които купуваме, да отговаря на някакъв праг. Така че за всяко хранително вещество имаме ограничение. Най-лесният е калориите; ние изискваме общият брой консумирани калории да е поне (да речем) 2000. Така че, ако представлява броят на калориите в храната, ние се нуждаем. Може също да искаме да ограничим максимален брой калории, но като цяло диетата с повече калории предполага по-високи разходи и затова, когато линейната програма свежда до минимум разходите, трябва да очакваме да не произвежда диета със значително повече от 2000 калории.

Тъй като разполагаме с един набор от информация за хранителните вещества за всяка двойка (хранителни вещества, храна), трябва да се насладим на индексирането. Ще нарека количеството хранителни вещества в храната. Имайте предвид, че това ще бъде голяма матрица, затова казвам, че хранителните вещества представляват редовете на матрицата, а храните представляват колоните. Тоест, всеки ред от матрицата представлява количеството на едно специфично хранително вещество във всички храни, а всяка колона представлява хранителното съдържание на една храна. Винаги ще използваме за обозначаване на броя на храните и за обозначаване на броя на хранителните вещества.

И накрая, имаме долна и горна граница за всяко хранително вещество, което зад кулисите се преобразува в долни граници (вероятно отричане на променливите). Това не е необходимо, за да напишете програмата, както ще видим. За отбелязване, ние изискваме, че за всеки, хранителните ограничения са изпълнени. Ако отново използваме векторна нотация за ограниченията, можем да напишем целия набор от ограничения като „матрично уравнение“

И това означава, че всеки запис на вектора, който получавате при умножаване на лявата страна, е по-голям от съответния запис от дясната страна. Така че цялата линейна програма е обобщена, както следва

Това е синтактичната форма на нашата линейна програма. Сега всичко (!), Което трябва да направим, е да изберем набор от храни и хранителни вещества и да попълним константите за .

Хранителни вещества и храни

По-лесното от двете данни е ограничението на хранителните вещества. Системата, използвана в Съединените щати, се нарича система за диетичен референтен прием. Състои се от пет части, които съм перифразирал от Уикипедия.

  • Очаквани средни изисквания (EAR), което се очаква да задоволи нуждите на 50% от хората във възрастова група.
  • Препоръчителни хранителни добавки (RDA), дневното ниво на прием се счита за достатъчно, за да отговори на изискванията на 97,5% от здравите индивиди (две стандартни отклонения).
  • Адекватен прием (AI), където не е установена RDA. Предназначен да допълни RDA, но има по-малко солидни доказателства.
  • Поносими горни нива на прием (UL), най-високото ниво на дневна консумация, които не са показали вредни странични ефекти.

Докато баща ми измисля свой собствен набор от ограничения, тези, които съм публикувал в хранилището на github, по същество са копиране/поставяне от текущата RDA/AI като долна граница, а UL като горна граница. Стойностите, които избрах, са в csv. Липсващи стойности в горната граница означават, че няма горна граница. И съжалявам дами, тъй като за баща ми избрах мъжките ценности. Жените имат малко по-различни стойности поради различен среден размер/тегло.

Стойностите на хранителните вещества за храната са малко по-трудни, тъй като не е лесно да се получат данни за хранителните вещества. Има няколко бази данни, които са непълни и някои от които таксуват за използване. Баща ми прекарва дълго време в търсене на хранителните вещества (той искаше някои допълнителни специални хранителни вещества) за своите 200 най-странни храни.

Вместо това в тази публикация ще използваме безплатната база данни на USDA за 8000+ храни. Той се предлага в един, съкратен, странно форматиран текстов файл, който съм анализирал в csv и съм избрал произволна подгрупа от 800-те храни, с които да си поиграя.

Python ИЛИ Инструменти

Документите на Google за ortools ви молят да изтеглите tarball, за да инсталирате техния пакет, но установих, че това е ненужно (може би е необходимо да прикачите решаващ инструмент на трети страни към техния интерфейс?). Вместо това човек може просто да го инсталира.

След това в скрипт на python можете да импортирате библиотеката на ortools и да създадете проста линейна програма:

Това дава основната идея на библиотеката. Можете да използвате претоварването на оператора на python (до известна степен), за да направите ограниченията да изглеждат добре в изходния код.

Настройване на LP за храна

Основният файл diet_optimizer.py съдържа дефиниция за клас, който освен зареждане на данните, капсулира всички променливи и ограничения.

Ще влезем за момент в променливите и ограниченията, но преди това можем да видим метода за решаване

Тук nutri_in_diet е помощна функция, която, като се има речник на храните и хранително вещество, извежда съдържанието на хранителни вещества за тази храна. Това може да се използва независимо от разтворителя, за да се оцени съдържанието на хранителни вещества в предложената диета.

След това имаме метода за създаване на променливите.

Всяка храна трябва да присъства в неотрицателно количество и аз съм наложил ограничение от 10 (1 кг) за всяка отделна храна. Причината за това е, че първоначално имах ограничение „вода“ и линейната програма реши да оптимизира за това, като помоли човек да пие 2L червено вино на ден. Пренебрегнах да вкарам хранително вещество с алкохол (защото вече го нямаше и съм мързелив), затова вместо това ограничих количеството на всяка отделна храна. Все още изглежда разумно ограничение да се наложи, че никой не би искал да яде повече от 1 кг от която и да е храна за един ден.

И накрая, можем да изградим ограниченията. Основният метод отнема хранително вещество и долна и горна граница:

Този метод е предимно счетоводен, докато food_for_nutrient прави индивидуалното търсене на хранителни вещества. Имайте предвид, че не е позволено да се прави неравенство с двоен край като self.solver.Add (по-ниско. Ако опитате, ortools ще игнорира единия край на обвързаното.

Тук сме малко неефективни, като преглеждаме цялата таблица, вместо само тези храни, съдържащи въпросното хранително вещество. Но в нашата примерна база данни има само няколкостотин храни (8000, ако използвате цялата база данни SR28), така че оптимизацията не е необходима.

Също така имайте предвид, че докато ortools позволява на човек да използва метода sum, той го прави по наивен начин, защото sum ([a, b, c]) става ((a + b) + c), което е проблем, защото ако списъкът е твърде дълъг, тяхната библиотека надвишава ограничението на рекурсия по подразбиране на Python. Вместо това ние конструираме SumArray на ръка.

И накрая, макар да го пропуснахме тук за простота, в целия код в хранилището на Github ще видите препратки към%_constraints. Това съществува, тъй като някои хранителни вещества, като мазнини, се препоръчват да бъдат ограничени до процент от калориите, а не до абсолютно количество. Така че ние дефинираме механизъм за определяне на хранителното вещество, което трябва да се обработва с проценти и картографиране от грамове към калории. Това в крайна сметка използва параметъра scale_by по-горе, както за мащабиране на мазнините с 9 калории на грам, така и за мащабиране на калориите като процент. Вж. специалната функция за създаване на процентни ограничения.

И накрая, имаме методи само за красив печат на оптимизационния проблем и решението, наречени съответно summarize_optimization_problem и summarize_solution.

Стартиране на решавача

Извикването на решаващия инструмент е тривиално.

С примерните храни и ограничения в github repo резултатът е:

За съжаление това изисква килограм сурови кълнове от люцерна, които определено не бих ял. Проблемът е, че люцерна е нелепо питателна. Обобщавайки диетата с поставения флаг print_details, виждаме, че те допринасят значително количество от почти всяко важно хранително вещество.

Но пренебрегвайки това, имаме някои разумно звучащи храни: риба, сладък картоф, розмарин (добре, това е тон розмарин), яйце и вино. Обзалагам се, че някой може да направи вкусно ястие от тези груби съставки.

Разширения и упражнения

Нито един урок не би бил пълен без упражнения. Всички те са свързани с действителния проблем за моделиране на линейна програма.

Групи храни: Да предположим, че сте имали допълнителна графа за всяка храна, наречена „група храни“. Искате да създадете балансирано хранене, така че добавяте допълнително ограничение за всяка хранителна група, изискваща някаква храна, но не твърде много, от всяка група. Освен това, за някои храни като подправки може да се добави специално ограничение за всяка подправка, изискваща не повече от, да речем, 20 g от дадена подправка. Или, както може да се види, линейната програма може да произвежда диети, включващи неприлично големи количества подправки.

Като се започне от даден набор от храни: Да предположим, че имате идея за рецепта (или няколко рецепти за дневни ястия), но искате да добавите каквото и да е друго, за да отговаря на хранителните стандарти. Променете LP, за да позволите това.

Цели числа вариации: Пакетът ortools поддържа и цялостно програмиране. Всичко, което трябва да направите, за да активирате това, е да промените типа на решаващия инструмент на CBC_MIXED_INTEGER_PROGRAMMING. Решителят ще работи нормално и сега можете да създавате целочислени променливи, използвайки solver.IntVar вместо NumVar. Използвайки двоични променливи, може да се дефинират логически ИЛИ ограничения (разберете как трябва да работи това). Дефинирайте нова двоична променлива за всяка храна и дефинирайте ограничение, което прави тази променлива 0, когато храната не се използва, и 1, когато храната се използва. След това добавете термин към проблема с оптимизацията, който наказва наличието на твърде много различни храни в ежедневната диета.

(По-трудно) Вземане на проби: Част от мотивацията за този проект е да се измислят редица различни ястия, които са „добри“ по отношение на този проблем с оптимизацията. Може би има повече от едно оптимално решение или може би има качествено различни диети, които са достатъчно близки до оптималните. Това изпълнение обаче дава детерминистичен резултат. Намерете начин да въведете произволност в програмата, така че да можете да получите повече от едно решение.

Чувствайте се свободни да предлагате други идеи и да разширявате или пренаписвате модела, за да направите нещо съвсем различно. Небето е границата!