改进小生境遗传算法在元搜索引擎调度优化中的研究

《改进小生境遗传算法在元搜索引擎调度优化中的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据2008年7月重庆师范大学学报(自然科学版)July2008第25卷第3期Joumal0fChongqingNornlalUniversity(NaturalScience)V01．25No．3改进小生境遗传算法在元搜索引擎调度优化中的研究+刘双印，徐龙琴。沈玉利(广东海洋大学信息学院，广东湛江524088)摘要：针对多独立搜索引擎组合调度时查询精度、查询完全度和响应时问不理想等问题，结合元搜索引擎调度特点对多独立搜索引擎组合调度进行动态优化。文中借鉴小生境思想，将小生境技术与遗传算法相结合，提出了一种多目标组合优化调度的改进小生境遗传算法。该算法使每个个体在其小生境内进行局部

2、寻优操作，保证了群体的多样性，增强了局部搜索能力，抑制了种群的早熟现象。在多个子目标不能同时达到最优时，采用个体综合适应度对各个目标函数的适应度进行加权，来协调优化各搜索引擎的组合，找到搜索引擎组合调度序列的非劣解。仿真实验结果表明该算法提高了元搜索引擎的调度效率，在查询精度和计算速度上均优于常用的查询优化技术。关键词：多目标优化；最优解；小生境；遗传算法中图分类号：TP311文献标识码：A文章编号：1672-6693(2008)03-0046-05面对众多用户的搜索请求，元搜索引擎本身不提供搜索信息的数据库，而是将其请求分发到实际的独立搜索引擎上，对独立搜索引擎返回的结果进行分析处理

3、后再将搜索结果返回给用户。元搜索将整个搜索空间分为若干不同的领域，对于不同领域，各独立搜索引擎的性能有所不同，元搜索引擎根据用户的查询请求，调度若干个独立搜索引擎的组合来响应用户请求。对于任一领域的查询请求，元搜索引擎的目标是使得搜索该领域的信息性能最佳，这就要求所分派调度的独立搜索引擎组合是一个优化组合，最简单的调度方法就是通过人工模拟的方法来测试不同搜索引擎的组合，然后指定某一固定搜索引擎组合为某一领域的请求服务。但独立搜索引擎的数量、服务功能、性能也都在不断地变化，这种简单的搜索引擎调度策略不能反映系统的变化，特别是在查询精度、查询完全度和响应时间等综合方面查询效果不理想。近年来

4、，广泛应用于各种优化技术的全局优化搜索算法——遗传算法(GeneticAlgorithm，GA)⋯被引入到信息检索领域，从而为信息查询优化技术提供了新的解决途径。尽管GA在信息检索中的应用取得了一定的效果旧J，但存在局部搜索能力不强、易陷入局部最优和早熟等缺陷，使得传统的GA在进行查询优化时效果不理想。许多文献针对遗传算法的缺陷提出了各种改进方法，如引入爬山法、模拟退火法旧J、自适应遗传算法、实数编码遗传算法p圳，并获得了性能上的一定改善。与其它优化的遗传算法不同，本文结合元搜索引擎查询调度的特点，引入小生境的思想，提出了一种基于小生境的改进遗传算法，通过构造遗传算法的操作算子，有效提

5、高局部搜索能力、克服早熟缺陷、加快收敛速度，以解决动态优化多独立搜索引擎组合调度问题。经仿真验证，该算法在查询精度和计算速度上均优于常用的查询优化技术。1小生境技术原理在自然界中，“物以类聚，人以群分”的小生境现象普遍存在。生物总是倾向于与自己特性、形状相类似的生物生活在一起，交配繁殖后代。在生物学中，把某种特定环境及其在此环境中生存的组织称为小生境”J。小生境的形成在生物学上是有积极意义的，它为新物种的形成提供了可能性，在小生境形成初期，小生境中的物种的基因常常是不同的，由于多个小生境间相对隔离，缺少必要的基因交流，使·收稿日期：200r7一ll—09修回日期：2008—02—20．

6、资助项目：广东省粤港关键领域重点突破项目(N0．2006A2500r7002)；广东省自然科学基金项目(No．70lOll6)作者简介：刘双印(1978-)，男，讲师，硕士，研究方向为人工智能、分布式计算、智能信息系统等。万方数据第3期刘双印，等：改进小生境遗传算法在元搜索引擎调度优化中的研究47得这种基因差异得以保留。各小生境中生物的变异是随机发生的，因而通常有着不同的变异方向，这种变异的差异使物种间的基因差异不断扩大。由于地理位置和自然环境的不同，自然选择的方向和压力也各不相同．这一差异导致了物种间基因组成产生更大的差异，于是各物种向各自的方向发展进化，正因为如此自然界中生物保持近

7、乎于无限多样性，使其充满了生机和活力旧1。在具体的工程应用，小生境技术演变为：将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群以及不同种群之间通过杂交、变异产生新一代个体群，同时采用预选择机制、排挤机制或共享机制完成选择操作。也就是说让个体在一个特定的生存环境中进化，形成多个小生境，最终达到小生境内的峰值，从而找到全局最优解。受此启发，近年来人们将小生境现象引入到遗传算法中，实践证明，这一技术