paretosearch算法- MATLAB和Simulink Ma金宝appthWorks日本 - 金宝app,下载188bet金宝搏,金宝搏官方网站

`paretosearch`算法

`paretosearch`算法概述

的paretosearch算法利用模式搜索一个点集搜索迭代nondominated点。看到多目标的术语。模式搜索满足所有边界,在每个迭代线性约束。

从理论上讲,该算法收敛于点附近的真正的帕累托面前。讨论和收敛性的证明,看到库斯托迪奥et al。[1],其证明适用于李普希兹连续目标和约束的问题。

定义`paretosearch`算法

paretosearch使用许多中间量和公差算法。

数量	定义
排名	的秩迭代的定义。 Nondominated分等级1。对于任何一个整数`k`> 1,一个点`k`当只有点控制严格小于排名`k`。
体积	超体积的点集p在目标函数空间满足不平等,每一个索引j, f_我(j)<p_我< M_我, 在哪里f_我(j)是我th组成部分j在帕累托集th目标函数值,M_我是一个上界的我th组件中所有点帕累托集。在这个图,称为参考点。图中的灰色阴影表示部分的体积,计算算法使用作为容斥计算的一部分。 ,弗莱舍[3]。 `paretosearch`计算体积只有当nondominated点的数量超过目标的数量。`paretosearch`使用参考点M =`马克斯(pts, [], 1) + 1`。在这里,`分`是一个矩阵的行点。体积变化是停止算法的一个因素。有关详细信息,请参见停止条件。
距离	距离是衡量个人的亲密关系对其最近的邻居。的`paretosearch`个体之间的距离相同的排名算法的措施。在目标函数空间距离算法的措施。该算法集个人极端位置的距离`正`。对于剩下的个体,算法计算距离作为一个求和的尺寸归一化绝对个人的排序的邻居之间的距离。换句话说,对于维度`米`和排序,按比例缩小的个体`我`: `距离(i) = sum_m (x (m i + 1) - x (m,张))`。算法种类分开每个维度,所以这个词邻居意味着在每个维度的邻居。个人相同的等级更高的距离有更高的机会选择(更高的距离是更好的)。距离是一个因素在传播的计算,这是停止准则的一部分。有关详细信息,请参见停止条件。
传播	传播是一个衡量运动的帕累托集。计算传播,`paretosearch`算法首先评估σ,拥挤距离测量的标准偏差的点在帕累托方面有限的距离。问这些点的数量,d是测量这些点之间的平均距离。然后算法评估μ、求和`k`目标函数的指数标准之间的区别当前最小值帕累托点指数和指数的最小值点在前面的迭代。然后传播 `传播`= (μ+σ)/ (μ+Qd)。传播极端时小目标函数值不改变迭代之间(即μ点时小)和帕累托分布均匀(也就是说,前面σ是小的)。 `paretosearch`使用情况停止传播。迭代停止传播时不会改变太多。有关详细信息,请参见停止条件。
`ParetoSetChangeTolerance`	停止条件搜索。`paretosearch`停止时,体积,传播,或由超过距离不会改变`ParetoSetChangeTolerance`在一个窗口的迭代。有关详细信息,请参见停止条件。
`MinPollFraction`	在一个迭代中最低分数的地点调查。`paretosearch`调查至少`MinPollFraction`*(模式)的点的位置。如果调查点给nondominated点的数量,调查被认为是成功的。否则,`paretosearch`继续调查,直到发现一个nondominated点或耗尽分模式。这个选项时不适用`UseVectorized`选择是`真正的`。在这种情况下,`paretosearch`调查所有模式点。

的草图`paretosearch`算法

初始化搜索

创建初始点集,paretosearch生成options.ParetoSetSize分quasirandom样本基于边界问题,默认情况下。详情,请参阅Bratley和狐狸[2]。当问题有超过500个维度,paretosearch使用拉丁超立方抽样生成初始点。

如果一个组件没有界限,paretosearch使用一个人工的下界-10年和一个人造的上界10。

如果一个组件只有一个绑定,paretosearch使用绑定的一个端点区间的宽度20 + 2 * abs(绑定)。例如,如果没有上界组件有一个下界的15日paretosearch使用一个区间的宽度20 + 2 * 15 = 55岁,所以使用人造上限15 + 55 = 70。

如果你通过一些初始点options.InitialPoints,然后paretosearch使用这些点作为初始点。paretosearch生成更多的点,如果有必要,至少获得options.ParetoSetSize初始点。

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

移动点满足线性约束后,如果有必要,paretosearch检查是否点满足非线性约束。paretosearch给一个点球的价值正任何时候,不满足所有非线性约束。然后paretosearch计算任何缺失的目标函数值的可行点。

请注意

目前,paretosearch不支持非线性等式约金宝app束量表(x) = 0。

创建存档和现有

paretosearch维护两套分:

存档——一个包含nondominated结构分与下面的网格大小有关options.MeshTolerance和满足所有的约束options.ConstraintTolerance。的存档结构包含不超过2 * options.ParetoSetSize分和最初是空的。每一个点的存档包含一个相关的网格大小,生成的网格大小点。
迭代——包含nondominated结构分,可能一些主导点与较大的网格大小或不可行性。每一个点的迭代包含一个网格大小有关。迭代包含不超过options.ParetoSetSize点。

调查找到更好点

paretosearch调查分迭代调查,指出继承相关的网格点的大小迭代。的paretosearch算法使用一项民意调查显示,认为可行性界限和所有的线性约束。

如果问题非线性约束,paretosearch计算每个调查点的可行性。paretosearch保持不可行点的分数分别得分的可行点。可行的得分点的目标函数值的向量。不可行点的分数的和非线性的不可行性。

