一种用于便携式酒壶设计的混杂型交互式进化优化方法

摘要

本发明公布了一种用于便携式酒壶设计的混杂型交互式进化优化方法，旨在提高便捷式酒壶个性化设计的效率，具体步骤如下：(1)进化开始前，系统为用户提供设计环境，随机生成初始进化种群；(2)在人机交互过程中，为用户提供评价窗口；(3)对用户评价的个体适应值进行不确定性分析，基于适应值不确定度划分出两种适应值类型，即单一数值型与区间数值型；(4)系统针对适应值类型建立相应数学模型，修正个体适应值，并参与后续进化。两类修正后的适应值同时参与进化优化，期望生成符合用户心理需求的设计，达到高效优化目的。

说明书

技术领域

本发明属于情感计算领域，提出了一种用于便携式酒壶设计的交互式进化优化方法，可用于引导用户进行酒壶外观方案的设计。

背景技术

不锈钢酒壶是流行于国内外的一种户外消费品，它具有高雅精致、美观小巧、便于随身携带的特点，深受男士青睐。由于消费水平的推动，便携式酒壶的市场需求逐渐增大，对酒壶的外观要求逐渐提高。传统的方圆扁型设计逐渐被个性化设计取代，为了增强市场竞争力，酒壶的外观设计对设计人员提出了挑战。为了应对这种状况，本发明将进化优化思想引入到产品的外观设计中来，借助遗传算法的优化能力，为设计人员创作设计提供设计灵感。

目前，基于计算机辅助工程的产品(艺术)设计系统已经逐渐被采用，但借助于进化优化方法的实用设计系统并不多。便携式酒壶设计的目标是找出“最满意的酒壶外观设计”，由于不同人对“满意的设计”有不同的标准，因而评价结果具有很强的不确定性，这是一类典型的适合用交互式遗传算法解决的隐式性能指标优化问题。

但单纯采用传统交互式遗传算法构建设计系统，性能并不理想。因为交互式优化的每款产品适应值(评价值)由人评价产生，所以适应值反映了人的主观偏好，而人的偏好会使适应值具有不确定性，不确定性增加，适应值的精确程度便会降低，进化优化效果将会变差。提高适应值精确程度，降低不确定性的直接方法是令设计人员在评价个体时投入更多的注意力，但这样无疑会造成人的疲劳，评价不确定性反而会增强。所以提高适应值精度与降低人的操作负担是互为矛盾的，这也是交互式遗传算法应用的难题。

目前，应用交互式进化优化方法进行产品外观设计，已经公布了一些策略。这些策略大致分为两种类型，其一是通过建立合理的适应值赋值方式，改善人机交互环境，降低人的操作负担，提高适应值精度。如2008年3月出版的期刊《Progress in Natural Science》第18期“Adaptive Interactive Genetic Algorithms withInterval Fitness of Evolutionary Individuals”一文中提出的区间数和模糊数适应值赋值方法及在服装设计系统上的应用；中国发明专利“用于窗帘设计的交互式进化优化方法”(公开号：CN10263249A，公开日：2011.08.24)给出的多集势模糊评价、精确值评价与自动评价。相比精确数与离散数，区间数与模糊数可以较好的反映出评价过程的不确定性与渐进性，大大提高了适应值精度。但在进行适应值赋值操作时，区间数要进行适应值上限与下限的两次评价；模糊数要进行中心值与宽度的确定，这其实都增加了设计人员的负担。其二是采用合适的代理模型代替用户估计进化个体的适应值减轻用户疲劳。代表方法如2009年10月出版的期刊《控制与决策》第24期“区间适应值交互式遗传算法神经网络代理模型”一文提出的通过代理模型预测评价结果从而减少人的评价的方法；2013年5月出版的期刊《控制理论与应用》第30期“新的基于相似度估计个体适应值的交互式遗传算法”一文提出的机器估计适应值策略；中国发明专利“基于交互式进化优化的图书个性化搜索方法”(公开号：CN103984721A，公开日：2014.08.13)给出的用户偏好搜索方法。这类机器学习技术拓展了算法搜索能力，减轻了设计人员的操作负担，具有重要指导意义。但这些代理模型是依据于不同的适应值赋值方式，提取有价值信息而建立，所以适应值赋值方式的影响依然存在。更重要的是，上述所有方法均未涉及适应值形态在进化过程中的自然变化规律，没有体现出适应值的数值多样性变化。

