主要内容

gamultiobj算法

介绍

本节介绍该算法gamultiobj用于在帕累托前端创建一组点。gamultiobj使用一种受控的精英遗传算法(NSGA-II的变体)[3]).精英型遗传算法总是偏爱适合度值(等级)较高的个体。受控制的精英遗传算法也青睐那些有助于增加种群多样性的个体,即使它们的适应度值较低。

多目标的术语

大多数的术语gamultiobj算法和遗传算法的术语.然而,还有一些附加的术语,将在本节中描述。有关术语和算法的更多细节,请参见Deb[3]

  • 主导地位——一个点x在一个点y对于向量值目标函数f当:

    fx)≤fy)为所有

    fjx) <fjy)对于一些j

    “支配”一词相当于“劣势”一词:x占主导地位y什么时候y不如x

    一个nondominated集在一组点中P是点的集合吗P不受任何一点支配P

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

    等级越低的个体被选择的机会越大(等级越低越好)。

    所有不可行的个体都比任何可行的个体级别低。在不可行的种群中,秩是按不可行的测度排序的顺序,加上可行成员的最高秩。

    gamultiobj使用等级来选择父母。

  • 拥挤距离-拥挤距离是一个人与其最近邻居的距离。的gamultiobj算法测量同一等级的个体之间的距离。默认情况下,算法在目标函数空间中度量距离。然而,你可以通过设置变量来测量决策变量空间(也称为设计变量空间)中的距离DistanceMeasureFcn选项{@distancecrowding,基因型的}

    该算法将处于极端位置的个体的距离设置为.对于其余的个体,该算法将距离计算为个体排序后的邻居之间的标准化绝对距离的维数之和。换句话说,对于维度排序,缩放个体

    x(m,i+1) - x(m,i-1)

    算法对每个维度分别进行排序,所以术语邻居表示每个维度上的邻居。

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

    您可以选择一个不同于默认的拥挤距离度量@distancecrowding函数。看到多目标的选择

    拥挤距离是计算传播的一个因素,它是停止标准的一部分。当两个被选中的个体拥有相同的排名时,拥挤距离也被用来作为比赛选择的决胜局。

  • 传播-传播是帕累托集合运动的度量。为了计算价差gamultiobj算法首先评估σ,即在帕累托前沿距离有限的点的拥挤距离度量的标准差。是这些点的数量,和d是这些点之间的平均距离。然后算法计算μ,即该指标的当前最小帕累托点与上一次迭代中该指标的最小值帕累托点之差的范数之和。然后是蔓延

    传播= (μ+σ)/(μ+Qd).

    当极端目标函数值在迭代之间变化不大时(即,μ是小的),当帕累托前沿的点分布均匀(即,σ是小的)。

    gamultiobj在停止状态下使用蔓延。当价差变化不大,且最终价差小于最近价差的平均值时,迭代就停止了。看到停止条件

初始化

第一步gamultiobj算法创建了一个初始种群。算法创建总体,或者你可以通过使用InitialPopulationMatrix选项(见人口的选择).将种群中的个体数设置为PopulationSize选择。默认情况下,gamultiobj创建一个相对于边界和线性约束可行的总体,但相对于非线性约束不一定可行。默认创建算法为@gacreationuniform当没有约束或只有约束时,并且@gacreationlinearfeasible当存在线性或非线性约束时。

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

迭代

主要的迭代gamultiobj算法如下。

  1. 利用对当前种群的选择函数为下一代选择亲本。唯一可用于的内置选择功能gamultiobj是二进制的比赛。您还可以使用自定义选择函数。

  2. 通过突变和交叉从选定的父母创造孩子。

  3. 通过计算目标函数值和可行性对儿童进行评分。

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

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

  6. 削减扩大的人口PopulationSize每个职级保留适当数量的个人。

当问题有整数或线性约束(包括边界)时,算法修改种群的进化。看到整数和线性约束

停止条件

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

exitflag价值 停止条件
1

分布值相对变化的几何平均值选项。MaxStallGenerations世代少于选项。FunctionTolerance最后的价差小于过去的平均价差选项。MaxStallGenerations一代又一代

0

超过了最大代数

-1

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

-2

未发现可行点

-5

超过了期限

对于退出标志1,息差相对变化的几何平均值的乘数是½k的相对变化k上一代。

整数和线性约束

当一个问题有整数或线性约束(包括边界)时,算法修改种群的进化。

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

  • 当问题只有线性约束时,软件不会根据这些约束修改个体以使其可行。必须使用相对于线性约束保持可行性的创建、变异和交叉函数。否则,人口会变得不可行的,结果也会不可行的。默认操作符保持线性可行性:gacreationlinearfeasiblegacreationnonlinearfeasible为创造,mutationadaptfeasible突变,crossoverintermediate交叉。

整数可行性和线性可行性的内部算法类似于surrogateopt.当问题有整数约束和线性约束时,算法首先创建线性可行点。然后,该算法试图通过使用试图保持线性可行点的启发式算法将线性可行点舍入为整数来满足整数约束。当这个过程不能获得足够的可行点来构建种群时,算法调用intlinprog试着找到更多关于边界,线性约束,和整数约束的可行点。

之后,当变异或交叉产生新的种群成员时,算法通过相似的步骤确保新成员是整数且线性可行的。如果有必要,每个新成员都会被修改,使其尽可能接近其原始值,同时也满足整数和线性约束和边界。

参考书目

[1] Censor, Y.《多目标问题中的帕累托最优性》,达成。数学。Optimiz。,第4卷,第41-59页,1977。

N. O. Da Cunha和E. Polak。《有限维空间中向量值准则下的约束极小化》j .数学。肛交。达成。,第19卷,第103-124页,1967年。

[3] Deb, Kalyanmoy。“基于进化算法的多目标优化”,John Wiley & Sons, Ltd, Chichester,英国,2001。

[4] Zadeh, l.a.,《最优性和非标量价值绩效标准》IEEE反式。自动售货机。来讲。, AC-8卷,1963年第1页。

另请参阅

相关的话题