基于免疫协同进化的多Agent辅助浏览系统研究

李国庆, 鄢靖丰

（许昌学院计算机科学与技术学院,河南许昌 461000）

0 引言

随着网络技术的飞速发展,人们越来越习惯于借助网络媒介工作和学习。不同用户使用浏览器访问的数据大都有用户自己的偏好。用户长时间使用浏览器,会在Web服务器中积累大量的用户访问数据,通过对这些数据进行采集和分析,就可以获得用户的浏览兴趣和浏览习惯,从而获得用户上网的真实意图。将免疫协同进化机制应用于Web服务的自动发现与合成是一种新的方法,由Agent来完成用户的要求。

虽然Web服务的发现与合成已经很成功的使用了Agent[1],但在Web服务的管理过程中,如何向用户提供主动的服务,以及数量众多的Agent的产生、通信、消亡如何管理还没有成熟的方法。这将是今后互联网发展的主要瓶颈。对于今后Web的服务动态管理的发展趋势,HaiZhuge[2]总结了主要特征:自动合成策略;服务访问的分布性、自扩展性;服务变化自适应以及对服务合成自调整性等。遗传进化与人工免疫协同进化都是模拟生物进化的算法,但是基于免疫协同的进化机制更加适合处理那些复杂的动态环境优化问题。虽然遗传进化算法可以使种群较快速收敛并获得解,但也会失去种群的多样性,人工免疫协同进化机制则在多样性维持能力方面取得了较好的效果。Gasper等最先尝试将人工免疫系统（SAIS）用于动态优化[3],人工免疫算法设置了两种自适应变化的抗体适应度评价策略,实验结果表明人工免疫算法在鲁棒性与收敛速度方面比遗传算法要好。但是,由于免疫机理的繁复性,无论在模型建立还是算法设计等方面对免疫现象的描述都还不完善[4]。由于多Agent系统在求解复杂分布问题时的高效性,将人工免疫网络与多Agent结合,利用多Agent的现有成果,为构建基于免疫协同的个性化浏览系统提供思路。

文中将人工免疫协同进化机制与多Agent系统（Multi-Agent System,MAS）相结合引入Web服务。在多A-gent系统中,模拟生物免疫中的抗体间的促进和抑制关系,采集和分析用户的兴趣爱好,用户的兴趣爱好间既有一定的排斥性,又有相互协作的关系,基于免疫调节的思想,免疫协同把单个Agent个体看作一个抗体,把网络资源看作抗原,引入亲和度调节机制,设计抗体适应度方案,对现有兴趣模型中的Agent个体进行进化,并由进化后的个体组成新的兴趣模型,实现抗体间促进和抑制的免疫调节作用关系[3],为用户提供满足需求的信息。

1 免疫协同进化的多Agent Web客户端模型

多Agent的免疫协同进化原理如图1所示。其中抗原代表所有的网络资源,抗体对应用户的兴趣爱好、浏览偏好。Agent通过以下过程选择抗原:

（1）用户需要使用个人账号登陆浏览器,Web服务器根据用户以往的使用记录,从兴趣库中提取用户兴趣项组成候选解。经过多次迭代运行更新抗体集合和兴趣库。每次迭代时根据抗体和抗原之间的匹配程度计算各自的亲和度;

（2）克隆增殖。其目的是根据用户的浏览行为挖掘出用户的兴趣变化。用户经常浏览和检索的内容其兴趣亲和度增加,反之减少。并利用免疫协同进化机制将兴趣项在多Agent之间克隆。

（3）变异。多Agent在搜索用户的兴趣项过程中,可能会限于局部最优,通过模拟免疫系统的变异,可以使Agent在更大范围内搜索最优解。

（4）基因库进化。选取亲和度值高的兴趣作为成熟抗体,删除亲和度值低的其它抗体,通过兴趣库更新的方式反馈回兴趣基因库,以期提高兴趣基因库的性能。

