智能控制技术-第十三课鲁棒优化

多目标优化，鲁棒优化主讲人：徐鸣，沈希什么是多目标优化普通的优化问题可以视为单目标优化问题多目标优化问题可以描述为：12121212Minimize/Maximize()((),(),...,())Subjectto()((),(),...,())0(,,...,)(,,...,)KmDkfffccccxxxXyyyYfyxxxxxxxxxy生活中的多目标优化问题例子：买衣服：希望质量好，价格低投资理财：希望收益高，风险小淘宝买商品：同样的商品，在一定的情况下买最便宜的。价格便宜，购买风险小。f1为商品质量；f2为商品价格质量差质量好价格便宜价格贵多目标优化问题几乎现实世界中的所有问题都存在多个目标，而这些目标通常是相互冲突，相互竞争的。一个目标的改善往往同时引起其他目标性能的降低。也就是说，不存在使各目标函数同时达到最优的解，而只能对他们进行协调和折衷处理。多目标优化问题，就是寻找满足约束条件和所有目标函数的一组决策变量和相应各目标函数值的集合（Pareto最优解），并将其提供给决策者。由决策者根据偏好或效用函数确定可接受的各目标函数值及相应的决策状态。多目标问题的定义多目标优化问题的定义为：在可行域中确定由决策变量组成的向量，使得一组相互冲突的目标函数值尽量同时达到极小。设有k个优化目标，且这q个优化目标可能是相互冲突的。其数学表达式为：()0igxiS={x|g(x)0,i=1,2,,m}qR1122Z={z|(),(),,()}qqqRzfxzfxzfx1122qqiminz=f(x),z=f(x),L,z=f(x)s.t.g(x)0,i=1,2,L,m12121212Minimize/Maximize()((),(),...,())Subjectto()((),(),...,())0(,,...,)(,,...,)KmDkfffccccxxxXyyyYfyxxxxxxxxxy支配（占优）关系()()(1,2,,)kkfpfqkr设p和q是Pop中的任意二个个体，我们称p支配（dominated）q，则必须满足下列条件：（1）对所有的子目标，p不比q差。即，其中r为子目标的数量（求极小值）。此时称p为非支配的，q为被支配的。{1,2,,},()()lllrfpfq使()()(1,2,,)kkfpfqkr支配关系其中1、2、3、4代表四个可行解，点4表示的解支配点1、2、3所表示的解，点2、3所表示的解均支配点1表示的解；点2与点3所表示的解彼此不相关。Pareto边界非劣解又称为Pareto最优解，多目标优化问题有很多个Pareto最优解，解决多目标优化问题的关键在于获得有这些Pareto最优解组成的集合。Pareto最优解集在解空间中往往会形成一条边界线（超平面），又叫front。多目标优化的国内外研究现状1.传统的方法：权重法，约束法，混合法，目标规划法，最大最小法等。特点：将多个目标聚合成一个函数。缺点：各目标加权值的分配带有较大的主观性；优化过程中各目标的优度进展不可操作等；在处理高维数、多模态、非线性等复杂问题上存在许多不足。1Minimize/Maximize()()Kiiiffxx多目标优化的国内外研究现状遗传算法是模拟自然界生物进化过程与机制，求解优化与搜索问题的一类自组织、自适应的人工智能技术。由于遗传算法是对整个群体进行的进化运算操作，它着眼于个体的集合，而多目标优化问题的非劣解一般也是一个集合，遗传算法的这个特性表明遗传算法非常适合求解多目标优化问题。近年来，遗传算法应用于多目标优化领域。多目标优化的国内外研究现状2.多目标优化遗传算法：VEGA，HLGA，FFGA，MOGA，NPGA，NSGA，SPEA，NSGA-II，SPEA2，PAES缺点：1.多目标遗传算法的局部搜索能力较差2.求解过程依赖于染色体的表示形式，即与个体编码方式的关系很密切3.非劣最优解域收敛性分析困难4.参数较多，如果设置不恰当会导致算法运行的性能下降NSGA非支配排序遗传算法NSGA（Non-dominatedSortingGeneticAlgorithm）是由Srinivas和Deb提出的，这是一种基于Pareto最优概念的遗传算法。优点：优化目标个数任选，非劣最优解分布均匀，并允许存在多个不同的等价解。缺点：a）计算复杂度较高，算法复杂度是(其中N为种群大小，M为目标函数的个数)，当种群较大时，计算相当耗时；b）没有精英策略，精英策略能加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失；c）需要指定共享半径share3OMNNSGA-II1.快速的非劣解分类方法：为了根据个体的非劣解水平将种群分类，必须将每一个体与其他个体进行比较。NSGA-II算法采用快速的非劣解分类方法，计算速度提高。首先，对每一个解计算两个属性：（1）ni，支配解i的解数目；（2）si，解i所支配解的集合。找到所有ni=0的解并将其放入F1，称F1是当前非劣解，其等级为1。对当前非劣解中的每一个解i，考察其支配集中si的每一点j并将nj减少一个，如果某一个体j其nj成为零，我们把它放入单独的类H。如此反复考察所有的点，得到当前非劣解H。依次类推，直至所有解被分类。NSGA-II2.拥挤距离的计算:为了保持个体分布均匀，防止个体在局部堆积，NSGA-II算法首次提出了拥挤距离的概念。它指目标空间上的每一点与同等级相邻两点之间的局部拥挤距离。使用这一方法可自动调整小生境，使计算结果在目标空间比较均匀地散布，具有较好的鲁棒性。NSGA-IItan1122[]([1].[1].)([1].[1].)discePiPifPifPifPiftan1[]([1].[1].)rdiscekkkPiPifPifNSGA-II3.选择运算:选择过程使优化朝Pareto最优解的方向进行并使解均匀散布。比较两个个体，如果非劣等级不同，则取等级高（级数值小）的点。否则，如果两点在同一等级上，则取比较稀疏区域内的点，以使进化朝非劣解和均匀散布的方向进行。NSGA-II4.精英保留策略:首先，将父体和子代全部个体合并成一个统一的种群放入进化池中，种群的个体数成为2N。然后种群按非劣解等级分类并计算每一个体的局部拥挤距离。依据等级的高低逐一选取个体直到个体总数达到N，从而形成新一轮进化的父代种群，其个体数为N。在此基础上开始新一轮的选择，交叉和变异，形成新的子代种群。这种方法可加快进化的速度。一种基于maximin的多目标优化算法适应度值计算方法maximin()max{min{()()}}.ikikjkjifffxxx()min(())().max(())min(())kikikkikikikkfffffxxxxxε-支配策略的引入和改进maximin()max{min{()()/(1)}}.ikikjkjifffxxx算法流程步骤1：初始化：给定粒子种群数M，随机产生M个粒子并存放在DomList中，设每个粒子的个体最优位置即为初始位置，并初始化初始速度为0，初始化εset.步骤2：根据式(3.2)计算DomList中每个粒子的所有目标函数值，并根据式(3.4)来确定每个粒子的适应度函数值，将适应值为负的粒子存放在外部集nonDomList中。重新根据式(3.4)计算nonDomList中粒子的适应函数值，以消除劣解的影响[165].步骤3：对DomList中的每个粒子i进行迭代计算：1.根据适应值大小在nonDomList中选取前20%的非劣粒子作为pg候选，通过轮盘赌法在其中选择一个pg作为粒子i的全局最优值，若粒子i优于当前的pi用其替代当前的pi,否则pi保持不变。2.根据速度更新公式(1.1)更新速度，并将速度变化限制在区域[-Vdmax,Vdmax]内，即在迭代中超出了边界则设定为边界值。同时根据位置更新公式(1.2)更新位置，并将位置变化限制在区域[-Xdmax,Xdmax]内，计算出粒子i的后代存储在DomList中。步骤4：如果已经满足停止准则，例如nonDomList中已经达到最大或者已经达到最大迭代次数，则中止计算，输出nonDomList；否则迭代次数加1并跳转到步骤2。测试函数ZDT系列测试函数是Zitzler最早提出来的用来测试多目标优化算法的比较经典的测试函数，ZDT系列测试函数都具有以下相同的形式：其中，ZDT1函数的Pareto前沿是凸的并且是连续的，其具体如下式所示：11222112min()((),())..()(,...,)((),(,...,))nnffxfstfgxxhfxgxxxxx1112211()(,...,)19(1)(,)1nniifxxgxxxnhfgfgmatlab演示鲁棒优化鲁棒的概念220.350.85()()0.250.03Minimize()20.8Subjectto:0,1xxfxeex00.20.40.60.810.811.21.41.61.82xf(x)OriginalAverageAB常用的鲁棒处理方法目标函数的期望fexp(x)与方差fvar(x)exp()()()ffpdxxvarexp2()(()())()fffxpdxx鲁棒优化问题复杂性对于不同的多目标优化问题和优化问题的变量扰动存在的差异，用鲁棒的方法得到的鲁棒Pareto最优前沿和原有的Pareto最优前沿肯定有着不同的分布和排列，但是可以归结为以下4种情况课程结束，谢谢大家！