基于MOPSO算法的營(yíng)養(yǎng)決策方法

張繼新,周德祥,張 浩,王高平

(1.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,河南鄭州 450001; 2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北武漢 430070; 3.河南工業(yè)大學(xué)糧油食品學(xué)院,河南鄭州 450052)

基于MOPSO算法的營(yíng)養(yǎng)決策方法

張繼新1,2,周德祥1,張 浩3,王高平1

(1.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,河南鄭州 450001; 2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北武漢 430070; 3.河南工業(yè)大學(xué)糧油食品學(xué)院,河南鄭州 450052)

針對(duì)營(yíng)養(yǎng)決策多目標(biāo)優(yōu)化模型,提出基于MOPSO(Multi-Objective Particle Swar m Optimization)算法的營(yíng)養(yǎng)決策方法.提出基于支配原則的選優(yōu)方案,外部種群 Pareto解集與當(dāng)代解共同參與的競(jìng)爭(zhēng)原則,最后把MOPSO算法應(yīng)用到營(yíng)養(yǎng)分析和決策的優(yōu)化問(wèn)題來(lái)獲求最佳膳食營(yíng)養(yǎng)結(jié)構(gòu).結(jié)果證明該方法是有效的.

多目標(biāo)優(yōu)化;PSO算法;營(yíng)養(yǎng)決策

0 引言

隨著營(yíng)養(yǎng)健康時(shí)代的來(lái)臨,人們開始關(guān)注自身的健康,由于各自身體狀況不同,對(duì)食物的營(yíng)養(yǎng)有不同的需求和禁忌.即使在營(yíng)養(yǎng)專家與醫(yī)師的建議下,面對(duì)眾多的食物種類人們?nèi)匀浑y以選擇出合理的飲食方案.營(yíng)養(yǎng)膳食決策優(yōu)化是基于營(yíng)養(yǎng)學(xué)原理和各種膳食的國(guó)家供給標(biāo)準(zhǔn),結(jié)合信息技術(shù)和智能優(yōu)化技術(shù),為不同人群和對(duì)象提供營(yíng)養(yǎng)膳食決策和分析.

實(shí)際的營(yíng)養(yǎng)決策優(yōu)化問(wèn)題是一個(gè)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題.有各種營(yíng)養(yǎng)素的目標(biāo)函數(shù)、三餐熱能配比要求、價(jià)格要求等等,各個(gè)目標(biāo)之間通常相互制約,對(duì)其中一個(gè)目標(biāo)優(yōu)化可能會(huì)以其他目標(biāo)為代價(jià).傳統(tǒng)的多目標(biāo)優(yōu)化問(wèn)題求解方法是通過(guò)對(duì)每一目標(biāo)進(jìn)行優(yōu)先級(jí)排序并給予權(quán)重,將多目標(biāo)優(yōu)先問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題,但此方法僅求出一個(gè)最優(yōu)解,而且敏感于優(yōu)先級(jí)和權(quán)重,因此該方法效率很低.

進(jìn)化算法作為一類啟發(fā)式算法已成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域,文獻(xiàn)[1]將模糊多目標(biāo)遺傳算法應(yīng)用到營(yíng)養(yǎng)決策,并且證明其解是有效的.粒子群優(yōu)化(PSO)算法具有過(guò)程簡(jiǎn)單、易于實(shí)現(xiàn)、參數(shù)簡(jiǎn)潔、無(wú)需復(fù)雜調(diào)整的優(yōu)點(diǎn),從提出至今,已迅速應(yīng)用于遺傳算法的一些應(yīng)用領(lǐng)域.筆者提出一種新的解題思路,將多目標(biāo)粒子群算法應(yīng)用到營(yíng)養(yǎng)決策優(yōu)化問(wèn)題中,提出基于MOPSO的營(yíng)養(yǎng)決策方法.

1 多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型

通常一個(gè)多目標(biāo)優(yōu)化問(wèn)題可以描述如下:

式中:X為 n維決策向量;F(X)為 k個(gè)目標(biāo)函數(shù)向 n維決策向量的映射;G(X)定義了 m個(gè)約束函數(shù).