单个Agent所能代表的用户的兴趣比较有限,多个Agent采用协商机制就可以解决单个Agent的问题,以共同完成用户多个兴趣的检索任务,显现出智能的系统行为。在协商过程中,每一个Agent都试图达到自己的目标或目的,当出现冲突时,通过协同进化或寻求其他的解决办法来达成一致的意见[3]。

2 免疫协同进化的多Agent Web客户端设计

图1 多Agent的免疫协同进化原理图

2.1 用户兴趣模型

用户兴趣模型包括用户账号、用户兴趣项、用户兴趣项亲和度及更新日期等属性。兴趣模型使用二维表的结构。

对不同的用户使用用户账号进行区分,每个用户使用密码登陆浏览器;兴趣项用于表示用户的兴趣爱好和浏览习惯,可以包含表示相应兴趣的关键字,用于检索资源,一个兴趣项可以有多个关键字;亲和度用来表示用户对相应兴趣项的关注程度,亲和度越高,表示该类资源对用户越重要;日期时间用于记录最近一次更新兴趣项、亲和度等信息的时间,用户注册账号是日期为注册时间,兴趣项和亲和度等均为空,系统根据用户之后的浏览习惯分析用户的兴趣项和亲和度,然后对用户兴趣项等进行更改。每次登陆系统,用户兴趣模型都将被更新。

2.2 初始化兴趣模型

当用户第一次使用浏览器时需要注册,系统会给用户分配唯一的账号,并初始状态兴趣项、关键词、亲和度等内容为空或者0。用户使用账号登陆浏览器时,Agent会主动记录并分析用户的浏览和检索操作,并对用户兴趣表进行初始设置。提取用户的兴趣项、检索关键词等信息内容,并设置亲和度,以此作为用户以后使用账号登陆浏览器时的初值。但是用户兴趣项要受到数量的限制。当用户以后再次登陆浏览器时,协同Agent会根据用户的兴趣亲和度匹配相应的网络资源推荐给用户。亲和度越高,资源越接近用户的需要。

2.3 动态更新兴趣模型

用户使用浏览器登陆时,系统会根据用户兴趣表中的兴趣的亲和度反馈相应的信息,并根据信息主动检索用户需要的资源推荐给用户,从而可以节省大量的时间。用户如果浏览了系统推荐的相关资源,则相应的兴趣项的亲和度会增加,如果用户访问了系统没有推荐的资源,说明用户的兴趣可能发生了变化,无论哪种情况,用户兴趣模型都将被更新,通过免疫协同进化修改已有兴趣项的亲和度、删除长时间没有关注的兴趣项、加入最近的兴趣项。基于免疫协同进化的多Agent浏览系统通过采样分析用户的访问数据来总结用户的兴趣,实现自主学习,自动更新。下面提出一种计算用户兴趣亲和度的方法。

用户经常浏览的内容就是用户主要的兴趣,相应亲和度值应增加;长时间不访问某一兴趣项,说明相关内容用户已不再关注,相应兴趣项亲和度应减少,当小于某一设定值时则应删除相应兴趣项并使用新的兴趣项替换。用户兴趣项亲和度Di与用户使用系统的浏览时间Hi、用户检索次数Si、登陆系统次数 Ti等相关。系统对该兴趣项的亲和度Di设计公式如下:

公式的设计使计算出的用户兴趣项的兴趣度Di在区间[0,1],当Di越接近1,表明用户对该项兴趣投入时间越多。

2.4 根据兴趣模型过滤信息

在选择最优资源时,Agent首先把兴趣项、亲和度等内容发送给服务器,查询相应的资源与历史记录的相关程度,将相似度超过一定阈值的资源推荐给用户。资源与用户兴趣相关度的计算公式如下:

其中:Di表示用户兴趣项i的亲和度,Ti表示兴趣项i在资源中的重要程度（可以用兴趣项在资源中出现的词频或者次数表示）。相似度越高,资源对用户的可用性越高。

3 系统设计

3.1 系统实现