采用交互式进化优化方法开发产品设计系统，对于中小企业具有广阔的市场前景。经查阅相关文献，目前还不存在应用具有多种适应值类型同时并存进化的交互式遗传算法于便携式酒壶设计的方法。如能开发出相关的高效设计系统，不仅会对酒壶产品的设计带来推动价值，对其他产品设计也将具有重大启发意义。

发明内容

本发明提出了一套完整的便携式不锈钢酒壶产品生成、交互及进化设计方法，通过进化优化可完成酒壶外观的设计。本发明的特点在于采用了改进的高性能交互式遗传算法进行酒壶外观设计，具体表现是提出了混杂型适应值概念，进化过程中适应值同时具有两种表现类型，体现了交互式进化优化评价的复杂多样性。另外，给出了一种评价不确定性的度量方法，基于此提出了适应值扩展策略，为适应值分类提供了新的参考。与同类方法比较，本发明的设计结果明显占有优势。

本发明分为两大部分。第一部分是人机交互式单元。利用友好的人机交互平台，完成设计人员对系统提交酒壶设计的设计信息，即通过对洒壶外观的评价打分确定设计人员的偏好程度和设计方向。第二部分是进化单元。具体包括：首先，进化优化算法利用酒壶设计的每款产品评价的不确定度作为适应值类型划分依据，保证酒壶设计评价值分类的合理性；其次，根据设计人员的设计行为，系统对产品款式设计评价值的单一数值类型利区间数值类型分别构建相应数学模型，提高评价的准确性；最后针对不同类型的款式设计采取不同的个体进化策略，完成对酒壶外观的自动设计。

本发明的优点和积极效果是：

1.有效降低设计人员的操作负担，设计人员只需粗略评价少量产品款式即可，系统在后台自动完成适应值修正；

2.提高了设计质量，通过算法对评价结果的修正，可以在不增加人的负担的同时，对个体进行有效评价；

3.提高了设计效率，多种类型的评价结果共同参与优化，更符合设计人员的设计行为，优化效率高于单一类型评价结果。

附图说明

图1本发明提出的用于酒壶外观设计的交互式进化优化方法总体流程图；

图2依据本发明所提方法开发的酒壶外观设计系统界面图；

图3本发明与T-IGA轮赌法、IGA-IIF概率占优的锦标赛算的进化代数比较；

图4本发明与T-IGA轮赌法、IGA-IIF概率占优的锦标赛算法的满意解数目比较；

具体实施方式

以下对本发明实施做进一步详述，以下实施例只是描述性的，不是限定性的，不能以此限定本发明的保护范围。

一种基于混杂型适应值交互式遗传算法的便携式酒壶设计方法，方法流程如图1所示，该方法的步骤如下：

步骤1.设计开始时系统进行初始化，即设置进化优化的进化代为0。设计人员设定遗传算法参数，如交叉、变异概率等。系统会根据酒壶壶口(带壶盖)和壶身两部分的二进制编码，随机从素材库中读入3ds格式的酒壶结构模型，利用OpenGL完成对模型的贴图和显示，得到一个完整的酒壶个体(样本)。重复该过程直至呈现初始进化种群，即8个酒壶初始设计样本。设计系统界面如图2所示，其中每个样本(个体)下的滑动条为设计人员打分评价使用，滑动条的显示数值即为该个体的适应值，打分范围为1-100。

