多目标优化工具

pygmo.fast_non_dominated_sorting(points)

在输入的points上运行快速非支配排序算法

Parameters

points (2d-array-like object) – 输入的点

Raises

• ValueError – 如果 points 格式不正确

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

(ndf, dl, dc, ndr), 其中:

• ndf (list of 1D NumPy int array): 非支配前沿

• dl (list of 1D NumPy int array): 支配列表

• dc (1D NumPy int array): 支配计数

• ndr (1D NumPy int array): 非支配等级

Return type

tuple

示例

>>> import pygmo as pg
>>> ndf, dl, dc, ndr = pg.fast_non_dominated_sorting(points = [[0,1],[-1,3],[2.3,-0.2],[1.1,-0.12],[1.1, 2.12],[-1.1,-1.1]])

---

pygmo.nadir(points)

计算一组点（即目标向量）的最低点。最低点是在非支配前沿的点中具有目标函数最大值的点。

复杂度为 \(\mathcal{O}(MN^2)\)，其中 \(M\) 是目标的数量，\(N\) 是点的数量。

Parameters

points (2d-array-like object) – 输入的点

Raises

• ValueError – 如果 points 格式不正确

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

最低点

Return type

一维NumPy浮点数数组

---

pygmo.ideal(points)

计算一组点的理想点，即目标向量。理想点是在每个组件中具有输入点目标函数最小值的点。

复杂度为\(\mathcal{O}(MN)\)，其中\(M\)是目标的数量，\(N\)是点的数量。

Parameters

points (2d-array-like object) – 输入的点

Raises

• ValueError – 如果 points 格式不正确

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

理想点

Return type

一维NumPy浮点数数组

---

pygmo.pareto_dominance(obj1, obj2)

如果 obj1 Pareto 支配 obj2，则返回 True，否则返回 False。假设为最小化。

比较obj1和obj2中的每一对对应元素：如果obj1中的所有元素都小于或等于obj2中的对应元素，但至少有一个不同，将返回True。否则，将返回False。

Parameters

• obj1 (数组类对象) – 第一个目标列表

• obj2 (类似数组的对象) – 第二个目标列表

Raises

• ValueError – 如果 obj1 和 obj2 的维度不同

• TypeError – 如果 obj1 或 obj2 无法转换为浮点数向量的向量

Returns

True 如果 obj1 支配 obj2，False 否则。

Return type

bool

示例

>>> import pygmo as pg
>>> pg.pareto_dominance(obj1 = [1,2], obj2 = [2,2])
True

---

pygmo.non_dominated_front_2d(points)

找到一组二维目标的非支配前沿。复杂度为\(\mathcal{O}(N \log N)\)，因此低于调用fast_non_dominated_sorting()的复杂度。

参见：Jensen, Mikkel T. “减少多目标进化算法的运行时间复杂性：NSGA-II及其他算法。” IEEE 进化计算汇刊 7.5 (2003): 503-515.

Parameters

points (2d-array-like object) – 输入的点

Raises

• ValueError – 如果 points 包含的不是二维目标

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

非支配前沿

Return type

一维NumPy整数数组

示例

>>> import pygmo as pg
>>> pg.non_dominated_front_2d(points = [[0,5],[1,4],[2,3],[3,2],[4,1],[2,2]])
array([0, 1, 5, 4], dtype=uint64)

---

pygmo.crowding_distance(points)

拥挤距离的实现。复杂度为\(O(M N \log N)\)，其中\(M\)是目标的数量，\(N\)是个体的数量。该函数假设points包含一个非支配前沿。不满足此条件将导致未定义的行为。

参见：Deb, Kalyanmoy, 等人。 “一种用于多目标优化的快速精英非支配排序遗传算法：NSGA-II。” 自然并行问题解决 PPSN VI。 施普林格柏林海德堡，2000年。

Parameters

points (2d-array-like object) – 输入的点

Raises

• ValueError – 如果 points 不包含至少两个点，或者格式不正确

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

拥挤距离

Return type

一维NumPy浮点数数组

