基于MOPSO算法的营养决策方法

张继新,周德祥,张 浩,王高平

(1.河南工业大学信息科学与工程学院,河南郑州 450001; 2.武汉理工大学计算机科学与技术学院,湖北武汉 430070; 3.河南工业大学粮油食品学院,河南郑州 450052)

基于MOPSO算法的营养决策方法

张继新1,2,周德祥1,张 浩3,王高平1

(1.河南工业大学信息科学与工程学院,河南郑州 450001; 2.武汉理工大学计算机科学与技术学院,湖北武汉 430070; 3.河南工业大学粮油食品学院,河南郑州 450052)

针对营养决策多目标优化模型,提出基于MOPSO(Multi-Objective Particle Swar m Optimization)算法的营养决策方法.提出基于支配原则的选优方案,外部种群 Pareto解集与当代解共同参与的竞争原则,最后把MOPSO算法应用到营养分析和决策的优化问题来获求最佳膳食营养结构.结果证明该方法是有效的.

多目标优化;PSO算法;营养决策

0 引言

随着营养健康时代的来临,人们开始关注自身的健康,由于各自身体状况不同,对食物的营养有不同的需求和禁忌.即使在营养专家与医师的建议下,面对众多的食物种类人们仍然难以选择出合理的饮食方案.营养膳食决策优化是基于营养学原理和各种膳食的国家供给标准,结合信息技术和智能优化技术,为不同人群和对象提供营养膳食决策和分析.

实际的营养决策优化问题是一个复杂的多目标优化问题.有各种营养素的目标函数、三餐热能配比要求、价格要求等等,各个目标之间通常相互制约,对其中一个目标优化可能会以其他目标为代价.传统的多目标优化问题求解方法是通过对每一目标进行优先级排序并给予权重,将多目标优先问题转化为单目标优化问题,但此方法仅求出一个最优解,而且敏感于优先级和权重,因此该方法效率很低.

进化算法作为一类启发式算法已成功应用于多目标优化领域,文献[1]将模糊多目标遗传算法应用到营养决策,并且证明其解是有效的.粒子群优化(PSO)算法具有过程简单、易于实现、参数简洁、无需复杂调整的优点,从提出至今,已迅速应用于遗传算法的一些应用领域.笔者提出一种新的解题思路,将多目标粒子群算法应用到营养决策优化问题中,提出基于MOPSO的营养决策方法.

1 多目标优化问题的数学模型

通常一个多目标优化问题可以描述如下:

式中:X为 n维决策向量;F(X)为 k个目标函数向 n维决策向量的映射;G(X)定义了 m个约束函数.

多目标优化问题与单目标优化问题不同,其所包含的不同目标函数之间往往存在一定的矛盾冲突,因此很难在问题的约束集合m中找到一个能够使 k个目标函数同时达到最小的最优解,也就是说,多目标优化问题中的多个目标几乎不可能在同一解上同时达到最优.因此,只要存在一个X向量满足公式(1)中的m个约束函数称它为可行解.所有可行解组成的集合称为可行解集.在可行解中如果一个可行解 Xa的每一个目标函数值都比另一可行解 Xb的目标函数值小,就称 Xa支配 Xb,或者说 Xa是占优的.多目标优化问题就是在可行解集中寻找这样的解,此解不被任何其他解所支配,称为 Pareto最优解.

2 多目标粒子群算法

粒子群优化(PSO)算法是受鸟群觅食行为的启发而提出的.PSO概念简单,容易实现,收敛速度快,参数设置少,是一种高效的搜索算法.PSO中,每个优化问题的解都是搜索空间中的一只鸟,称之为“粒子”.所有粒子都有一个根据事先设定的适应值函数计算的适应值,每个粒子还有一个速度决定他们飞翔的方向和距离.然后,粒子们就根据自身的最优位置和群体的最优位置在解空间中搜索.每次迭代中,粒子根据如下公式来更新自己的速度和位置:

式中:v是粒子的速度;w是惯性权重,用于改善算法的收敛性能;Pt是个体最优;Pg是群体最优; r1、r2是介于 (0,1)之间的随机数;c1、c2是学习因子.

PSO算法在许多单目标优化问题中的成功应用说明 PSO算法还是很有效的,但是却不能直接用于多目标优化问题.多目标优化问题各个目标可能互相矛盾,因此并不存在最优解,多目标优化过程必须考虑如何向 Pareto最优解靠近并且如何保持非支配解的多样性,防止陷入局部最优.

NSGA-Ⅱ[2]提出基于分级的快速非支配解排序方法;然后将低级别非支配集选择到精英集中,如果小于种群个数,再从同级别非支配集中采用拥挤距离排序选择非支配解到精英集中,直到精英集个数达到种群个数;交叉变异形成的新种群与精英集同时进入下一次迭代过程.NSGA-Ⅱ不仅保留精英和下一代一起进行选择,而且采用拥挤距离概念代替适应度,可以说是目前最优秀的进化多目标算法之一,但此算法解的均匀性较差.