系统开发利用Java语言设计实现。Java语言是一种跨平台,适合于分布式计算环境的面向对象的程序编辑语言,具有可靠、安全、平台无关、可移植、高性能、多线程、动态性等特点,用Java编程比较容易实现多Agent间的通讯及功能模块的编程。兴趣模型的属性课操作被设计为相应的类,基于免疫协同进化的生物功能也设计在其中。系统利用自动网页搜集程序（Robot）先在网络搜寻所有资源,再利用用户兴趣模型将搜寻到的信息进行分类整理,并术建立相应的索引,当用户使用浏览系统时,系统根据用户兴趣模型,参考用户的兴趣项和亲和度等信息,通过智能检索将检索结果数据过滤排序并推荐给用户。系统结构图如图2所示。

图2 浏览系统结构图

3.2 实验仿真

实验仿真采用美国德保罗大学网站的“在线资源”数据集进行处理。先对数据进行清洗,然后去除支持度大于80%的记录以及会话长度小于4的记录。最后把剩余的数据分为训练集和测试集两部分,训练集trainingl0000条记录,测试集test 1623条记录。测试所采用的环境为Intel（R）Xeon（R）3.47GHz,内存4G。从推荐系统的准确率、召回率和响应时间3个方面对系统进行评测。

（1）召回率（Recall,R）:召回率是待推荐页面与被推荐页面的比率。

其中Recommend表示测试集页面中系统主动推荐给用户并被用户访问的页面数量,Miss表示被过滤掉的页面数量。

（2）准确率（Precision）表示系统推荐的页面推荐成功的比率:

False表示测试集中系统虽然推荐但是用户没有访问的页面数量。

在现实生活中很难对召回率和准确率这两个指标进行平衡,如果推荐的页面数量增加,则 Recall值将会增加,而Precision值却减少。然而召回率和推荐精度都很重要。故而综合考虑这两方面是比较恰当的,指标R通过设定采用相同的权重将召回率和准确率结合起来,在二者找到最佳的平衡。

（3）响应时间结果分析

用户通过推荐系统访问Web服务器,与用户直接访问Web服务器的延时差别主要体现为推荐系统与Web服务器之间信息传递和推荐系统生成信息的时间。前者和具体的网络传输速度相关,不易于定量分析,然而推荐系统生成推荐信息的时间是可以把握的。推荐系统生成推荐信息的时间正是推荐算法所花费的时间。系统的平均推荐时间如图4所示。

图3 准确率仿真结果

图4 系统的平均推荐时间

通过分析实验结果可以看出,提出的基于免疫协同进化的多Agent技术实现Web的个性化服务,无论是从推荐时间还是推荐的准确度上,都有较大的改进。通过MAS技术优势,可以将大量计算在离线状态下完成,对比实验说明该系统模型是有效的。同时系统通过用户反馈Agent可不断收集更多的推荐和评价信息,随着用户使用时间的增加推荐质量会逐渐提高。

4 结束语

讨论了基于免疫协同进化的多Agent技术实现Web的个性化服务,智能Agent通过学习自动建立用户兴趣模型,并以此模型通过模拟生物的免疫系统来实现个性化的服务:对用户搜索的信息进行过滤,提高搜索的精确度,主动向用户推荐信息,利用用户反馈Agent不断收集更多用户推荐和评价信息,实现Agent自学习性,随着用户使用时间的增加,推荐质量会逐渐提高。对比实验证实本系统模型的有效性。

[1] Sycara K,Paolucci M,Soudry J,et al.Dynamic Discovery and Coordination of Agent-Based Semantic Web Services[J].IEEE Internet Computing,2004,8（3）:66-73.

[2] Hai Zhuge.The Future Interconnection Environment[J].IEEE Computer,2005,38（4）:27-33.

[3] GRSPAR A,COLLARD P.Two models of immunization for time dependent optimization[C]//IEEE International Conference on Systems,Man and Cybernetlcs,New York:IEEE,2000,1:113-118.

[4] 焦李成,杜海峰,刘芳,等.免疫优化算法、学习与识别[M].北京:科学出版社,2007:316-325.

[5] 张泊平,王睿.基于网页结构相关性的个性化推荐技术研究[J].许昌学院学报,2007,26（5）90-95.