遗传算法（GA）是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说，遗传算法是对生物进化过程进行的数学方式仿真。霍兰德（Hol-land）在他的著作《Adaptation in Natural and Artificial Systems（自然与人工系统中的适应）》中首次提出遗传算法，并主要是由他和他的学生发展起来的。

1.交互式进化算法

随着数据在日常决策中的重要性越来越显著，人们对数据处理技术的要求也不断提高。人们需要能够对数据进行较高层次处理的技术，从中找出规律和模式，以帮助人们更好地利用数据进行决策和研究。在数据库技术飞速发展的同时，人工智能领域的一个分支——机器学习自20世纪50年代开发以来也取得了很大进展，提出了很多机器学习的方法，如实例学习、神经网络和遗传算法等。其中遗传算法在自动获取知识方面的应用范围非常广泛。遗传算法是一个全局优化的搜索算法，在进化计算过程中一般无须借助外部信息，而直接凭借适应度值的计算来对个体的优劣进行评估，并以此作为遗传操作的依据。然而在一些领域的适应度函数表达式很难明确地给出，如图像合成、人脸识别等，图像的优劣一般交由用户评估，而难以通过计算得到。针对遗传算法的自动化程度高，而用户介入程度低的问题，人们提出了用交互式遗传算法来提高遗传算法的应用范围。

交互式遗传算法是针对一些应用领域存在的适应度函数难以明确表达的问题而提出来的。它是一种通过用户参与进化过程和对进化个体进行评估，以代替计算过程的改进方法。它最初应用于汽车、手表的设计等领域，也是一种基于用户主观评价的全局搜索优化技术，换言之，这种方法就是在进化的过程中，采用人机交互的方式，并由用户确定适应度函数的值，再通过选择、交叉、变异等遗传操作而在特征空间进行搜索；用户通过给出适应度函数值，来评价搜索结果与用户主观空间或心理空间的相似度，并将人的主观情感融入到进化过程，从而实现了主观心理空间和客观特征空间的映射。图6-15表明了GA与IGA的区别。

图6-15 GA与IGA的比较

IGA也有不足之处，即用户在交互过程中，对每代的所有个体都要进行评估，当个体的数量较大、进化时间较长时，用户容易疲劳，特别是当某一代中存在差别不大的类似个体时，要对它们进行相对优劣的评估，心理压力更大，因而更容易产生疲劳。针对这一问题，HideyukiTakagi曾提出用离散适应度值（即只有若干个不同级别的适应度值）来代替连续适应度值（即有几十甚至几百个不同级别的适应度值），以减轻用户的心理压力。但该方法的结果是使遗传操作的收敛性变差。针对用户疲劳问题，本节提出了两种解决方法：其一是跟踪并记录用户每次所选择的最佳个体，当用户疲劳时，根据对记录的历次最佳个体的学习来自动计算个体的适应度值，以代替用户对个体的评估过程，即采用用户评估与机器自动计算相结合的方法；其二是当用户预先能对所选个体提出大致的要求时，从数据库中搜寻出大致符合用户要求的若干个体，以代替最初随机产生若干个体呈现给用户的过程，以此加速收敛性，缩短用户评估的过程。基于以上考虑，设计了个性化交互系统的在线推理机模型。

2.模型描述

系统模型如图6-16所示。图中，三个点画线框分别表示预处理模块、交互式GA模块和自主式GA模块。

图6-16 系统模型

预处理模块主要完成交互式GA操作之前的数据预处理工作。交互式GA模块分别由用户评估、选择、交叉、变异和群体更新等几个功能模块所组成。自主式GA模块则根据所记录的历次最佳个体对新的个体进行适应度值的自动计算，以机器评估代替用户评估。

（1）预处理模块 遗传算法中，初始群体的设定可采取如下策略：根据问题固有知识，设法把握最优解所占空间在整个问题空间的分布范围，然后在此分布范围内设定初始群体。在交互实验中，发现第一次呈现给用户的服装图片中，大致符合用户要求得越多，在随后的IGA操作过程中，得到用户满意结果的速度就越快。由此，考虑了利用使用数量化I类理论作为初始信息处理工具。

