Paretosearch算法

`paretosearch`算法

`paretosearch`算法概述

的paretosearch该算法利用一组点的模式搜索来迭代搜索非占优点。看到多目标术语．模式搜索满足每个迭代的所有界限和线性约束。

理论上，该算法收敛于真帕累托前沿附近的点。关于收敛性的讨论和证明，请参见Custòdio等。［1］，其证明适用于具有Lipschitz连续目标和约束的问题。

定义`paretosearch`算法

paretosearch在算法中使用了一些中间量和容差。

数量	定义
排名	点的秩具有迭代定义。非劣势点的排名是1。对于任何整数`k`> 1，一分有秩`k`当唯一占主导地位的分数的排名严格低于`k`．
体积	点集的超体积p在满足不等式的目标函数空间中，对于每一个指标j， f_我（j) <p_我_我，哪里f_我（j)是我第Th分量j目标函数在Pareto集合中的值，M_我是一个上限我Pareto集合中所有点的第th分量。在这个图中，M被称为参考点。图中的灰色阴影表示一些计算算法用作包含-排除计算的部分体积。有关详细信息，请参阅Fleischer［3］． `paretosearch`仅当非支配点数超过目标数时计算体积。`paretosearch`使用参考点M =`马克斯(pts, [], 1) + 1`．在这里,`PTS.`是一个矩阵，其行是点。体积变化是停止算法的一个因素。有关详细信息，请参阅停止条件．
距离	距离是对其最近邻居个人的近距离的衡量标准。的`paretosearch`该算法测量同一等级个体之间的距离。该算法测量目标函数空间中的距离。该算法将极端位置的个体距离设置为`正`．对于其余的个体，该算法将距离计算为个体排序后的邻居之间的标准化绝对距离的维数之和。换句话说，对于维度`米`并对每个人进行分类、缩放`我`： `x(m,i+1) - x(m,i-1)`．算法对每个维度分别进行排序，所以术语邻居表示每个维度上的邻居。与距离高相同等级的人具有更高的选择机会（更高距离更好）。距离是计算价差的一个因素，价差是停止标准的一部分。有关详细信息，请参阅停止条件．
传播	价差是衡量帕累托集合移动的一个指标`paretosearch`算法首先评估σ，是距离有限的帕累托前沿点拥挤距离度量的标准差。问是这些要点的数量，还有d是这些点之间的平均距离测量。该算法然后评估μ的和`k`目标函数索引的常量常量折射点与前一个迭代中该索引的最小点的差异。那么蔓延就是 `传播`= (μ+σ) / (μ+量子点)．当极端目标函数值在迭代之间变化不大时（即，μ当帕累托前沿上的点均匀分布时（即，σ是小的)。 `paretosearch`使用停止条件的传播。当传播不会变化时，迭代停止。有关详细信息，请参阅停止条件．
`ParetoSetChangeTolerance`	搜索的停止条件。`paretosearch`当音量、传播或距离的变化不超过`ParetoSetChangeTolerance`在迭代窗口上。有关详细信息，请参阅停止条件．
`MinPollFraction`	迭代期间要轮询的位置的最小分数。`paretosearch`调查至少`MinPollFraction`*（模式中的点数）位置。如果轮询点数给出非支配点数，则认为轮询成功。否则，`paretosearch`继续轮询，直到找到一个非主导点或在模式中耗尽所有点。此选项不适用于`使用矢量化`选择是`符合事实的`那样的话`paretosearch`民意调查所有模式点。

的草图`paretosearch`算法

初始化搜索

要创建初始点集，paretosearch生成选项。ParetoSetSize基于问题边界的拟随机样本点，默认情况下。详情请参见Bratley和Fox［2］．当问题的维度超过500时，paretosearch使用拉丁超级采样生成初始点。

如果一个组件没有边界，paretosearch使用的人为下限-10和一个人工的10．

如果一个组件只有一个边界，paretosearch使用绑定为宽度间隔的端点20 + 2 * abs(绑定)．例如，如果一个分量没有上界，而下界是15，paretosearch使用20 + 2 * 15 = 55的间隔宽度，因此使用15 + 55 = 70的人工上限。

