论文研读RotatedTestProblemsforAssessingthePerformanceofMOEAs

觉得有用的话,欢迎一起讨论相互学习~

论文研读-多目标自适应memetic算法

论文研读-基于决策变量分析的大规模多目标进化算法

论文研读-多目标优化中的多源选择迁移框架

论文研读-基于决策变量聚类的大规模多目标优化进化算法

论文研读-基于变量分类的动态多目标优化算法

• A. Iorio and X. Li, Rotated test problems for assessing the performance of multi-objective optimization algorithms, vol. 1. 2006, p. 690.

• 本文介绍了四个可旋转的多目标测试问题&＃xff0c;这些问题设计用于测试EMO&＃xff08;进化多目标优化&＃xff09;算法在处理参数交叉&＃xff08;parameter interactions.&＃xff09;方面的能力。 只有同时改进每个决策变量&＃xff0c;才能有效解决此类问题。 针对此类问题的EMO算法评估与现实世界中的问题相关&＃xff0c;这些问题很少可分离。 但是&＃xff0c;许多EMO测试问题不具有此特征。 本文提出的一组测试问题旨在解决这一重要要求。 介绍了这些测试问题的设计原理以及每个新测试问题的描述。 提出了使用差分进化多目标优化算法解决这些问题的实验结果&＃xff0c;并与非支配排序遗传算法II&＃xff08;NSGA-II&＃xff09;进行了对比。

• 传统上&＃xff0c;已经使用经典技术解决了多目标问题&＃xff0c;但是这种方法通常在它们可以解决的问题类型方面有很多限制&＃xff0c;甚至可能无法为函数未知&＃xff08;function unknown&＃xff09;的问题找到最佳解决方案。 解决多目标问题的一种相对较新的方法是population based基于总体的进化算法&＃xff08;EA&＃xff09;的应用。 在基于种群的进化方法&＃xff08;它同时搜索决策空间中的多个点&＃xff09;与多目标问题&＃xff08;具有帕累托最优解集&＃xff09;之间存在自然的协同作用。 进化方法可以提供一组近似于帕累托最优集合的解。 Despite their apparent successes, there is a disparity between how we evaluate EMO algorithms with test problems with specified properties, and the characteristics of many real-world problems.

1.1 Test problems for EMO Algorithms

• 为了评估EMO算法在各种fitness landscapes 的性能&＃xff0c;采用了具有各种特征的测试问题。例如考虑PF的凹性concavity of the Pareto-optimal front&＃xff0c;不连续的PF discontinuous Pareto optimal front&＃xff0c; 稀疏分布的PF sparsely distributed solutions near the Pareto optimal front, 决策空间和目标空间的非均匀映射non-uniform mappings between the decision and objective space.根据[1]的指导&＃xff0c;[13]提出了ZDT测试集。在[1]中&＃xff0c;讨论了可能会给EMO算法带来困难的问题特征&＃xff0c;并提出了一个框架来构造表现出此类特征的测试问题。近来&＃xff0c;在用于多目标优化的测试问题的构造方面取得了进一步的进展。尽管许多方法只关注于构建两个目标的问题&＃xff0c;但在[6]和[3]中&＃xff0c;其他方法则涉及具有两个以上目标的测试问题的构建。在[9]中还提出了一个框架&＃xff0c;用于在决策空间中构造任意用户指定的帕累托最优集&＃xff0c;这些集合映射到目标空间中的帕累托最优前沿。在多目标组合优化领域&＃xff0c;已经提出了针对二次分配问题的实例生成器[8]。这些生成器对于研究组合问题中的参数交互作用很有用。