数量化理论（Theory of Quantification）作为多元统计分析的一个分支，始于20世纪50年代。起初它的应用仅限于“计量社会学”方面，随着电子计算机的广泛应用，60年代以后，它在自然科学领域中的应用日益增多。数量化理论按其所研究问题的目的的不同，可分为四种，分别称为数量化理论Ⅰ、Ⅱ、Ⅲ、Ⅳ。这是一种正在发展着的理论，还有不少问题值得研究，例如项目如何选取、类目如何划分、定量数据转化为定性数据时对结果有怎样的影响等，这些问题都有待于从理论与实践两方面来解决。数量化理论I是用于定量基准变量的预测问题。在本节中，主要用到了用于定量基准变量预测的数量化I类理论，其目的是定量地估计定性变量对一个被称为目标变量的影响。数量化Ⅰ类理论用于自变量都是定性变量，基准变量是定量变量的预测问题。但是，应用数量化理论建立的模型是一种线性的模型，而人的心理具有许多非线性的特征，所以只能用来做简单的预估。下面简单介绍其理论基础。

在数量化理论Ⅰ中，假定基准变量与各项目、类目的反应间遵从下列线性模型：

式中，b_jk是仅依赖于j项目的k类目的常系数；ε_i是第i次抽样中的随机误差。

现在根据最小二乘原理寻求系数b_jk的最小二乘估计，换言之即寻求使得

达到最小值。为此，求q关于b_uv的偏导数，并令其等于0，得到

因为这是极小值点的必要条件，故如记使q达到最小值的b_jk，则b_jk应满足下式：

以矩阵形式表示为

所解问题归结为求一个使误差E’E为极小值的线性函数。根据最小二乘法，寻求系数b的最小二乘估计，求得

B^∗=（X^T-X）^-1X^TY （6-15）

即为定性类目的数量化。令

就是预测的理论值。

在求得最小二乘估计B^∗之后，可用样本复相关系数r来衡量，它可以按下式计算：

其基本思路是先根据数量化Ⅰ类理论公式将数据库中的所有被检索对象进行划分，并根据此划分分别计算出数据库中每一个对象的上近似和下近似，然后确定每一个对象与目标检索的相关联程度，最后根据其相关联程度从高向低依次检索出用户感兴趣的图片。此外，若用户提不出任何具体要求，则随机产生若干个服装图片呈现给用户。图6-17为预处理模块流程框图。

图6-17 预处理模块流程框图

预处理建模的一般过程如下：

1）收集表达心理的形容词对；

2）抽选调查的对象来做评价实验，以服装图片为对象进行SD评价实验，得到的评价运用因子分析方法来处理，完成形容词对的量化，得到情感矩阵Y；

3）抽取服装的特征值，得到特征空间反应矩阵X；

4）将心理描述和特征值的关系定量化——使用数量化Ⅰ类理论式（6-15），即

B^∗=（X^TX）^-1X^TY

建立形容词对于商品特征的数量化关系，求出B^∗之后，利用式（6-16），即

就可以通过B和商品特征的反应矩阵X来预测该商品的评价值，求出对应于所有形容词对的B值，即建立了商品的预处理模型。每一位用户在进入到个性空间后，都必须进行注册，在注册中，对训练样本图像做出评价，构成大众情感矩阵Y，进而得到B。参与的人越多，B值越准确，对图像的预测就会越近似。对于系统的准确度和速度都有极大的影响。随后当用户提出个性选购要求时，系统首先根据预处理模块给出基于大众心理的图像，然后再根据用户对这些图像的满意度评价来决定遗传方式。

（2）IGA模块 IGA模块由评估、选择、交叉和变异及群体更新等主要算法模块所组成。由于遗传算法在优化搜索中基本上不用外部信息，仅用适应度函数为寻找依据，而且遗传算法对适应度函数的惟一要求是该函数不能为负，所以在这里取用户对系统检索出图片的满意度值作为IGA的适应度函数。一般将用户的满意度用五种语气表达：极其不满意、不满意、一般、满意、非常满意。这五种语气分别对应1、2、3、4、5。为保证收敛性，采用优秀个体保护法将每代中的最优个体即适应度最高的个体不进行配对交叉，而直接复制到下一代中，相应淘汰其子代中适应度最差的个体，使种群规模不变。在所挑选出的图片中，用户的评价小于2所对应的图片将直接被淘汰，而用户的评价大于4所对应的图片将直接遗传进入下一代。其余的图片进行交叉或变异操作。其系统框图如图6-18所示。

