1.2.2 协同搜索

协同搜索是指多智能体在一定的约束条件下能够完成对目标区域的遍历搜索，其本质是一种路径规划问题，应用领域主要包括安全监控、战场侦察、目标搜索、地形测绘、矿藏勘测等。目前，常见的搜索策略有随机搜索、平行搜索（“Z”字形或“之”字形）、网格搜索等。

① 随机搜索：指智能体以恒定的方向在搜索区域内行动到达区域边界后，再以最小转弯半径转弯进入搜索区域，此时智能体沿该方向继续前行，如此往复。

② 平行搜索：指受性能的约束，从能量、路程、时间角度表明转弯过程比直线飞行过程的效率要低，因此，智能体在平行于区域长度或宽度的方向上进行平行线式的搜索。

③ 网格搜索：指搜索区域被离散为一系列的小正方形区域，当一个小正方形区域被搜索完后，智能体选择另一个小正方形区域作为起点继续搜索。初始时，所有的小正方形的值都为1，当小正方形区域进入智能体的搜索范围时，该值变为0。当一个小正方形区域被搜索完后，智能体选择另一个小正方形区域作为搜索起点。选择的原则是离其最近且为1的小正方形区域。一旦选择了，这个信息将会共享给搜索区域内的所有智能体。

在智能体协同搜索过程中，搜索精度、碰撞类型、避障策略、路径平滑化等均可作为优化目标。除以上传统搜索策略外，还有多种算法，包括粒子群优化算法、细菌觅食优化算法、人工蜂群算法等均展现出了不俗的搜索效果。

从算法特点来看，粒子群优化算法的核心模型是一组位置与速度状态方程，计算简单、易于实现，但该模型的随机性大、群体智能性低、算法优化精度低，粒子易早熟；2002年，Passino遵循最优觅食原则，模拟人体内大肠杆菌或黏细菌的觅食行为，提出了细菌觅食优化算法（bacterial foraging optimization algorithm, BFOA），它可以以一种自然的方式结束算法，即在没有任何迭代次数和精度要求的前提下，算法会随着菌落的消失而自然结束，并能保持一定的精度，其主要包括趋化、繁殖和驱散三个基本操作步骤，具有突出的平行搜索优点；人工蜂群算法参数少，简单灵活，具有较好的探索能力，但由于人工蜂群的搜索随机性大，导致算法在寻优的过程中容易陷入局部最优，具有全局搜索能力不强和局部搜索精度低等缺点。

下面介绍细菌觅食优化算法在协同搜索中的应用，其三个基本操作步骤中的趋化操作是指模拟菌群的移动和转向，循环计算适合度，若适合度得到提升，则沿该方向继续移动，至适合度不发生改变时，此操作结束；繁殖操作是指按照适合度排列，淘汰适合度低的，以适合度更高的代替，并保持细菌总量的不变；驱散操作是指以一定的概率用新的个体代替原有个体，当陷入局部极值时，可通过将细菌向其他解空间随机分配以提高全局搜索能力。细菌觅食优化算法的具体步骤如下。

步骤1：初始化各参数及种群。

步骤2：驱散操作循环。

步骤3：繁殖操作循环。

步骤4：趋化操作循环，至达到趋化结束条件。

步骤 5：执行繁殖操作，至循环次数达到繁殖次数设定值，否则返回步骤3循环。

步骤 6：执行驱散操作，至循环次数达到驱散次数设定值，否则返回步骤2循环。

步骤7：将所有非支配解加到外部存放最优解的集合S中（非支配解：定义一个确定半径r的圆区域为个体的支配区域，该半径范围内的解均为支配解，之外的为非支配解，半径为r与2r的两个圆范围之间的区域称为个体的支配区域外围；集合 S指支配解与该个体的非支配区域内的解之间的函数距离最小值的集合）。

步骤8：采取以下区域搜索策略。

① 将当前种群的非支配解依次加到未被处理的列表中，保证列表中的所有解不被其他解支配。

② 计算列表中的解在集合S中支配区域内的个数，按支配区域内的个体数量从小到大排列。

③ 设定循环次数的循环操作：计算集合中解v的支配区域中的个体数n。若个体数n大于设定值N，则取出N个个体生成新的菌群进行区域搜索，否则，在解v的支配区域内随机生成N−n个个体，并与原n个个体形成新的菌群进行区域搜索。搜索结束后，所有非支配解更新到外部存放最优解的集合 S中；找到解 v的所有非支配解加到列表中，并保证互相不支配。

步骤9：结束优化协同搜索过程。

实验表明：细菌觅食优化算法这类信息仿生算法具有普遍适用性，模型简单、易于实现，但算法控制参数较多且没有明确的取值标准，只能依据经验设置，算法在不同的搜索时期不能匹配到最优参数，同时传统的信息仿生算法缺乏信息交流，收敛缓慢且易陷入局部最优。为此，许多学者引入了精英策略，使用融合算法增加种群的多样性，避免算法在搜索路径时陷入局部最优；通过引入自适应搜索机制、改进算法参数等办法扩大算法的搜索范围，减少无效搜索的次数，提高算法的收敛速度和搜索精度。