个性化食谱智能优化系统

郭广颂，席俊杰，文振华

(1.郑州航空工业管理学院 智能工程学院，河南 郑州 450046；2.郑州航空工业管理学院 航空工程学院，河南 郑州 450046)

0 引 言

食谱设计是营养学重要组成部分，其核心目的是设计出同时满足用户偏好和营养需求的健康食谱。相对于计算法和食物交换份法等传统食谱设计方法的复杂低效[1]，近年来，采用智能方法的营养决策逐渐成为食谱设计的代表思路。该类方法的特点是应用智能算法优化饮食要素，快速高效地为用户提供健康合理的个性化菜品搭配。最近的研究成果中，文献[2]采用遗传算法优化食谱结构，并生成一周食谱。文献[3]将食谱优化视为碳水化合物、蛋白质和脂肪的多目标优化问题，采用NSGA-II为糖尿病患者食谱优化最佳食材重量。这些方法虽然对食谱设计具有重要启发意义，优化结果也完全符合营养标准，但是均没有考虑用户的偏好，即不能肯定优化出的食谱方案一定符合用户口味。考虑到用户偏好，文献[4,5]基于互联网技术，采用协同过滤算法为用户推荐食谱。这些方法推荐的食谱虽然可以满足用户口味，但没有足够考虑食谱的营养性和健康性，优化结果同样存在片面性。所以，设计能同时满足营养需求与用户口味需求的个性化食谱仍然是难以解决的问题。

交互式多目标优化(interactive multi-objective optimization，IMO)是目前进化优化领域的热点研究方向之一[6]。IMO求解问题有一类特殊类型，即优化过程中同时存在能够用明确定义的函数表示的显式指标(也称为定量指标)和不能用明确定义的函数表示的隐式指标(也称为定性指标)的混合指标优化问题[7]。由于同时包含两类性质不同的优化目标，该类型IMO十分适合求解融入偏好的多目标优化问题[8,9]。

综合上述，基于食谱优化问题特点，采用交互式进化计算求解是一条可行的食谱设计研究思路。基于此，本文开发一种交互式食谱智能优化方法。首先，将食谱的营养性、价格、热量等定量因素作为显式指标，将用户偏好这一主要定性因素作为隐式指标，从而将食谱设计问题转化为混合指标指标优化问题；然后，采用指标均衡度设计新的交互式进化策略并求解这一问题；最后，得到同时满足食品营养性和用户口味的个性化食谱。

本文的创新之处是：①提出了混合指标优化指标均衡度概念和计算方法；②提出了新的基于指标均衡度的指标占优准则；③提出了新的结合非交互式进化方法的Pareto前沿修正策略；④尝试将上述策略应用于食谱设计问题。

1 食谱优化模型

(1)

式中：cjr为第j种食材单位质量含有的营养素r的量，r∈[1,42]。

(2)

式(2)中加撇变量为原变量做归一化后的取值，约束条件中带有上下横线的值为菜品标准值的范围。式(2)的含义是在满足用户需求情况下，食谱菜品定量、能量、营养素和价格等因素与标准值偏差最小。

2 交互式进化优化方法

2.1 进化指标均衡度

个性化食谱除了需要满足营养性、价格、热量等定量指标外，还应同时满足用户个人口味的个性化需求。不失一般性，考虑混合指标优化问题

(3)

式中：x是d维决策变量，S为x的可行域，f(x)是被优化的性能指标。其中fk(x),k=1,2,…,p为个体x(食谱)显式指标，fk′(x),k′=p+1,p+2,…,p+q为个体x隐式指标。由于用户个性化需求可以通过对食谱菜品的评价这一定性指标刻画，所以，可以将用户对食谱的评价值作为个体隐式指标；按式(2)计算出的食谱优化值反映了食谱菜品营养性、价格、热量等定量指标的最优化结果，所以，可以将f1(x)作为个体显式指标。在本文中，个体显式指标与隐式指标均只有一个，即p=q=1,p+q=2，个体混合指标形式记为f1(x)/f1+1(x)。

通过式(3)及食谱的特点可以发现，用户的偏好与食谱的营养性、价格等因素往往存在冲突，即受“口腹之欲”获得的食谱菜品，往往对应着不健康的营养性，反之亦然。这样一来，交互式进化优化获得的食谱会出现难以调和的定性与定量指标矛盾，而最优的食谱应在用户偏好和定量指标之间获得最佳平衡。基于此，本节提出进化指标均衡度概念。