步骤2.用户按个人偏好对各个酒壶样本设计打分评价，确定各款产品的适应值；

步骤3.产品样本评价不确定度的测量；

便携式酒壶进化优化设计的第t代进化种群x(t)中的第i个评价个体(产品样本)表示为x_i(t)，i＝1，2，…，N，N表示所有酒壶款式设计样本数目(种群规模)，x_i(t)的适应值表示为f(x_i(t))，x_i(t)∈x(t)。则酒壶样本评价值构成的数值序列表示为f(x(t))＝(f(x₁(t))，f(x₂(t))，…，f(x_N(t)))。

根据二元排序原则，若将f(x_i(t))的不确定度表示为θ(x_i(t))，则有

$>\theta \left(x_i\left(t\right)\right)=1-\frac{\min (f\left(x_{i-1}\left(t\right)\right),f\left(x_i\left(t\right)\right))}{\max (f\left(x_{i-1}\left(t\right)\right),f\left(x_i\left(t\right)\right))}(i=2...N)---\left(1\right)$>

式中，min(f(x_i-1(t))，f(x_i(t)))表示f(x_i-1(t))，f(x_i(t))中的较小值，max(f(x_i-1(t))，f(x_i(t)))表示f(x_i-1(t))，f(x_i(t))中的较大值。

(1)式的意义是：在便携式酒壶款式进化设计初期，由于人对产品的偏好具有模糊性，所以对系统呈现的样本款式的认知程度比较低，对样本个体评价差异很大，评价的不确定性较大，θ(x_i(t))也较大。随着款式样本种群的不断进化，酒壶款式差异逐渐减小，适应值趋于一致，设计人员评价的不确定度相应变小。

步骤4.样本适应值类型划分阈值的确定；

可以根据(1)式确定评价不确定度，则有

$>\underset{i=2}{\overset{N}{\Sigma }}\frac{1}{N-1}(1-\frac{\min (f\left(x_{i-1}\left(t\right)\right),f\left(x_i\left(t\right)\right))}{\max (f\left(x_{i-1}\left(t\right)\right),f\left(x_i\left(t\right)\right))})\le 1-\frac{\underset{x_i\left(t\right)\in x\left(t\right)}{\min }f\left(x_i\left(t\right)\right)}{\underset{x_i\left(t\right)\in x\left(t\right)}{\max }f\left(x_i\left(t\right)\right)}(i=2...N)---\left(2\right)$>

(2)式的意义是：设计人员对同一进化代的样本评价不确定度小于个体适应值信息的最大差异。即在每一进化代评价中，设计人员设计行为遵循二元排序原则，偏好对适应值的影响主要体现在相邻酒壶样品的评价上。

根据(2)式对样本的评价值进行划分：评价初期，样本评价不确定度较大，适应值表现为区间数值型；随着评价的深入，设计人员对环境的认知逐渐清晰，样本评价不确定较小，适应值表现为单一数值型。

步骤5.适应值的区间扩张；

对于样本评价不确定度较大情况，设计人员评价的单一数值不能全面反映评价的客观性，此时需要将其扩展为信息容量较大的区间数值。定义δ(x_i(t))为个体单一适应值f(x_i(t))扩展成区间适应值f′(x_i(t))的区间半径。由于样本评价不确定度θ(x_i(t))反映了评价的不确定性，所以本发明在θ(x_i(t))和δ(x_i(t))之间用函数关系δ＝g(θ)映射，函数拟合如下式：

$>\delta \left(x_i\left(t\right)\right)=K(1-e^{-\mathrm{\lambda \theta }\left(x_i\left(t\right)\right)})---\left(3\right)$>

式中K，λ为调节系数，可以根据不同的设计环境取值。

这样，将单一评价值f(x_i(t))扩张成区间数值，表示如下：

