关于计算机算法设计及其评价标准分析

李仟奕

【摘要】随着机器学习大热，一大批算法涌现出来。现实世界中的许多问题往往需要同时优化几个目标，这些目标在大多数情况下是冲突的。针对多目标优化问题，进化算法被验证是较为高效的。本文针对进化算法，首先概述进化算法的特点，随后再对其評价标准展开了简要分析。

【关键词】进化算法;机器学习;评价标准;多目标

在处理许多问题时，往往需要对多个目标进行考虑，用数学的方式来说就是同时对目标函数集合进行优化，这个过程称为多目标优化。在解决多目标优化问题时，多目标进化算法是较为常用的且高效的算法。其如此受欢迎的原因主要有以下几点：（1） 使用该类算法去解决问题时不需要对问题有预先只是，也就是说即使不了解问题也可以对其进行求解;（2） 该类基于种群的搜索方法能够在一次运行中获得多个解决方案，这能够保证决策者在最终多个解中选择自己偏向的方案;（3） 这类算法的全局搜索能力强，在负责的解空间能够进行全局搜索，善于跳出局部最优，找到全局最优解。

1 不同的多目标进化算法

1.1 多目标遗传算法

Goldberg提出了第一个处理多目标优化的遗传算法，并将选择建立在个体的非支配方面。其基本思想是，首先给所考虑的种群中的所有非支配个体分配等级1，然后将被分配等级的个体删除，随后找到相对于其余个体的新的非支配个体，并给它们分配等级2，以此类推，直到种群中的所有个体都被分配等级。

多目标遗传算法（MOGA）是由Fonseca和Fleming提出的。MOGA使用了进化个体之间的非支配关系来给他们计算等级。然而，有一个微小的区别。在被评价的种群中，局部的非支配个体，和以前一样，被赋予等级1。而被支配的个体，则以种群内支配它们的个体数量的继承者来排序[1]。

1.2 多目标粒子群算法

Raquel和Naval提出的多目标粒子群算法（MOPSO）结合了最近邻密度估计器的概念，用于选择全局最佳粒子，也用于从外部非主导解档案中删除粒子。当选择当前全局最优解时，根据密度估计器对非主导解的档案进行降序排序，并从列表的顶部随机选择一个粒子[2]。另一方面，当外部档案满了，它又会根据密度估计器的值按降序排序，并从列表的底部随机选择一个粒子进行删除。这种方法使用Coello等人提出的突变算子，其方式是只在流程开始的一定代数期间应用。最后，作者采用了NSGA-II中的约束处理技术。

1.3蚁群优化算法

蚁群优化（ACO）是一种用于解决困难的组合优化问题的元启发式方法。ACO的灵感来源是真实蚂蚁的信息素线索铺设和跟随行为，蚂蚁使用信息素作为通信媒介。通过与生物实例类比，ACO是基于由（人工）信息素踪迹为媒介的简单代理群体（称为（人工）蚂蚁）内部的间接通信。ACO中的信息素踪迹作为分布式的数字信息，被蚂蚁用来概率地 构建正在解决的问题的解决方案，并在算法执行过程中对其进行调整，以反映其搜索经验。在初始化参数和信息素轨迹后，主循环包括三个主要步骤。首先，蚂蚁根据信息素信息和可用的启发式信息，对所考虑的问题实例构建解。一旦蚂蚁完成了他们的解决方案，这些解决方案可能会在一个可选的局部搜索阶段进行改进。最后，在下一次迭代开始之前，信息素轨迹将被调整以反映蚂蚁的搜索经验[3]。

1.4 灰狼算法

灰狼算法（GWO）是最近提出的一种基于群智能的算法。GWO算法的灵感来自于自然界中的灰狼，即寻找猎物的最佳方式。GWO算法应用了自然界中相同的机制，它遵循狼群等级制度来组织狼群中的不同角色。在GWO中，狼群的成员根据狼的角色类型被分为四组，以帮助推进狩猎过程。这四组分别是阿尔法、贝塔、德尔塔和欧米伽，其中阿尔法代表了目前发现的最佳狩猎方案。在GWO论文原文中，为了符合自然界中灰狼的优势等级，将种群划分为四组[4]。该算法的设计者进行了大量的实验，观察到在基准问题和一组低维真实世界的案例研究中，考虑四组可以获得最佳的平均性能。然而，在解决大规模挑战性问题时，考虑更多或更少的群体可以作为未来的工作进行研究。

1.5 人工蜂群算法

