主要内容

gamultiobj.算法

介绍

本节描述了gamultiobj.用于在Pareto前面创建一组点。gamultiobj.使用受控的精英遗传算法(NSGA-II的变体[3]).精英遗传算法总是偏爱具有更好适应值(等级)的个体。受控精英遗传算法也有利于个体,即使他们的适应值较低,也能帮助增加群体的多样性。

多目标术语

大多数的术语gamultiobj.算法与遗传算法术语. 但是,本节还介绍了一些附加术语。有关术语和算法的更多详细信息,请参见Deb[3].

  • 支配地位-一点x支配一点Y关于向量值目标函数F什么时候:

    F(x) ≤F(Y)总的来说.

    FJ(x) <FJ(Y)对一些人来说J.

    “主导”一词相当于“劣质:”术语x支配Y确切时间Y差不多x.

    A.非支配集在一组点中P是一组积分QP这是不受任何一点影响的P.

  • 等级-对于可行个体,存在个体秩的迭代定义。排名1的个人不受任何其他个人的支配。排名2的个体仅由排名1的个体支配。一般来说,排名K个人只受等级的个人支配k-1或更低。

    级别较低的个体有较高的选择机会(级别越低越好)。

    所有不可行的个体都比任何可行的个人都有更糟糕的排名。在不可行的人口中,排名是按照排序的排序度量,加上可行成员的最高等级。

    gamultiobj.使用秩选择父级。

  • 拥挤距离-拥挤距离是衡量一个人与其最近邻居之间距离的一种尺度gamultiobj.该算法测量相同等级个体之间的距离。默认情况下,该算法在目标函数空间中测量距离。但是,您可以通过设置distancemeasurefcn.选择{@ distancrovding,'genotype'}.

    该算法将极端位置的个体距离设置为Inf. 对于其余个体,该算法将距离计算为个体排序邻居之间的标准化绝对距离维度的总和。换句话说,对于维度M并对每个人进行分类、缩放:

    距离(i)=和(x(m,i+1)-x(m,i-1)).

    该算法单独对每个维度进行排序,因此术语邻居意味着每个维度的邻居。

    相同等级的个体距离越远,选择的机会越高(距离越远越好)。

    您可以选择不同的拥挤距离测量比默认值@距离拥挤功能。请参阅多目标选项.

    拥挤距离是计算排列的一个因素,是停车标准的一部分。当两个被选中的个人具有相同的排名时,拥挤距离也被用作锦标赛选择中的平局破坏者。

  • 传播-价差是衡量帕累托集合运动的一个尺度。要计算价差,请使用gamultiobj.算法首先计算σ,具有有限距离的帕累托前面的挤压距离的标准偏差。Q是这些要点的数量,还有D是这些点之间的平均距离测量。该算法然后评估μ,k个目标函数的总和在该索引的当前最小值帕累托点与此索引中该索引中该索引中的最小点之间的差异的规范。那么蔓延就是

    传播=(μ+σ)/(μ+量子点)。

    当极端目标函数值不会在迭代之间变化时,扩展很小(即,μ小),当帕累托前面的点均匀蔓延(即,σ(体积小)。

    gamultiobj.在停止条件下使用排列。当价差变化不大,且最终价差小于最近价差的平均值时,迭代停止。看见停止条件.

初始化

第一步gamultiobj.算法正在创建初始总体。该算法创建总体,或者您可以使用initialpopulationmatrix.选项(参见人口选项)。人口中的个人数量被设定为价值人口规模选项默认情况下,gamultiobj.创建相对于边界和线性约束可行,但相对于非线性约束不一定可行的总体。默认的创建算法是@gacreationuniform不存在约束或仅存在绑定约束时,以及@GACREATIONLINEAR是可行的当存在线性或非线性约束时。

gamultiobj.评估总体的目标函数和约束,并使用这些值为总体创建分数。

迭代

的主要迭代gamultiobj.算法进行如下。

  1. 使用当前人口上的选择功能选择父母进行下一代。唯一的内置选择功能可供选择gamultiobj.是二进制锦标赛。您还可以使用自定义选择功能。

  2. 通过变异和交叉从选定的父对象创建子对象。

  3. 通过计算目标函数值和可行性给孩子打分。

  4. 将当前人口和儿童合并为一个矩阵,即扩展人口。

  5. 计算扩展群体中所有个体的等级和拥挤距离。

  6. 削减扩大的人口,使其拥有人口规模通过保留每个等级的适当数量的个人。

当问题具有整数或线性约束时(包括界限),该算法修改了人口的演变。看整数和线性约束.

停止条件

下列停止条件适用。每个停止条件都与退出标志相关联。

EXITFLAG值 停止条件
1.

传播价值相对变化的几何平均值options.maxstall几代人数小于options.FunctionTolerance.,且最终利差小于过去的平均利差options.maxstall世代

0

已超过最大生成数

-1

优化由输出函数或绘图函数终止

-2

没有找到可行点

-5

超过时限

对于退出标志1,传播中相对变化的几何平均值具有倍增器½K相对变化K上一代。

整数和线性约束

当问题具有整数或线性约束(包括边界)时,该算法修改总体的演化。

  • 当问题既有整数约束又有线性约束时,软件修改所有生成的个体,使其相对于这些约束是可行的。您可以使用任何创建、变异或交叉函数,并且对于整数和线性约束,整个总体仍然是可行的。

  • 当问题只有线性约束时,软件不会修改个体使其相对于这些约束是可行的。必须使用创建、变异和交叉函数来保持线性约束的可行性。否则,种群可能变得不可行,结果也可能不可行。默认操作符保持线性可行性:GaCreationLearfeasible.gacreationnonlinearfeasible.为了创造,,umatationAptFeasible.对于突变,和Crossoverintermediate.交叉。

整数和线性可行性的内部算法类似于代理人考试.当问题具有整数和线性约束时,算法首先创建线性可行点。然后,算法尝试通过使用试图保持点线性可行的启发式来满足线性可行点到整数来满足整数的约束。当此过程在获得足够的可行点来构建群体时不成功,算法调用intlinprog要尝试找到更多的点,即关于界限,线性约束和整数约束是可行的。

后来,当突变或交叉创建新的人口成员时,算法确保通过采取类似步骤,确保新成员是整数和线性可行的。如有必要,每个新成员都被修改为尽可能接近其原始值,同时还满足整数和线性约束和界限。

参考文献

[1]审查,y。“帕累托在多目标问题中的最优性”,苹果。数学。Optimiz。,卷。4,PP 41-59,1977。

[2] 有限维空间中向量值准则下的约束极小化,”数学,分析,应用。,第19卷,第103-124页,1967年。

[3] Deb,Kalyanmoy。“使用进化算法的多目标优化,”英国奇切斯特,2001年约翰瓦利&Sons,Ltd。

[4] Zadeh,L.A。“最优性和非卡尔有价值的绩效标准”IEEE传输自动控制。,第AC-8卷,第1页,1963年。

另见

相关话题