賀德富 謝 龍

（1.湖北第二師范學(xué)院計(jì)算機(jī)學(xué)院 武漢 430205）（2.陸軍青藏兵站部 西寧 810000）

1 引言

食譜生成主要有計(jì)算法、食物交換份法［1］和計(jì)算機(jī)生成法［2］。利用計(jì)算機(jī)生成食譜，具有方便、快捷、準(zhǔn)確、高效的特點(diǎn)，已經(jīng)廣泛地應(yīng)用于糖尿病、“三高”、中小學(xué)生等特殊人群食譜生成［3］。蘇喜生教授等研究的“模板轉(zhuǎn)換法”［4］可應(yīng)用于團(tuán)餐食譜，其基本思路是：1）確定食物范圍。根據(jù)食物消費(fèi)習(xí)慣，分析得出符合膳食結(jié)構(gòu)需要的各類食物用量的合理范圍。2）制定食譜模式。結(jié)合團(tuán)餐要求的伙食費(fèi)標(biāo)準(zhǔn)與辦伙條件確定食譜模式排，即膳食模式中的主食安排、全日主要菜肴數(shù)量及質(zhì)量，特殊品種（主要指牛奶、水果及飲料等）的安排。3）替換算法規(guī)則。利用人工智能原理確定規(guī)則庫，包括當(dāng)?shù)氐墓?yīng)條件、經(jīng)實(shí)時(shí)計(jì)算的菜肴價(jià)格、加工方法等。4）模板置換。先利用專家知識(shí)制訂“標(biāo)準(zhǔn)食譜”，根據(jù)替換算法規(guī)則對(duì)同類食物進(jìn)行替換，得出“派生食譜”。但該算法也存在一定的局限性，主要表現(xiàn)在兩個(gè)方面：一是標(biāo)準(zhǔn)食譜模板需要大量的專家知識(shí)，制訂起來需要花費(fèi)大量的時(shí)間和精力；二是替換規(guī)則，約束條件少了，生成的食譜可操作性不強(qiáng)，約束條件多了，計(jì)算機(jī)生成的時(shí)間較長(zhǎng)，用戶可接受性不好。

鑒于此，筆記研究采用遺傳算法生成團(tuán)餐食譜。遺傳算法是由Holland提出的，該算法本質(zhì)上是依照適者生存原則，通過模仿生物進(jìn)化過程，搜索最優(yōu)解決方案［5］。遺傳算法在使用中具體有編碼、初始種群生成、適應(yīng)度值評(píng)估檢測(cè)、選擇、交叉、

? 收稿日期：2018年1月6日，修回日期：2018年2月24日

基金項(xiàng)目：后勤信息化重點(diǎn)科研項(xiàng)目（編號(hào)：BS215R09025）資助。

作者簡(jiǎn)介：賀德富，男，博士，教授，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)與軟件工程。謝龍，男，碩士，研究方向：軍需信息化。變異和中止等求解步驟［6］。

2 食譜模型構(gòu)建

食譜是由若干主副食菜肴組成的，每個(gè)菜肴又由若干食材組成，通過市場(chǎng)調(diào)查的物價(jià)信息可以得到可供應(yīng)的食材數(shù)目M，依據(jù)可提供的食材，能夠獲得可加工的菜肴數(shù)目為N，用ai標(biāo)識(shí)第i道菜肴，其中i∈［1，N］。根據(jù)《食物營養(yǎng)成分表》［7］可以得到每種食材含有的42種營養(yǎng)成分。設(shè)每單位的第j種食材含有第r種營養(yǎng)成分的數(shù)量為cjr，第j種食材的單價(jià)為pj。

將種類繁多的各式菜肴劃分為N類，分別是基本主食、花樣主食、糕點(diǎn)、蛋品、乳品、大葷、半葷、小葷、全素、小菜、湯、飲料、水果、粥［8］，即N=14。另外每道菜肴包含重量、價(jià)格、能量、營養(yǎng)素等屬性。則使用一個(gè)46維的列向量來表述第i道菜的各個(gè)屬性?？梢员硎鰹?/p>

其中：ai1：用以表示第i道菜所屬的菜肴類別屬性；ai2：用以表示第i道菜的重量屬性，單位為克（g）；ai3：用以表示第i道菜的價(jià)格屬性，單位為元；ai4：用以表示第i道菜的能量屬性，單位為千焦；ai5，ai6，ai7，…，ai46：分別表示第i道菜中42類營養(yǎng)素的含量。

其中：i∈［1，N］，j∈［1，m］，m ≤ 6，即一道菜肴最多由6種食材烹制而成。