人工蜂群（ABC）算法是一种基于蜂群的元启发式算法，由Karaboga提出，用于优化数值问题。它的灵感来自于蜜蜂的智能觅食行为。该算法具体基于Tereshko和Loengarov提出的蜜蜂群觅食行为模型。该模型由三个基本部分组成：受雇和失业的觅食蜂，以及食物来源。前两个组成部分，即就业和失业的觅食蜂，寻找丰富的食物来源，这是第三个组成部分，靠近它们的蜂巢。该模型还定义了两种领先的行为模式，这是自组织和集体智慧的必要条件：招募觅食者到丰富的食物来源导致正反馈，觅食者放弃差的来源导致负反馈。在ABC中，人工觅食蜂群（代理）寻找丰富的人工食物来源（给定问题的良好解决方案）。为了应用ABC，首先将考虑的优化问题转换为寻找使目标函数最小化的最佳参数向量的问题。然后，人工蜜蜂随机发现一组初始解向量，然后通过采用以下策略对其进行迭代改进：通过邻域搜索机制向更好的解发展，同时放弃差的解[5]。

2 多目标进化算法评价标准

多目标进化算法领域的一个重要问题是如何对算法的性能评价。由于一个多目标进化算法单次运行就可以得到一组非支配解，所以多目标进化算法的性能评价通常是指不同非支配解集的比较。目前已经提出了各种按性能评价指标来评价非支配解集的质量。例如，世代距离（GD）、反世代距离（IGD）、超体积（HV）、空间指标（Spacing）等等[6]。

世代距离计算的是算法结果集合M到参考集合M’的最小平均距离。计算值越小则说明算法获得的解集质量越好。它的优点是计算代价较小，消耗计算资源少，但具有仅度量解集的收敛性，无法评估多样性和依赖参考集的局限性。

反世代距离计算的是每个参考点到最近的算法获得的解的平均距离。值越小则算法的表现越好。相比于世代距离，它能够同时评价算法获得解的收敛性和多样性，同样，它消耗的计算资源也比较小。缺点与世代距离一样，也是需要参考集合。

超体积计算的是算法获得的解集与事先设定的参照点所围成的目标空间中区域的体积。值越大就说明算法表现性能更好。它能够再评价收敛性的同时也对种群的多样性进行评价。但它也一些不足，如它消耗较多的计算资源，每次计算一次超体积都会花费更多的时间，特别是当问题的规模和维度增加时，耗时更多。并且，预先设定的参考点比较难以确定，设定不同的参考点对最终的结果影响也很大。

空间指标计算的是算法最终收敛得到的每个解到其他解的最小距离的标准差。值越小就说明最终得到的解集分布越均匀。它的优点是能够很好的度量解集的均匀性，但同时这也是它的缺点，因为分布均匀的点不一定是广泛的，也就是说，不能保证算法最终获得的解是多样的。并且它也不能很好地度量解集的收敛性。

结束语

综上所述，可以得出在解决多目标优化问题方向，已经有许许多多不同的进化算法被提出，文中只列举了一些较为典型和经典的算法，这些算法都具有各自不同的特点，各自适合解决的问题也是不尽相同。凭借进化算法一次運行可以获取多个解方案以及其优秀的全局搜索特性，它的热度也仍在逐渐升高。同时，各种检验算法性能的评估标准也有许多，这里也仅仅列举了一些较为常用的评价指标。大多数评价指标都存在自身的优点和缺点，所以当评价某个具体进化算法的时候，通常都会选用多个评价指标来从多方面来评价性能。由此可见，对于进化算法和评价标准必须一起发展，相互促进，提升算法解决现实问题的能力。

{参考文献}

[1]王瑞琪，李珂，张承慧.基于混沌多目标遗传算法的微网系统容量优化[J].电力系统保护与控制，2011，39（22）：16-22.

[2]吴小刚，刘宗歧，田立亭，丁冬，杨水丽.基于改进多目标粒子群算法的配电网储能选址定容[J].电网技术，2014，38（12）：3405-3411.

[3]夏小云，周育人.蚁群优化算法的理论研究进展[J].智能系统学报，2016，11（01）：27-36.

[4]龙文，蔡绍洪，焦建军，伍铁斌.一种改进的灰狼优化算法[J].电子学报，2019，47（01）：169-175.

[5]刘三阳，张平，朱明敏.基于局部搜索的人工蜂群算法[J].控制与决策，2014，29（01）：123-128.

[6]胡涵，李振宇.多目标进化算法性能评价指标综述[J].软件导刊，2019，18（09）：1-4.

山东省青岛市黄岛区山东科技大学  山东青岛  250000