多目標(biāo)優(yōu)化問(wèn)題與單目標(biāo)優(yōu)化問(wèn)題不同,其所包含的不同目標(biāo)函數(shù)之間往往存在一定的矛盾沖突,因此很難在問(wèn)題的約束集合m中找到一個(gè)能夠使 k個(gè)目標(biāo)函數(shù)同時(shí)達(dá)到最小的最優(yōu)解,也就是說(shuō),多目標(biāo)優(yōu)化問(wèn)題中的多個(gè)目標(biāo)幾乎不可能在同一解上同時(shí)達(dá)到最優(yōu).因此,只要存在一個(gè)X向量滿足公式(1)中的m個(gè)約束函數(shù)稱它為可行解.所有可行解組成的集合稱為可行解集.在可行解中如果一個(gè)可行解 Xa的每一個(gè)目標(biāo)函數(shù)值都比另一可行解 Xb的目標(biāo)函數(shù)值小,就稱 Xa支配 Xb,或者說(shuō) Xa是占優(yōu)的.多目標(biāo)優(yōu)化問(wèn)題就是在可行解集中尋找這樣的解,此解不被任何其他解所支配,稱為 Pareto最優(yōu)解.

2 多目標(biāo)粒子群算法

粒子群優(yōu)化(PSO)算法是受鳥群覓食行為的啟發(fā)而提出的.PSO概念簡(jiǎn)單,容易實(shí)現(xiàn),收斂速度快,參數(shù)設(shè)置少,是一種高效的搜索算法.PSO中,每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥,稱之為“粒子”.所有粒子都有一個(gè)根據(jù)事先設(shè)定的適應(yīng)值函數(shù)計(jì)算的適應(yīng)值,每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離.然后,粒子們就根據(jù)自身的最優(yōu)位置和群體的最優(yōu)位置在解空間中搜索.每次迭代中,粒子根據(jù)如下公式來(lái)更新自己的速度和位置:

式中:v是粒子的速度;w是慣性權(quán)重,用于改善算法的收斂性能;Pt是個(gè)體最優(yōu);Pg是群體最優(yōu); r1、r2是介于 (0,1)之間的隨機(jī)數(shù);c1、c2是學(xué)習(xí)因子.

PSO算法在許多單目標(biāo)優(yōu)化問(wèn)題中的成功應(yīng)用說(shuō)明 PSO算法還是很有效的,但是卻不能直接用于多目標(biāo)優(yōu)化問(wèn)題.多目標(biāo)優(yōu)化問(wèn)題各個(gè)目標(biāo)可能互相矛盾,因此并不存在最優(yōu)解,多目標(biāo)優(yōu)化過(guò)程必須考慮如何向 Pareto最優(yōu)解靠近并且如何保持非支配解的多樣性,防止陷入局部最優(yōu).

NSGA-Ⅱ[2]提出基于分級(jí)的快速非支配解排序方法;然后將低級(jí)別非支配集選擇到精英集中,如果小于種群個(gè)數(shù),再?gòu)耐?jí)別非支配集中采用擁擠距離排序選擇非支配解到精英集中,直到精英集個(gè)數(shù)達(dá)到種群個(gè)數(shù);交叉變異形成的新種群與精英集同時(shí)進(jìn)入下一次迭代過(guò)程.NSGA-Ⅱ不僅保留精英和下一代一起進(jìn)行選擇,而且采用擁擠距離概念代替適應(yīng)度,可以說(shuō)是目前最優(yōu)秀的進(jìn)化多目標(biāo)算法之一,但此算法解的均勻性較差.

Cello提出多目標(biāo)優(yōu)化的MOPSO算法[3],采用了自適應(yīng)網(wǎng)格的機(jī)制來(lái)保存外部種群,當(dāng)外部種群中個(gè)體的數(shù)目超過(guò)規(guī)定的大小時(shí),這些個(gè)體的目標(biāo)函數(shù)空間被均勻地劃分為間隔相等的網(wǎng)格,然后統(tǒng)計(jì)每個(gè)網(wǎng)格中的個(gè)體數(shù)量,那些位于個(gè)體數(shù)量較少的網(wǎng)格中的個(gè)體在參與錦標(biāo)賽選擇時(shí)賦予較高的被選中的概率.MOPSO不僅具有 PSO算法的高收斂速率,而且還考慮了多目標(biāo)問(wèn)題解分布的均勻性和多樣性.筆者采用NSGA-Ⅱ和MOPSO思想,對(duì)傳統(tǒng)的粒子群算法進(jìn)行改進(jìn)并將其應(yīng)用到營(yíng)養(yǎng)決策多目標(biāo)優(yōu)化問(wèn)題上.