每種食材都含有價(jià)格屬性，之前已設(shè)定使用pj表示第j種食材的價(jià)格，以表示第i道菜肴的第j種食材的單價(jià)，則第i道菜肴的價(jià)格屬性 pi可表述為一個(gè)m維的列向量：。

依據(jù)式（1）的設(shè)定，以ai2表示第i道菜肴的重量，從而有

ai3表示第i道菜肴的價(jià)格，從而有

同理，第i道菜肴中含有的能量值和營養(yǎng)素含量為

生成符合需要的團(tuán)餐食譜重點(diǎn)關(guān)注食物定量、伙食費(fèi)、能量和營養(yǎng)素供給量四個(gè)方面，分別以表示。在軟件系統(tǒng)中，該值由專家給出默認(rèn)值，并可由用戶根據(jù)具體情況自主設(shè)定，實(shí)現(xiàn)系統(tǒng)適用于不同人群。

食物定量標(biāo)準(zhǔn)中對(duì)主食、植物油、副食、燃料等都進(jìn)行了規(guī)定［9］。設(shè)對(duì)食物定量標(biāo)準(zhǔn)規(guī)定的品種數(shù)為K，則有：)。依據(jù)伙食費(fèi)和勞動(dòng)強(qiáng)度的不同，將選取不同的值。對(duì)于42種營養(yǎng)素，組成一個(gè)向量：，式中，表示每日攝入第r種營養(yǎng)素的理想值。

另外每道菜肴中所含有的各類食物品種的數(shù)量是不一致的，如同菜肴“紅燒肉”其中就包含了肉類、蔬菜類等。設(shè)第i道菜肴第k類食物的重量為，則有：

實(shí)際中，食譜的制定應(yīng)確保該值在理想值的一個(gè)可行的范圍內(nèi)。另外，伙食的重復(fù)次數(shù)過多會(huì)造成就餐人員飲食出現(xiàn)乏味，因此應(yīng)確保一道菜肴在周食譜中出現(xiàn)的次數(shù)小于3次，每日該菜肴最多出現(xiàn)一次。設(shè)定I為日食譜中菜肴的品種數(shù)，xi為日食譜中第i道菜肴在食譜中被選用的情況，則有：

設(shè)食譜中某類別的菜肴實(shí)際出現(xiàn)的次數(shù)為t，則實(shí)際出現(xiàn)的次數(shù)t可以表示為一個(gè)向量：t=(t1，t2，…，t14)。

據(jù)以上設(shè)定可以得出，每日食譜的食物總重量為

總開支為

總能量值為

各營養(yǎng)素的總量為

令

式中p的一般取值范圍為［1，∞），當(dāng)取p=2時(shí)，周食譜要素點(diǎn)與理想點(diǎn)的L2（x）即為歐化距離。我們采用p=2。而優(yōu)選周食譜的數(shù)學(xué)模型可表示為minL2（x）。

其約束條件為

其中I為一日食譜中的菜肴總數(shù)，帶有上下橫線的值為理想值的范圍。

3 遺傳算法使用設(shè)計(jì)

遺傳算法是基于生物進(jìn)化與選擇機(jī)制的優(yōu)化算法［10］。基本遺傳算法應(yīng)定義好編碼方式C、適應(yīng)度評(píng)價(jià)函數(shù)F、初始種群P0、種群大小M、選擇算子Φ、交叉算子Γ、變異算子Q、遺傳運(yùn)算終止條件T。據(jù)此可以定義為一個(gè)8元組：

這里對(duì)遺傳算法的使用進(jìn)行如下假設(shè)：為簡(jiǎn)化計(jì)算，先將主食剔除，即先不考慮軍糧定量標(biāo)準(zhǔn)；另假設(shè)早、中、晚三餐在菜肴種類上無差別，每餐都包含有4個(gè)菜，要求每日菜肴不重樣，則每日共計(jì)烹制菜肴12種。

使用遺傳算法進(jìn)行食譜生成的一般流程為：首先依據(jù)提供的物價(jià)供給信息得到伙食單位本周可加工的菜肴種類總數(shù)N，這N種可加工的菜肴即為食譜中菜肴的解析庫；而后，系統(tǒng)執(zhí)行遺傳算法得到周食譜中一日食譜；再判斷該食譜中的菜肴在本周使用次數(shù)是否達(dá)到2次，如果達(dá)到則將該菜肴從解析庫中剔除；如果已生成7天的日食譜，則判斷本周食譜與上周是否完全一樣，如果相同，隨機(jī)地獲取本周食譜中的1/3菜肴，將其從菜肴的解析庫中剔除，再重新執(zhí)行算法，若得到不完全一致的食譜則停止循環(huán)，結(jié)束使用遺傳算法生成食譜，獲得算法生成的周食譜，其流程如圖1所示。

