进化算法以其搜索的全局性逐渐成为解决MOP问题的有效工具。以下按照Coello Coello[14，15]的总结方式来简介多目标进化优化领域的一些代表性算法。第一代多目标进化算法1989年，Goldberg建议用非支配排序和小生境技术来解决MOP问题。第一代多目标进化算法以基于非支配排序的选择和基于共享函数的多样性保持为其主要特点，但这一代MOEA算法的缺点也十分明显。因此，第二代多目标进化算法普遍使用了精英策略。......
2023-11-26
多目标进化算法形式化描述
【摘要】：下面介绍进化算法的相关定义和统一的描述框架[1]。对于各种进化计算方法，存在一个非空集合I，I称为这个进化计算的个体空间。D的值域确定了进化计算的实际搜索范围。随机函数被称为随机种群变换，其中Ω为采样空间。遗传算法是目前研究的进化算法中三种典型算法之一，其他两种分别是进化规划和进化策略。进化规划的特点在于没有使用交叉算子，采用随机选择机制，因而变异在进化过程中占据重要地位。
对于各种进化计算方法，存在一个非空集合I，I称为这个进化计算的个体空间。当将进化计算用于优化搜索时，每一个个体i∈I代表了优化问题的一个候选解。编码方案可以形式化地定义为解码函数。
定义1:令I为一个非空的集合，目标函数f:Rn→R(Rn为n维的实数空间)。若存在一个映射D:I→Rn，则称D为一个解码函数。
在定义1中，不要求D是一个满映射。D的值域确定了进化计算的实际搜索范围。个体i∈I的适应度值代表了候选解D(i)∈Rn的品质，这种为每个个体产生适应度数值的函数称为适应度值函数，它是进化计算过程中实际上的优化对象。适应度值函数可以用数学形式定义，下面给出其定义。
定义2:令I为一个非空集合，目标函数为f:Rn→R，解码函数D:I→Rn，则称映射Φ
Ts×f×D为适应度值函数。其中映射Ts:R→R称为实值标度函数。
由定义2可知，目标函数f由问题确定，解码函数D和实值标度(Scaling)函数Ts则需自己设计。
进化计算的执行过程通常从集合I的随机采样和替换开始，所得到的初始集合称为初始种群，记为P(0)。在进化第t代时，群体P(t)＝{i1(t)，…，iμ(t)}是由个体ik(t)∈I组成，个体数目μ称为种群规模或群体大小。
定义3:令I为一个非空集合，μ，μ′∈Z＋分别代表父代种群规模和子代种群规模，则映射T:Iμ→Iμ′被称为一个种群变换。若T(P)＝P′，则称P为父代种群，P′为子代种群。若μ＝μ′，则将它们简单称为种群规模。
定义4:令I为一个非空集合，μ∈Z＋。随机函数
被称为随机种群变换，其中Ω为采样空间。
定义5:令I为一个非空集合，μ′∈Z＋，X为参数空间，Ω为采样空间，则称映射X→T
为一个进化算子，记为evop(I，μ，X，Ω)。
随机种群变换X(Θ)简记为XΘ，种群变换XΘ(ω)也简记为X(Θ)。
进化算子的引入是受到了生物学的启发，它们对达尔文“适者生存”理论的不严格模仿。最常用的进化操作算子包括重组(或者交叉)、变异和选择，其中重组算子是最具有一般性的算子。重组算子不同于其他算子的特性在于，后代种群中至少有一个个体的形式依赖于一个以上的父代个体。下面的定义反映出这种变换的特征。
定义6:令r∈evop(I，μ，X，Ω)，若存在P∈Iμ，Θ∈X，ω∈Ω使得在后代种群rΘ(P)中至少存在一个个体依赖于P中的多个个体，则称r为一个重组算子。
与重组算子相对应，变异算子的特性在于，后代种群中的个体至多依赖于一个父代个体。变异算子的定义如下。
定义7:令m∈evop(I，μ，X，Ω)，若对于所有的P∈Iμ，所有的Θ∈X，所有的ω∈Ω，后代种群mΘ(P)中的个体至多只依赖于P中的一个个体，则称m为变异算子。
选择算子的特性与前两个算子不同，它要求后代种群中的所有个体都是父代种群中的成员，且其种群变换依赖于父代种群中个体的适应值。
定义8:令s∈evop(I，μ，X，Ω)，若对于所有的P∈Iμ，所有的Θ∈X，所有的适应度值函数Φ:I→R，满足:∀i∈S(Θ，Φ)(P)⇒i∈P，则称S为选择算子。
以下给出一些简单的符号表示及其含义。
f:Rn→R记为被优化的目标函数，不失一般性，通常考虑函数最小化问题。(www.chuimin.cn)
适应度函数Φ:I→R，其中I是个体空间，通常不要求个体的适应度值与目标函数相同，而f是Φ的变量，i∈I记为个体，x∈Rn为目标变量，μ≥1记为父代群体规模。
λ≥1为子代群体规模(λ相当于定义5中的μ′)，即在每一代交叉和变异后产生的个体数。
在进化第t代，群体P(t)＝{i1(t)，…，iμ(t)}由个体ik(t)∈I组成。
r:Iμ→Iλ记为交叉(重组)算子，其控制参数集为Θr。
m:Iλ→Iλ记为变异算子，其控制参数集为Θm，这里r、m均指宏算子，即把群体变换为另一个群体，将相应作用在个体上的算子分别记为r′和m′。
选择算子S:(Iλ∪Iμ)→Iμ用于产生下一代群体，其控制参数集为Θs。
∧Iμ→{T，F}记为停止准则，其中T表示真，F表示假。
根据上述符号表示，可以将进化算法的过程用统一的框架表示如下。
这里Q∈{∅，P(t)}是选择步骤中附加所考虑的个体集合。上述只是进化算法的一个通用的框架，还有一些其他的变化形式。
遗传算法是目前研究的进化算法中三种典型算法之一，其他两种分别是进化规划(EP)和进化策略(ES)。尽管它们之间很相似，但历史上这三种算法却是彼此独立地发展起来的。遗传规划(Genetic Programming，GP)可以认为是在遗传算法的基础上发展改进得到的。
在20世纪60年代中期，Fogel等为有限状态机的演化提出进化规划方法来求解预测问题。这些机器的状态变换表是在对应的离散、有界集上进行均匀的随机变异。进化规划根据被正确预测的符号数来度量适应值。父代群体中的每个机器通过变异产生一个子代，父代和子代中最好的个体被选择生存下来。进化规划的特点在于没有使用交叉算子，采用随机选择机制，因而变异在进化过程中占据重要地位。
进化策略的研究始于1964年，当初主要是用于试验处理流体动力学问题，如弯管形态优化。在进化策略的发展中，Rechenberg和Schwefel做出了重要贡献[5]。Rechenberg针对(1＋1)-ES的进化策略研究了其收敛速度理论。(1＋1)-ES是一种简单变异选择机制，每代通过高斯变异作用在个体上产生一个子代。Rechenberg还首次提出了(μ＋1)-ES，该策略是将μ(μ>1)个个体经过选择形成的一个子代替换掉变异后最差的父代个体。
后来，Schwefel在Rechenberg研究的基础上，提出了(μ＋λ)-ES和(μ，λ)-ES策略。前者是针对多父本和子本的，在算法过程中μ个父本产生λ个子本，这(μ＋λ)个候选解同时参加竞争并且适者生存(一般生存数目为μ)；后者也是针对多父本和子本的，在算法过程中μ个父本产生λ个子本，但只有这λ个候选解参与竞争，然后父本被完全取代，即每个候选解的生命期只限在当前代。这两种策略尤其是后者在进化策略中占据着重要地位。进化策略的特点在于变异是主要的，交叉是次要的，选择算子是确定型的，并将某一部分个体排除在外。
以下对遗传算法、进化规划和进化策略三类方法的特点和区别进行简单总结和比较[1]。
遗传算法的特点是:交叉算子是主要的，变异操作是次要的；规定选择概率取非零的数值。
进化规划的特点是:没有交叉；变异很重要；选择时采用随机机制，某些个体不参与选择过程。
进化策略的特点是:适应度值函数直接等于目标函数；变异操作是主要的，交叉操作是次要的；选择过程是确定的，部分个体不参与选择过程，只在λ个个体中进行选择操作。
目前在进化计算领域，遗传算法是最广为人知的进化算法，以遗传算法的研究和应用最为广泛和深入，在多目标进化算法中，遗传算法作为主要的进化模型也是被采用最多的。
有关多目标群体智能优化算法的文章
- 详细阅读
-
多目标群体算法萤火虫算法详细阅读
萤火虫算法的核心思想是萤火虫被绝对亮度比它大的萤火虫所吸引，并根据位置更新公式更新自身的位置。考虑到萤火虫i的亮度随着距离的增加以及空气的吸收而减弱，可以定义萤火虫i对萤火虫j的相对亮度为:式(5.1)中，Ii为萤火虫i的绝对亮度，等于萤火虫i所处位置的目标函数值；γ为光吸收系数，可设为常数；rij为萤火虫i到萤火虫j的距离。γ为光吸收系数，表示吸引力的变化，它的值对萤火虫算法的收敛速度和优化效果有很大的影响。......
2023-11-26
-
多目标蚁群算法模型优化详细阅读
算法根据决策变量X和式～式的约束条件依次确定任务续传调度标识符和相应的执行时间，从而得到决策变量X的目标函数。图9-27可用时间窗口更新交叉；嵌入；包含；无关确定所有任务的续传调度标识和执行时间后，计算目标函数F=｛f 1，f 2，f 3｝，即可评价此调度方案优劣。......
2023-07-02
-
多目标算法解决高维问题详细阅读
为有效求解高维多目标优化问题，研究者从不同的方面开展研究，概括起来可分成如下几类。使用改进的支配关系为提升Pareto支配关系在高维多目标优化问题上的选择压力，一些改进的支配关系陆续提了出来。Yuan等[54]将高维多目标降维问题视为一个3-目标的优化问题，并从维持解群的支配结构和目标相关性出发定义了目标函数。......
2023-11-26
-
生成图算法，形式化构件装配详细阅读
生成式程序设计包括两个开发周期——领域工程和应用工程。应用工程与领域工程不同，开发人员是根据用户的需求开发特定的系统，没有对领域的对象进行抽象。领域工程和应用工程并不存在先后顺序，而是两个并行的过程。生成式程序设计目标集中于特定领域，因此必须要对“领域”这个概念先有一个理解。在领域模型的基础上，设计、开发和组装可复用资源。下面详细地介绍领域工程中的三个不同阶段——领域分析、领域设计以及领域实现。......
2023-10-26
-
多序列比对算法形式化实现详细阅读
本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。prog构件该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。result_op构件该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。......
2023-10-25
-
多目标蚁群算法的设计与优化详细阅读
为消除各类约束导致的大量任务间冲突，获得问题的Pareto解集，本书采用多目标蚁群算法优化任务的调度顺序。由于本章算法为多目标蚁群算法，因此本章算法采取与第3章的优化算法不同的启发策略。本章算法多目标蚁群算法采用自适应策略，在算法起始阶段，启发选择比例参数q 0［式（3-6）］取较大值利于加快收敛速度；在算法搜索后期，选择较小的q 0值可增加种群多样性。......
2023-07-02
-
多目标群体智能算法-萤火虫算法基础详细阅读
同其他的智能优化算法相比，萤火虫算法概念简单，流程清晰，需要调整的参数较少，更加容易实现。虽然目前萤火虫算法还缺乏完备的数学理论基础，但已有的仿真实验结果表明，萤火虫算法具备较高的寻优精度和收敛速度，是一种可行有效的优化方法，它为智能优化提供了新的思路[2]。......
2023-11-26
相关推荐