设第t代种群个体xi(t)显式适应值为f1(xi(t)),f2(xi(t)),…,fp(xi(t))，隐式适应值为fp+1(xi(t)),fp+2(xi(t)),…,fp+q(xi(t))，对显式和隐式适应值归一化后，可以获得种群无量纲指标行矩阵B(xi(t))1×(p+q)。根据问题(3)，在B(xi(t))1×(p+q)中，1～p列元素b11(xi(t)),b12(xi(t)),…,b1p(xi(t))为显式指标，即成本型指标，该指标值越小越好；p+1～p+q列元素b1(p+1)(xi(t)),b1(P+2)(xi(t)),…,b1(p+q)(xi(t))为隐式指标，即效益型指标，该指标值越大越好。为了刻画B(xi(t))1×(p+q)的指标均衡性，下面采用Gini系数建立个体指标均衡度[10]。

在交互式进化过程中，由于每一代的个体指标在决策中所起作用相同，设指标效用系数为1，且每一代均能收集到相关数据对相应指标进行评价，故直接将个体xi(t)的各项指标b11(xi(t)),b12(xi(t)),…,b1(p+q)(xi(t))做升序排列，记为V11(xi(t)),V12(xi(t)),…,V1(p+q)(xi(t))，则个体xi(t),i=1,2,…N的指标均衡度为

(4)

(5)

2.2 优化算法

对于问题(3)，本节基于个体指标均衡度概念，将交互式进化优化与非交互式进化优化结合，获得更高效的进化求解方法，具体如下：

(1)系统初始化生成初始种群。为减少评价噪声，用户对个体xi(t),i=1,2,…,N按1-5级评分，该离散值反映了用户偏好，表达了用户个性化信息，所以该值既是个体适应值，也是个体隐式指标；同时，系统在后台按式(2)计算个体显示指标f1(xi(t))，则提取的个体混合指标为f1(xi(t))/f1+1(xi(t))；然后，采用NSGA-II算法优化种群，获得Pareto最优解，并作为案例存入案例库；

(6)

式中：T′max为GA最大进化代数。

(3)考虑种群规模，选择一个GA优化的最优个体替换掉当前种群中个体指标均衡度最低的个体，改善当前种群指标均衡性；

(4)用户若对优化结果满意，则终止程序，否则，重新评价个体，继续遗传操作。算法架图如图1所示，其中斜体下划线部分是本文工作的创新之处。

图1 算法框架

3 食谱智能优化系统设计

3.1 染色体编码

为实现进化优化，将食谱样本作为进化个体。结合食谱菜品的3个组成部分，进化个体编码也由主食、配菜和饮品3部分组成。采用二进制编码，其中前4位为主食，包括基本主食、花样主食、糕点等3类共16种方案；中间6位为配菜，包括蛋品、乳品、大荤、半荤、小荤、全素、小菜、水果等8类共64种家常菜方案；最后4位为饮品，包括汤、饮料、粥等3类共16种方案。个体染色体长度为14，搜索空间包含24×26×24=16384种食谱组合方案(优化解)，用户通过算法找到最满意的食谱样本(满意解)。图2表示了染色体编码过程，其中xi1,xi2,xi3表示个体xi(t)的3个组成部分，b1-b14表示染色体各基因位。图中个体染色体为0001 100101 0110，对应的食谱菜品是“米饭/素炒西芹/银耳汤”。食谱样本以.bmp格式储存在根目录下的数据库中。

图2 染色体编码

3.2 系统实现与操作

本系统采用Visual Basic 6.0实现，系统结构如图3所示。系统划分为模型载入模块、模型处理模块和交互式进化算法模块，3个模块通过交互进化界面融合，共同完成交互式进化设计。采用绘图软件构建食谱模型，并编写程序实现模型的读取和显示。模型载入模块基于MFC创建SDI应用程序，当运行“打开”命令后，生成文件所在位置的路径，并调用载入模型函数。由于该文件的块是嵌套存储，读取的内容也是嵌套存入内存中。将读取的内容转化为能够用OpenGL表现的格式，最后，调用视图类中的OnDraw()函数，利用OpenGL技术将模型显示出来。模型处理模块的作用是构成完整的食谱样本。该模块首先调用图片库中主食、配菜和饮品图案，之后将这些图案贴图到模型表面。剩余操作采用按钮控制，由用户决定是否执行。该模块的流程是添加按钮，建立消息响应函数，在不同函数中调用相应的OpenGL函数。交互式进化算法模块将本文提出的算法整合到系统中，为保证系统运行效率，交互进化界面设置按钮控制算法执行。人机交互过程中，用户首先对界面显示的模型打分；之后，用户点击进化按钮，由系统调用进化算法以产生下一代个体；重复上述过程直到找到最优个体。

图3 系统结构

图4 用户信息界面

图5 系统操作界面

4 实验与分析

本系统的体验用户是男女各5名在校大学生，年龄区间20-25，身高体重均属正常范围，记为用户1-10。本节从适应性、有效性和可用性等3个方面分别验证系统的性能。