paretosearch调查至少MinPollFraction*(模式)的点数量为每个点位置迭代。如果调查点给至少一个nondominated点对现任(原始)点,调查被认为是成功的。否则,paretosearch继续调查,直到发现一个nondominated点或耗尽分模式。如果paretosearch耗尽了分,不会产生一个nondominated点,paretosearch宣布调查成功,部分网格的大小。

如果调查发现nondominated点,paretosearch反复调查成功的方向延伸,每次翻网格大小,直到扩展产生主导点。在这个扩展,如果网格大小超过options.MaxMeshSize(默认值:正),停止调查。如果目标函数值下降负,paretosearch声明无界和停止的问题。

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

在轮询所有的点迭代,该算法检查新分一起分迭代和存档结构。paretosearch计算排名,或帕累托数量面前,每一个点,然后下面。

标记为删除没有等级1的所有点存档。
马克的新秩1点插入迭代。
马克的可行性分迭代谁的筛孔尺寸小于相关options.MeshTolerance为转移存档。
马克主要分迭代为去除只有防止新的nondominated点添加到迭代。

paretosearch然后计算每个点的体积和距离的措施。如果存档将溢出的结果包括标记点,然后点最大的体积占据存档,和其他人离开。同样,新的点标记为补充迭代输入迭代为了他们的卷。

如果迭代到处都是,没有主导点呢paretosearch补充说没有点迭代和声明了迭代是不成功的。paretosearch增加网格的大小迭代的1/2。

停止条件

三个或更少的目标函数,paretosearch停止使用体积和传播的措施。四个或更多的目标,paretosearch停止使用距离和传播的措施。在本文的剩余部分,这两个指标paretosearch使用表示适用的措施。

过去八的算法保持向量的值适用的措施。八个迭代后,算法检查的值两个适用的措施在每个迭代的开始,在那里托尔= options.ParetoSetChangeTolerance:

spreadConverged = abs(传播(结束- 1)-扩散(结束))< =托尔*马克斯(1,传播(结束- 1));
volumeConverged = abs(体积(结束- 1)-体积(结束))< =托尔*马克斯(1卷(结束- 1));
distanceConverged = abs(距离(结束- 1)-距离(结束))< =托尔*马克斯(1,距离结束(- 1));

如果适用的测试真正的,该算法停止。否则,算法计算的最大平方项适用的措施-傅里叶变换的第一项。算法然后比较顶点删除条款(变换的直流分量)。如果删除项大于100 *托尔* (max的所有其他条款),则算法停止。这个测试基本上确定措施的顺序不是波动,因此聚合。

另外,一块功能或输出功能可以阻止算法,或算法可以停止,因为它超过时间限制或函数评价极限。

返回值

该算法返回点在帕累托方面如下。

paretosearch结合分存档和迭代成一个集合。
当有三个或更少的目标函数,paretosearch返回从最大体积最小的点,最多ParetoSetSize点。
当有四个或更多的目标函数,paretosearch返回从最大的距离最小的点,最多ParetoSetSize点。

修改为并行计算和矢量化功能评估

当paretosearch并行计算目标函数值或矢量化的方式(UseParallel是真正的或UseVectorized是真正的),有一些修改算法。

当UseVectorized是真正的,paretosearch忽略了MinPollFraction选择和评估所有调查分模式。
当并行计算,paretosearch按顺序检查每一个点迭代从每个点并执行一个平行的调查。回国后MinPollFraction调查的一部分点,paretosearch决定是否调查点主导基础点。如果是这样,调查被认为是成功的,和任何其他平行评估停止。如果没有,调查仍在继续,直到支配点出现或调查。
paretosearch执行目标函数评价工人或矢量化的方式,而不是两个。如果您设置UseParallel和UseVectorized来真正的,paretosearch在工人并行计算目标函数值,但不是矢量化的方式。在这种情况下,paretosearch忽略了MinPollFraction选择和评估所有调查分模式。

运行`paretosearch`很快

最快的方式运行paretosearch取决于几个因素。

如果目标函数的评价是缓慢的,那么通常是最快使用并行计算。并行计算的开销可以大量当目标函数的评价是快,但当他们是缓慢的,它通常是最好的使用更多的计算能力。

请注意

并行计算需要并行计算工具箱™许可证。
如果目标函数评价不是很耗费时间,那么它通常是最快使用矢量化评估。然而,这并非总是如此,因为整个模式矢量化计算评估,而连续评估可以只是一小部分的一个模式。尤其是在高维度,这可以减少评估导致连续评估要快一些问题。
使用矢量化计算,你的目标函数必须接受一个矩阵与任意数量的行。每一行代表一个点来评估。目标函数必须返回一个目标函数值的矩阵的行数相同的接受,为每个目标函数与一列。简略的讨论,请参阅Vectorize健身功能(遗传算法)或矢量化目标函数(patternsearch)。

引用

[1]库斯托迪奥,a . L。,J. F. A. Madeira, A. I. F. Vaz, and L. N. Vicente.直接Multisearch多目标优化。暹罗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 quasirandom序列发生器。ACM反式。数学。软件14日,1988年,页88 - 100。

[3]弗莱舍,M。帕累托最佳状态的测量:应用多目标Metaheuristics。在《学报》第二次国际会议上进化Multi-Criterion Optimization-EMO”法2003年4月,葡萄牙。斯普林格出版社出版的计算机科学系列课程讲稿中,2632卷,第519 - 533页。预印在https://apps.dtic.mil/dtic/tr/fulltext/u2/a441037.pdf。

另请参阅

paretosearch