Cello提出多目标优化的MOPSO算法[3],采用了自适应网格的机制来保存外部种群,当外部种群中个体的数目超过规定的大小时,这些个体的目标函数空间被均匀地划分为间隔相等的网格,然后统计每个网格中的个体数量,那些位于个体数量较少的网格中的个体在参与锦标赛选择时赋予较高的被选中的概率.MOPSO不仅具有 PSO算法的高收敛速率,而且还考虑了多目标问题解分布的均匀性和多样性.笔者采用NSGA-Ⅱ和MOPSO思想,对传统的粒子群算法进行改进并将其应用到营养决策多目标优化问题上.

3 改进的多目标粒子群算法

为了保存 Pareto解集,将采用外部种群存储,粒子飞行中产生的新解与外部种群采用以下支配原则决定优胜关系:

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

2)如果新解被外部种群中任意解支配,则放弃;

3)如果外部种群中解 X被新解支配,则将 X从外部种群中删除.

对公式(2)、(3)进行改进,以适用于多目标优化,改进后公式如下:

为了保持解的多样性与收敛性,全局最优REP(h)的选择采用一种新的适应方法进行.外部种群中每一解 X对当代解的支配个数记为|X|.随机产生一逻辑量,若为真,选择 |X|值最小的解作为 REP(h);若为假,选择 |X|值最大的解作为 REP(h).

MOPSO算法详细过程如下:

1)初始化粒子群,包括:随机产生粒子的位置和速度,用目标函数评价粒子,每一粒子的初始最优即为初始粒子状态,初始化外部种群,外部种群用来存储 Pareto非支配解集;

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

3)用目标函数评价所有粒子;

4)若某个粒子的当前评价值支配历史最优评价值,则记当前评价值为该粒子历史最优值,同时记当前位置为该粒子历史最优位置,求出 REP (h);

5)利用支配原则更新外部种群.

重复步骤 2到步骤 5,直到满足终止条件或最大迭代数.

4 营养决策仿真实验

4.1 问题说明

营养膳食目标是一个复杂的高维目标优化问题,比如糖类、蛋白质、脂肪等营养素,各种营养比例的关系、三餐配比、价格等.对于高维问题目前还没有较好的方法.笔者提出的算法适合于低维目标(一般低于 4个).对于复杂的高维目标化简,比如三餐配比 (30%∶40%∶30%),可以将三餐分别作为独立目标去优化,或者建立通用模型,用户可以根据不同的营养目标去选择优化目标.笔者仿真实验为午餐配餐,确定目标为能量、蛋白质、钙和价格,其他目标忽略.测试输入条件如表1所示.

表1 测试输入条件

测试输入条件中,营养标准是成人男性营养标准.仿真实验中的数据(不同年龄、不同性别所需的营养素标准、不同种类不同食物的成分表)来自于卓越食谱管理软件.

4.2 数学模型

营养决策优化多目标优化数学模型如下:

式中:b1,b2,b3分别表示对应个体的能量、蛋白质和钙的每天标准摄入量;D表示价格标准,不同的收入水平对价格的承受力不同,因此设置价格标准;ai1,ai2,…,ain分别表示 N种食物中营养素的含量;x1,x2,…,xn分别表示食物的质量.

4.3 实验结果

实验环境采用VC++6.0,在普通微机上进行模拟实验,学习因子 c1、c2为 2,惯性权重 w采用模糊系统[4],部分实验结果如表 2所示.

表2 营养决策优化数据结果 g

配餐结果的营养评估结果见表 3,如表 3所示,其配餐设计具有理想的效果,达到预计的要求.

表3 配餐营养达标率 %

5 结论

笔者描述了多目标优化模型,建立了营养决策数学模型,提出多目标粒子群方法并将此方法应用到营养决策问题上,结果表明:配餐结果达到营养标准,为解决营养决策问题提出了一种新的优化方法.

营养决策问题是一个复杂的问题,笔者仅仅对营养素进行优化,没有考虑营养素之间的相互作用,需要对营养决策模型继续改进.多目标粒子群算法适用于低维的多目标优化问题,当目标函数过多时,算法收敛很慢,仍需进一步改进.

[1] 王高平,王永骥,王浩.模糊多目标遗传算法及其在营养决策中的应用[J].河南工业大学学报:自然科学版,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

国家科技支撑计划项目基金(2008BADA8B04)

张继新(1973-),女,河南新乡人,博士研究生,讲师,研究方向为智能信息技术、人工智能与优化算法.