3 改進(jìn)的多目標(biāo)粒子群算法

為了保存 Pareto解集,將采用外部種群存儲(chǔ),粒子飛行中產(chǎn)生的新解與外部種群采用以下支配原則決定優(yōu)勝關(guān)系:

1)如果新解不被外部種群中任意解支配,則加入外部種群;

2)如果新解被外部種群中任意解支配,則放棄;

3)如果外部種群中解 X被新解支配,則將 X從外部種群中刪除.

對(duì)公式(2)、(3)進(jìn)行改進(jìn),以適用于多目標(biāo)優(yōu)化,改進(jìn)后公式如下:

為了保持解的多樣性與收斂性,全局最優(yōu)REP(h)的選擇采用一種新的適應(yīng)方法進(jìn)行.外部種群中每一解 X對(duì)當(dāng)代解的支配個(gè)數(shù)記為|X|.隨機(jī)產(chǎn)生一邏輯量,若為真,選擇 |X|值最小的解作為 REP(h);若為假,選擇 |X|值最大的解作為 REP(h).

MOPSO算法詳細(xì)過(guò)程如下:

1)初始化粒子群,包括:隨機(jī)產(chǎn)生粒子的位置和速度,用目標(biāo)函數(shù)評(píng)價(jià)粒子,每一粒子的初始最優(yōu)即為初始粒子狀態(tài),初始化外部種群,外部種群用來(lái)存儲(chǔ) Pareto非支配解集;

2)用公式 (4)、(5)更新粒子的速度與位置;

3)用目標(biāo)函數(shù)評(píng)價(jià)所有粒子;

4)若某個(gè)粒子的當(dāng)前評(píng)價(jià)值支配歷史最優(yōu)評(píng)價(jià)值,則記當(dāng)前評(píng)價(jià)值為該粒子歷史最優(yōu)值,同時(shí)記當(dāng)前位置為該粒子歷史最優(yōu)位置,求出 REP (h);

5)利用支配原則更新外部種群.

重復(fù)步驟 2到步驟 5,直到滿足終止條件或最大迭代數(shù).

4 營(yíng)養(yǎng)決策仿真實(shí)驗(yàn)

4.1 問(wèn)題說(shuō)明

營(yíng)養(yǎng)膳食目標(biāo)是一個(gè)復(fù)雜的高維目標(biāo)優(yōu)化問(wèn)題,比如糖類、蛋白質(zhì)、脂肪等營(yíng)養(yǎng)素,各種營(yíng)養(yǎng)比例的關(guān)系、三餐配比、價(jià)格等.對(duì)于高維問(wèn)題目前還沒有較好的方法.筆者提出的算法適合于低維目標(biāo)(一般低于 4個(gè)).對(duì)于復(fù)雜的高維目標(biāo)化簡(jiǎn),比如三餐配比 (30%∶40%∶30%),可以將三餐分別作為獨(dú)立目標(biāo)去優(yōu)化,或者建立通用模型,用戶可以根據(jù)不同的營(yíng)養(yǎng)目標(biāo)去選擇優(yōu)化目標(biāo).筆者仿真實(shí)驗(yàn)為午餐配餐,確定目標(biāo)為能量、蛋白質(zhì)、鈣和價(jià)格,其他目標(biāo)忽略.測(cè)試輸入條件如表1所示.

表1 測(cè)試輸入條件

測(cè)試輸入條件中,營(yíng)養(yǎng)標(biāo)準(zhǔn)是成人男性營(yíng)養(yǎng)標(biāo)準(zhǔn).仿真實(shí)驗(yàn)中的數(shù)據(jù)(不同年齡、不同性別所需的營(yíng)養(yǎng)素標(biāo)準(zhǔn)、不同種類不同食物的成分表)來(lái)自于卓越食譜管理軟件.

4.2 數(shù)學(xué)模型

營(yíng)養(yǎng)決策優(yōu)化多目標(biāo)優(yōu)化數(shù)學(xué)模型如下:

