针对几种元启发式算法的应用性能对比研究

尚正阳，顾寄南，唐仕喜，孙晓红

（1.安徽工程大学机械与汽车工程学院，安徽 芜湖 241000；2.江苏大学制造业信息化研究中心，江苏 镇江 212000）

1 引言

启发式算法（heuristic algorithm）是一种根据人为经验或者自然规律所构造的算法，它能够在可接受的计算花费下给出一个较优的可行解。现阶段，由于元启发式算法（meta-heuristic）具有较少依赖算法本身组织结构的特点，其通用性强、泛化性好，已经被广泛应用在了实际生产和生活的各个领域。特别是针对工业中大量存在的NP-hard 问题，元启发式算法已成为求解此类问题的主要途径。在此，将针对具有代表性的四种算法：遗传算法（Genetic Algorithm，简称GA）、模拟退火算法（Simulated annealing algorithm，简称SA）、禁忌搜索算法（Tabu Search，简称TS）和蚁群算法（Ant Colony Optimization，简称ACO）进行基于其应用性能的对比分析。其中，遗传算法于1975 年被文献[1]提出，它借鉴了生物的进化过程，能够按照优胜略汰的原则对群体目标进行逐代演化；模拟退火算法于1953 年被文献[2]提出，它模拟了固体退火原理，能够通过对新解的动态概率接收来获得一个较优解；禁忌搜索算法于1986 年被文献[3]提出，它模拟了人类记忆过程，通过引入禁忌表来避免迂回搜索实现全局优化；蚁群算法于1992 年被文献[4]提出，该算法模拟了蚂蚁寻食过程中的路径发现行为，能够在正反馈机制的作用下逐渐增加对较优解的获得概率。以上四种元启发式算法，由于具有较好的适应性和求解效果，已经在路径规划[5-6]，资源调度[7-8]和参数优化[9-10]等多个方面得到了普遍应用。除此之外，为提高针对特定对象的优化能力，算法之间也能够通过模块耦合来实现其功能上的互补，例如混合遗传模拟退火算法[11-12]，遗传蚁群算法[13-14]，模拟退火蚁群算法[15-16]等。……