• 文章太经典&＃xff0c;这里就写引用
• [1] K. Deb. Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3):205–230, 1999.
• [2] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: Nsga-ii. IEEE Trans. Evol. Comput., 6(2):182–197, 2002.
• [3] S. Huband, L. Barone, L. While, and P. Hingston. A scalable multi-objective test problem toolkit. In Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005, Lecture Notes in Computer Science, volume 3410, pages 280–295, Mexico, 2005.
• [4] A. Iorio and X. Li. Solving rotated multi-objective optimization problems using differential evolution. In AI 2004: Advances in Artificial Intelligence: 17th Australian Joint Conference on Artificial Intelligence, Cairns, Australia, page 861, Heidelberg, 2004.
• [5] A. Iorio and X. Li. Incorporating directional information within a differential evolution algorithm for multi-objective optimization. In Proceedings of the 2006 Genetic and Evolutionary Computation Conference (GECCO-06), 2006.
• [6] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multi-objective optimization. Technical Report TIK-Report No. 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, 2001.
• [7] J. Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multi-objective optimization problems. IEEE Trans. Evol. Comput., 10(1):50–66, 2005.
• [8] J. Knowles and D. Corne. Instance generators and test suites for the multi-objective quadratic assignment problem. In Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003, Lecture Notes in Computer Science, volume 2632, pages 295–310, Portugal, 2003.
• [9] T. Okabe and Y. Jin. On test functions for evolutionary multi-objective optimization. In Parallel Problem Solving from Nature - PPSN VIII, Lecture Notes in Computer Science, volume 3242, pages 792–802, Birmingham, 2004.
• [10] K. Price. Differential Evolution, chapter 2, pages 79–108. McGraw-Hill, London UK, 1999.
• [11] T. Robic. Performance of demo on new test problems: A comparison study. In Proceedings of the Fourteenth International Eletrotechnical and Computer Science Conference ERK 2005, pages 121–124, 2005.
• [12] R. Salomon. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions: A survey of some theoretical and practical aspects of genetic algorithms. Bio. Systems, 39(3):263–278, 1996.
• [13] E. Zitzler, K. K. Deb, and L. Thiele. Comparison of multi-objective Evolutionary Algorithms: Empirical results.

1.2 带有参数交叉的问题

• Before discussing the previous work in the area of test problems with parameter interactions, it is necessary to define what we mean by a linearly separable problem (线性可分). Parameter interactions occur in a problem because the parameters in the problem are not linearly separable (不是线性可分的). The geometric interpretation of what constitutes a linearly separable problem is where the n parameters of a problem in n-dimensional space can be separated by an n−1 dimensional hyperplane. We will see in Section 2 how linear separability occurs with a simple ellipsoid function, and how rotation can make the function non-separable. (构成线性可分离问题的几何解释是&＃xff0c;问题在n维空间中的n个参数可以被n-1维超平面分开。 我们将在第2节中看到如何通过简单的椭圆函数实现线性可分离性&＃xff0c;以及如何旋转使函数不可分离。)
• 文献12中的工作证明了对旋转问题评估单一目标进化算法的重要性&＃xff0c;以测试其旋转不变的行为&＃xff0c;争论的是EA的评估应独立于任何坐标系。 此外&＃xff0c;在EMO领域&＃xff0c;NSGA-II在简单的旋转问题上表现不佳[2]&＃xff0c;在多目标问题中讨论了参数交互的重要性[7]。 如果EMO算法可以在这样一个简单的问题上失败&＃xff0c;但在问题与决策空间的主坐标系对齐时成功&＃xff0c;那么显然许多关于此类测试问题的报告结果都可能会产生误导。 在[12]中提出了一个强有力的案例&＃xff0c;即所有EA评估都应独立于特定的坐标系&＃xff0c;而我们的论点是&＃xff0c;对于EMO算法的评估也应同样如此。
• 最近&＃xff0c;多目标问题中的参数交互问题引起了更多关注。 在[3]中&＃xff0c;多目标问题的不可分性被证明是现有多目标测试套件所缺乏的重要特征&＃xff0c;并且描述了一种针对任意数量的目标构造具有参数交互作用的问题的方法。 在[11]中&＃xff0c;对[3]中提出的许多提出的不可分离和可分离的问题&＃xff0c;评估了一种差分进化多目标算法。

1.3 Overview

