基于指标选择的多目标搜索算法（IBEA）详解
基于指标选择的多目标搜索算法（IBEA）详解
在多目标优化领域，如何将决策者的偏好信息整合到搜索算法中是一个重要问题。本文介绍了一种基于指标选择的多目标搜索算法（IBEA），该算法能够灵活适应用户偏好，且无需额外的多样性保护机制。通过与NSGA-II和SPEA2等流行算法的比较，IBEA在多个基准问题上展现了显著优势。
算法简介
多目标优化的目标通常是找到帕累托最优解集的良好近似值。然而，对于什么是帕累托集的良好近似并没有通用定义，这取决于用户的特定偏好。例如，可以将目标形式化为最大化由结果逼近主导的客观空间的超体积。但这种定义在某些情况下可能并不适用，因为优化目标可能因每个决策者和问题而异。
针对这一问题，本文提出了一种通用的基于指标的进化算法（IBEA）。其主要思想是根据优势关系的连续泛化来形式化偏好，这导致了一个简单的算法概念。因此，IBEA不仅可以适应任意的偏好信息和优化场景，而且不需要任何多样性保护技术。IBEA更通用，因为总体大小可以是任意的，而且更快，因为它只比较成对的个体，而不是整个近似集。结果表明，所提出的方法可以显著提高生成的Pareto集近似的质量。
绪言
在评估Pareto集近似质量时，常用两种指标：Iε+指标和IHD指标。
Iε+指标
Iε+指标给出了一个Pareto集近似在每个维度上需要平移的最小距离，使得另一个近似被弱支配。假设A点即X1，B点即X2：
- 对于垂直方向：f垂直方向（A）−f垂直方向（B）>0
- 对于水平方向：f水平方向（A）−f水平方向（B）<0
𝜖 >= fi(x1)-fi(x2), for i in {1，，，n}，这是代表 ϵ 对每一个fi(x)均需满足 ,所以 ϵ 应大于最大正差距，即垂直方向上的值（该值是大于0 的）。又因为我们要最小化该值，所以𝐼应取最大的正差距，即该图中A与B的水平方向上的差值。
二进制质量指标I表示为优势保持。
IHD指标
IHD指标基于超体积概念，用于测量由集合B支配但不由集合A支配的空间体积。虽然对于包含多个决策向量的近似计算IHD(A,B)值在计算上较为昂贵，但在比较两个决策向量时，其计算复杂度为O(n)。
基本算法
约定：α表示种群大小，N表示最大迭代次数，
step1: 产生初始种群P，种群大小为α，当前迭代此时m=0
step2: 适应度计算，根据以下公式计算P里个体的适应度，例如x1∈P（k为比例缩放因子，参数）
k是一个大于0的比例缩放因子，实验结果表明k=0.05时算法能取得较好的结果
step3: 对每一代P，执行如下运算（缩减），直到种群大小为α
- 选择适应度最小的解
- 从种群中去掉该解
- 更新剩余解的适应度值
step4: 终止条件判断
step5: p’ 为p 的复制，
step6: 用交叉变异作用在p’上，p=p’+p，m=m+1，转step2。
提高鲁棒性（自适应IBEA）
为了提高算法的鲁棒性，可以采用自适应策略调整参数k的值。通过监测算法的收敛速度和多样性保持情况，动态调整k值，使算法在不同问题上都能保持良好的性能。
测试结果
在ZDT6测试函数上，IBEA展现了其优越性。下图展示了IBEA与其他算法在ZDT6上的对比结果：
从图中可以看出，IBEA在保持解的多样性和收敛性方面都优于其他算法。
总结
IBEA作为一种基于指标选择的多目标搜索算法，通过直接在选择过程中使用性能指标，能够灵活适应用户的偏好信息，且不需要额外的多样性保护机制。实验结果表明，IBEA在多个基准问题上都能显著改善优化结果，展现了其在多目标优化领域的潜力和优势。