Matematika ∩ programozás

Korábban ebben a sorozatban:

programozás

Az Atya ételei

Apám érdekes srác.

Olyan gyakran vesz fel olyan egészségügyi trendet és/vagy fogyási célt, amely miatt sok embernek leesik az állkapcsa. Például egyszer egy 5 napos, 50 mérföldes hátizsákos kirándulásra indultunk a Grand Tetons-ban, apám pedig napi egyet hozott vacsorára, és fennmaradó élelmében vitamintablettákat fogyasztott. A többiek napi 3000 kalóriát terveztek. Kipróbálta a „magas zsírtartalmú” és a „zsírmentes” diétát, és jó néhányat. Fogyásával foglalkozik, de hosszabb ideig is él, ezért többek között kalória-korlátozásban van.

Nemrégiben arra kért, hogy segítsek neki az étrend optimalizálásában. Leírt egy sémát, amelyet kézzel hajtott végre, hogy minimalizálja a naponta elfogyasztott kalóriák számát, miközben fenntartja az FDA ajánlásai által előírt minimális tápanyagtartalmat. Táblázata volt az egyes élelmiszerek tápanyagaihoz, és egy táblázata az egyes tápanyagok korlátozásával. Olyan ételkészletet akart előállítani (vagy csak az összes ételt turmixgépbe dobni), amely ésszerű ízű, de megfelel ezeknek a kritériumoknak.

Lényegében egy lineáris programot oldott meg kézzel, nagyjából a lehető legjobban, néhány száz változóval! Miután megkérdeztem, hogy létezik-e bármilyen matematika, amely segíthet neki fáradságos erőfeszítéseinek automatizálásában, úgy döntöttem, hogy kezet nyújtok. Végül is elmúlt három év, mióta megígértem olvasóimnak, hogy lineáris programozást alkalmazok az étrend optimalizálására (bár ez inkább a költségekre, mint a kalóriákra optimalizálódott).

Bár soha nem lépte túl azt, amit a lineáris programozás képes kezelni, apám kérései elég gyorsan specializálódtak azon túl, ami egy általános olvasót érdekelne. Talán ez a matematikai tanácsadás jellege, de úgy tűnik, amikor azt adod valakinek, amit akar, rájön, hogy nem ezt akarta.

De az alapötletek még mindig elég relevánsak. Megoldásom: a Python száz ish sora a bemenet beállításához, a Google nyílt forráskódú műveletek kutatási eszközeit használva alapvető megoldóként. Jogi nyilatkozat: Dolgozom a Google-nál, de nem abban a csapatban dolgozom, amely ezt az eszközt írta. Ebben a bejegyzésben semmi sem képviseli a munkáltatóm véleményét. Csak én vagyok, és ennek a problémának a mértéke egyébként is nevetséges a Google számára.

Tehát ez a bejegyzés félig oktató, amely bemutatja az or-tools python burkoló használatát (ez csak kissé dokumentált), és fele reális használati esetet mutat a lineáris programozáshoz.