圖1 使用遺傳算法生成食譜的流程

3.1 編碼方案

遺傳算法的使用要求通過編碼的方式將要求解的問題轉(zhuǎn)化為遺傳中由基因構(gòu)成的染色體或個(gè)體［11］。在對(duì)食譜生成問題應(yīng)用遺傳算法解決的過程中使用二進(jìn)制編碼的方式對(duì)個(gè)體進(jìn)行編碼。由物資供應(yīng)信息可解得可烹制的菜肴共計(jì)N種，并為每個(gè)菜肴進(jìn)行編號(hào)，這里使用整數(shù)編號(hào)，即為1～N。

設(shè)12種菜肴為x1，x2，…，x12，xr的數(shù)值為在N種可烹制菜肴中對(duì)應(yīng)的編號(hào)值，即

因xr為1～N之間的整數(shù)，故在使用二進(jìn)制編碼時(shí)，由菜肴庫中的菜肴數(shù)目N確定編碼長(zhǎng)度，直接將編號(hào)轉(zhuǎn)化為二進(jìn)制數(shù)值。若N=100，則可用長(zhǎng)度為7的二進(jìn)制數(shù)表示，將xr連接在一起將組成一個(gè)個(gè)體的基因型，表征一個(gè)可行的解。如一個(gè)數(shù)值為：x=0000111 0001001 0001111 0010010 0010101 0011001 0011110 0100000 0100111 0101000 0101011 0101111的基因型其表示的解為：x=［7，9，15，18，21，25，30，32，39，40，42，47］。

3.2 初始種群的產(chǎn)生

在遺傳算法中要對(duì)種群執(zhí)行進(jìn)化操作，必須要設(shè)定搜索的起始點(diǎn)，即選擇初始種群。在進(jìn)行食譜生成中，我們將群體規(guī)模設(shè)置為20，即群體由20個(gè)個(gè)體組成，每個(gè)個(gè)體通過隨機(jī)方法產(chǎn)生。在生成基因型的過程中，要求不出現(xiàn)相同的xr，即保證菜肴每日只出現(xiàn)一次。

3.3 適應(yīng)度函數(shù)

適應(yīng)度表征了個(gè)體的優(yōu)劣程度，用以代表個(gè)體被選中的概率高低，如果個(gè)體的適應(yīng)度高，其被選中的概率就高，否則其被選中的概率就低［12］。在遺傳算法中，適應(yīng)度函數(shù)是區(qū)分種群中個(gè)體優(yōu)劣的唯一標(biāo)準(zhǔn)，能夠決定是否進(jìn)行繁殖。在食譜生成問題中，依據(jù)之前的設(shè)定，每道菜肴包含數(shù)量、價(jià)格、能量、營養(yǎng)素等屬性。通過簡(jiǎn)化，計(jì)算minL2（x）。由于目標(biāo)函數(shù)的值總是非負(fù)的，而且目標(biāo)函數(shù)值越小表示越符合，因此可以將求得的值作為個(gè)體的適應(yīng)度，函數(shù)F即為適應(yīng)度函數(shù)。

3.4 選擇運(yùn)算

選擇算子的作用是確保將種群中適應(yīng)度高的個(gè)體選中并將其基因型遺傳到下一代群體中。一般來說，選擇運(yùn)算就是建立起適應(yīng)度和選擇概率的規(guī)則或模型，再依據(jù)計(jì)算的概率來確定個(gè)體能否復(fù)制到下一代［13］。在進(jìn)行食譜生成中，適應(yīng)度越小的個(gè)體更應(yīng)該復(fù)制到下一代中，因此應(yīng)該采用與適應(yīng)度成反比的概率計(jì)算規(guī)則來確定各個(gè)體復(fù)制到下一代群體中的數(shù)量。

針對(duì)食譜生成問題，在進(jìn)行選擇時(shí)將當(dāng)前種群中所有個(gè)體的適應(yīng)度計(jì)算出來，其值可以表示為一個(gè)列向量：

式中的M為這一代群體的個(gè)體總量，將群體中所有個(gè)體的適應(yīng)度的反比例值求和，再用個(gè)體的適應(yīng)度值r反比例值除以求和得到的值，則可以獲得個(gè)體被復(fù)制到下一代群體的概率：