$>f^{\prime }\left(x_i\left(t\right)\right)=[\underset{‾}{f}\left(x_i\left(t\right)\right),\bar{f}\left(x_i\left(t\right)\right)]=[f\left(x_i\left(t\right)\right)-\delta \left(x_i\left(t\right)\right),f\left(x_i\left(t\right)\right)+\delta \left(x_i\left(t\right)\right)]---\left(4\right)$>

式中，是区间数值的下限，是区间数值的上限。

进一步对区间适应值进行估计，令

$>\theta =\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}\frac{\underset{‾}{f}\left(x_i\left(t\right)\right)+\bar{f}\left(x_i\left(t\right)\right)}{2}=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}f\left(x_i\left(t\right)\right)---\left(5\right)$>

$>m=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}\frac{\bar{f}\left(x_i\left(t\right)\right)-\underset{‾}{f}\left(x_i\left(t\right)\right)}{2}=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}\delta \left(x_i\left(t\right)\right)---\left(6\right)$>

式中，θ表示对设计人员满意程度的点估计值，m表示点估计的盲度，m越小，估计的把握越大。m＝0意味着对满意程度绝对有把握。

步骤6.单一数值型适应值灰色Verhulst模型的建立；

当评价不确定度较小时，适应值表现为单一数值。此时，酒壶设计过程已经比较深入，酒壶外观差异比较小，设计人员会产生疲劳。为了进一步降低设计人员主观评价的不确定性，此时适用灰模型对适应值建模，并对适应值修正。

6.1.灰模型的建立

在本发明中，酒壶样本的评价值f(x_i(t))构成原始序列f⁽⁰⁾(x_i(t))＝(f⁽⁰⁾(x₁(t))，f⁽⁰⁾(x₂(t))，…，f⁽⁰⁾(x_N(t)))。每一进化代内，酒壶样本的评价值序列先进行灰生成序列和平均值序列的转化，灰生成序列表示为f⁽¹⁾(x_i(t))＝AGOf⁽⁰⁾(x_i(t))，平均值序列表示为F⁽¹⁾(x_i(t))＝MEANf⁽¹⁾(x_i(t))，再构建进化个体适应值灰Verhulst模型GM(1，1，V)为：

f⁽⁰⁾(x_i(t))+aF⁽¹⁾(x_i(t))＝b(F⁽¹⁾(x_i(t)))²   (7)

GM(1，1，V)的白化响应式为

$>{\hat{f}}^{\left(1\right)}\left(x_{i+1}\left(t\right)\right)=\frac{\frac{a}{b}}{1+(\frac{a}{{\mathrm{bf}}^{\left(0\right)}\left(x_1\left(t\right)\right)}-1)e^{\mathrm{ai}}}---\left(8\right)$>

$>{\hat{f}}^{\left(0\right)}\left(x_{i+1}\left(t\right)\right)={\hat{f}}^{\left(1\right)}\left(x_{i+1}\left(t\right)\right)-{\hat{f}}^{\left(1\right)}\left(x_i\left(t\right)\right)---\left(9\right)$>

式中即为酒壶款式样本个体x_i+1(t)的评价值预测值；a，b为一级参数。

GM(1，1，V)的二级参数包表示如下：

$>C_V=\underset{i=2}{\overset{N}{\Sigma }}{F}^{\left(1\right)}{\left(x_i\left(t\right)\right)}^3---\left(10\right)$>

$>E=\underset{i=2}{\overset{N}{\Sigma }}{F}^{\left(1\right)}\left(x_i\left(t\right)\right)·f^{\left(0\right)}\left(x_i\left(t\right)\right)---\left(11\right)$>

$>F=\underset{i=2}{\overset{N}{\Sigma }}{\left(F^{\left(1\right)}\left(x_i\left(t\right)\right)\right)}^2--\left(12\right)$>

$>G=\underset{k=2}{\overset{n}{\Sigma }}{F}^{\left(1\right)}{\left(x_i\left(t\right)\right)}^4---\left(14\right)$>