Azonban ne hagyja, hogy ez a bejegyzés lebeszéljen arról a meggyőződésről, hogy a lineáris programozás a diétán túl is hasznos. Az emberek lineáris programozást használnak mindenféle érdekes probléma megoldására. Íme néhány, akikkel csak az elmúlt hetekben találkoztam:

  • Nagy mátrixok faktorálása
  • Nulla összegű játékok megoldása
  • A vendégek optimális elhelyezése egy esküvőn (technikailag egész programozást használnak, amely vagy

És ez nem is említi az üzemeltetési kutatásban mindenütt jelen lévő alkalmazásokat (hálózati áramlás, termelésoptimalizálás, közgazdaságtan), amelyekre minden nagyvállalat támaszkodik. Az alkalmazások végtelennek tűnnek!

Szokás szerint az összes kód és adat, amelyet a bejegyzés készítéséhez használunk, elérhető a blog Github oldalán.

Frissítés 2018-01-01: Ezzel a kóddal apám kipróbált néhány nem tanácsos főzési technikát: vegye be az összes hozzávalót és dobja be egy omlettbe, vagy turmixolja össze őket. Az étel főzése megváltoztatja a tápértéket, ezért állítása szerint többé-kevésbé nyersen kellett megennie. Az így kapott „étkezések” annyira kellemetlenek voltak, hogy úgy tűnik, feladta az ebben a bejegyzésben szereplő optimalizálási technikákat. Úgy tűnik, az íz/egészség kompromisszum végső vége nincs ott, ahol lenni akar. Ez nyitott problémára utal: találjon jó módszert annak modellezésére (vagy támaszkodjon az adatokra), hogy az ételek milyen ízűek és milyen mennyiségben. Lehet, hogy tanulhatunk egy receptkészletből, bár azt képzelem, hogy ez csak enyhén főzött összetevőknél mehet el ennyire. De olyan hipotetikus korlátozásokkal, mint „megbüntetni/előnyben részesíteni ezeket az ételeket ugyanazon étkezés mellett”, képes lehet számszerűsíteni az íz/egészség kompromisszumot oly módon, hogy apámat boldoggá tegye. Hasznos lehet egy egyszerű módja annak, hogy csúsztasson a skálán (ahelyett, hogy csak naivan optimalizálna).

Frissítés

Ha emlékszik a lineáris programok működésére, nyugodtan kihagyhatja ezt a részt.

Frissítésként vázoljuk fel a táplálkozási probléma lineáris programként történő modellezését, és idézzük fel az alapvető jelölést. A változók 100 g-os lépésenkénti élelem. Így lehet az elfogyasztott borsókonzerv mennyisége, homár hús stb. Minden változónak természetesen nem negatívnak kell lennie. A cél az összes elfogyasztott kalória számának minimalizálása. Ha a kalória mennyisége 100 g konzerv borsóban van, akkor a borsó által adott kalóriákban kell fizetni. Ha különböző változataink vannak, akkor a célfüggvény a lineáris kombináció

Félkövér betűt használunk a vektor ábrázolására. Hasonlóképpen képviseli az élelmiszerek költségvektorát. Mint sokszor láttuk, a fenti összeget tömören megírhatjuk belső termékként .

Végül megköveteljük, hogy a megvásárolt cuccokban egyesített tápanyagok mennyisége megfeleljen bizonyos küszöbértékeknek. Tehát minden tápanyagra vonatkozik egy korlátozás. A legegyszerűbb a kalória; megköveteljük, hogy az összes elfogyasztott kalória legalább (mondjuk) 2000 legyen. Tehát ha az élelmiszerekben szereplő kalóriák számát képviseli, szükségünk van rá. Lehet, hogy korlátozni szeretnénk a maximális kalóriaszámot is, de általában a több kalóriát tartalmazó étrend magasabb költségekkel jár, ezért amikor a lineáris program minimalizálja a költségeket, akkor arra kell számítanunk, hogy ne állítson elő olyan étrendet, amely lényegesen több mint 2000 kalóriát tartalmaz.

Mivel minden tápanyag-párra (tápanyag, étel) egy tápanyag-információval rendelkezünk, kedvelnünk kell az indexelést. Meghívom az ételben lévő tápanyag mennyiségét. Vegye figyelembe, hogy nagy mátrix lesz, ezért azt mondom, hogy a tápanyagok a mátrix sorait, az ételek pedig az oszlopokat. Vagyis a mátrix minden sora egy adott tápanyag mennyiségét jelzi az összes ételben, és minden oszlop egyetlen élelmiszer tápanyagtartalmát. Mindig az élelmiszerek számát és a tápanyagok számát fogjuk használni.

Végül minden tápanyaghoz van egy alsó és felső határunk, amelyet a kulisszák mögött alacsonyabb határokká alakítunk (esetleg a változókat tagadva). Erre nincs szükség a program megírásához, mint látni fogjuk. Jelölésként azt követeljük meg, hogy mindenki számára teljesüljön a tápanyag-korlát. Ha ismét a vektorok jelölését használjuk a kényszerekhez, akkor a korlátozások teljes halmazát „mátrixegyenletként” írhatjuk

Ez azt jelenti, hogy a vektor minden bejegyzése, amelyet a bal oldali szorzásával kapunk, nagyobb, mint a megfelelő bejegyzés a jobb oldalon. Tehát a teljes lineáris programot az alábbiakban foglaljuk össze

Ez a lineáris programunk szintaktikai formája. Most már csak annyit kell tennünk (!), Hogy kiválasztunk egy sor ételt és tápanyagot, és kitöltjük az állandókat .

Tápanyagok és élelmiszerek

A két adat közül a könnyebb a tápanyag-korlát. Az Egyesült Államokban használt rendszert étrendi referencia beviteli rendszernek nevezik. Öt részből áll, amelyeket a Wikipédiából fogalmaztam meg.

  • Becsült átlagos követelmények (EAR), várhatóan kielégíti a korcsoportban élők 50% -ának szükségleteit.
  • Ajánlott étrendi juttatások (RDA), a napi beviteli szint elegendőnek tekinthető az egészséges egyének 97,5% -a követelményeinek teljesítéséhez (két szórás).
  • Megfelelő bevitel (AI), ahol nem hoztak létre RDA-t. Az RDA kiegészítésére szolgál, de kevésbé szilárd bizonyítékokkal rendelkezik.
  • Elviselhető felső beviteli szintek (UL), a napi fogyasztás legmagasabb szintje, amely nem mutatott káros mellékhatásokat.

Míg apám előáll a saját megszokott kötöttségével, azok, amelyeket a github-adattárba tettem fel, lényegében az aktuális RDA/AI-ból másolják/illesztik be alsó határként, az UL-t felső határként. Az általam kiválasztott értékek csv-ben vannak. Hiányzó értékek a felső határ oszlopban azt jelentik, hogy nincs felső határ. És sajnálom hölgyeim, mivel apámnak szóltam, a férfi értékeket választottam. A nők kissé eltérő értékekkel rendelkeznek az eltérő átlagos méret/súly miatt.

Az élelmiszerek tápanyagértékei egy kicsit nehezebbek, mert a tápanyagadatok nem könnyűek. Van néhány adatbázis, amelyek mind hiányosak, és amelyek egy része használatáért díjat számít fel. Apám sokáig vadászta a tápanyagokat (további speciális tápanyagokat kívánt) a 200 legnépszerűbb ételéhez.

Ehelyett ebben a bejegyzésben az USDA több mint 8000 élelmiszert tartalmazó, ingyenesen használható adatbázisát fogjuk használni. Egyetlen, rövidített, furcsa formátumú szövegfájlban van, amelyet csv-ként elemeztem és a 800-as élelmiszerek tetszőleges részhalmazát választottam, amellyel játszani.

Python VAGY Eszközök

A Google ortools dokumentumai azt kérik, hogy töltsön le egy tárcsát a csomagjuk telepítéséhez, de én ezt feleslegesnek találtam (talán egy harmadik féltől származó megoldót kell csatolni a felületükhöz?). Ehelyett egyszerűen telepítheti.

Ezután egy python szkriptben importálhatja az ortools könyvtárat, és létrehozhat egy egyszerű lineáris programot:

Ez adja a könyvtár alapötletét. Használhatja a python operátorának túlterhelését (bizonyos mértékig), hogy a megszorítások szépek legyenek a forráskódban.

Az élelmiszer LP beállítása

A diet_optimizer.py fő fájl tartalmaz egy osztály definícióját, amely az adatok betöltése mellett az összes változót és korlátot összefoglalja.

Pillanatnyilag belemerülünk a változókba és a korlátokba, de előtte láthatjuk a megoldási módszert

Itt a tápanyagok az étrendben egy segítő funkció, amely az élelmiszerek szótárát és egy tápanyagot kiadva adja ki az adott tápanyag tartalmát. Ez a megoldótól függetlenül használható a javasolt étrend tápanyagtartalmának értékelésére.

Ezután megvan a módszer a változók létrehozására.

Minden ételnek nem negatív mennyiségben kell lennie, és minden egyes ételre 10 (1kg) sapkát szabtam. Ennek oka az, hogy eredetileg „víz” korlátom volt, és a lineáris program úgy döntött, hogy ezt optimalizálja azzal, hogy megkéri az embert, hogy igyon naponta 2 liter vörösbort. Nem hagytam alkoholtartalmú tápanyagot (mert még nem volt ott, és lusta vagyok), ezért ehelyett korlátoztam az egyes ételek mennyiségét. Még mindig ésszerű korlátozásnak tűnik annak előírása, hogy senki ne akarjon egyetlen nap alatt 1 kg-nál többet enni egyetlen ételből.

Végül elkészíthetjük a megszorításokat. Az alapvető módszer tápanyagot, valamint alsó és felső határt vesz fel:

Ez a módszer többnyire könyvelés, míg a tápanyagok_tápláléka elvégzi az egyes tápanyagok felkutatását. Ne feledje, hogy az ember nem végezhet kettős végű egyenlőtlenséget, mint például az self.solver.Add (alacsonyabb. Ha megpróbálja, az ortools figyelmen kívül hagyja a kötött egyik végét.

Itt kissé hatástalanok vagyunk, ha az egész táblázatot végig iteráljuk, nem csak a szóban forgó tápanyagot tartalmazó ételek helyett. De a minta adatbázisunkban csak néhány száz étel található (8000, ha a teljes SR28 adatbázist használja), ezért az optimalizálás nem szükséges.

Vegye figyelembe azt is, hogy míg az ortools lehetővé teszi az összeg módszer használatát, ezt naiv módon teszi, mert az összeg ([a, b, c]) ((a + b) + c) lesz, ami problémát jelent, mert ha a a lista túl hosszú, könyvtáruk meghaladja a Python alapértelmezett rekurziós korlátját. Ehelyett kézzel készítünk egy SumArray-t.

Végül, bár itt az egyszerűség kedvéért kihagytuk, a Github-adattárban található teljes kódban a percent_constraints hivatkozásokat láthatja. Ez azért van, mert bizonyos tápanyagokat, például a zsírt, ajánlott a kalóriák százalékára korlátozni, nem pedig abszolút mennyiségre. Tehát meghatározunk egy mechanizmust annak meghatározására, hogy egy tápanyagot hány százalékkal kell kezelni, és a grammoktól a kalóriákig történő feltérképezést. Ennek eredményeként a fenti scale_by paramétert használják, mind a zsír 9 kalóriával/grammal történő skálázására, mind a kalóriák százalékos arányban történő skálázására. Vö. a százalékos korlátok létrehozásának speciális funkciója.

Végül, vannak módszereink az optimalizálási probléma és a megoldás szép kinyomtatására, amelyeket összefoglaló_optimációs_probléma és.

A megoldó futása

A megoldó meghívása triviális.

A github repo példáján szereplő ételekkel és korlátozásokkal az eredmény:

Sajnos ez egy kiló nyers lucerna csírát kér, amit biztosan nem ennék meg. A probléma az, hogy a lucerna nevetségesen tápláló. Összefoglalva az étrendet a print_details jelzőkészlettel, azt látjuk, hogy ezek jelentős mennyiségben hozzájárulnak szinte minden fontos tápanyaghoz.

De ezt figyelmen kívül hagyva vannak ésszerű hangzású ételeink: hal, édesburgonya, rozmaring (oké, ez egy csomó rozmaring), tojás és bor. Fogadok, hogy valaki finom ételeket tudna készíteni ezekből a durva alapanyagokból.

Bővítések és gyakorlatok

Egyetlen oktató sem lenne teljes gyakorlatok nélkül. Mindezek a tényleges lineáris programmodellezési problémához kapcsolódnak.

Ételcsoportok: Tegyük fel, hogy minden ételhez volt egy további oszlop, az úgynevezett „élelmiszercsoport”. Kiegyensúlyozott ételt szeretne létrehozni, ezért további korlátozásokat fűz minden egyes élelmiszer-csoporthoz, amelyhez valamilyen étel szükséges, de nem túl sok minden csoporttól. Ezenkívül bizonyos ételek, például a fűszerek esetében külön korlátozást lehetne fűzni minden egyes fűszerhez, amelyhez legfeljebb 20 g szükséges az adott fűszer. Vagy különben, amint az látható, a lineáris program trágáran nagy mennyiségű fűszert tartalmazó étrendet állíthat elő.

Egy adott ételkészletből kiindulva: Tételezzük fel, hogy van ötleted egy receptre (vagy pár receptre egy napi étkezéshez), de hozzá akarsz adni mindent, ami szükséges ahhoz, hogy megfeleljen a táplálkozási normáknak. Módosítsa az LP-t ennek engedélyezéséhez.

Egész variációk: Az ortools csomag támogatja az egész programozást is. Ehhez csak annyit kell tennie, hogy megváltoztatja a megoldó típusát CBC_MIXED_INTEGER_PROGRAMMING-re. A megoldó a szokásos módon fog futni, és mostantól a solV.IntVar használatával egész számértékű változókat hozhat létre a NumVar helyett. A bináris változók segítségével meghatározhatunk logikai VAGY korlátozásokat (kitalálhatjuk, hogy ennek hogyan kell működnie). Határozzon meg egy új bináris változót minden egyes ételhez, és határozzon meg egy korlátozást, amely ezt a változót 0-ra teszi, ha az ételt nem használják, és 1-t, ha az ételt használja. Ezután adjon hozzá egy kifejezést az optimalizálási problémához, amely bünteti a túl sok különféle étel napi étrendjét.

(Nehezebb) mintavétel: Ennek a projektnek az a motivációja, hogy számos különféle étellel álljon elő, amelyek mind „jók” ebből az optimalizálási problémából. Lehet, hogy egynél több optimális megoldás létezik, vagy esetleg vannak minőségileg különböző étrendek, amelyek elég közel állnak az optimálishoz. Ez a megvalósítás azonban determinisztikus kimenetet eredményez. Találjon módot a véletlenszerűség bevezetésére a programba, hogy egynél több megoldást kaphasson.

Javasoljon nyugodtan más ötleteket, és egészítse ki vagy írja át a modellt, hogy valami egészen mást tegyen. A határ a csillagos ég!