一种基于NSGA-II的协同过滤推荐算法

支配排序，只有最优的前N个个体会被选中，其他的将被淘汰。

然后再次迭代整个过程，直到达到最大迭代次数后退出循环，取其前最优的N个作为最终解。

3 NSGA-П算法在推荐算法中的应用

3.1 权重系数的初始化

R₁'、R₂'和R₃'是三种不同的推荐系统算法ItemCF、UserCF和MF得出的三组推荐列表。三组列表推荐方式不同，得出多目标函数值也不同。为了得出多目标均较优的推荐结果，利用线性加权的方法可得到新的预测评分R''如公式7所示：

(7)

其中，λ1, λ2和λ3分别为各数据集所代表算法的权重系数，并且λ1+λ2+λ3=1。

根据λ1和λ2的值，得出对应的推荐列表，计算每组权重系数对应的各目标函数值。

3.2 非支配和拥挤距离排序

将当前权重系数种群进行非支配排序，每个权重系数被分配到各个等级中，得到等级变量。然后计算同一等级内，根据每组权重系数的多目标函数值，计算拥挤距离，根据结果进行排序。由此产生了整个种群的排序结果。

判断当前种群数量是否超过额定种群数量N，如是，则选取排序列表中前N个作为本代的结果。

3.3 子代权重系数的产生

在遗传算法中，两个父母代可以通过基因重组和遗传变异产生新的子代。包括以下三个基本遗传算子：选择、交叉和变异[7]。

1、选择。随机选取两组不同的权重系数作为父代和母代，λ_p11λ_p12和λ_p21λ_p22。

2、交叉。设置交叉系数为1，父代和母代在子代中所占的比例相同。故可定义产生的子代权重系数为：

(8)

(9)

3、变异。实际中，遗传变异是个小概率事件，故考虑设置变异系数。每当要产生子代前，随机产生一个0到1之间的数，若该数小于变异系数，则发生遗传变异，否则跳过此部分。遗传变异的过程产生的新权重系数为：

(10)

(11)

产生新的权重系数后，再进行排序和更新种群，筛选出M 个最优个体。如此反复进行迭代，不断产生新的权重系数和种群。

4 实验设计与实验结果

4.1 评测指标

本文中选择了精确度和召回率作为评价的主要标准。

令R(u)是根据用户在训练集上的行为给用户做出的推荐列表，而T(u)是用户在测试集上的行为列表。

那么，推荐结果的召回率定义为：

(12)

推荐结果的精确度定义为：

(13)

4.2 实验设计

(1) 实验数据

本文中利用的数据是MovieLens数据集，用户对自己看过的电影进行评分，分值为1～5，该数据是943个独立用户对1682部电影作的100000次评分的数据，其中每个用户至少对20个物品进行了评分^[6]。

(2) 算法实现

全文的算法设计包括以下三个步骤：

1、基础算法的实现;

2、多目标遗传算法—NSGA-П的实现;

3、综合算法的整体实现。

1、基础算法的实现

ItemCF的实现：数据集的读入、各物品之间的相似度的计算以及最终推荐列表的获得。其中，在获取推荐列表时，选取N个与目标物品最相似的物品的过程中，N的值并不固定。取值规则为，从5-20中选取使得其精确度与召回率最高的那个值作为N。

UserCF的实现：数据集的读入、各用户之间的相似度的计算以及最终推荐列表的获得。其中，在获取推荐列表时，选取N个与目标用户最相似的用户的过程中，N的值并不固定。取值规则为，从5-20中选取使得其精确度与召回率最高的那个值作为N。

MF的实现：实现过程包括：数据集的读入、矩阵P与Q的初始化，各用户负样本的设定。对数据集进行训练迭代一定的步数，当误差达到局部最小或者迭代步数达到设置时退出训练，利用得到的矩阵P与Q获取最终的推荐列表。

2 多目标遗传算法的实现

多目标遗传算法的实现包括以下几个部分：

(1)随机产生100组权重系数λ₁和λ₂。

(2)读入基础算法的三组推荐表单，和

(3)编写目标函数和。

(4)NSGA-П主函数部分, 并在其中根据加权后的集合获取最终的推荐表单。

(5)输出10组最好的权重系数λ1和λ2，以及对应的目标函数值。

3 综合算法的整体实现

对以上五个数据集随机初始化100个权重系数，迭代10次，种群规模为10，交叉概率设置为1，变异概率设置为0.1。经过交叉和变异，得到五个数据集的权重系数，每个数据集有10组最优的λ₁和λ₂。对这五个数据集中的权重系数进行加权取平均值，得到最终的10组λ₁和λ₂。最后在u1.test，u2.test，u3.test，u4.test，u5.test上重新测试，每组得到10组Recall和Precision值。

4.3 实验结果

将基本算法得到的推荐表单代入计算程序，得到Recall和Precision值。表1为u1的实现结果。

分别对五组数据集，各随机初始化100组权重系数，通过NSGA-П的交叉变异迭代10次，得到最终的10组权重系数。表2为ItemCF、UserCF和MF在数据集u1上得到的权重系数表。

从表2可知，多目标最优化的ItemCF、UserCF和MF分布，MF的权重值最