不同启发式初始化方法对基于二进制种群的优化算法性能的影响

《Journal of Computational Science》：The effect of different heuristic initialization approaches on the performance of binary population-based optimization algorithms

　　诺尔·阿尔丁·阿拉瓦德（Noor Aldeen Alawad）| 比拉尔·H·阿贝德-阿尔古尼（Bilal H. Abed-alguni）| 大卫·保罗（David Paul）| 穆罕默德·阿兹米·阿尔-贝塔尔（Mohammed Azmi Al-Betar）
阿拉伯联合酋长国艾因大学（Al Ain University）工程学院

**摘要**
在基于二进制人口的优化算法（Binary Population-Based Optimization Algorithms, BPOAs）中，种群初始化在实际问题的求解过程中起着关键作用，尤其是在特征选择问题上，它能显著提升算法收敛到最优解的速度。本研究在一个统一且受控的实验框架内，比较和评估了常用的启发式种群初始化方法。所有策略均基于相同的二进制差分进化（Binary Differential Evolution, BDE）算法，并使用相同的参数设置、适应度函数以及真实世界基准数据集进行评估，以确保公平比较。九种初始化方法分别从种群多样性、分类准确性和选定特征子集大小三个方面进行了评估。实验结果表明，与其他常用初始化方法相比，k-means聚类和Sobol准随机序列方法能够产生更高的种群多样性；当这些方法集成到同一BDE框架中时，在选择较小特征子集的情况下也能实现更优的分类准确性。相比之下，基于高斯扰动的初始化方法则表现出较低的多样性和较差的性能。这些发现强调了种群初始化对优化效果的重要影响，并为实际应用中的二进制种群优化提供了选择适当初始化策略的实用指导。

**引言**
优化技术因其在解决复杂实际问题中的关键作用而成为研究的热门领域。在优化问题中，目标是要找到一组决策变量的最优值，以最大化或最小化特定的目标函数[1]。决策变量有多种形式，包括二进制、连续型、离散型、排列型和结构化类型。优化问题的解空间通常非常庞大，存在大量可能的解决方案。在这其中识别最优值在很大程度上取决于具体优化问题的搜索空间结构。因此，学术界根据问题的复杂性对优化问题进行了分类，例如NP完全问题（NP-complete）和NP难问题（NP-hard）[2]。问题的复杂性和约束条件共同影响了优化算法的选择。因此，选择一个合适的优化算法对于有效解决问题的特定方面至关重要。

元启发式（Metahuristic, MH）算法是一类广泛的优化技术，它们从一组随机生成的初始解（即种群）开始。在每次迭代过程中，这些解通过智能操作符进行优化，这些操作符由精心选择的参数引导。这一过程在搜索空间的不同区域之间的探索与利用已有知识之间取得平衡，最终收敛到最优解。元启发式算法通常分为局部搜索方法和基于种群的方法[3]。本研究主要关注基于种群的元启发式算法的二进制变体。

基于二进制人口的优化算法（Binary Population-Based Optimization Algorithms, BPOAs）作为一种近似搜索方法，越来越受欢迎，被用于解决复杂或NP难的二进制优化问题[4, 5]，例如特征选择（Feature Selection, FS）、图着色（Graph Coloring）、背包问题（Knapsack Problem）和二次分配问题（Quadratic Assignment Problems）[8]。每年都有大量的新种群优化算法（Population-Based Optimization Algorithms, POAs）被提出，基于这些新算法，还会创造出数百甚至数千种二进制变体。值得注意的是，任何BPOA的基本结构几乎都是相同的。

除了BPOAs之外，基于二进制的局部搜索技术（Binary Local Search-Based Techniques, BLSTs），如二进制爬山法（Binary Hill Climbing[9]、[10]）、二进制禁忌搜索（Binary Tabu Search[11]）和二进制变邻域搜索（Binary Variable Neighborhood Search[12, 13, 14]）也是流行的近似搜索方法。BPOAs与BLSTs的不同之处在于，BPOAs通过一个或多个适应度函数反复优化整个可行解种群，而BLSTs则是通过特定的邻域移动操作符逐步改进单个可行解。