如果你传入一些初始点选项。InitialPoints,然后paretosearch使用这些点作为初始点。paretosearch必要时生成更多点，以至少获得选项。ParetoSetSize初始点。

paretosearch然后检查初始点，以确保它们相对于边界和线性约束是可行的。如果有必要,paretosearch通过求解一个线性规划问题，将初始点投影到线性可行点的线性子空间上。在这种情况下，这个过程会导致一些点重合paretosearch删除任何重复的点。paretosearch对人工边界不改变初始点，只对指定的边界和线性约束。

移动点满足线性约束后，如有必要，paretosearch检查点是否满足非线性约束。paretosearch给出的惩罚值为正到任何不满足所有非线性约束的点。然后paretosearch计算剩余可行点的任何缺失目标函数值。

请注意

目前，paretosearch不支持非线性平等约金宝app束CEQ（x）= 0．

创建归档和现有人员

paretosearch维护两组点：

存档-包含与下面网格大小相关的非主导点的结构选项。MeshTolerance并满足所有的限制选项.约束容忍度．的存档结构只包含2 * options.paretosetsize.点和最初是空的。每一个点的存档包含相关的网格大小，这是生成点的网格大小。
迭代- 含有NondOminated积分的结构，并且可能有一些与较大网格尺寸或不可缺点相关的主导点。每一个点的迭代包含相关的网格大小。迭代不包含更多选项。ParetoSetSize点。

民意调查找到更好的积分

paretosearch从迭代，其中轮询点继承中的点的关联网格大小迭代．的paretosearch该算法使用一个轮询来保持边界和所有线性约束的可行性。

如果问题有非线性约束，paretosearch计算每个民意调查点的可行性。paretosearch将不可行点的得分与可行点的得分分开。可行点的得分是该点目标函数值的向量。不可行点的得分是非线性不可行的总和。

paretosearch调查至少MinPollFraction*(图案上的点数)每个点的位置迭代．如果民调点相对于现有(原始)点至少给出一个非主导点，则认为投票成功。否则,paretosearch继续轮询，直到找到一个非主导点或在模式中耗尽所有点。如果paretosearch耗尽点且不产生非支配点，paretosearch声明轮询不成功并将网格大小减半。

如果民意调查发现非统计点，paretosearch在成功的方向上重复扩展轮询，每次将网格大小加倍，直到扩展生成支配点。在此扩展过程中，如果网格大小超过选项。MaxMeshSize(默认值:正)，则轮询停止。如果目标函数值降至负，paretosearch声明问题没有边界并停止。

更新`存档`和`迭代`结构

在轮询所有点迭代，该算法将检查新点和迭代和存档结构。paretosearch计算每个点的等级或帕累托前编号，然后执行以下操作。

对所有排名不为1的分数做删除标记存档．
马克的新秩1插入点迭代．
标记可行的点迭代谁的关联网格尺寸小于选项。MeshTolerance为转移存档．
标记主导地点迭代仅当它们阻止将新的非支配点添加到迭代．

paretosearch然后计算每个点的体积和距离。如果存档由于包含标记点的结果将溢出，那么占据最大占据的点存档，其他人离开。同样，标记为添加到迭代进入迭代按卷的顺序排列。

如果迭代是满的，没有劣势点，是吗paretosearch没有要点迭代并声明迭代是不成功的。paretosearch将网格尺寸乘以迭代1/2。

停止条件

对于三个或更少的目标函数，paretosearch使用卷并作为停止措施传播。对于四个或更多目标，paretosearch使用距离和扩展作为停止度量。在本讨论的其余部分中，以下两个度量paretosearch用途表示可应用的措施。

该算法维护适用措施的最后八个值的向量。八次迭代后，算法检查每次迭代开始时的两个适用措施的值托尔=选项。ParetoSetChangeTolerance：

