可伸缩的高维约束基准和算法

​ 在过去二十年里,进化约束多目标优化受到了广泛的关注和研究,并且已经提出了一些基准测试约束多目标进化算法(CMOEAs)。特别地,约束函数与目标函数值有紧密的联系,这使得约束特征太单调并且与真实世界的问题不同。因此,之前的CMOEAs不能特别好的解决现实问题,这些问题涉及多态或者非线性特征的决策空间约束。因此,我将介绍一个新的基准框架和设计一个合适的可伸缩的高维决策空间约束的新测试函数。具体来说,不同的高维约束函数和变量之间的复杂联系与现实特征都有紧密联系。在这个框架里,提供了许多的参数接口,以便用户可以比较容易地调整参数获得不同的函数,并且可以测试算法的性能。现已存在不同类型的CMOEAs被用来测试已经提出的测试函数,但是结果很容易陷入局部可行区域。因此我也会介绍一个基于多任务CMOEA去更好的处理这些问题,这个算法有一个新的搜索算法去提高种群的搜索能力。

SDC基准

​ SDC(Scalable High-Dimensional Constraint)有以下特征:

  1. 在决策空间中构造约束,以便建立单峰或多峰约束;
  2. 可伸缩变量与距离函数相关,这可以使约束困难可调节;
  3. 可伸缩变量与距离函数相关,这可以使收敛性困难得到调节;
  4. 设置CPF(Constraint Pareto Front)和UPF(unconstraint Pareto Front)之间的重叠度来测试算法局部调整种群分布的能力

SDC框架

如图所示,SDC框架可以定义不同的层次和把变量分成不同的组。

Objective level:在这个层次里,变量被分为两部分,形状函数变量和距离函数变量。形状函数变量用于形状函数,这可以控制UPS(unconstraint Pareto Solution)与UPF(unconstraint Pareto Front)的形状和位置。距离函数变量用于距离函数,以便增加收敛难度。

Variable linkage level:为了强制变量联动使距离函数的最优解旋转,距离函数变量通常与形状函数变量中的第一个变量相关联。因此,我们把距离函数变量分为两部分,并且只有后一部分是强制变量联动。

Constraint level:在这个层里,变量 x
1
s
,…,x
a1
s
被改写为 x
1
lc
,…,x
a1
lc
,因为它们被用来构造低维度约束变量(LCV)。LCV是用在低维度约束函数中,它可以控制CPS的位置和形状。除此之外,为了提高约束的复杂性,引入了高维度约束,并且与高维度约束相关的变量 x
1
hc
,…,x
a2
hc
(HCV(high-dimension constraint variable))。可伸缩HCV x
1
sc
,…,x
a3,1
sc
(SHCV(Scalable HCV))可通过转化操作变为THCV(transformed HCV)。

​ 基于以上定义,可以生成以下测试函数公式:

d
1
是CEC2006的约束问题,d
2
是距离函数,g
1
和g
2
分别代表低维度约束和高维度约束。

​ SDC框架里的一些重要观点:

  1. 统一的搜索空间:可以看出 x
    sc
    与 x
    thc
    和 x
    ud
    都有关系,因此,最优解 x
    sc,*
    应当同时满足 d
    2
    == 0 和 g
    2
    == 0。然而,d
    2
    和 g
    2
    可能有不同的搜索范围。为了使不同范围的形状函数、约束函数和距离函数能在SDC 框架中使用,需要定义一个统一的搜索空间。每一个变量有一个固定的范围 [0 , 1]。当计算任何形状、约束和距离函数,首先将变量从统一搜索空间映射到真正的搜索范围。除此之外,变量联动和转化操作都在统一搜索空间实现。
  2. 高维约束函数和距离函数的难度分离控制:现已存在的形状函数和高维度约束函数,它们都有一个固定的维度,例如,a
    1
    和 a
    2
    是固定的。因此对一个D维向量, a
    3
    是固定的。当 a
    3,1
    增加,a
    3
    是固定的,g
    2
    的难度将会增加,而 d
    2
    将不会改变。同样的,当a
    3,1
    固定,a
    3
    增加时,g
    2
    的难度将不会改变,而d
    2
    的难度将会增加。因此,高维度约束函数和距离函数的难度可以控制。
  3. 高维度约束的可伸缩难度:因为CEC2006 函数不可伸缩,它的难度直接调整。为了使它可伸缩,我们使用SHCV 和HCV 获得 THCV,如下图所示。

形状函数(shape functions)

​ 形状函数( h(x
s
)) 的作用是控制UPF的位置和形状。除此之外,当约束 g
1
(x
lc
) 增加时,可以控制CPF的位置和形状。因此,我们可以控制CPF 和 UPF 的关系来检验算法局部调整种群分布的能力。这里有两种调整函数,其中一个的公式如下:

参数 b 可以控制可行区域的位置,不同的值可以使得可行域旋转。另一个调整函数的公式如下:

参数b 可以控制UPF 和 CPF 之间的重叠度,不同的值可以改变可行区域。

高维度约束函数

​ 选择高维度约束函数一会重要的问题是接近现实问题的实质。CEC2006 函数集可以满足真实的约束多目标优化问题,除此之外,CEC2006 函数提高了优化可行目标值。

转换函数

​ 为了保证优化解得到存在,x
thc
的范围应该在[0 , 1]。上图中的x
t
代表参与转换操作的变量集,这里设计了两种转换函数:

距离函数

​ 如图所示,提供了五个距离函数。

​ 除此之外,变量的联系函数在决策空间不同位置中被用来改变最优解,这里也有两种函数:

在公式中,这里设置了一个参数(DTC)来控制 [DCT * x
d,2
]中的x
d,2
变量参与变量的联系。

IMCMO算法

  1. 动态辅助任务分配

    • 算法中引入了辅助任务,为每个主任务分配一个动态变化的辅助任务。
    • 辅助任务的目的是帮助共享和传递有价值的信息,以提高整体优化性能。
  2. 多目标优化

    • 该算法专注于同时处理多个目标函数,以便获得一组帕累托最优解。
    • 通过维护帕累托最优解集合来实现多目标优化的目标。
  3. 演化多任务学习

    • 算法利用演化多任务学习的方法,通过任务间的知识共享来提高收敛速度和全局搜索能力。
    • 任务之间的交叉和突变促进信息传递,有助于优化过程中各任务之间的协作。
  4. 约束处理

    • 对于受约束的多目标优化问题,算法设计了有效的约束处理策略。
    • 这可能涉及罚函数、约束处理技术等方法,以确保生成的解满足所有的约束条件。
  5. 动态性与自适应性

    • 该算法具有一定的动态性和自适应性,可以根据优化过程中的需求和变化来调整任务分配和资源分配策略。
    • 动态地适应不同的优化场景,并根据需要灵活调整算法参数。

通过结合多目标优化、动态任务分配和演化多任务学习等技术,这种算法能够有效解决受约束的多目标优化问题,并在复杂的优化环境中取得良好的性能表现。

以下是算法伪代码:


标签: none

添加新评论