• 每个实际编码的ZDT测试问题在决策空间中均具有Pareto optimal集合&＃xff0c;该集合与主坐标系对齐。这可以使问题变得更容易&＃xff0c;因为可以分阶段解决目标。本文的目的是使用[1]中描述的方法提出一系列与额外的ZDT系列测试问题&＃xff0c;并提供对旋转多目标问题的进一步了解。The primary motivation for this is that most real world problems have parameter interactions, and ideally we would also like a variety of test problems which have parameter interactions as well. The framework employed for constructing the ZDT problems is commonly used by practitioners, and it is easily employed in the construction of test problems.
• The proposed problems in this paper can be arbitrarily (武断的) rotated on any axis of the decision space. Through a rotation of the coordinate system(坐标系), parameter interactions can be introduced to the problem. When the proposed problems are rotated in the decision space, the Pareto-optimal set is rotated accordingly. In Section 2.1 we will see that when any solution in the set is perturbed independently with respect to any of the decision variables, it can only be perturbed to non-dominated solutions which are not Pareto-optimal.
• 本文提出的一系列旋转问题的提议将提供一种评估EMO算法性能的方法&＃xff0c;该方法不会偏重于问题相对于坐标轴的特定方向。 不管问题在决策空间中的方向如何&＃xff0c;这都为EMO从业人员提供了其算法性能的可靠指示。
• 在以下部分中&＃xff0c;我们将更详细地描述旋转如何使单目标和多目标问题更难优化。 在第3节中&＃xff0c;我们描述了提出的问题套件以及如何构造问题。 为了与NSGA-II算法进行比较&＃xff0c;在第4部分中简要介绍了一种新的EMO差分进化方法&＃xff0c;并进行了实验。 然后在第5节中讨论提出的问题套件的结果和实用性&＃xff0c;并在第6节中作总结。

• 参数交叉可以引入到任何一种问题中&＃xff0c;组合优化问题也可以。在本论文中仅仅讨论实值优化问题。一个或者多个目标具有非线性的参数交互。
• 先从一个单目标椭球型函数入手
  
• 这个公式和初中学的椭圆的公式一样&＃xff0c;当x1和x2分别取0时&＃xff0c;可以在原坐标系的原点处得到最小值。其推导公式可以如下图所示。这当决策变量是二维&＃xff0c;当决策变量是n维的时候&＃xff0c;式子的项数为1/2(n²&＃43;n)
  
• 举个具体一点的例子
  
• 画出等高线图
  
  
• 对于图1的第一个式子&＃xff08;1&＃xff09;&＃xff0c;发现其是变量可分的&＃xff0c;并且和坐标轴对齐。两个变量可以单独的视为两个独立的优化问题进行优化。而当其进行旋转以后其是不可分的&＃xff0c;因为引入了式子参数交叉项a1x1x2&＃xff0c;只有同时对所有参数值进行改进&＃xff0c;才能有效地向全局最优方向发展。
  
• 图1&＃xff0c;虚线段方向的任何改进都是可行的&＃xff0c;A’代表经过A旋转之后的同一点&＃xff0c;发现其可以改进的余地变小了。
• 此外&＃xff0c;如图2所示&＃xff0c;搜索可以很容易地限制在将椭圆形纵向二等分的线段上。通过同时对每个决策变量进行改进&＃xff0c;该线段上的任何点都只能移至可以评估为更好解决方案的另一点。例如&＃xff0c;在图2&＃xff08;a&＃xff09;中&＃xff0c;可以在x1轴上独立干扰点A&＃xff0c;以找到位于坐标系原点的全局最小值。但是在图2&＃xff08;b&＃xff09;中&＃xff0c;随着坐标轴的方向并不能使其降低得最快。通常&＃xff0c;吸引盆地比较容易找到&＃xff0c;但是当问题不可分割时&＃xff0c;搜索可能会陷入困境。 在所有情况下&＃xff0c;只有同时改善所有参数&＃xff0c;才能发现更合适的解决方案。 对于这些类型的问题&＃xff0c;众所周知&＃xff0c;遗传算法中经常使用的小突变率比随机搜索的效率更低[12]。 进化策略已经在解决这类问题上取得了相对成功&＃xff0c;但是它们需要学习适当的相关突变步长&＃xff0c;并且当决策空间尺寸变大时&＃xff0c;在计算上可能会相当昂贵[10]。
  

2.1 旋转多目标问题Rotated Multi-objective Problems

• 下图展示的是R1函数
  

• 横纵坐标为两个变量x1,x2,纵轴为f1
  

• 横纵坐标为两个变量x1,x2,纵轴为f2
  

• 如果使用旋转矩阵
  

• 横纵坐标为两个变量x1,x2,纵轴为f1
  

• 横纵坐标为两个变量x1,x2,纵轴为f2
  

• 如果是三个变量进行旋转
  

