1.3 群优化算法在目标跟踪中的应用

1.3.1 元启发式优化算法

跟踪算法的主要目的是找到目标模型和一组潜在解之间的最佳匹配，近似于在合理的运行时间内，在离散搜索空间中找到一个满意的解。目标跟踪的解决方法与元启发式优化算法的求解行为一致。元启发式优化算法可以看作一种近似求解算法，它为解决采用传统优化技术所无法解决的优化问题提供了技术保证。大多数元启发式优化算法的健壮性通常来自它的本质启发。

元启发式优化算法通过模仿生物或物理现象来解决优化问题，可以分为基于进化的方法、基于物理的方法和基于群体的方法。基于进化的方法受到自然进化规律的启发，搜索过程从随机产生的种群开始，进行几代种群的进化。这类方法的优点是，最优的个体总是结合在一起形成下一代个体，使得种群可以在几代进化的过程中得到优化。受进化论启发的最流行的技术是遗传算法（Genetic Algorithm，GA）[71]，它模拟了达尔文的进化论。其他流行的算法有基于概率的增量学习（Probability Based Incremental Learning，PBIL）[72]、遗传规划（Genetic Programming，GP）[73]和基于生物地理学的优化器（Biogeography-Based Optimizer，BBO）[74]等。

基于物理的方法模拟了宇宙中的物理规则。最受欢迎的算法有模拟退火算法（SA）[75]、引力搜索算法（Gravitational Search Algorithm，GSA）[76]、人工化学反应优化算法（Artificial Chemical Reaction Optimization Algorithm，ACROA）[77]、射线优化算法（Ray Optimization，RO）[78]及曲线空间优化算法（Curved Space Optimization，CSO）[79]等。

基于群体的方法模仿动物群体社会行为的群居技术，即群优化算法。群优化算法中最为人熟知的是PSO算法。它是由Kennedy和Eberhart[80]开发的。PSO算法的灵感来自鸟类群体的社会行为。它使用大量粒子在搜索空间中寻找最佳解，同时在各粒子的路径中跟踪最佳位置。还有另一种比较常用的基于群体的算法是蚁群优化（Ant Colony Optimization，ACO）算法，由Dorigo等人[81]首先提出。该算法的灵感来自蚂蚁寻找离巢穴最近的路径和食物来源方面的行为。其他流行的群优化算法还有海豚回声定位（Dolphin Echolocation，DE）算法[82]、蜂群算法（Artificial Bee Colony，ABC）[83]、布谷鸟搜索（CS）算法[84]、蝙蝠算法（Bat-inspired Algorithm，BA）[85]、萤火虫算法（Firefly Algorithm，FA）[86]、蜻蜓算法（Dragonfly Algorithm，DA）[87]、蚁狮优化（ALO）算法[88]、鲸鱼优化算法（Whale Optimization Algorithm，WOA）[89]、樽海鞘群算法（Salp Swarm Algorithm，SSA）[90]、蝴蝶算法（Butterfly-inspired Algorithm）[91]等。

另外，也有其他受人类行为启发的元启发式优化算法，目前流行的有基于教学学习的优化（Teaching Learning Based Optimization，TLBO）算法[92]、禁忌搜索（Taboo Search，TS）算法[93]、群体搜索优化器（Group Search Optimizer，GSO）算法[94]、内部搜索算法（Interior Search Algorithm，ISA）[95]、团体咨询优化（Group Counseling Optimization，GCO）算法[96]等。

1.3.2 基于群优化算法的目标跟踪方法

由1.3.1节可知，模仿动物群体社会行为的群优化算法在元启发式优化算法中研究最多、发展最快，它们具有一个共同的特征，即搜索过程分为两个阶段：探索阶段和开发阶段。在探索阶段，移动（设计变量的扰动）应尽可能随机化；开发阶段可以定义为对搜索空间中有希望的区域进行详细调查的过程。种群中的每个个体都具有相对较低的智能因子，从而提高了其有效探索搜索空间的能力；群体中进行沟通和共享信息的能力会增强群体的整体智力，并带来更好的解决方案。因为具有较强的全局寻优能力，所以很多群优化算法已被应用于目标跟踪方法研究中，通过将跟踪问题转换为全局匹配获得最优解的处理方式，实现目标状态的跟踪。表1.3列出了部分群优化算法在目标跟踪中的应用。

表1.3 部分群优化算法在目标跟踪中的应用

尽管各种基于群优化及其改进的跟踪方法不断被提出，但没有哪种方法能够适应所有的问题。因此，更多的方法被继续引入目标跟踪领域。本书提出基于群优化及其改进的跟踪方法解决目标跟踪中的突变运动问题。

1.3.3 基于混合群优化算法的目标跟踪方法

前文提及的算法在某些特定问题上表现较好，而在其他问题上则表现较差。到目前为止，如何针对优化问题设计一种新的启发式优化算法仍然是一个悬而未决的问题[113]。

群优化领域研究大致有3个重点方向：提出新的算法、改进现有算法和混合不同的算法。其中，第三个研究方向是通过杂交或混合不同的算法来改革已有的成果或解决不同的问题[114]。近年来，混合算法由于在处理许多具有不确定性、复杂性、不精确性和模糊性的现实问题方面效率较高，越来越受到欢迎。

针对高维优化问题，元启发式优化算法采用了不同的探索和利用策略。混合元启发式优化算法是解决高维问题的最新研究趋势，克服了一种算法搜索能力较差和另一种算法开发能力较差的缺点。在大量文献中均提及混合元启发式算法，如混合Cat Swarm Optimization（CSO）[115]、Particle Swarm and Artificial Bee Colony （PS-ABC）[116]、Hybrid Spiral-Dynamic Bacteria-Chemotaxis（HSDBC）[117]、Genetic Algorithms and Cross Entropy（GACE）[118]、Cultural Algorithms Framework with Trajectory-Based Search[119]、Artificial Bee Colony Algorithm Based on Improved-Global-Best-Guided Approach and Adaptive-Limit[120]和Gravitational Search Algorithm-Particle Swarm Optimization with Time Varying Acceleration Coefficients[121]等。目前，已有很多混合优化算法被应用于目标跟踪。Chen等人[122]提出了一种基于欧几里得距离的混合量子PSO（Hybrid Quantum PSO，HQPSO）算法。Nenavath等人[123-125]提出了混合正余弦算法（Sine Cosine Algorithm，SCA）和基于教与学的优化（Teaching-Learning-Based Optimization，TLBO）算法、混合SCA与PSO算法和SCA与DE算法，并用于全局优化和目标跟踪。Zhang等人[126]提出了一种基于模拟退火（Simulated Annealing，SA）算法的扩展核相关滤波器（Kernel Correlation Filter，KCF）跟踪器。Zhang等人[127]提出了一种基于KCF的布谷鸟搜索扩展的跟踪器。Xu等人[128]提出了一种基于差分进化的跟踪框架。Gao等人[129]提出了一种基于萤火虫算法的改进粒子滤波算法，应用于目标跟踪。Gao等人[130]提出了一种新的元启发式优化算法——微分和谐搜索（DHS），可用于解决人脸跟踪问题。Gao等人[131]提出了一种基于蝙蝠的粒子滤波算法。Hua等人[132]提出了一种利用SDAE多级特征学习能力的目标跟踪算法。这些混合算法在一定程度上均使原始的优化算法在性能上有所提升，并且将其应用在目标跟踪领域使其跟踪精度或跟踪效率得到了很大的提高。