通过上述进化操作产生的新染色体，可能在其图像库中未必有完全一致的对应项，因此为提高IGA性能，本节提出了相似距离值这一方法。所以应将图像库中的每一幅图像与其进行比较，并按相似距离计算它们的相似度，再取出其中相似度最小的6幅图像作为新的群体，显示给用户，供用户作进一步分析判断。

图6-18 IGA系统框图(www.daowen.com)

假设两个体A、B的编码为

A=（a₁，a₂，…，a_n） B=（b₁，b₂，…，b_n）

两个体之间的相似距离值定义如下：

式中，

d（A，B）值越大，说明两个体间的相似距离值越小，反之亦然。同样，用户也可通过比较两个体间的相似距离值来对新的个体进行评估。交互式模块的工作流程如图6-19所示。

（3）自主式GA模块

自主式GA模块的自主式GA部分与交互式GA部分的不同之处在于前者的每一代个体适应度值是自动计算得到的，而不是根据用户评估得到的。在交互式GA过程中，系统自动记录了用户历次所选的最新、最佳个体若干。当用户感到疲劳时，可退出交互式GA过程，而进入自主式GA过程。系统记录的每一个体对应一个输入向量。基于输入向量分别计算每一个体与其他个体间的相似性。本节以两向量间夹角的余弦作为向量的相似性度量。

图6-19 IGA模块

相似性的值分别对应权值大小，角度越小，相似性越大，权值也就越大，故权值P可定义如下：

P_ij=cosθ_ij （6-20）

新的适应度值被定义为原始适应度值的加权平均。例如，记录有编号分别为1、2、3、4的四个最佳个体，设其原始适应度值分别为S₁、S₂、S₃、S₄；各个体之间相似性值分别为P₁₂、P₁₃、P₁₄、P₂₃、P₂₄、P₃₄，则个体1的新适应度值可计算如下：

fitness[1]=P₁₂×S₂+P₁₃×S₃+P₁₄×S₄ （6-21）

计算出新的适应度值之后，再进行GA过程，所产生的新个体若满足用户的要求，则停止此过程。若不满足用户的要求，则重复自主式GA过程，或退出此过程而进入交互式GA过程，直至产生用户满意的个体为止。这里用户满意的含义是所产生的新个体超过75%的个体是用户所期望的。这样通过交互式GA与自主式GA相结合，可以在某种程度上有效缓解用户的疲劳程度。

3.算法的设计与实现

（1）数据结构与算法参数 基本遗传算法处理的对象主要是个体，因此设计了结构变量individual来描述个体信息，其中包括个体的染色体串chrom、个体适应度fitness、个体对应的变量varible、交叉位置xsite，以及记录父个体编号parent等。为记录历代最佳个体，设计结构变量bestever，表示最佳个体对应的染色体chrom、个体适应度fitness、个体对应的变量varible及最佳个体产生的代数。根据个体变量定义，设计当前代种群oldpop及新一代群newpop，为全局变量。此外，将当前种群中个体最大适应度max、个体平均适应度avg、最小适应度min、个体适应度累计值也定义为全局变量。

算法参数可定义为一个8元组：

GA=（C，E，P₀，M，Φ，Γ，Ψ，T） （6-22）

式中，C为个体的编码方法，这里使用46位二进制符号串的编码方式；E为个体的适应度评价函数，这里定义用户的满意度值为适应度值；P₀为初始群体，借助数量化Ⅰ类公式来产生初始图片；M为群体大小，取20～100；Φ为选择算子，采用优秀个体保护法和淘汰最差法；Γ为交叉算子，使用单点交叉算子，交叉概率取0.6～0.95之间的值；Ψ为变异算子，使用基本位变异算法，变异概率取0.001～0.01之间的值；T为算法终止条件，定义终止进化代数为10～50。

（2）产生初始种群

（3）遗传操作设计 为返回种群中被选择的个体编号设计函数select（）；为单点交叉操作设计的函数crossover（）；随机产生交叉点位置jcross；由flip（）函数来确定是否发生交叉操作。