示例

>>> import pygmo as pg
>>> pg.crowding_distance(points = [[0,5],[1,4],[2,3],[3,2],[4,1]])
array([inf,  1.,  1.,  1., inf])

---

pygmo.sort_population_mo(points)

对一个多目标、无约束的种群（这里指的是一个包含目标向量的二维数组）进行排序，遵循以下严格顺序：

• \(f_1 \prec f_2\) 如果非支配等级满足 \(i_1 < i_2\)。如果 \(i_1 = i_2\)， 那么 \(f_1 \prec f_2\) 如果拥挤距离满足 \(d_1 > d_2\)。

复杂度为 \(\mathcal{O}(M N^2)\)，其中 \(M\) 是目标向量的大小，\(N\) 是个体的数量。

注意

此函数也适用于单目标优化，即目标向量大小为1的情况，但在这种情况下，使用Python内置的排序方法会更高效。

Parameters

points (2d-array-like object) – 输入的目标向量

Raises

• 未指定 – 由pygmo.fast_non_dominated_sorting()和pygmo.crowding_distance()抛出的所有异常

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

排序后的目标向量的索引。

Return type

一维NumPy整数数组

示例

>>> import pygmo as pg
>>> pop = pg.population(prob = pg.dtlz(prob_id = 3, dim=10, fdim=4), size = 20)
>>> pg.sort_population_mo(points = pop.get_f()) 
array([ 4,  7, 14, 15, 16, 18,  9, 13,  5,  3,  6,  2, 12,  0,  1, 19, 17, 8, 10, 11])

---

pygmo.select_best_N_mo(points, N)

返回（无序）多目标、无约束种群中的最佳N个个体，（此处意图为一个包含目标向量的2D类数组）。使用的严格排序与sort_population_mo()中定义的相同。

复杂度为 \(\mathcal{O}(M N^2)\)，其中 \(M\) 是目标的数量，\(N\) 是个体的数量。

虽然复杂度与sort_population_mo()相同，但此函数在可能的情况下更受青睐，因为它避免计算所有个体的拥挤距离，而仅计算包含在最佳N中的最后一个非支配前沿的个体的拥挤距离。

如果N为零，将返回一个空数组。

Parameters

• points (2d-array-like object) – 输入的目标向量

• N (int) – 返回的最佳列表的大小。

Raises

• 未指定 – 由pygmo.fast_non_dominated_sorting() 和 pygmo.crowding_distance() 抛出的所有异常

• TypeError – 如果 points 无法转换为浮点数向量的向量

Returns

N 个最佳目标向量的索引。

Return type

一维NumPy整数数组

示例

>>> import pygmo as pg
>>> pop = pg.population(prob = pg.dtlz(prob_id = 3, dim=10, fdim=4), size = 20)
>>> pg.select_best_N_mo(points = pop.get_f(), N = 13) 
array([ 2,  3,  4,  5,  6,  7,  9, 12, 13, 14, 15, 16, 18])

---

pygmo.decompose_objectives(objs, weights, ref_point, method)

分解目标向量。

使用分解技术将目标向量简化为仅一个目标。

这里提供了三种不同的method可能性：

• 加权分解，

• 切比雪夫分解，

• 边界拦截方法（带有惩罚约束）。

在\(n\)个目标的情况下，我们用：\(\mathbf f(\mathbf x) = [f_1(\mathbf x), \ldots, f_n(\mathbf x)]\)表示包含原始多个目标的向量，用：\(\boldsymbol \lambda = (\lambda_1, \ldots, \lambda_n)\)表示一个\(n\)维权重向量，用：\(\mathbf z^* = (z^*_1, \ldots, z^*_n)\)表示一个\(n\)维参考点。我们还假设\(\lambda_i > 0, \forall i=1..n\)且\(\sum_i \lambda_i = 1\)。

因此，最终的单目标定义为：

• 加权分解: \(f_d(\mathbf x) = \boldsymbol \lambda \cdot \mathbf f\)