遺傳算法模擬了自然界的繁殖規(guī)律，即越能適應(yīng)的個(gè)體具有更高的可能性繁殖后代，但是并不一定概率越大其具有的后代越多（可能陷入到局部最優(yōu)解），由此采用輪盤賭選擇法（Roulette Wheel Se?lection）［14］進(jìn)行個(gè)體的選擇。每個(gè)個(gè)體的概率值表征著輪盤中的一個(gè)區(qū)域，區(qū)域大的表示其概率大，區(qū)域小的表示其概率小，全部個(gè)體的概率總和為1。使用產(chǎn)生隨機(jī)數(shù)的方法獲得一個(gè)0～1之間的數(shù)值，依據(jù)該數(shù)值出現(xiàn)在概率區(qū)中的次數(shù)來判定個(gè)體是否被選中。

3.5 交叉運(yùn)算

在食譜生成問題中個(gè)體采用二進(jìn)制編碼，因而在進(jìn)行交叉運(yùn)算時(shí)，可以采用單交叉點(diǎn)法、雙交叉點(diǎn)法、“與/或”交叉法來產(chǎn)生新的個(gè)體。在這里我們選擇使用單交叉點(diǎn)法進(jìn)行，其具體的操作方法為：隨機(jī)的對(duì)群體中的個(gè)體進(jìn)行配對(duì)，配對(duì)的兩個(gè)基因型為父代基因，再依據(jù)基因型的長(zhǎng)度隨機(jī)取得一個(gè)數(shù)值作為交叉點(diǎn)的位置，在這個(gè)位置將父代基因截?cái)啵⒅匦陆M合得到子代基因型，得到的子代基因型在交叉點(diǎn)前的部分是從一個(gè)父代基因中獲得，交叉點(diǎn)后的部分從另一個(gè)父代基因型中獲得。至此可以完成交叉運(yùn)算。具體的例子如下：

x1和x2為兩個(gè)父代基因型，其中：

x1=0000111 0001001 0001111 0010010 0010101 0011001 0011110 0100000 0100111 0101000 0101011 0101111

x2=1110001 0010001 1110010 0100010 101001 1001001 1110010 0000010 0111001 0100001 0101101 0111100

假定隨機(jī)獲得的交叉點(diǎn)位置為16，則通過交叉運(yùn)算獲得的子代基因型x1'，x'2為

x1=0000111 0001001 0?101111 0010010 0010101 0011001 0011110 0100000 0100111 0101000 0101011 0101111

x2=1110001 0010001 1?010010 0100010 101001 1001001 1110010 0000010 0111001 0100001 0101101 0111100

式中“?”符號(hào)為交叉點(diǎn)的位置，將群體中所有的父代基因進(jìn)行交叉操作，就得到了新一代的基因型。

3.6 變異運(yùn)算

在遺傳算法中，通過變異運(yùn)算也可以產(chǎn)生新的子代個(gè)體，其運(yùn)算規(guī)則是依照按某一較小的變異概率把父代個(gè)體基因型中的一些基因值替換為其他基因值。變異運(yùn)算的方法也有很多，常用的變異算子為基本位變異算子和逆轉(zhuǎn)變異算子［15］。在食譜生成問題中采用基本位變異算子對(duì)父代基因型進(jìn)行變異運(yùn)算。其運(yùn)算規(guī)則為：依據(jù)基因型的長(zhǎng)度隨機(jī)地確定出3個(gè)位置作為變異點(diǎn)，然后將父代基因變異點(diǎn)位置的值進(jìn)行取反操作，即原來位置是1變異為0，原來位置為0則變異為1。

3.7 算法的終止

當(dāng)出現(xiàn)適應(yīng)度值F=0，終止算法；但通常情況下不會(huì)出現(xiàn)F=0的情況，這時(shí)候就需要將計(jì)算的適應(yīng)度與前幾代中的最小適應(yīng)度進(jìn)行比較，如果二者相差不大則終止算法。

4 結(jié)語

依據(jù)食堂所在地域以及季節(jié)的不同，采購的食材會(huì)呈現(xiàn)出較大的區(qū)別。使用模板置換法進(jìn)行食譜生成未能將這些因素充分考慮進(jìn)去，致使生成的食譜針對(duì)性不強(qiáng)。本算法通過使用公布的物價(jià)及供應(yīng)信息求解出一個(gè)適應(yīng)食堂自身特點(diǎn)的食譜庫，再依據(jù)遺傳算法對(duì)構(gòu)建的食譜模型進(jìn)行求解，在新構(gòu)建的食譜庫中求解出最優(yōu)化的食譜，能夠較好地解決原有系統(tǒng)在這方面存在的問題。