paretosearch 算法
paretosearch 算法概述
paretosearch 算法使用一组点上的模式搜索来迭代搜索非支配点。请参阅 多目标术语。模式搜索在每次迭代中满足所有边界和线性约束。
理论上，该算法收敛到接近真实帕累托前沿的点。有关收敛的讨论和证明，请参阅 Custòdio 等人的 [1]，其证明适用于具有 Lipschitz 连续目标和约束的问题。
paretosearch 算法的定义
paretosearch 在其算法中使用了许多中间量和容差。
| 数量 | 定义 |
|---|---|
| 等级 | 点的排名具有迭代定义。
|
| 体积 | 目标函数空间中满足不等式的点集 p 的超体积，对于每个指标 j， fi(j) < pi < Mi, 其中 fi(j) 是帕累托集中第 i 个目标函数值的第 j 个分量，Mi 是帕累托集中所有点的第 i 个分量的上界。在该图中，M 被称为参考点。图中的灰色阴影表示某些计算算法用作包含-排除计算的一部分的体积部分。
有关详细信息，请参阅 Fleischer [3]。
体积变化是停止该算法的一个因素。有关详细信息，请参阅停止条件。 |
| 距离 | 距离是衡量个体与其最近邻居的接近程度的标准。 该算法将极端位置上个体的距离设置为
该算法对每个维度分别进行排序，因此术语邻居表示每个维度上的邻居。 同一排名的个体，距离越大，被选择的机会就越大（距离越大越好）。 距离是计算扩散的一个因素，也是停止条件的一部分。有关详细信息，请参阅停止条件。 |
| 散布 | 扩展是帕累托集移动的量度。为了计算扩展，
当极端目标函数值在迭代之间变化不大（即，μ 较小）以及帕累托前沿上的点分布均匀（即，σ 较小）时，扩展较小。
|
ParetoSetChangeTolerance | 搜索的停止条件。当体积、扩展或距离在一个迭代窗口内的变化不超过 ParetoSetChangeTolerance 时，paretosearch 停止。有关详细信息，请参阅停止条件。 |
MinPollFraction | 在一次迭代期间要轮询的位置的最小比例。 当 |
paretosearch 算法示意图
初始化搜索
为了创建初始点集，paretosearch 默认根据问题边界从准随机样本中生成 options.ParetoSetSize 点。有关详细信息，请参阅 Bratley 和 Fox [2]。当问题的维度超过 500 时，paretosearch 使用拉丁超立方体采样来生成初始点。
如果分量没有边界，则 paretosearch 使用 -10 的人工下界和 10 的人工上界。
如果一个分量只有一个边界，则 paretosearch 将使用该边界作为宽度为 20 + 2*abs(bound) 的区间的端点。例如，如果某个分量没有上界，而下界为 15，则 paretosearch 使用的区间宽度为 20 + 2*15 = 55，因此使用人工上界为 15 + 55 = 70。
如果在 options.InitialPoints 中传递了一些初始点，那么 paretosearch 会使用这些点作为初始点。如果需要，paretosearch 会生成更多点，以获得至少 options.ParetoSetSize 个初始点。
然后 paretosearch 检查初始点以确保它们相对于边界和线性约束是可行的。如有必要，paretosearch 通过解决线性规划问题将初始点投影到线性可行点的线性子空间上。该过程可能导致一些点重合，在这种情况下，paretosearch 会删除所有重复的点。paretosearch 不会改变人工边界的初始点，只会改变指定的边界和线性约束。
移动点以满足线性约束后，如有必要，paretosearch 将检查这些点是否满足非线性约束。paretosearch 将对任何不满足所有非线性约束的点给予 Inf 的惩罚值。然后 paretosearch 计算剩余可行点的任何缺失的目标函数值。
注意
目前，paretosearch 不支持非线性等式约束 ceq(x) = 0。
创建档案和现任者
paretosearch 维护两组观点：
archive- 包含与低于options.MeshTolerance的网格大小相关的非支配点的结构体，并满足options.ConstraintTolerance内的所有约束。archive结构体包含的点不超过2*options.ParetoSetSize个，并且最初为空。archive中的每个点都包含一个相关的网格大小，即生成该点的网格大小。iterates- 包含非支配点和可能一些与较大网格大小或不可行性相关的支配点的结构体。iterates中的每个点都包含相关的网格大小。iterates包含的点不超过options.ParetoSetSize个。
轮询以找到更好的观点
paretosearch 从 iterates 轮询点，轮询的点从 iterates 中的点继承相关的网格大小。paretosearch 算法使用轮询来保持相对于边界和所有线性约束的可行性。
如果问题具有非线性约束，paretosearch 会计算每个轮询点的可行性。paretosearch 将不可行点的得分与可行点的得分分开保存。可行点的得分是该点的目标函数值向量。不可行点的得分是非线性不可行性的总和。
paretosearch 对 MinPollFraction 中的每个点至少轮询 iterates*(模式中的点数) 个位置。如果轮询的点相对于现任（原始）点至少有一个非支配点，则轮询被视为成功。否则，paretosearch 将继续轮询，直到找到非支配点或用尽模式中的点。如果 paretosearch 用尽了点并且没有产生非支配点，则 paretosearch 宣布轮询不成功并将网格大小减半。
如果轮询发现非支配点，paretosearch 会在成功的方向上反复扩展轮询，每次将网格大小加倍，直到扩展产生一个支配点。在此延长期间，如果网格大小超过 options.MaxMeshSize（默认值：Inf），则轮询停止。如果目标函数值减少到 -Inf，paretosearch 则表明问题无界并停止。
更新 archive 和 iterates 结构体
在轮询 iterates 中的所有点之后，该算法会将新点与 iterates 和 archive 结构中的点一起检查。paretosearch 计算每个点的排名或帕累托前沿数，然后执行以下操作。
标记所有在
archive中排名不为 1 的点以供删除。将新排名
1点标记为插入到iterates中。将
iterates中相关网格大小小于options.MeshTolerance的可行点标记为可行点，以便转移到archive。仅当
iterates中的主导点阻止新的非主导点添加到iterates时，才将其标记为删除。
然后 paretosearch 计算每个点的体积和距离测量值。如果 archive 因为标记点被包含而溢出，则体积最大的点占据 archive，其他点离开。类似地，标记为添加到 iterates 的新点按其体积的顺序进入 iterates。
如果 iterates 已满且没有支配点，则 paretosearch 不会向 iterates 添加任何点并宣告迭代失败。paretosearch 将 iterates 中的网格大小乘以 1/2。
停止条件
对于三个或更少的目标函数，paretosearch 使用成交量和价差作为停止措施。对于四个或更多目标，paretosearch 使用距离和扩展作为停止措施。在本次讨论的其余部分，paretosearch 使用的两种措施被称为适用措施。
该算法维护适用度量的最后八个值的向量。经过八次迭代之后，算法会在每次迭代开始时检查两个适用度量的值，其中 tol = options.ParetoSetChangeTolerance：
spreadConverged = abs(spread(end - 1) - spread(end)) <= tol*max(1,spread(end - 1));volumeConverged = abs(volume(end - 1) - volume(end)) <= tol*max(1,volume(end - 1));distanceConverged = abs(distance(end - 1) - distance(end)) <= tol*max(1,distance(end - 1));
如果任一适用测试是 true，则算法停止。否则，该算法将计算适用度量的傅里叶变换的平方项减去第一个项的最大值。然后，该算法将极大值与其删除的项（变换的直流分量）进行比较。如果删除的任一项大于 100*tol*(max of all other terms)，则算法停止。该测试本质上确定了测量序列没有波动，因此已经收敛。
此外，绘图函数或输出函数可以停止算法，或者算法可以因为超出时间限制或函数评估限制而停止。
返回值
该算法按如下方式返回帕累托前沿上的点。
paretosearch将archive和iterates中的点合并为一组。当目标函数有三个或更少时，
paretosearch从体积最大到体积最小返回点，最多返回ParetoSetSize个点。当目标函数有 4 个或更多时，
paretosearch将返回从距离最大到距离最小的点，最多返回ParetoSetSize个点。
并行计算和向量化函数求值的修改
当 paretosearch 以并行或向量化方式计算目标函数值（UseParallel 是 true 或 UseVectorized 是 true）时，算法会发生一些变化。
当
UseVectorized为true时，paretosearch会忽略MinPollFraction选项并评估模式中的所有轮询点。在并行计算时，
paretosearch依次检查iterates中的每个点，并从每个点执行并行轮询。返回轮询点的MinPollFraction部分后，paretosearch确定是否有任何轮询点主导基点。如果是这样，轮询被视为成功，并且任何其他平行评估都会停止。如果没有，则继续轮询，直到出现主导点或轮询完成。paretosearch对工作进程或以向量化方式执行目标函数评估，但不能同时执行两者。如果将UseParallel和UseVectorized都设置为true，则paretosearch会在工作进程进程上并行计算目标函数值，但不是以向量化的方式。在这种情况下，paretosearch会忽略MinPollFraction选项并评估模式中的所有轮询点。
快速运行 paretosearch
运行 paretosearch 的最快方法取决于几个因素。
如果目标函数评估很慢，那么使用并行计算通常是最快的。当目标函数评估速度很快时，并行计算的开销可能很大，但当目标函数评估速度很慢时，最好使用更多的计算能力。
注意
并行计算需要 Parallel Computing Toolbox™ 许可证。
如果目标函数评估不是很耗时，那么使用向量化评估通常是最快的。然而，情况并非总是如此，因为向量化计算会评估整个模式，而串行评估可能只占用模式的一小部分。尤其是在高维度中，评估的减少可能会导致某些问题的串行评估更快。
要使用向量化计算，您的目标函数必须接受具有任意行数的矩阵。每行代表一个需要评估的点。目标函数必须返回与其接受的行数相同的目标函数值矩阵，每个目标函数一列。对于单一目标讨论，请参阅 向量化适应度函数 (
ga) 或 向量化目标函数 (patternsearch)。
参考
[1] Custòdio, A. L., J. F. A. Madeira, A. I. F. Vaz, and L. N. Vicente. Direct Multisearch for Multiobjective Optimization. SIAM J. Optim., 21(3), 2011, pp. 1109–1140. Preprint available at https://www.researchgate.net/publication/220133323_Direct_Multisearch_for_Multiobjective_Optimization.
[2] Bratley, P., and B. L. Fox. Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Software 14, 1988, pp. 88–100.
[3] Fleischer, M. The Measure of Pareto Optima: Applications to Multi-Objective Metaheuristics. In "Proceedings of the Second International Conference on Evolutionary Multi-Criterion Optimization—EMO" April 2003 in Faro, Portugal. Published by Springer-Verlag in the Lecture Notes in Computer Science series, Vol. 2632, pp. 519–533. Preprint available at https://api.drum.lib.umd.edu/server/api/core/bitstreams/4241d9c0-f514-4a41-bd58-07ac2538d918/content.
