搜索技术——群智能-创新互联

如果有兴趣了解更多相关内容，欢迎来我的个人网站看看：瞳孔空间

站在用户的角度思考问题，与客户深入沟通，找到薛城网站设计与薛城网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都网站设计、网站建设、企业官网、英文网站、手机端网站、网站推广、域名与空间、雅安服务器托管、企业邮箱。业务覆盖薛城地区。一：初识群智能 1.1：粒子群算法

粒子群算法，也称粒子群优化算法或鸟群觅食算法（Particle Swarm Optimization），缩写为 PSO， 是近年来由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法(Evolutionary Algorithm - EA)。PSO 算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

粒子群算法(Particle Swarm Optimization，简称PSO)的思想源于对鸟群捕食行为的研究，模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的。

设想这样一个场景，—群鸟在随机搜索食物，已知：在这块区域里只有一块食物，所有的鸟都不知道食物在哪里，但它们能感受到当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？很显然，最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO正是从这种模型中得到了启发：信息的社会共享。鸟群在整个搜寻的过程中，通过相互传递各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即找到了最优解。

PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

1.2：人工鱼群算法

人工鱼群算法为山东大学副教授李晓磊2002年从鱼找寻食物的现象中表现的种种移动寻觅特点中得到启发而阐述的仿生学优化方案。

定义：在一片水域中，鱼往往能自行或尾随其他鱼找到营养物质多的地方，因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方，人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从而实现寻优。

人工鱼拥有以下几种典型行为：

• 觅食行为：一般情况下鱼在水中随机地自由游动，当发现食物时，则会向食物逐渐增多的方向快速游去。
• 聚群行为：鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群，鱼聚群时所遵守的规则有三条：
  • 分隔规则：尽量避免与临近伙伴过于拥挤
  • 对准规则：尽量与临近伙伴的平均方向一致
  • 内聚规则：尽量朝临近伙伴的中心移动
• 追尾行为：当鱼群中的一条或几条鱼发现食物时，其临近的伙伴会尾随其快速到达食物点
• 随机行为：单独的鱼在水中通常都是随机游动的，这是为了更大范围地寻找食物点或身边的伙伴

算法实现的步骤：

1. 初始化设置，包括种群规模N、每条人工鱼的初始位置、人工鱼的视野visual、步长step、拥挤度因子δ、重复次数Trynumber
2. 计算初始鱼群各个体的适应值，取最优人工鱼状态及其值赋予给公告牌
3. 对每个个体进行评价，对其要执行的行为进行选择，包括觅食Pray、聚群Swarm、追尾Follow和评价行为bulletin
4. 执行人工鱼的行为，更新自己，生成新鱼群
5. 评价所有个体。若某个体优于公告牌，则将公告牌更新为该个体
6. 当公告牌上最优解达到满意误差界内或者达到迭代次数上限时算法结束，否则转步骤3

1.3：人工蜂群算法

人工蜂群算法(Artificial Bee Colony Algorithm，简称ABC算法)是一个由蜂群行为启发的算法，在2005年由Karaboga小组为优化代数问题而提出。

人工蜂群算法是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。

机理如下：

• 蜜蜂是一种群居昆虫，虽然单个昆虫的行为极其简单，但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在任何环境下，以极高的效率从食物源（花朵）中采集花蜜；同时，它们能适应环境的改变
• 蜂群产生群体智慧的最小搜索模型包含基本的三个组成要素：食物源、被雇佣的蜜蜂和未被雇佣的蜜蜂；两种最为基本的行为模型：为食物源招募蜜蜂和放弃某个食物源
  • 食物源：食物源的价值由多方面的因素决定，如：它离蜂巢的远近，包含花蜜的丰富程度和获得花蜜的难易程度。使用单一的参数，食物源的“收益率”，来代表以上各个因素
  • 被雇用的蜜蜂：也称引领蜂，其与所采集的食物源一一对应。引领蜂储存有某一个食物源的相关信息（相对于蜂巢的距离、方向、食物源的丰富程度等）并且将这些信息以一定的概率与其他蜜蜂分享
  • 未被雇用的蜜蜂：其主要任务是寻找和开采食物源。有两种未被雇用的蜜蜂：侦查蜂和跟随蜂。侦察蜂搜索蜂巢附近的新食物源；跟随蜂等在蜂巢里面并通过与引领蜂分享相关信息找到食物源。一般情况下，侦察蜂的平均数目是蜂群的5%-20%

在群体智慧的形成过程中，蜜蜂间交换信息是最为重要的一环。舞蹈区是蜂巢中最为重要的信息交换地。蜜蜂的舞蹈叫做摇摆舞。食物源的信息在舞蹈区通过摇摆舞的形式与其他蜜蜂共享，引领蜂通过摇摆舞的持续时间等来表现食物源的收益率，故跟随蜂可以观察到大量的舞蹈并依据收益率来选择到哪个食物源采蜜。收益率与食物源被选择的可能性成正比。因而，蜜蜂被招募到某一个食物源的概率与食物源的收益率成正比。