$>H=\underset{k=2}{\overset{n}{\Sigma }}{F}^{\left(1\right)}{{\left(x_i\left(t\right)\right)}^{2}f}^{\left(0\right)}\left(x_i\left(t\right)\right)---\left(14\right)$>

式(10)-(14)是中间参数，由这些中间参数可求得灰模型GM(1，1，V)的一级参数(a，b)。

$>a=\frac{C_{V}D-\mathrm{GE}}{\mathrm{FG}-C_V^2}---\left(15\right)$>

$>b=\frac{\mathrm{FH}-C_{V}E}{\mathrm{FG}-C_V^2}---\left(16\right)$>

6.2.个体适应值灰预测

由于进化个体适应值序列是偏好环境下各种因素作用的结果，可以通过灰模型滚动检验预测设计人员的偏好分布。酒壶样本评价值的滚动残差ε(i+1)为：

$>ϵ(i+1)=\frac{f^{\left(0\right)}\left(x_{i+1}\left(t\right)\right)-{\hat{f}}^{\left(0\right)}\left(x_{i+1}\left(t\right)\right)}{{\hat{f}}^{\left(0\right)}\left(x_{i+1}\left(t\right)\right)}---\left(17\right)$>

根据滚动残差，可得酒壶样本个体x_i(t)的适应值可信度p_r(x_i(t))为：

p_r(x_i(t))＝[100-|ε(i)|]％   (18)

6.3.个体适应值修正

通过适应值可信度对评价后的进化个体适应值进行修正：

f′(x_i(t))＝p_r(x_i(t))·f(x_i(t))   (19)

式中：f′(x_i(t))为进化个体x_i(t)修正后的适应值，修正后的适应值不确定性将降低，参与后续遗传操作，会减小优化结果的偏差。

步骤7.遗传操作由选择、交叉和变异操作组成。对于扩展成区间数的区间适应值，可以按区间占优进行个体选择；对于通过灰模型预测的修正后的单一数值适应值，可以按轮赌法进行个体选择。两种选择机制在本发明中同时存在，是本发明的突出特点。

步骤8.选择操作后，生成新一代种群。如果设计人员对新种群的酒壶款式样本满意，则保存最优设计方案，完成设计。否则，算法跳转步骤2，设计人员点击“下一代”进化按钮，继续对酒壶样本打分评价。在整个进化过程中，如果设计人员对当前的酒壶方案始终不够满意，可重新初始化酒壶种群，开始新的进化。设计人员在每一次进化设计结束前，统计本次设计所需的进化代数数目，统计结果如图3所示；另外，在每一个进化代打分评价结束后，统计本次评价的满意样本数目，满意样本是指每代中精确数适应值最高和次高的酒壶个体，统计结果如图4所示。

该算法与目前算法的比较

目前已有的应用于产品设计的算法主要有传统的交互式遗传算法(T-IGA)和基于概率占优的区间适应值交互式遗传算法(IGA-IIF)。本发明从进化代数、满意解数目和耗时等三个方面对算法性能衡量。

三种方法的进化代数统计如图3所示。可以看到，本发明的进化代数最少，说明设计人员的操作负担最小。算法获得满意解的统计情况如图4所示，可以看出，本发明获得的满意解数目最多，说明本发明的优化质量最高。

结合图3和图4可以看出，本发明可以在最少的进化代内获得最多的满意解数目，这加快了算法收敛速度，显示了良好的进化优化能力。

最后，统计算法的耗时情况如下表所示。由于本发明的进化代数少，所以每次实验的耗时也比较少，对比其他两种算法，本发明耗时只有传统交互式遗传算法耗时的大约一半。与IGA-IIF相比，本发明操作量大幅降低，对个体只评价精确数值即可获得比对个体进行区间赋值评价更好的效果。而耗时减少意味着缩短了人的操作时间，自然有效降低了设计人员的操作负担。