基本BPOA的优化框架通常包括两个阶段：初始化和优化。初始化阶段是配置算法参数及初始可行解种群的关键步骤；在优化阶段，BPOA利用精心设置的参数控制智能操作符，不断改进可行解种群以寻找最优解。第一阶段的成功往往能保证第二阶段的高效运行。保持初始种群的适当多样性通常也会带来更好的结果。因此，多样性是初始化阶段的一个关键因素。

多项研究强调了种群初始化在基于种群优化算法中的重要性，特别是初始种群多样性对提高搜索效率和整体算法性能的作用[5, 15, 16]。多样化的初始种群增加了探索不同搜索区域的可能性，有助于加速优化过程。因此，已经提出了多种增强BPOA中种群初始化的方法，包括基于对抗的学习（ Opposition-based Learning, OBL）[5]、折射学习（Refraction Learning, RL）[17]、Sobol准随机序列[16]和高斯扰动[18]。

尽管初始化技术层出不穷，但仍存在一些重要问题：这些方法之间有何差异？哪些方法能够生成最具多样性的种群？如何有效测量不同初始化策略的种群多样性？本文通过回顾和系统比较BPOAs中广泛使用的初始化方法来回答这些问题。

**本文的目标**
1. 提供对BPOAs中常用种群初始化策略的系统性、结构化综述，重点分析它们的机制和局限性（这些内容在以往研究中并未得到全面探讨）。
2. 通过使用多种多样性指标，确定哪些初始化方法能够生成最多样化的种群。

**实验设计与方法**
为了隔离初始种群的多样性，我们专注于一种BPOA算法——二进制差分进化算法（Binary Differential Evolution, BDE）。设计了九种基于BDE的基本算法版本，每种版本都融入了一种流行的初始化方法。随后，将这些版本应用于六个规模不一的真实世界数据集。模拟分析显示，k-means聚类和Sobol准随机序列（SQS）方法在所有初始化方法中展现出最高的初始种群多样性，并且在所有数据集中实现了最高的准确率和最小的特征集大小；相比之下，高斯扰动（GP）方法则导致最低的种群多样性和最差的表现。

**相关研究**
其他研究者也探讨了初始种群多样性的重要性。李等人[19]研究了初始种群与全局最优解之间的距离对优化性能的影响，发现这种距离与最终解的质量关联不大。阿古沙卡等人[20]提出了瞪羚优化算法（Gazelle Optimization Algorithm）并将其在基准优化问题上的有效性进行了评估，但他们并未对替代的种群初始化机制进行系统研究。本文的重点并非初始解与全局最优解的接近程度，而是在同一二进制差分进化框架内对多种种群初始化策略进行控制性比较。通过保持所有实验中的优化算法和参数设置一致，我们得以分析不同初始化机制对种群多样性和搜索行为的影响，从而深化了对初始化作用的理解。

**论文结构**
第2节提供了关于BPOA结构的一般背景信息，特别关注BDE框架。第2.2节介绍了如何将连续决策变量转换到二进制域的方法（包括几种转换函数）。第3节详细讨论了几种常用的BPOA初始化方法，并描述了种群多样性指标。第4节展示了实验结果。第5节总结了本文并提出了未来的研究方向。

**结论**
本研究深入探讨了不同初始化方法对基于二进制人口的差分进化优化算法性能的影响。结果表明，多样化的初始种群能够提高算法探索搜索空间的能力，从而提升优化效果。特别是k-means聚类和Sobol准随机序列（SQS）方法表现出色。

**作者贡献**
- 诺尔·阿尔丁·阿拉瓦德（Noor Aldeen Alawad）：撰写初稿、监督工作、软件开发、项目管理、方法论设计、数据分析、概念框架构建。
- 比拉尔·H·阿贝德-阿尔古尼（Bilal H. Abed-alguni）：撰写与编辑、数据验证、资源调配、调查分析、数据分析。
- 大卫·保罗（David Paul）：撰写与编辑、数据验证、资源调配、调查分析。
- 穆罕默德·阿兹米·阿尔-贝塔尔（Mohammed Azmi Al-Betar）：撰写与编辑、数据可视化、验证分析、数据整理。

**伦理声明**
本文未涉及任何涉及人类参与者或动物的实验研究。

**利益冲突声明**
作者声明不存在可能影响本文研究结果的已知财务利益冲突或个人关系。