• 切比雪夫分解: \(f_d(\mathbf x) = \max_{1 \leq i \leq m} \lambda_i \vert f_i(\mathbf x) - z^*_i \vert\)

• 边界拦截方法（带惩罚约束）：\(f_d(\mathbf x) = d_1 + \theta d_2\)

其中 \(d_1 = (\mathbf f - \mathbf z^*) \cdot \hat {\mathbf i}_{\lambda}\) , \(d_2 = \vert (\mathbf f - \mathbf z^*) - d_1 \hat {\mathbf i}_{\lambda})\vert\) , 并且 \(\hat {\mathbf i}_{\lambda} = \frac{\boldsymbol \lambda}{\vert \boldsymbol \lambda \vert}\)

请注意，虽然ref_point是必需的，但它不会影响如上所示的weighted方法的计算。

Parameters

• objs (数组类对象) – 目标向量

• weights (数组类对象) – 权重 \(\boldsymbol \lambda\)

• ref_point (数组类对象) – 参考点 \(\mathbf z^*\)。如果 method 是 "weighted"，则不使用它。

• method (str) – 分解方法：其中之一是 "weighted", "tchebycheff" 或 "bi"

Raises

• ValueError – 如果 objs、weight 和 ref_point 的大小不同，或者如果 method 不是 "weighted"、"tchebycheff" 或 "bi" 之一。

• TypeError – 如果 weights 或 ref_point 或 objs 无法转换为浮点数向量。

Returns

一个包含分解目标的一维数组。

Return type

一维NumPy浮点数数组

示例

>>> import pygmo as pg
>>> pg.decompose_objectives(objs = [1,2,3], weights = [0.1,0.1,0.8], ref_point=[5,5,5], method = "weighted") 
array([ 2.7])
>>> pg.decompose_objectives(objs = [1,2,3], weights = [0.1,0.1,0.8], ref_point=[0,0,0], method = "weighted") 
array([ 2.7])
>>> pg.decompose_objectives(objs = [1,2,3], weights = [0.1,0.1,0.8], ref_point=[5,5,5], method = "tchebycheff") 
array([ 1.6])

---

pygmo.decomposition_weights(n_f, n_w, method, seed)

生成所需数量的权重向量，用于分解多目标问题。有三种方法可用：

• "grid" 在均匀网格上生成权重。此方法只能在请求生成的权重数量使得均匀网格确实可能的情况下使用。在二维情况下，这总是可能的，但在更高维度中，均匀网格仅在特殊情况下可能。

• "random" 生成权重，随机均匀分布在单纯形上（权重满足 \(\sum_i \lambda_i = 1\)）

• "low discrepancy" 使用低差异序列生成权重，最终获得更好的帕累托前沿覆盖。由于目标数量预计为低维度（即少于20），因此使用Halton序列被认为是合适的。

注意

所有方法都保证在单纯形上生成权重（\(\sum_i \lambda_i = 1\)）。所有权重生成方法都保证首先生成规范权重 [1,0,0,…], [0,1,0,..], …。

Parameters

• n_f (int) – 目标向量的数量

• n_w (int) – 权重的数量 \(\boldsymbol \lambda\)

• method (str) – 权重生成方法：其中之一为 "grid", "random", 或 "low discrepancy"

• seed (int) – 内部随机数生成器使用的种子

Raises

• OverflowError – 如果 n_f, n_w 或 seed 为负数或大于实现定义的值

• ValueError – 如果 n_f 和 n_w 与所选的权重生成方法不兼容，或者如果 method 不是 "grid", "random" 或 "low discrepancy" 之一

Returns

生成的权重

Return type

2D NumPy 浮点数数组

示例

>>> import pygmo as pg
>>> pg.decomposition_weights(n_f = 2, n_w = 6, method = "low discrepancy", seed = 33) 
array([[ 1.   ,  0.   ],
       [ 0.   ,  1.   ],
       [ 0.25 ,  0.75 ],
       [ 0.75 ,  0.25 ],
       [ 0.125,  0.875],
       [ 0.625,  0.375]])