• 尽管可以直观地期望在多目标域中遇到的情况是相同的&＃xff0c;但是情况并不是那么简单。 为了突出旋转的单目标问题和多目标问题之间的区别&＃xff0c;我们将考虑一个简单的多目标问题。 这也将有助于我们理解旋转对多目标问题的影响&＃xff0c;在该问题中&＃xff0c;搜索算法会寻找非主导解集。 这种情况类似于单个目标域&＃xff0c;在该域中&＃xff0c;对每个决策变量具有独立扰动的搜索算法将很难找到更多的最优解。
  

• Figure 3 shows a simple bi-objective optimization problem with a 2-dimensional decision space. This is problem R1, defined in Section 3.2。这个问题的特点是在目标f2中有一个略微倾斜的槽。目标f1是一个与目标f2的斜面方向相反的斜面。在目标f2和目标f1中&＃xff0c;pareto最优集分别用一条分割决策空间的线段表示&＃xff08;即对于PS而言是决策空间的一条线段&＃xff09;。决策空间受制于一个旋转矩阵R。

• 现考虑其在等高线图投影表示F4&＃xff0c;首先在Fig4中考虑未旋转版本&＃xff0c;O是PS中的一个点&＃xff0c;如果O在OA方向上扰动&＃xff0c;则在f1上变小&＃xff0c;f2上变大&＃xff08;注意看坐标轴&＃xff09;把握住PS应该是x1取-0.3-0.3 x2取0。接下来一段话的意思就是说旋转前只通过改变一个变量能够找到PS&＃xff0c;而旋转后不能通过值改变一个变量找到PS。
  
  
  

• 实际上&＃xff0c;此分析所基于的图3中的问题相对于可行空间具有非常小的区域&＃xff0c;其中非支配解可以位于O C和O D方向。在这些方向上非支配的解决方案仅随着问题的方向接近与主坐标轴对齐的可能性而变得越来越可能。当帕累托最优前端的方向与轴x1对齐时&＃xff0c;线矢量O C进一步延伸&＃xff0c;因此可以在该区域中更容易地发现更多非支配解。其次&＃xff0c;这样的非支配解将接近帕累托最优集。对于线向量O D同样如此&＃xff0c;因为帕累托最优前端与轴x2对齐。换句话说&＃xff0c;导致帕累托最优集不与任何主坐标轴对齐的问题的旋转&＃xff0c;使得当仅出现决策变量的独立扰动时&＃xff0c;很难发现其他帕累托最优解。

• 在仅存在独立扰动的情况下&＃xff0c;倾向于在较低的f1评估和较高的f2评估的方向上发现点&＃xff0c;这将使非支配解集远离帕累托最优集&＃xff0c;并且随着时间的推移会降低搜索范围。这种行为的结果是&＃xff0c;搜索可能会陷入“帕累托最优”区域&＃xff0c;而无法在“帕累托最优”集中找到更多非支配解。 覆盖帕累托最优前沿的进展变得极其缓慢。这种效应在[4]和[2]中也很明显&＃xff0c;其中NSGA-II在旋转的单模态多目标问题上产生了帕累托最优前沿的较差覆盖。任何非旋转不变的多目标优化算法都会表现出这种行为。

• 提出的每个测试问题均使用[1]中提出的框架进行设计。 g函数负责影响到Pareto最优前沿的收敛。 h函数指定问题是否旋转的帕累托最优前沿的形状。 可以通过将g函数设置为1.0并在可行解的范围内评估f1来确定帕累托最优集。 多样性也受f1函数的影响。
• 为了构造具有参数交互作用的问题&＃xff0c;该问题必须至少具有一个非线性函数。 考虑到这一点&＃xff0c;我们在本文中提出的可旋转测试问题将在至少一个目标函数中具有至少一个非线性函数。 如果f1超出问题描述中指定的范围&＃xff0c;则每个测试问题还将f1和f2设置为较大的值。 这很重要&＃xff0c;因为旋转可能会使功能评估超出实验者[1]期望的范围。
• 为了构造一个旋转的问题&＃xff0c;我们还必须注意&＃xff0c;在旋转的情况下&＃xff0c;问题必须仍然可以求出一个有意义的结果。应该避免通过旋转转换导致决策变量取负值&＃xff0c;然后取平方根函数的情况。这可以通过避免导致这种情况的函数来实现&＃xff0c;或者通过在函数中使用偏移向量&＃xff0c;使其永远不会产生负值。还应该注意的是&＃xff0c;执行旋转的方法可以应用于文献中的其他问题&＃xff0c;而不限于ZDT问题。唯一需要考虑的问题是确保旋转后的矢量仍然可以进行评价。帕累托最优集仍然可以通过用户使用的测试问题构造方法中指定的方法来确定