式中:b1,b2,b3分別表示對(duì)應(yīng)個(gè)體的能量、蛋白質(zhì)和鈣的每天標(biāo)準(zhǔn)攝入量;D表示價(jià)格標(biāo)準(zhǔn),不同的收入水平對(duì)價(jià)格的承受力不同,因此設(shè)置價(jià)格標(biāo)準(zhǔn);ai1,ai2,…,ain分別表示 N種食物中營(yíng)養(yǎng)素的含量;x1,x2,…,xn分別表示食物的質(zhì)量.

4.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境采用VC++6.0,在普通微機(jī)上進(jìn)行模擬實(shí)驗(yàn),學(xué)習(xí)因子 c1、c2為 2,慣性權(quán)重 w采用模糊系統(tǒng)[4],部分實(shí)驗(yàn)結(jié)果如表 2所示.

表2 營(yíng)養(yǎng)決策優(yōu)化數(shù)據(jù)結(jié)果 g

配餐結(jié)果的營(yíng)養(yǎng)評(píng)估結(jié)果見表 3,如表 3所示,其配餐設(shè)計(jì)具有理想的效果,達(dá)到預(yù)計(jì)的要求.

表3 配餐營(yíng)養(yǎng)達(dá)標(biāo)率 %

5 結(jié)論

筆者描述了多目標(biāo)優(yōu)化模型,建立了營(yíng)養(yǎng)決策數(shù)學(xué)模型,提出多目標(biāo)粒子群方法并將此方法應(yīng)用到營(yíng)養(yǎng)決策問(wèn)題上,結(jié)果表明:配餐結(jié)果達(dá)到營(yíng)養(yǎng)標(biāo)準(zhǔn),為解決營(yíng)養(yǎng)決策問(wèn)題提出了一種新的優(yōu)化方法.

營(yíng)養(yǎng)決策問(wèn)題是一個(gè)復(fù)雜的問(wèn)題,筆者僅僅對(duì)營(yíng)養(yǎng)素進(jìn)行優(yōu)化,沒有考慮營(yíng)養(yǎng)素之間的相互作用,需要對(duì)營(yíng)養(yǎng)決策模型繼續(xù)改進(jìn).多目標(biāo)粒子群算法適用于低維的多目標(biāo)優(yōu)化問(wèn)題,當(dāng)目標(biāo)函數(shù)過(guò)多時(shí),算法收斂很慢,仍需進(jìn)一步改進(jìn).

[1] 王高平,王永驥,王浩.模糊多目標(biāo)遺傳算法及其在營(yíng)養(yǎng)決策中的應(yīng)用[J].河南工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2006,27(5): 62-65.

[2] Deb K,Pratap A,Agar wal S,et al.A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Trans on Evolutionary Computation,2002,6(2):182-197.

[3] Coello Coello C A,Pulido G T,Lechuga M S.Handing multiple objectives with particle s warm optimization[J].IEEE Trans on Evolutionary Computation, 2004, 8 (3): 256-279.

[4] Shi Y,EberhartR.A Modified particle s warmopt imizer[C]//IEEE International Conference on Evolutionary Computation.Anchorage:IEEE Press,1998:69-73.

NUTR ITION DECISION METHOD BASED ON MULTI-OBJECTIVE PARTICLE S WARM OPTIM IZATION ALGOR ITHM

ZHANG Ji-xin1,2,ZHOU De-xiang1,ZHANG Hao3,WANG Gao-ping1
(1.School of Infor mation Science and Engineering,Henan University of Technology,Zhengzhou450001,China; 2.Department of Computer Science and Technology,W uhan University of Technology,W uhan430070,China; 3.School of Food Science and Technology,Henan University of Technology,Zhengzhou450052,China)

In this paper,we put for ward a nutrition decision method based onMOPSO(Multi-Objective Particle Swarm Opt imization)algorithm in order to construct a multi-objective model for nutrition decision optimization.An optimization scheme based on the dominance principle and the competition principle inwhich external Pareto solutions and contemporary solution participated together were put for ward.Finally,the MOPSO algorithm was applied to the optimization of nutrition analysis and decision to obtain the best dietary structure.The result shows that the method is effective.

multi-objective optimization;PSO algorithm;nutrition decision

TS201

B

1673-2383(2010)03-0082-04

2010-01-15

國(guó)家科技支撐計(jì)劃項(xiàng)目基金(2008BADA8B04)

張繼新(1973-),女,河南新鄉(xiāng)人,博士研究生,講師,研究方向?yàn)橹悄苄畔⒓夹g(shù)、人工智能與優(yōu)化算法.