一种改进的主题网络蜘蛛搜索算法.kdh
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００７，４３（１０）
１引言
随着Ｉｎｔｅｒｎｅｔ的快速发展，人们获得信息资源的有效工具─搜索引擎变的越来越重要。人们能否有效地获得自己所需的信息在很大程度上取决于搜索引擎的性能。而网络蜘蛛（ｗｅｂｃｒａｗｌｅｒ）在搜索引擎中占据着重要的地位，网络蜘蛛的搜索策略是搜索引擎的核心技术。近几年来出现了许多著名的搜索算法，如早期的Ｂｒｅａｄｔｈ－Ｆｉｒｓｔ算法和Ｄｅｐｔｈ－Ｆｉｒｓｔ算法，后来出现的ＳｈａｒｋＳｅａｒｃｈ算法（ＦｉｓｈＳｅａｒｃｈ算法的变体），还有基于链接结构的ＰａｇｅＲａｎｋ算法和ＨＩＴＳ算法以及基于网页内容的Ｂｅｓｔ－Ｆｉｒｓｔ［１］算法等。
主题网络蜘蛛是近几年才兴起的研究热点，它是针对某一专门领域的信息进行搜索，用于专业搜索引擎系统中，满足特定人群的需要。随着人们对信息查询要求的不断提高，专业领域化的搜索引擎正日益得到广大研究者的重视。系统对主题网络蜘蛛的要求更高，其搜索策略更加复杂，往往需要引入机械学习算法使搜索具有一定的适应性和进化性，要尽可能地使所搜索的网页与主题之间具有很高的相关度。
目前主题网络蜘蛛搜索策略的主要困难在于：网络蜘蛛对ｗｅｂ搜索空间中信息资源的整体分布总是未知的，不能很好地预测爬行方向。虽然目前出现的“启发式”搜索策略可以借助某些领域知识对信息资源的分布情况做出某种程度的估计，据此推断出大致的搜索方向，但是这种方法的计算量大、时空复杂度高，目前也没有找到很合适的学习算法来指导训练过程。
本文经过对几种主题网络蜘蛛的研究比较，利用Ｂｅｓｔ－Ｆｉｒｓｔ算法的优越性，在Ｂｅｓｔ－Ｆｉｒｓｔ算法的基础上引入并行分布式计算的思想对Ｂｅｓｔ－Ｆｉｒｓｔ算法进行了改进，提出了ＢＳ－ＢＳ算法。该算法具有在全局范围内获到最优解的功能，改善了Ｂｅｓｔ－Ｆｉｒｓｔ算法的贪婪特性。
２对现有网络蜘蛛的性能评价
把获得的与主题相关的页面称为“回报”，将可以通过直接计算相关度得到的页面称为“立即回报”，将网络蜘蛛不能直接获得必须通过间接计算才能得到的页面称为“未来回报”。
文献［２］中采用了一种性能评价策略主要对Ｂｅｓｔ－Ｆｉｒｓｔ算法、Ｂｒｅａｔｈ－Ｆｉｒｓｔ算法、ＳｈａｒｋＳｅａｒｃｈ算法和ＩｎｆｏＳｐｉｄｅｒｓ［３］这几种算法进行了全方位的评价。评价策略的系统框架如图１所示。
这里仅针对这几种搜索策略的“召回率”进行比较，结果如图２所示。
对这几种算法评价过程中将存放链接的最大缓冲区ＭＡＸ＿ＢＵＦＦＥＲ设为２５６。从图２中比较可以得出Ｂｅｓｔ－Ｆｉｒｓｔ算法在这几种算法中表现的性能最优，其次Ｉｎｆｏｓｐｉｄｅｒｓ算法，Ｂｒｅａｔｈ－Ｆｉｒｓｔ算法得到的“召回率”最低。
一种改进的主题网络蜘蛛搜索算法
林海霞，原福永，陈金森，刘俊峰
ＬＩＮＨａｉ－ｘａｉ，ＹＵＡＮＦｕ－ｙｏｎｇ，ＣＨＥＮＪｉｎ－ｓｅｎ，ＬＩＵＪｕｎ－ｆｅｎｇ
燕山大学信息科学与工程学院，河北秦皇岛０６６００４
ＩｎｓｔｉｔｕｔｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＹａｎｓｈａｎＵｎｉｖｅｒｓｉｔｙ，Ｑｉｎｈｕａｎｇｄａｏ，Ｈｅｂｅｉ０６６００４，Ｃｈｉｎａ
Ｅ－ｍａｉｌ：ｌｉｎｈａｉｇｉｒｌ＠ｙａｈｏｏ．ｃｏｍ．ｃｎ
ＬＩＮＨａｉ－ｘａｉ，ＹＵＡＮＦｕ－ｙｏｎｇ，ＣＨＥＮＪｉｎ－ｓｅｎ，ｅｔａｌ．Ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍａｂｏｕｔｔｏｐｉｃｗｅｂｃｒａｗｌｅｒ’ｓｓｅａｒｃｈｓｔｒａｔｅｇｙ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１０）：１７４－１７６．
Ａｂｓｔｒａｃｔ：Ｔｏｐｉｃｗｅｂｃｒａｗｌｅｒｓｅａｒｃｈｓｔｒａｔｅｇｙｉｓｔｈｅｃｏｒｅｏｆｐｒｏｆｅｓｓｉｏｎａｌｓｅａｒｃｈｅｎｇｉｎｅｔｅｃｈｎｏｌｏｇｙ．Ｈｏｗｅｖｅｒ，ｔｈｅｃｕｒｒｅｎｔｔｏｐｉｃｓｅａｒｃｈａｌｇｏｒｉｔｈｍｓａｌｗａｙｓｅｘｉｓｔｌａｒｇｅｇｒｅｅｄｙ．Ｉｔｉｓｄｉｆｆｉｃｕｌｔｔｏｆｉｎｄｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｉｎｔｈｅｏｖｅｒａｌｌｓｉｔｕａｔｉｏｎ．ＴｈｒｏｕｇｈｃｏｍｐａｒａｔｉｖｅａｎａｌｙｓｉｓｆｉｎｄｔｈａｔｄｅｓｐｉｔｅＢｅｓｔ－Ｆｉｒｓｔａｌｇｏｒｉｔｈｍｈａｖｉｎｇｓｈｏｒｔｃｏｍｉｎｇｓ，ｂｕｔｉｔｓｐｅｒｆｏｒｍａｎｃｅｉｓｏｐｔｉｍａｌｉｎｓｅｖｅｒａｌａｌｇｏｒｉｔｈｍｓ．ＳｏｂａｓｅｄｏｎＢｅｓｔ－ＦｉｒｓｔａｌｇｏｒｉｔｈｍｓｉｔｒａｉｓｅｓＢＳ－ＢＳａｌｇｏｒｉｔｈｍｓ．ＴｈｅｎｉｔｅｖａｌｕａｔｅｓＢＳ－ＢＳａｌｇｏｒｉｔｈｍ．Ａｎｄｆｉｎｄｔｈａｔｎｏｔｏｎｌｙ＂ｒｅｃａｌｌｒａｔｅ＂ｈａｓｉｍｐｒｏｖｅｄ，ｂｕｔｃａｎｇｅｔｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓｉｎｔｈｅｏｖｅｒａｌｌｓｉｔｕａｔｉｏｎ．
Ｋｅｙｗｏｒｄｓ：ｔｏｐｉｃｗｅｂｃｒａｗｌｅｒ；Ｂｅｓｔ－Ｆｉｒｓｔａｌｇｏｒｉｔｈｍ；ｒｅｃａｌｌｒａｔｉｏ
摘要：主题网络蜘蛛搜索策略是专业搜索引擎的核心技术。但是目前的主题搜索算法往往存在很大贪婪性，难以在全局范围内找到最优解。通过比较分析发现Ｂｅｓｔ－Ｆｉｒｓｔ算法虽然有它的不足，但是它在几种算法中表现的性能最优。故以Ｂｅｓｔ－Ｆｉｒｓｔ算法为基础，提出了ＢＳ－ＢＳ算法。对ＢＳ－ＢＳ算法进行性能评价，发现应用此算法搜索不但“召回率”有所提高，还能在一定程度上找到全局范围内的最优解。
关键词：主题网络蜘蛛；Ｂｅｓｔ－Ｆｉｒｓｔ算法；召回率
文章编号：１００２－８３３１（２００７）１０－０１７４－０３文献标识码：Ａ中图分类号：ＴＰ３９１
作者简介：林海霞（１９７８－），女，硕士研究生，主要研究方向：计算机网络信息检索技术、网络缓存系统、数据库应用系统；原福永（１９５８－），男，副教授，系主任，研究生导师，主要研究方向：计算机网络信息检索技术、网络缓存系统、数据库应用系统。
１７４
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００７，４３（
１０
）本文利用文献［２］中的网络蜘蛛性能评价系统对Ｂｅｓｔ－Ｆｉｒｓｔ算法进行了更为深入地研究。针对其不足之处作了相应的改进。
３
算法分析与改进
３．１Ｂｅｓｔ－Ｆｉｒｓｔ算法简单介绍
Ｂｅｓｔ－Ｆｉｒｓｔ算法：Ｂｅｓｔ－Ｆｉｒｓｔ算法是由Ｃｈｏ和Ｈｅｒｓｏｖｉｃｉ等人
于１９９８年研究提出的，后人在此基础上也作了很多改进。其基本思想是构建一个ＵＲＬ链接列表，然后按照某种评价选择策略选择出最好的链接进行访问。不同的Ｂｅｓｔ－Ｆｉｒｓｔ算法有着不同的选择链接的方法。有基于页面内容评价的方法和基于链接结构评价的方法。通常最常用的是基于页面内容的评价方法［４］。采用的是计算网页文档内容与主题关键字之间相似度的方法，相似度的计算通常采用下列公式：
ｓｉｍ（ｑ，ｐ）＝
ｋ∈ｑ∩ｐ
#ｗ
ｋｑ
＊ｗｋｐ
（
ｋ∈ｐ
#ｗ
２ｋｐ
）＊（
ｋ∈ｑ
#ｗ
２ｋｑ
）
$
（１）
其中ｑ表示主题，ｐ表示网页文档，ｗｋｐ代表主题词ｋ在文档ｐ中的权重值，一般采用ｔｆ－ｉｄｆ方法计算，ｗｋｑ为关键词的权重。计算所得结果即为网页内容与主题的相关度。
３．２Ｂｅｓｔ－Ｆｉｒｓｔ算法分析
虽然Ｂｅｓｔ－Ｆｉｒｓｔ算法在这几种算法中表现出了最优的性
能，但从实验中可以看出算法本身也存在着一定的缺陷，它具有很大的贪婪性，容易过早的陷入Ｗｅｂ搜索空间中局部最优子空间的陷阱。在搜索的网页范围达到１０００页时，算法已经开始收敛。也就是说Ｂｅｓｔ－Ｆｉｒｓｔ算法只适用于小范围内主题的搜索。算法的贪婪性体现在它只选择本身与主题相关度值很大的链接，而忽略掉某些蕴涵很大远期价值的链接。这些蕴涵远期价值很大的链接本身与主题内容的相关度值并不高，但是通过这些链接节点可能搜索到大量的与主题相关的网页。搜索策略的这种贪婪性使得搜索在还没有扩大到一定范围时就已经开始收敛了。故搜索难以得到全局范围内的最优解，只能找到局部范围内的最优解［５－７］。
３．３ＢＦ－ＢＦ算法的提出
这里将直接可以得到的主题相关链接称为“立即回报”，将经过若干与主题无关链接之后才能获得的主题相关链接称为“未来回报”。在搜索过程中，对立即回报的预测值，称为“立即回报”价值；对未来回报的预测值，称为“未来回报”价值。“立即回报”价值大的链接，其“综合价值”不一定大。因为有些链接节点尽管与主题的相关度不高，也就是说“立即回报”价值很小，但是通过此链接节点可以找到更多的与主题相关的链接，这说明它的“未来回报”价值很大。所以某些链接尽管没有立即回报价值，但它们依然具有很大的“回报”值。网络蜘蛛在搜索时如何权衡“立即回报”价值和“未来回报”的关系，获得“综合价值”最大的链接，一直是网络蜘蛛搜索策略研究的热点［７］。Ｂｅｓｔ－Ｆｉｒｓｔ算法恰恰是一种只注重“立即回报”价值，忽略“未来回报”价值的贪婪算法。
图３为网络蜘蛛搜索过程示意图，ｐ０，ｐ２，ｄ０，ｄ１，ｄ２，ｄ３，ｄ４
为主题相关页面，ｐ１为无关页面，假设网络蜘蛛从ｐ０开始搜索，一般Ｂｅｓｔ－Ｆｉｒｓｔ算法的思想是：如果经过计算发现ｐ１为无关页面，而ｄ０为相关页面，就会将ｐ１这个链接节点忽略，沿着ｌ０这
条路径搜索。这样就会导致ｐ２，ｄ１，ｄ２，ｄ３，ｄ４这些潜在的相关页面也被网络蜘蛛所忽略，从而导致搜索的整体“
回报”不高，不能使网络蜘蛛得到全局范围内的最优解。本文所提出的ＢＳ－ＢＳ算法的基本思想是：虽然网络蜘蛛发现ｐ１为无关链接节点，但它暂时也不会放弃这个链接，它会继续验证ｐ１的邻节点是否存在与主题非常相关的页面。系统设定一个参数Ｄ，Ｄ是网络蜘蛛在遇到无关链接时所需最大的爬行深度。如果网络蜘蛛在爬行深度Ｄ步以后仍然没有发现相关页面，才将ｐ１这个无关链接舍弃。但是如果网络蜘蛛经过ｌ２，ｌ３，ｌ４，ｌ５，ｌ６，这几条路径
林海霞，原福永，陈金森，等：一种改进的主题网络蜘蛛搜索算法１７５
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００７，４３（１０）
的搜索后都能找到主题相关页面，这说明ｐ
１
这个链接虽然“立
即回报”价值很小，但是它蕴涵着很大的远期回报价值。故ＢＳ－
ＢＳ算法会很注重它的“未来回报”价值。这时，ＢＳ－ＢＳ算法就会
并发出另一个线程将ｐ
１
作为初始节点开始搜索。
ＢＳ－ＢＳ算法部分数据结构及参数设定：
（１）构建一个存放候选链接的ＵＲＬ列表，用于存放未被访
问但需要访问的链接。
（２）构建一个存放没有回报价值的链接的ＵＲＬ列表，这些
链接节点将被网络蜘蛛视为无用链接而被舍弃。
（３）设定相似度阈值ｒ
１
，用于衡量“立即回报”价值。如果
“立即回报”价值大于ｒ
１
，就将链接的ＵＲＬ存入候选链接列表。
如果“立即回报”价值小于ｒ
１
，就计算此链接的“未来回报”价值。
（４）设定相似度阈值ｒ
２
，用于衡量“未来回报”价值。如果
“未来回报”价值大于ｒ
２
，算法就并发新的线程。如果“未来回
报”价值小于ｒ
２
，就将该链接舍弃。
（５）设定参数Ｄ，表示当链接的“立即回报”价值小于给定
阈值ｒ
１
时，网络蜘蛛在计算“未来回报”价值时所需要爬行的深度。
ＢＳ－ＢＳ算法过程描述：
（１）网络蜘蛛首先从一个“种子集”出发，选择其中的一个链接进行访问（“种子”链接由系统给定）。
（２）抽取所访问链接节点页面内容及超级链接。
（３）按照主题和网页文本的相似度公式计算每个链接节点的“立即回报”价值。
（４）判断所得的“立即回报”价值是否大于系统所给定阈值
ｒ
１
，如果大于给定阈值，就将该链接的ＵＲＬ地址加入到候选
ＵＲＬ地址列表中。如果所得的“立即回报”价值小于给定阈值ｒ
１
，就计算此链接的“未来回报”价值。
（５）如果经计算所得的“未来回报”价值大于系统所给定的
阈值ｒ
２
，系统就并发另一个线程从此链接节点开始重复执行以上各步。
（６）如果所得的“未来回报”价值小于所给定的阈值ｒ
２
，就视此链接节点为无用链接节点，将它列入被舍弃的ＵＲＬ列表。３．４“立即回报”价值和“未来回报”价值的计算方法ＢＳ－ＢＳ算法中相关度的计算选用公式（１）来计算主题与网页文本的相似度，用相似度值表示对“立即回报”价值的预测。
对“未来回报”价值预测的关键问题是参数Ｄ的设定。Ｄ值太小，算法的收敛速度不会得到明显的改善，算法的贪婪性依然很强，不能达到很好的效果。Ｄ值太大，会造成网络蜘蛛爬行的盲目性和计算资源的严重浪费，但结果可能没有任何意义。通过实验证明Ｄ＝３是一个比较理想的深度值。也就是说网络蜘蛛在遇到一个“立即回报”价值很小的链接后，会继续沿链接爬行，直到深度值大于３，如果此时仍然没有发现主题相关页面，就停止爬行，并将此链接节点放入被舍弃的ＵＲＬ列表中。４实验分析
本文将改进后的算法利用文献［２］中的性能评价系统进行了评价，实验结果仅给出了算法“召回率”曲线图，如图４所示。
从实验中可以看出ＢＳ－ＢＳ算法的召回率比单纯的Ｂｅｓｔ－Ｆｉｒｓｔ算法有所提高，并且搜索范围得到了扩大，解决了单纯Ｂｅｓｔ－Ｆｉｒｓｔ算法收敛速度过快的缺陷和算法贪婪性问题。ＢＳ－ＢＳ算法不但考虑了链接的“立即回报”价值，同时还考虑了链接的“未来回报”价值，能够在一定程度上获得全局范围内的最优解。
５小节与展望
本文通过对几种主要的网络蜘蛛搜索策略的比较研究，得出Ｂｅｓｔ－Ｆｉｒｓｔ算法具有很大的优越性。并分析了Ｂｅｓｔ－Ｆｉｒｓｔ算法的优越性和缺陷，利用Ｂｅｓｔ－Ｆｉｒｓｔ算法的基本思想引入并行分布式的计算方式提出了ＢＳ－ＢＳ算法。并利用文献［２］中给出的网络蜘蛛搜索策略性能评价系统对ＢＳ－ＢＳ算法进行了评价，实验结果证明ＢＳ－ＢＳ算法的“召回率”比单纯的Ｂｅｓｔ－Ｆｉｒｓｔ算法有了提高，并且此算法能够在一定程度上获得全局范围内的最优解，解决了搜索算法的贪婪性问题。
对ＢＳ－ＢＳ算法的研究还不算很成熟，下一步要做的工作是针对ＢＳ－ＢＳ算法获得页面的“精确度”作一定研究，使算法更加完善。（收稿日期：２００６年８月）
参考文献：
［１］ＣｈｏＪ，Ｇａｒｃｉａ－ＭｏｌｉｎａＨ，ＰａｇｅＬ．ＣｒａｗｌｉｎｇｔｈｒｏｕｇｈＵＲＬｏｒｄｅｒｉｎｇ［Ｊ］．ＣｏｍｐｕｔｅｒｓＮｅｔｗｏｒｋｓａｎｄＩＳＤＮＳｙｓｔｅｍｓ，１９９８，３０：１６１－１７２．
［２］ＳｒｉｎｉｖａｓａｎＰ，ＭｅｎｃｚｅｒＦ，ＰａｎｔＧ．Ａｇｅｎｅｒａｌｅｖａｌｕａｔｉｏｎｆｒａｍｅｗｏｒｋｆｏｒｔｏｐｉｃａｌｃｒａｗｌｅｒｓ．ＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ，２００５，８（３）：４１７－４４７．
［３］ＡｎｇｋａｗａｔｔａｎａｗｉｔＮ，ＲｕｎｇｓａｗａｎｇＡ．Ｌｅａｒｎａｂｌｅｔｏｐｉｃ－ｓｐｅｃｉｆｉｃＷｅｂｃｒａｗｌｅｒ［Ｊ］．ＭａｓｓｉｖｅＩｎｆｏｒｍａｔｉｏｎ＆ＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇ，２００５，２８（２）：９７－１１４．
［４］ＭｅｎｃｚｅｒＦ，ＰａｎｔＧ，ＳｒｉｎｉｖａｓａｎＰ．ＴｏｐｉｃＷｅｂｃｒａｗｌｅｒｓ：ｅｖａｌｕａｔｉｎｇａｄａｐ－ｔｉｖｅａｌｇｏｒｉｔｈｍ［Ｊ］．ＡＣＭＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｔｅｒｎｅｔＴｅｃｈｎｏｌｏｇｙ，２００４，４（４）：３７８－４１９．
［５］ＣｈｓｋｒａｂａｒｔｉＳ，ｖａｎｄｅｒＢｅｒｇＭ，ＤｏｍＢ．Ｆｏｃｕｓｅｄｃｒａｗｌｉｎｇ：ａｎｅｗａｐｐｒｏａｃｈｔｏｔｏｐｉｃ－ｓｐｅｃｉｆｉｃＷｅｂｒｅｓｏｕｒｃｅｄｉｓｃｏｖｅｒｙ［Ｊ］．ＣｏｍｐｕｔＮｅｔｗ，１９９９，（３１）：１１－１６．
［６］ＭｅｎｃｚｅｒＦ，ＢｅｌｅｗＲ．Ａｄａｐｔｉｖｅｒｅｔｒｉｅｖａｌａｇｅｎｔｓ：ＩｎｔｅｒｎａｌｉｚｉｎｇｌｏｃａｌｃｏｎｔｅｘｔａｎｄｓｃａｌｉｎｇｕｐｔｏｔｈｅＷｅｂ［Ｊ］．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，２０００，３９：２０３－２４２．
［７］ＰａｎｔＧ，ＳｒｉｎｉｖａｓａｍＰ，ＭｅｎｃｚｅｒＦ．Ｅｘｐｌｏｒａｔｉｏｎｖｅｒｓｕｓｅｘｐｌｏｉｔａｔｉｏｎｉｎｔｏｐｉｃｄｒｉｖｅｎｃｒａｗｌｅｒｓ［Ｃ／ＯＬ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＷＷＷ－０２ＷｏｒｋｓｈｏｐｏｎＷｅｂＤｙｎａｍｉｃｓ．ｈｔｔｐ
：／／ｗｗｗ．ｍｕｓｃａｔ．ｃｏｍ／？ｍａｒｔｉｎ／ｓｔｅｍ．ｈｔｍｌ．
１７６
禁忌搜索算法浅析
禁忌搜索算法浅析 摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。 关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索 1禁忌搜索算法概述 禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。 TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 2禁忌搜索算法的基本思想 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁
改进的粒子群优化算法
第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授．
主题搜索引擎的设计与实现
第四代搜索引擎—— 主题搜索引擎的设计与实现 Design and Implementation of Focused Search Engine, 4th Generation Search Engine 北京大学计算机科学技术系计算机软件专业 九七级学士毕业论文 指导教师：李晓明王建勇 作者：罗昶 学号：09708136 2001年6月
指导老师对论文工作的评语 “面向主题的搜索引擎”，是我们“天网”搜索引擎下一步发展的重要方向之一。罗昶同学的毕业论文，是这一新方向的良好开端。 论文从系统实现的角度，较全面的阐述了实现一个高质量主题搜索引擎系统的各个方面，着重分析了导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种搜集策略的运用，并提出了“主题度”的概念，用以衡量主题搜索引擎的质量，意在指明一个搜索引擎在一个主题下的主题度越高，则它越贴近这个主题，用户就越容易找到跟这个主题相关的资料。特别地，将上述认识用于实践中，高质量地完成了一个面向影视主题的搜索引擎系统，搜集了十多万影视信息，在影视信息方面提供着比“天网”通用搜索引擎更有效的服务；论文内容丰富，所涉及的工作量很大，且有较强的系统性，是一篇很有参考价值的论文，为“天网”的发展做出了贡献。 老师签名:__________
论文摘要 互联网上的信息每天都以指数量级的速度爆炸性增长，面对如此浩瀚的资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索引擎出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。 但是，随着信息多元化的增长，千篇一律的给所有用户提供同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、对硬件要求低，数据全面深入、更新及时的面向主题的搜索引擎。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜索引擎。 本文阐述了第四代搜索引擎天网主题搜索引擎的设计与实现，并着重分析了导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种搜集策略的运用。论文最后定义了独创的“主题度”来衡量主题搜索引擎的性能，一个搜索引擎在一个主题下的主题度越高，证明这个搜索引擎越贴近这个主题，用户就越容易找到跟这个主题相关的资料。有了“主题度”，就可以很容易的比较使用多种搜集策略以后的天网主题搜索引擎与原天网通用搜索引擎的差别，说明了前者在特定的主题下要比后者更准确贴切。 关键词：互联网、万维网、搜索引擎、数据发掘、主题搜索、主题度
面向搜索引擎的网站开发
面向搜索引擎的网站开发 搜索引擎只是网站上一个普通的访客，对网站的抓取方式、对网站/网页的价值判断，也都是从用户的角度出发的，任何对用户体验的改进，都是对搜索引擎改进。对搜索引擎的优化，同时也会让用户受益。 面向搜索引擎的网站建设，主要分为三个部分：如何更好的让搜索引擎收录网站中的内容、如何在搜索引擎中获得良好的排名、如何让用户从众多的搜索结果中点击你的网站。简单来说，就是收录、排序、展现。下面我们将从这三个方面分别介绍。 网站的可读性 搜索引擎通过一个叫做Baiduspider的程序抓取互联网上的网页，经过处理后建入索引中。目前Baiduspider只能读懂文本内容，flash、图片等非文本内容暂时不能处理，放置在flash、图片中的文字，百度无法识别。建议能使用文字的尽量不用其它的。不使用frame和iframe框架结构，通过iframe显示的内容可能会被搜索引擎丢弃。合理的编写网页代码和链接增强搜索引擎的可读性。 做好网站结构 网站应该有清晰的结构和明晰的导航，这能帮助用户快速从你的网站中找到自己需要的内容，也可以帮助搜索引擎快速理解网站中每一个网页所处的结构层次。 网站结构建议采用树型结构，树型结构通常分为以下三个层次：首页——频道——文章页。象一棵大树一样，首先有一个树干（首页），然后再是树枝（频道），最后是树叶（普通内容页）。树型结构的扩展性更强，网站内容变多时，可以通过细分树枝（频道）来轻松应对。 理想的网站结构应该是更扁平一些，从首页到内容页的层次尽量少，这样搜索引擎处理起来，会更简单。同时，网站也应该是一个网状结构，网站上每个网页都应该有指向上、下级网页以及相关内容的链接：首页有到频道页的链接，频道页有到首页和普通内容页的链接、普通内容页有到上级频道以及首页的链接、内容相关的网页间互相有链接。网站中每一个网页，都应该是网站结构的一部分，都应该能通过其他网页链接到。 url和子域名 创建具有良好描述性、规范、简单的url，有利于用户更方便的记忆和判断网页的内容，也有利于搜索引擎更有效的抓取您的网站。网站设计之初，就应该有合理的url规划。网站中同一网页，只对应一个url，如果网站上多种url都能访问同样的内容，搜索引擎会选一种url为标准，可能会和正版不同，用户可能为同一网页的不同url做推荐，多种url形式分散了该网页的权重。另外长长的URL不仅不美观，用户还很难从中获取额外有用的信息。另一方面，短url还有助于减小页面体积，加快网页打开速度，提升用户体验。 选择使用子域名还是目录来合理的分配网站内容，对网站在搜索引擎中的表现会有较大的影响。在某个频道的内容没有丰富到可以当做一个独立站点存在之前，使用目录形式；等频道下积累了足够的内容，再转换成子域名的形式。一个网页能否排到搜索结果的前面，"出身"很重要，如果出自一个站点权重较高的网站，那排到前面的可能性就越大，反之则越小。通常情况下主站点的权重是最高的，子站点会从主站点继承一部分权重，继承的多少，视子站点质量而定。在内容没有丰富到可以做为一个独立站点之前，内容放到主站点下一个目录中能在搜索引擎中获得更好的表现。搜索引擎会识别站点的主题，如果站点中内
面向搜索引擎的网站建设
面向搜索引擎的网站建设 搜索引擎只是网站上一个普通的访客，对网站的抓取方式、对网站/网页的价值判断，也都是从用户的角度出发的，任何对用户体验的改进，都是对搜索引擎改进。对搜索引擎的优化，同时也会让用户受益。 面向搜索引擎的网站建设，主要分为三个部分：如何更好的让搜索引擎收录网站中的内容、如何在搜索引擎中获得良好的排名、如何让用户从众多的搜索结果中点击你的网站。简单来说，就是收录、排序、展现。下面安庆seo将从这三个方面分别介绍。 机器可读 百度通过一个叫做Baiduspider的程序抓取互联网上的网页，经过处理后建入索引中。目前Baiduspider只能读懂文本内容，flash、图片等非文本内容暂时不能处理，放置在flash、图片中的文字，百度无法识别。 建议使用文字而不是flash、图片、Javascript等来显示重要的内容或链接，搜索引擎暂时无法识别Flash、图片、Javascript中的内容，这部分内容无法搜索到；仅在flash、Javascript中包含链接指向的网页，百度可能无法收录。 百度建议 1.使用文字而不是flash、图片、Javascript等来显示重要的内容或链接； 2.如果必须使用Flash制作网页，建议同时制作一个供搜索引擎收录的文字 版，并在首页使用文本链接指向文字版； 3.Ajax等搜索引擎不能识别的技术，只用在需要用户交互的地方，不把希 望搜索引擎"看"到的导航及正文内容放到Ajax中；
4.不使用frame和iframe框架结构，通过iframe显示的内容可能会被百度丢 弃。 网站结构 网站应该有清晰的结构和明晰的导航，这能帮助用户快速从你的网站中找到自己需要的内容，也可以帮助搜索引擎快速理解网站中每一个网页所处的结构层次。 网站结构建议采用树型结构，树型结构通常分为以下三个层次：首页—— 频道—— 文章页。象一棵大树一样，首先有一个树干（首页），然后再是树枝（频道），最后是树叶（普通内容页）。树型结构的扩展性更强，网站内容变多时，可以通过细分树枝（频道）来轻松应对。 理想的网站结构应该是更扁平一些，从首页到内容页的层次尽量少，这样搜索引擎处理起来，会更简单。 同时，网站也应该是一个网状结构，网站上每个网页都应该有指向上、下级网页以及相关内容的链接：首页有到频道页的链接，频道页有到首页和普通内容页的链接、普通内容页有到上级频道以及首页的链接、内容相关的网页间互相有链接。 网站中每一个网页，都应该是网站结构的一部分，都应该能通过其他网页链接到。 总结一下，合理的网站结构应该是一个扁平的树型网状结构。 百度建议 1.确保每个页面都可以通过至少一个文本链接到达； 2.重要的内容，应该能从首页或者网站结构中比较浅的层次访问到； 3.合理分类网站上的内容，不要过度细分。 网站应该有简明、清晰的导航，可以让用户快速找到自己需要的内容，同时也可以帮助搜索引擎更好的了解网站的结构。 百度建议
禁忌搜索算法评述(一)
禁忌搜索算法评述(一) 摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法 1引言 工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。 迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。 禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。 2禁忌搜索算法的基本流程 TS算法一般流程描述1]: (1)设定算法参数,产生初始解x,置空禁忌表。 (2)判断是否满足终止条件?若是,则结束,并输出结果;否则,继续以下步骤。 (3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。 (4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsofar”状态,然后转步骤(6);否则,继续以下步骤。 (5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。 (6)转步骤(2)。 算法可用图1所示的流程图更为直观的描述。 3禁忌搜索算法中的关键设计 3.1编码及初始解的构造 禁忌搜索算法首先要对待求解的问题进行抽象,分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略,主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示2],十进制编码将问题的解用一个十进制串来表示3],实数编码将问题的解用一个实数来表示4],在某些组合优化问题中,还经常使用混合编码5]、0-1矩阵编码等。 禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以
搜索引擎优化(SEO)专业术语
亿推英文新闻稿，亿推英文软文，英文新闻稿推广，亿推英文软文写手，英文软文代写，亿推英文软文推广，英文推广，亿推发1000个英文新闻站，亿推标准化英文推广，TuiGuang123 亿推有超过1200个英文文章数据库平台合作站，超过60人欧洲美洲本土英文软文写手团队，超过20人英语法语专业软文团队，超过1600位外贸企业用户信赖亿推营销团队。LinkPopularity网站的链接广泛度 在搜索引擎排名中的作用已得到广泛的认同和重视。实际上，即使你没有在GOOGLE上提交你的站点，但与其它网站作了链接，GOOGLE也可能收录你的网站。搜索引擎还可能完全依据你的链接广泛度决定你的网站排名。 InternalLinks内部链接 本网站内部网页之间的链接。 ExternalLinks外部链接： 本网站外部的链接，一般是指其他网站连到本网站的链接。 BackwardLinks或IncomingInboundLinks反向导入链接： 意义与“外部链接”接近，指其他网站连到本网站的链接。 OutgoingOutboundLinks导出链接： 指从本网站连到其他网站的链接。 PageRank(简称PR) PageRank是Google衡量网页重要性的工具，测量值范围为从1至1分别表示某网页的重要性。在Google工具栏可以随时获得某网页的PageRank值。 SearchEngineOptimization(简称英文seo亿推)搜索引擎亿推英文推广优化：SearchEnginePositioning搜索引擎定位： SearchEngineRanking搜索引擎排名： Externalfiles外部文件存储： 把javascript文件和css文件分别放在js和css外部文件中。这样做的好处是把重要的页面内容放到页面顶部，同时能缩小文件大小。有利于搜索引擎快速准确地抓取页面重要内容。KeywordDensity关键词密度： ROBOTS搜索机器人： AffiliateMarketing联属网络营销(有的称会员制营销、网站联盟等)： 联属网络营销指的是一种网站A为网站B放置广告按钮，然后从为网站B带来的销售额中获得回佣的一种广告系统。某些广告主通过这种方式获得市场信息而不是现金销售。这种方式
面向主题搜索的网络爬虫信息采集策略研究
面向主题搜索的网络爬虫信息采集策略研究摘要：主题网络爬虫作为主题搜索引擎的信息抓取部分，负责对与用户感兴趣的某一主题相关的网页进行抓取。在深入分析主题页面在Web上的分布特征和主题相关性判别算法的基础上，本文提出了一个面向主题搜索的网络爬虫模型，它很好地克服了通用搜索引擎准率偏低、信息内容相对陈旧、信息分布范围不均衡等不足。 关键字：搜索引擎；主题爬虫；信息采集 1 引言 随着互联网规模的不断扩大，网络信息成爆炸式增长，网络已经成为最大的非结构化数据库。由于网络的分布式性，网络上的信息大多都是无组织的，很难对它进行结构化管理。如何高效提取和利用这些信息成为网络信息检索技术方面的一个巨大挑战。传统通用搜索引擎百度、Yahoo和好搜等，作为一个辅助人们检索信息的工具成为用户访问万维网的入口和指南，然而，通用搜索引擎在为网络用户提供便利之时，也暴露出种种不足，如：查准率偏低、信息内容相对陈旧、信息分布范围不均衡等。为了解决上述问题，主题搜索网络爬虫应运而生。 主题搜索亦称垂直搜索，是专为查询某一主题信息而设计的查询工具，它通过提供个性化信息搜索服务，把搜索应用限制在特定的主题或特定领域上，具体搜索过程中只访问与主题有关的页面，无须遍历整个Web系统，这既提高了服务质量，也节约了计算及网络资源。网络爬虫又叫网络蜘蛛，是一种能够自动采集Web页面内容的程序，它可从Web上下载页面，为搜索引擎构建知识库，网络爬虫是搜索引擎的重要组成部分。与通用网络爬虫相比，本文所描述的主题网络爬虫能够更快、更多地采集预先定义好的与主题相关的页面，另外，它还可实现按主题分块采集，并将采集结果整合到一起，以提高整个Web的采集覆盖率和页面利用率。 2 主题网络爬虫 在主题搜索引擎中，主题网络爬虫是引擎的最核心内容，主要用来负责对与用户感兴趣的某一主题相关的网页进行抓取。主题爬虫遍历信息的过程就是按照预先给出的主题，根据一定的页面算法过滤与主题无关的链接，并在URL队列中加入与主题相关的链接，之后预测待抓取的URL与当前网页的主题相关度，进而选择下一步将要抓取的网页URL，并重复上述过程，直至满足系统的停止条件时停止。所有网络爬虫抓取的页面都会被系统存储，并由系统对其进行过滤、分析，以建立索引，主题爬虫基本目标就是尽可能多地爬行、下载与主题相关的网页，尽可能少地下载无关网页。相对于通用网络爬虫，主题网络爬虫需要解决好四个方面的问题：(1) 主题如何描述或定义；(2) URL遍历次序如何确定；(3) 网页数据如何分析与过滤；(4)主题网络爬虫的覆盖度如何提高。 3 主题网络爬虫搜索策略算法研究 3.1 系统模型 主题网络爬虫在传统网络爬虫的基础上进行功能扩充，进行面向主题的网页信息提取。为实现面向主题的信息自动采集，主题爬虫处理过程一般包含四部分：主题确立、网页采集、页面分析和过滤、主题相关性计算（链接过滤），主题网络爬虫系统模型如图1所示：
禁忌搜索和应用
目录 一、摘要 (2) 二、禁忌搜索简介 (2) 三、禁忌搜索的应用 (2) 1、现实情况 (2) 2、车辆路径问题的描述 (3) 3、算法思路 (3) 4、具体步骤 (3) 5、程序设计简介 (3) 6、算例分析 (4) 四、禁忌搜索算法的评述和展望 (4) 五、参考文献 (5)
禁忌搜索及应用 一、摘要 工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 二、禁忌搜索简介 禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。 迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。 三、禁忌搜索的应用 禁忌搜索应用的领域多种多样，下面我们简单的介绍下基于禁忌搜索算法的车辆路径选择。 1、现实情况 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（vehicle routing problem简记vrp）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且vrp问题属于np-hard问题，求解比较困难，因此启发式算法成为求解vrp问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解vrp提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最
基于改进粒子群算法的优化策略
收稿日期:2009-12-13 基金项目:国家自然科学基金资助项目(60674021) 作者简介:卢 峰(1982-),男,辽宁抚顺人,东北大学博士研究生;高立群(1949-),男,辽宁沈阳人,东北大学教授,博士生导师 第32卷第9期2011年9月东北大学学报(自然科学版)Journal of Northeastern U niversity(Natural Science)Vol 32,No.9Sep.2011 基于改进粒子群算法的优化策略 卢 峰,高立群 (东北大学信息科学与工程学院,辽宁沈阳 110819) 摘 要:为提高传统粒子群算法的搜索速度和搜索精度,提出了一种改进的自适应粒子群优化算法 将正则变化函数和慢变函数引入传统位置更新和速度更新公式当中,形成两种新的更新机制:搜索算子和开发算子 在算法运行的初始阶段,种群中大部分个体将按照搜索算子进行更新,搜索算子将有助于种群遍历整个解空间;随着迭代次数的增加,按照搜索算子进行更新的个体将逐渐减少,而按照开发算子进行更新的个体将逐渐增多,开发算子将有效地克服陷入局部最优解的问题 通过典型测试函数的仿真实验,新算法在加快收敛速度同时,提高了算法的全局搜索能力 关 键 词:进化算法;粒子群算法;全局优化;慢变函数;自适应 中图分类号:T G 273 文献标志码:A 文章编号:1005 3026(2011)09 01221 04 Novel Optimization Mechanism Based on Improved Particle Swarm Optimization L U Feng ,GAO L i qun (School of Information Science &Engineering,Northeaster n U niv ersity,Shenyang 110819,China.Corresponding author :LU F eng,E mail:feng.lu.lf @g https://www.sodocs.net/doc/0d16224234.html,) Abstract :To accelerate searching speed and optimization accuracy of traditional PSO,an improved particle swarm optimization (PSO )algorithm w as presented.Regularly vary ing function and slow ly varying function were introduced in the position and velocity update formula.New mechanisms such as explorative operator and exploitative operator are formulated.At the beginning,most elements will be updated by explorative operator in the entire search space sufficiently.Within the iterations,more and more particles w ill be handled by ex ploitative operator,which are useful to overcome the deceptions of multiple local optima.It can be seen from the simulation results of the standard benchm ark test functions that the proposed algorithm not only accelerates the convergence process,but also improves g lobal optim ization ability. Key words:evolutionary algorithms;particle sw arm optimization;global optimization;slow ly v arying function;self adaptive 20世纪90年代初,产生了模拟自然生物群体行为的优化方法,被称为群智能优化方法 Dorigo 等人通过模拟蚂蚁的寻径行为,提出了蚁群优化算法(ant colony optimization)[1] ;Eberhart 等人基于对鸟群、鱼群的模拟,提出了粒子群优化算法(particle sw arm optim ization )[2] 作为一种群智能优化方法的代表,粒子群算法通过个体间的协作来寻找最优解,每个个体都被赋予一个随机速度并在整个解空间中搜索,通 过个体之间的合作与竞争来实现个体进化 由于粒子群优化算法运算简单,易于实现,具有良好的解决非线性、不可微和多峰值复杂优化问题的能力,已被广泛应用于科学和工程实际领域[3-5] 但是,粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向进化,在进化后期收敛速度将变得缓慢,同时算法在收敛到一定精度时,容易陷入停滞,无法继续进化更新,因此,存在早熟和陷入局部极值点的现象
启发式优化算法综述
启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，
以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型
搜索引擎优化行业术语(全)
搜索引擎优化行业术语（全） A Alexa Alexa是亚马逊公司(https://www.sodocs.net/doc/0d16224234.html,)下属的一个网站，用来估算世界各国网站的大体流量以确定网站的受欢迎程度。它给网站统一排名，越小数目的Alexa值说明排名越高，网站的流量越大。但是，这个数据仅能作为一个参考。因为它是第三方的估算，不能直接得到流量数据，而且与其依靠它的Alexa工具条的使用者作为基础，因此给出的流量数据都是有相当的夸大或者压缩，所以不具备真正衡量一个网站表现的功能。网站的实际表现必须看网站自己的独立统计系统的数据，而这个数据Alexa是得不到的。Alexa数据对搜索引擎优化没有参考价值。 Algorithm算法 算法是解决一个问题所形成的公式。在搜索引擎中，算法是程序员编写的用于自动分析网站内容、结构和相关性的一组程序，来确定网站的质量和价值，为关键词搜索结果的排列提供依据。 Anchor Text链接源头文字 链接源头文字是一张网页中被划线强调出的一段文字，用来指明连向其他网页的说明。点击这段文字，浏览器就调出这段文字后的目标，就是另外一张网页。链接源头文字的写作需要和指向页的内容相关，为访问者言简意赅地引见指向页。链接源头文字的编写对网站PR值的提高具有重要作用。 B Backlinks(Inbound Links)导入链接 导入链接是由其他网站指向你的网站的一个链接，和导出链接(outboundlinks)相反。导入链接的多少是搜索引擎，尤其是Google来衡量一个网站是否受欢迎的若干因素中重要的一个。追求导入链接，需要注意链接方与你的网站的相关性。 Bad Neighborhood坏邻居 坏邻居是指你的网站所链接的网站中的质量低下的网站。坏邻居网站很可能包括我们称为“链接养殖场”(1ink farm)这类专靠链接来骗取PR值的网站。坏邻居也包括过分优化的网站。这类网站最容易被搜索引擎惩罚。我们在建立链接的时候，要避免和这类网站挂钩。 Black-Hat-SEOh黑帽优化手段
一种求解高维复杂优化问题的动态自适应和声搜索算法
第３９卷第９期２０１２年９月计算机科学 ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ Ｖ０１．３９Ｎｏ．９ Ｓｅｐ２０１２ 一种求解高维复杂优化问题的动态自适应和声搜索算法 拓守恒邓方安 （陕西理工学院数学与计算机科学学院汉中７２３０００） 摘要为了更好地提高求解高维复杂优化问题的能力，提出一种动态自适应和声搜索（ＤＳＨＳ）算法。该算法采用正交试验来设计算法的初始化和声记忆库；利用多维动态自适应调整算子和单维和声微调算子相结合的策略进行和声创作；改进和声音调调解步长，从而增强算法的扰动能力，避免其陷入局部搜索。通过６个标准Ｂｅｎｃｈｍａｒｋ函数测试表明，该算法在全局搜索能力、收敛速度和稳定性方面都有明显提高。 关键词高维优化问题，动态自适应，和声搜索算法 中图法分类号ＴＰｌ８文献标识码Ａ ＤｙｎａｍｉｃＳｅｌｆ－ａｄａｐｔｉｖｅＨａｒｍｏｎｙＳｅａｒｃｈＡｌｇｏｒｉｔｈｍｆｏｒＳｏｌｖｉｎｇ Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌＣｏｍｐｌｅｘＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ ＴＵＯＳｈｏｕ－ｈｅｎｇＤＥＮＧＦａｎｇ－ａｎ （ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＳｈａａｎｘｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｎｚｈｏｎｇ７２３０００，Ｃｈｉｎａ） ＡｂｓｔｒａｃｔＴｈｉｓｓｔｕｄｙｐｒｅｓｅｎｔｅｄａｄｙｎａｍｉｃｓｅｌｆ－ａｄａｐｔｉｖｅｈａｒｍｏｎｙｓｅａｒｃｈ（ＤＳＨＳ）ａｌｇｏｒｉｔｈｍｔＯｓｏｌｖｅｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．ＩｎｔｈｅｐｒｏｐｏｓｅｄＤＳＨＳａｌｇｏｒｉｔｈｍ，ｔｈｅｏｒｔｈｏｇｏｎａｌｅｘｐｅｒｉｍｅｎｔａｌｄｅｓｉｇｎａｌｇｏｒｉｔｈｍｗａｓｕｓｅｄｔｏｉｎｉ—ｔｉａｌｉｚｅｐｏｐｕｌａｔｉｏｎ；ｔｗｏｎｅｗｈａｒｍｏｎｙａｄｊｕｓｔｍｅｎｔｏｐｅｒａｔｏｒｓ，ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌｄｙｎａｍｉｃａｄａｐｔｉｖｅａｄｊｕｓｔｍｅｎｔｏｐｅｒａｔｏｒａｎｄｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌｔｏｎｅｓｆｉｎｅ－ｔｕｎｉｎｇｏｐｅｒａｔｏｒ，ｗｅｒｅｉｎｔｅｇｒａｔｅｄｔｏｔｈｅｉｍｐｒｏｖｉｓａｔｉｏｎｓｃｈｅｍｅ．Ｆｏｒａｖｏｉｄｉｎｇｔｈｅｓｅａｒｃｈｂｅｉｎｇｔｒａｐｐｅｄｉｎ１０ｃａｌｏｐｔｉｍｕｍ。ａｎｉｍｐｒｏｖｅｄｂａｎｄｗｉｄｔｈａｄｊｕｓｔｍｅｎｔ ａｌｇｏｒｉｔｈｍｗａｓｅｍｐｌｏｙｅｄｔｏｅｎｈａｎｃｅｔｈｅｄｉｓｔｕｒｂａｎｅｅｐｅｒ－ ｆｏｒｍａｎｃｅ．６ｂｅｎｃｈｍａｒｋｆｕｎｃｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｈａｓ ｓｔｒｏｎｇｃｏｎｖｅｒｇｅｎｃｅｖｅｌｏｃｉｔｙ，ｓｔａｂｉｌｉ—ｚａｔｉｏｎａｎｄｃａｐａｃｉｔｙｏｆｓｐａｃｅｅｘｐｌｏｒａｔｉｏｎｏｎｓｏｌｖｉｎｇｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌｃｏｍｐｌｅｘｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ，ｃｏｍｐａｒｅｄｗｉｔｈｍｏｓｔｏｔｈｅｒａｐｐｒｏａｃｈｅｓ． ＫｅｙｗｏｒｄｓＨｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌ，Ｄｙｎａｍｉｃｓｅｌｆ－ａｄａｐｔｉｖｅ，Ｈａｒｍｏｎｙｓｅａｒｃｈａｌｇｏｒｉｔｈｍ １引言 仿生群体智能优化算法以对其优化问题的数学模型复杂度要求较低、优化过程与初始值无关、搜索速度快等优势，成为求解大规模复杂问题的研究热点。目前典型仿生群体智能优化算法主要有遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ：ＧＡ）、微粒子群算法ＰＳＯ、人工蜂群优化算法ＡＢＣ、蚁群算法Ａｃ０、模拟退火算法ＳＡ和差分进化算法ＤＥ等。仿生智能优化算法通过模仿生物的进化规则（ＧＡ，ＤＥ）或生物觅食规则（ＰＳ０、ＡＣ０、ＡＢＣ）等来进行优化问题求解，已经得到广泛应用。 和声搜索（ＨａｒｍｏｎｙＳｅａｒｃｈ：ＨＳ）算法是Ｇｅｅｍ和Ｋｉｍ等［１］提出的一种新型的仿生智能优化算法。ＨＳ算法模拟音乐家在音乐创作中不断调整各个乐器或音符，形成美妙动听的和声。同样地，在优化问题求解中，通过逐步调整各个解中的决策变量的值使其向全局最优解靠近。目前，该方法已在组合优化［２］、无约束函数优化［３］等问题中得到了广泛应用，Ｅｓ—ｍａｉｌｅＫｈｏｒｒｏｎ／４］将ＨＳ算法应用到热力和电力经济调度问题中，ＳｉｎｅｍＫｕｌｌｕｋ［５］应用ＨＳ算法训练神经网络，雍龙泉嘲采用ＨＳ算法求解绝对值方程。 ＨＳ算法在求解低维优化问题时，求解速度快，且稳定性好。但该算法是逐步淘汰和声库中最差和声向量，当问题的维数和复杂度较高时，往往需要多次迭代求解，因此非常容易早熟而陷入局部搜索，并且难以跳出局部搜索区域。针对该缺点，学者们提出了一些改进算法：改进的和声算法（ＩｍｐｒｏｖｅＨａｒｍｏｎｙＳｅａｒｃｈ，ＨＩＳ）［７｜、全局最优和声搜索算法（Ｇｌｏｂａｌ－ｂｅｓｔＨａｒｍｏｎｙＳｅａｒｃｈ，ＧＨＳ）［８］、自适应全局最优和声搜索算法（Ｓｅｌｆ－ａｄａｐｔｉｖｅＧｌｏｂａｌ－ｂｅｓｔＨａｒｍｏｎｙＳｅａｒｃｈ，ＳＧＨＳ）［９．１０３等。ＩＨＳ、ＧＨＳ和ＳＧＨＳ算法对ＨＳ算法从收敛性和搜索空间探索能力都有一定的提升，但对一些高维多模态复杂问题还是有一些不足，为此，本文在上述算法的基础上提出一种求解高维复杂优化问题的动态自适应和声搜索算法（ＤｙｎａｍｉｃＳｅｌｆ－ａｄａｐｔｉｖｅＨａｒｍｏｎｙＳｅａｒｃｈ，ＤＳＨＳ）。 到稿日期：２０１１－１２－０７返修日期：２０１２－０３－０５本文受国家高技术研究发展计划（８６３计划）（２００８ＡＡ０１Ａ３０３），国家自然科学基金（８１１６０１８３），宁夏自然科学基金项目（ＮＺｌｌｌ０５），宁夏卫生厅科研项目（２０１１０３３），陕西理工学院“汉水文化”省级重点学科课题（ＳＬＧＨｌ２２６）资助。 拓守恒（１９７８一），男，讲师，硕士，ＣＣＦ会员，主要研究方向为进化计算、人工智能、神经网络等；邓方安（１９６３一），男，博士，教授，主要研究方向为人工智能、粗糙集。 ?２４０? 万方数据