3.1 产生均匀的随机旋转

• 为了在旋转的问题上实现对算法的完全公正的评估&＃xff0c;必须保证均匀分布的随机旋转。 算法1概述了生成随机正交基础的过程&＃xff0c;该过程用于通过旋转参数向量将参数相互依赖性引入问题中。这个变换不会改变问题域的适应度因为它是一个等距变换;它保留了点与点之间的距离&＃xff0c;因此也保留了角度。当使用标准正交基旋转m维空间中的点时&＃xff0c;超球表面上的点的均匀分布是可能的。这个技术也可以随机的均匀的旋转一个决策向量x, 所以对于任何特定的坐标轴都没有偏差。旋转矩阵用于在决策空间中围绕主坐标轴的原点旋转。

旋转的测试问题

• 在本节中&＃xff0c;介绍了四个旋转的测试问题。这些问题可以在决策空间中任意旋转。这些问题中的每一个都具有至少一个非线性的目标&＃xff0c;并且可以通过旋转坐标系来引入参数交互作用。

R1

• 问题R1由Deb [1]首先提出。它的特征是在目标f2中有一个谷。帕累托最优集也沿着该谷的长度分布&＃xff0c;并且当问题受到旋转时&＃xff0c;该谷可以捕获沿其进行的非旋转不变搜索&＃xff0c;如第2.1节中所述。函数f1是线性的。
  
  
  
  

R2

• 问题R2与ZDT3问题相似&＃xff0c;并且具有不连续的帕累托最优前沿。R2给优化算法带来了困难&＃xff0c;因为R2必须定位多个不连续的Pareto最优前沿&＃xff0c;并在每个前沿中都保持解。 旋转R2时&＃xff0c;仅沿主坐标轴独立搜索的优化算法将生成非支配解&＃xff0c;这些解会明显偏离帕累托最优前沿。 出现这种现象的原因是&＃xff0c;在一个独立的扰动可以产生一个支配当前非支配集合的解之前&＃xff0c;被扰动的解必须沿着主坐标轴行进很远。函数f1是线性的&＃xff0c;而f2是非线性的。 g函数在指定范围内不是多模态的。此问题的可行空间和帕累托最优前沿如图6所示。
  

R3

• 决策空间变量有规则的递增&＃xff0c;但在问题R3的目标空间中以非规则的间隔进行求值&＃xff0c;因此很难沿着帕累托最优前沿找到均匀分布。解的密度越低&＃xff0c;则f1值越低。问题R3与ZDT6问题类似。f1和f2是非线性函数。g函数在指定范围内不是多模态的。此问题的可行空间和帕累托最优前沿如图7所示。
• f1
  
• f2
  
  
  

R4

• 问题R4基于Schwefel函数[12]&＃xff0c;其中局部前沿位于远离全局最小值的位置。容易被这种欺骗性的前沿困住了点。R4是困难的&＃xff0c;而目标f2的特征是有许多山谷&＃xff0c;包括远离真正的帕累托最优锋的高度欺骗性的山谷。这些谷对应于由函数g产生的多模态。这些谷中的每一个都可以将点陷在次优非支配的前沿中。此问题的可行空间和帕累托最优前沿如图8所示。
  
  
  
  

• 提出的每个测试问题均使用[1]中提出的框架进行设计。 g函数负责影响到Pareto最优前沿的收敛。 h函数指定问题是否旋转的帕累托最优前沿的形状。 可以通过将g函数设置为1.0并在可行解的范围内评估f1来确定帕累托最优集。 多样性也受f1函数的影响。
• G控制收敛&＃xff0c;H控制形状&＃xff0c;g设为1&＃xff0c;看f1, 和PF

R1

R2

R3

R4

• EMO算法在坐标旋转下应该是不变的&＃xff0c;以便有效地优化具有许多参数交互作用的复杂多目标问题。文献中报道的许多当前结果是针对那些不表现出复杂参数交互作用的问题&＃xff0c;尽管这种交互作用是许多现实世界问题的特征[7]