4.1 系统适应性测试

表1 系统优化解

表2 算法进化代数与满意解样本分析

图6 算法进化代数与满意解

(2)进化过程中用户偏好的波动是反映算法适应性的另一重要指标。用户偏好的波动可以通过进化过程中用户评价个体适应值变化反映，用户评价个体适应值变化可以分为由低变高、保持不变和由高变低等3种情况。统计用户进化优化过程中评价适应值上升率PR、保持率PH和下降率PD

(7)

式中：∑SR是用户评价适应值均值每代由低变高的次数之和；∑SH是用户评价适应值均值每代保持不变的次数之和；∑SD是用户评价适应值均值每代由高变低的次数之和；∑SF是系统出现的互异个体数之和，且PR+PH+PD=1。

用户的偏好波动统计结果见表3。由表3可以看出，两种方法中，进化过程中用户偏好均呈逐渐上升趋势，即用户对系统给出的食谱越来越满意，但本文方法的适应值上升率最高、保持率最低。这说明，使用本文方法用户偏好波动最小、优化结果更符合用户偏好。原因在于，本文方法考虑了定量指标的影响，用户对食谱菜品的评价结果包含的理性成分更多，优化解可以更好融入用户偏好，所以，偏好变化最小。两种方法的适应值下降率并无显著差异，这说明两种方法均可以搜索到符合用户偏好的优化结果。另外，通过t检验可知，两种方法中女生组与男生组的各项偏好波动指标均并无显著差异，这一与印象不符的有趣现象表明，对于食谱选择这类混合指标优化问题没有性别倾向性。

表3 用户偏好波动结果

4.2 系统有效性测试

本节测试算法对于显式指标的优化效果，即验证一份食谱除了满足用户口味外，对于营养性需求方面的满足效果。每位用户提供1份4.1节(1)中采用本文方法和IGA获得的食谱，以及根据10位用户体征，采用食物交换份法获得的10份食谱，共计30份食谱样本。按式(1)计算每份食谱中碳水化合物、蛋白质和脂肪等3种营养素含量，分别记为Ci,Pi,Fi,i=1,2,…,10。根据中国营养学会推荐的3种营养素标准点(C,P,F)=(405g,101g,75g)[11]，则营养指标为

(8)

其中，di越接近于0，说明食谱越接近营养需求。

3种方法的di曲线如图7所示。由图可见，本文方法获得的食谱营养指标最低，说明本文方法优化质量最高。原因在于，IGA只以用户偏好优化食谱，没有考虑食材份量、热量等因素，所以优化方案的营养指标最高，优化质量最差。食物交换法基于本文方法的食谱重新计算营养指标，由于没有根据用户情况进行优化，所以，营养指标介于本文方法和IGA之间。这表明，本文方法的优化结果营养性最好，用户可以获得最佳的营养配置，所以，本文方法有效性最佳。

图7 食谱营养指标

4.3 系统可用性测试

4.1节和4.2节两项实验结束后，对用户问卷调查本文方法和IGA可用性。该问卷分为有效性、满意度、易用性和易学性等4类共30个评分项目，每个评分项目都是正向陈述[13]。用户在7点Likert量表上对陈述给出评分。再根据评分项目权重将各项评分结果折算成相关类的体验值，最后，将体验值取均值，并用图8所示雷达图表示。由图可见，两种方法在易学性和易用性两个方面差异并不大，这是因为这两种方法的进化优化系统人机交互界面十分统一，所以系统可操做性一致。但在有效性和满意性两个方面，本文方法的体验值明显高于对比方法，这说明本文方法的优化结果更符合用户偏好，用户对系统的认可程度更高，算法的可用性最强。原因在于，将食谱优化问题视为求解混合指标优化问题，目标层次更为丰富，在不增加用户额外负担的情况下提高了优化质量。

图8 可用性雷达

通过上述3项实验测试可以见到，本文方法具有良好的交互性，能够适用于不同用户个性化需求。在兼顾营养、价格等因素前提下，本文方法可以获得更有效的健康食谱，并表现出最佳的可用性。

5 结束语

采用交互式进化优化与非交互式进化优化结合方法实现个性化食谱优化设计。该方法同时优化显式指标与隐式指标。采用交互式进化优化方法优化隐式指标。基于指标均衡度，采用非交互式进化优化方法优化显式指标，替换指标均衡度较差个体，改造Pareto前沿面。与传统食物交换法和单纯交互式进化优化方法对比，本文方法可以在最少的进化代内很便捷地获得最优满意解，获得的个性化食谱可同时满足用户偏好和营养性指标。系统的适应性更强，有效性更高，可用性显著。本文研究的食谱优化仍属简单的混合指标优化问题，探寻交互式进化计算求解高维混合指标优化对象是进一步研究的内容。