散差= ABS（扩展（端1） - 扩展（终端））<= TOL * MAX（1，扩展（端 - 1））;
VolumeCoverged=abs（容积（末端-1）-容积（末端））<=tol*max（1，容积（末端-1））；
distanceConverged = abs(distance(end - 1) - distance(end)) <= tol*max(1,distance(end - 1)); / /结束

如果其中一个适用的测试是符合事实的，算法停止。否则，该算法计算适用措施的傅立叶变换的Squared术语的最大值减去第一项。然后，算法将最大值与其删除的术语进行比较（变换的DC分量）。如果要么删除术语大于100*tol*(不超过其他所有条款)，然后算法停止。此测试基本上确定度量序列没有波动，因此已收敛。

此外，绘图函数或输出函数可以停止算法，或者算法可以因为超过时间限制或函数求值限制而停止。

返回值

该算法返回帕累托前沿上的点，如下所示。

paretosearch把这些点结合起来存档和迭代一组。
当有三个或更少的目标函数时，paretosearch返回从最大体积到最小体积（最多）的点ParetoSetSize点。
当有四个或更多客观函数时，paretosearch返回从最大距离到最小距离的点ParetoSetSize点。

并行计算和矢量化函数求值的改进

什么时候paretosearch以并行或向量化方式计算目标函数值(UseParallel是符合事实的或使用矢量化是符合事实的），算法存在一些变化。

什么时候使用矢量化是符合事实的，paretosearch忽略了MinPollFraction选择并评估模式中的所有投票站。
并行计算时，paretosearch顺序检查每个点迭代并从每个点执行一个平行轮询。回国后MinPollFraction投票点的分数，paretosearch确定是否有任何民意调查点占主导地位基点。如果是这样，轮询被视为成功，并且任何其他并行评估都停止了。如果没有，轮询仍在继续，直到出现主导点或轮询完成。
paretosearch对工人或以矢量化方式执行目标函数评估，但不能两者兼顾。如果你同时设置UseParallel和使用矢量化到符合事实的，paretosearch在辅助对象上并行计算目标函数值，但不是以矢量化方式。在本例中，paretosearch忽略了MinPollFraction选择并评估模式中的所有投票站。

跑`paretosearch`迅速地

最快的跑步方式paretosearch取决于几个因素。

如果目标函数计算很慢，那么使用并行计算通常是最快的。当目标函数计算速度较快时，并行计算的开销可能非常大，但当目标函数计算速度较慢时，通常最好使用更多的计算能力。

请注意

并行计算需要并行计算工具箱™许可证。
如果目标函数求值不是很耗时，那么通常使用向量化求值是最快的。然而，情况并非总是如此，因为向量化计算计算整个模式，而串行计算只计算模式的一小部分。特别是在高维方面，这种评估的减少可能会导致一些问题的串行评估更快。
若要使用矢量化计算，目标函数必须接受任意行数的矩阵。每行代表一个要计算的点。目标函数必须返回一个目标函数值矩阵，该矩阵的行数与其接受的行数相同，每个目标函数有一列。对于单目标讨论，see向量化适应度函数（遗传算法)或矢量化目标功能（PatternSearch.)．

参考文献

[1]Custòdio，A. L.，J.F. A. Madeira，A. I. F.Vaz和L. N.Vicente。直接多学习进行多目标优化．暹罗j . Optim。，21(3), 2011, pp. 1109–1140. Preprint available athttps://estudogeral.sib.uc.pt/bitstream/10316/13698/1/Direct%20multisearch%20for%20multiobjective%20optimization.pdf．

[2] Bratley，P.和B. L. Fox。算法659：实现Sobol的拟随机序列生成器。ACM Trans.Math.Software 14，1988年，第88-100页。

[3]弗莱舍,M。帕累托最优测度：在多目标超启发式中的应用。在葡萄牙法尔沃2003年4月4月的“第二届进化多标准优化 - emo”议事诉讼中。由斯普林斯 - Verlag发表于计算机科学系列，Vol的讲义。2632，pp。519-533。预印在https://apps.dtic.mil/dtic/tr/fulltext/u2/a441037.pdf．