（4）世代进化过程的实现 模拟世代进化过程设计的函数generation（），以种群的处理对象实现了一个世代内的三种遗传操作。

（5）主程序 主程序设计了多次运行遗传算法的过程，每次运行前，由使用者输入不同的参数设置，运行结束时，将有关进化过程的统计结果写入输出数据文件中。

算法描述如下：

4.实验结果与分析

为了验证该系统的有效性，我们首先创建了包含200张服装图片的特征库，由于服装是由四个部分组成，通过编码可以将每一个服装图片的特征表示成一个46位的二进制数。分别进行三组实验。第一组是验证数量化Ⅰ类公式在预测客户评价值方面的可行性实验。50名用户分别对10个训练样本进行评价，求出B∗后，再分别与20个校检样本相乘，得到20个校检样本的预测评估值Y′，与客户对20个校检样本的真实评价值Y比较可以看出，预测值相对比较集中在[2，4]这个范围内，在此范围内的预测基本比较准确，相比较而言，对两个极端评估的预测稍差。但这是合理的，因为作为人来讲，大多数人对一个事物的评价都会比较中庸，所以对这个范围的预测率会相对较高，这也是为何数量化Ⅰ类公式无法体现个性化的问题所在。实验结果说明，用此方案作为预处理是可行的。实验结果如图6-20所示。图中，实线Y代表20个校检样本的真实评价值，虚线Y′代表20个校检样本的预测评估值。

第二组实验对单独使用IGA与IGA和数量化Ⅰ类公式结合使用进行比较，前者随机产生N幅图片，再进入交互过程；后者则按照数量化公式从图片库中先分别搜索出能大致满足大众用户对此要求的图片1～3个，再进入交互过程。比较结果见表6-6。

图6-20 20个校验样本的预测值与实际值比较

表6-6 两种方法比较

实验结果表明：这种预处理方法与IGA相结合进行识别的效率要比单独使用IGA进行识别的效率高、速度快。图6-21显示了单独使用IGA进行实验的收敛曲线。

图6-21 第二组实验的收敛曲线（单独使用IGA）

第三组实验是在IGA过程中加进了相似距离值和自主式GA。每一代记录用户所选的最佳个体数量分别为2～6，在计算其新的适应度值和相似性后，进行GA操作过程。同样，每一组实验重复五次，取其收敛步数的平均值来绘制收敛曲线，实验结果如图6-22所示。

图6-22的收敛曲线表明：所提供的、满足用户大致要求的个体越多，产生用户满意结果的速度就越快。第三组实验表明：记录的个体数目越多，通过相似性计算，再进行GA操作，其收敛步数也呈加快的趋势。需要说明的是，记录的个体数目越多，IGA进化的代数就越多，所产生的相似个体也就越多。用户需要对相似个体进行评估，心理压力较大，评估时有波动现象产生。但从实验结果的曲线图看，此波动现象对个体间相似性的计算影响不大。

由本小节的讨论可知，应用IGA建立个性化智能服装选购系统模型的一般过程如下：

1）形容词对的确定及量化；

2）服装特征的确定及量化；

3）利用IGA建立个性化智能服装选购系统的人工心理模型。

图6-22 第三组实验的收敛曲线（加进了相似距离值和自主式GA）

交互式进化算法是一种通过用户参与进化过程和对进化个体进行评估，以代替计算过程的改进方法，也是一种基于用户主观评价的全局搜索优化技术。这种方法是在进化过程中，采用人机交互方式，并由用户确定适应度函数值，再通过选择、交叉、变异等遗传操作，在特征空间进行搜索；用户通过给出适应度函数值，来评价搜索结果与用户主观空间或心理空间的相似度，并将人的主观情感融入到进化过程，从而实现了主观心理空间和客观特征空间的映射。

用IGA建立的模型基本上符合实际调查情况，用户的满意度在80%左右，比较令人满意。同时自主式GA的引入更增加了系统的自学习能力，缓解了用户的疲劳程度。但是，人类心理是个复杂的大系统，心理活动普遍存在模糊性、混沌性，如何把握其非线性的特征，建立更加准确的心理模型，是我们进一步要做的工作。