初始时刻，蜜蜂以侦察蜂的身份搜索。其搜索可以由系统提供的先验知识决定，也可以完全随机。经过一轮侦查后，若蜜蜂找到食物源，蜜蜂利用它本身的存储能力记录位置信息并开始采蜜。此时，蜜蜂将成为“被雇用者”

• 被雇用的蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜，然后将有如下选择：
  • 放弃食物源而成为非雇佣蜂
  • 跳摇摆舞为所对应的食物源招募更多的蜜蜂，然后回到食物源采蜜
  • 继续在同一个食物源采蜜而不进行招募
• 对于非雇佣蜂有如下选择：
  • 转变成为侦察蜂并搜索蜂巢附近的食物源。其搜索可以由先验知识决定，也可以完全随机
  • 在观察完摇摆舞后被雇用成为跟随蜂，开始搜索对应食物源邻域并采蜜

1.4：蚁群算法

蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。

蚂蚁觅食的过程中，单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多：当蚂蚁到达终点之后会立即返回，距离短的路上的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，会留下更多信息素。而距离长的路正相反，因此越来越多的蚂蚁聚集到最短路径上来。

蚂蚁具有的智能行为得益于其简单行为规则，该规则让其具有多样性和正反馈。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力；正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。

二：群智能介绍

“群”的特征：

• 相互作用的相邻个体的集合
• 个体的行为简单，既有竞争又有协作
• 智能化的集体行为（1+1>2)
  • 个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为
  • 没有一个集中控制中心，分布式、自组织
  • 作为群体协同工作时，展现出非常复杂的行为特征—智能

Swarm(群)可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子：

• 鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避
• 蚂蚁成群则有利于寻找食物，因为任何一只蚂蚁发现食物都可带领蚁群来共同搬运和进食
• 一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的
• 社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力
• 信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能(1+1>2)

群智能的起源和发展：

• 1989年，加利福尼亚大学的教授贝尼在其元胞自动机系统中首次提出群智能的概念，分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。
• 任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法，或分布式解决问题的策略均属于群智能——伯纳堡等，《群智能:从自然到人工系统》， 1999
• 无智能或简单智能的主体，通过任何形式的聚集协同（不是竞争）而表现出智能行为的特性——伯纳堡
• 2001年，肯尼迪和艾伯哈特出版了《群体智能》一书，该书是群智能发展的里程碑，该书赞同伯纳堡关于群智能定义的基本精神，但反对“主体”一词，认为会限制“群”的定义范围。并提出重要观点：智能源于社会性的相互作用（多智能体，人多力量大）。
• 群智能已成为有别于传统人工智能联连接主义和符号主义的一种新的关于智能的描述方法

基于群智能的典型优化算法：

• 蚁群算法（蚂蚁觅食）
• 粒子群算法（蜂群或鸟群觅食）

群智能优化算法的优点：

• 灵活性
• 稳健性
• 自组织
• 潜在的并行性和分布式

群智能优化算法的特点：

• 分布式：无中心控制
• 随机性：非确定性
• 自适应：个体根据环境进行策略调整
• 正反馈：个体好的尝试会对个体产生正反馈
• 自发涌现：会在群体层面涌现出一种智能

已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法

三：蚁群算法 3.1：基本介绍

蚁群智能的基本思想：蚂蚁以信息素的强度为概率来决定路线选择

• 整体往往大于部分的“简单和”
  • 蚂蚁的低智能——蚁群的高智慧
  • 蚂蚁的简单行为——蚁群的智能突现
• 实际蚁群的觅食
  • 主体（agent）：蚂蚁
  • 简单的规则（rules）：分工、通讯
  • 相互作用（interaction）：
    • 蚂蚁<==触角放电==>蚂蚁
    • 蚂蚁<==气味累积==>蚂蚁

等长路径的情况下，选择路径1和路径2的蚂蚁数目相近

不等长的路径情况下，绝大多数蚂蚁选择长度较短的路径：

3.2：蚁群寻食过程分析

假设：

• 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。
• 假设初始时每条路线分配一只蚂蚁，每个时间单位行走一步

下图为经过9个时间单位时的情形：走ABD的蚂蚁已到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。

经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。

则假设蚂蚁每经过一处所留下的信息素为一个单位，经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2:1。

寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁(共2只)，而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条路线上的信息素单位积累为12和4，比值为3:1。

若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁(共3只)，而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条路线上的信息素单位积累为24和6，比值为4:1。

若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。

若用障碍物切断原来的通路：

那么蚁群会探索新的道路：

最终形成最佳路径：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前文章：搜索技术——群智能-创新互联
本文URL：http://cdxtjz.cn/article/gpihe.html