2022年遗传算法在多目标优化的应用：公式,讨论,概述总括 .pdf

遗传算法在多目标优化的应用：公式，讨论，概述/总括概述本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（ niche formation method）在此也有适当的延伸 , 并提供了群落大小界定的理论根据。 适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。1. 简介求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解， 仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法 (Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集，简化了多目标问题的优化求解步骤。多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣， 这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点， 我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最后对非劣解集的逼近。考虑一个 n维的多目标规划问题， 且均为目标函数最大化，其劣解可以定义为： fi(x*)fi(xt) i=1 ，2，?，n (1) 且式(1) 至少对一个 i 取“”。即至少劣于一个可行解的x必为劣解。对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解， 并以生成的新解予以替换。 经过数量足够大的种群一定次数的进化计算， 可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。个体的适应度计算方法确定后，为保证能得到非劣解集， 算法设计中必须处理好以下问题： (1) 保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解， 所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 后期时种群接近收敛不同， 多目标遗传算法中要求都要保持解的多样性以适应对已得到的优解 ( 也就是最后非劣解集的备选集) 能再进行更新。 (2) 优解的选择替换。算法必须能选出表现更好的解，并避免由于优解的替换不当使得解集收敛于同一个方向， 并使得解集的分布具有一定程度的均匀性。从上述思路出发， 本文在多目标遗传算法中使用了针对多目标的个体适应度确定方法，对交叉和变异概率依据种群和进化代数进行自适应调整，并控制种群个体并行向非劣解集前沿面逼近。二 向量评估基因算法Schaffer 在1984 年提出一种向量评价的遗传算法。它通过以目标向量的各个分量作为适应度来选择出几个等规模的子群体, 交叉和变异的操作则在由子。群体组成的整个群体内进行。即在每一代，基于个目标函数适应度的计算，产生一定数目的子种群， 子种群的大小为 N/q,q 为目标函数的个数， 然后将产生 q个子种群的后代混合起来成为新的种群N 继续杂交。杂交采用离散重组，变异采用均匀变异。然而1989年理查德提出：将所得的全部新个体都划分到同一个种群内，相当于将全部适合度符合的向量点集，线性划归到同一适合度函数曲线上。因此当下的效率权衡就取决于当下新组成的群体。实质上它是一种权重取于当前世代的适应度函数线性求和的将多目标合成单一目标的优化方法。在最优集的基础上 , 提出一种将各个目标值直接映射到适应度函数中的基于秩的适应度函数。 因此下一章我们提出： 提出了用于对整个种群的个体进行排序的结合目标值及其优先级偏好信息的关系算子。三以等级分三类的方式体现适应度分配方法在多目标优化遗传算法中的应用将 Xi 视为 t 子代中的一个个体， 该个体符合适应度函数Pi(t),假设其余全部个体都在现存种群中，则Xi 在该种群中的位置，可用以下函数表明：函数(Xi,t)=1+pti)(其余所有不完全符合Pi(t)的个体则被分配到等级1（rank1）的函数曲线上， 见图1.（见原稿 figure 1multiobjective ranking） ，这和 Fourman1985年提出的分类筛选的方法有所不同， 该等级分类的方式明确表明处于等级3 的个体劣于处于等级2的个体，原因在于后者 （等级 3）函数曲线对现存个体的描述较为粗略。但 1989年 Goldberg,提出的方法则忽略了这两的等级存在的些微差异。关于适应度分配方法我们应认识到： 不需要将某代该种群中的各个等级都呈现出来，例如图 1 中等级 4 的缺失即为一很好的例证。 传统的适应度按等级的分配方法在此有了一定延伸：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 1. 按等级找种群2. 将全部个体按适应度从最优 （等级 1） 排到最劣 （等级 n,其中 n 小于等于 N） ，从某方面看，该曲线一般为线性关系，但也不尽然。3. 按适合度将每个个体都分配到同一等级，则这些个体被选中继续作为下一代亲本的几率是相同的。值得注意的是该方法使得全球各种群的适应度具有连续性，并维持了适当的筛选淘汰的压力。上述所指的适应度分配方法仅为传统/标准方法的一个延伸， 适用于单目标优化或无相互竞争的多目标优化。四 基于小生境技术遗传算法适应度分享法可以有效地在复杂多峰函数优化问题中避免基因个体的堆积，保持群体的多样性。 这里引进的另一个遗传算法的矢量share需要特别注意。 现存的理论把share的价值设定为解集有优先知道的有限个峰和均匀小生境组成。在收敛上， 适应度高的个体将取代原有的结构相似的个体。另一方面，在多目标优化问题中的全体解的个体适应度是均匀单调的，而且无法预知解集的大小。 函数的运用已经强制性使搜索集中在在全体最优解中。通过在目标价值范围内应用使用度分享比在多种解决范围内要好。，并且只有在总体操作空间的两两间非支配个体间才能进化出均匀分配表现。适应度共享函数的直接目的时将搜索空间的多个不同峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例大小与峰值高度有关。为了实现这样的分布，共享法将个体的目标适应度降低得到个体邻集密集程度的估计。适应度函数共享法多少独立于现在使用的选择方法。4.1 对share的选择s h a r e的建立意义是较好峰值之间个体的最小距离，其建立基础是分享法将个体目标适应度降低。 通过以上部分， 我们无法知道在不同解决范围内多目标优化问题解集的大小，由于它依赖于目标函数图像。然而， 在目标价值范围内和由于非支配个体定义，一个更高的限制对于解集的大小可以被计算通过最小值和最大值评价各个目标假设在那个解集内。另S为不同解决方法范围内的解集。f(S) 为目标范围内的解集，）（yyq,1y,同时令),()m i n, 1(1mi nmmyyqyqym)()m a x,m a x(,11MMyyqyqyM设 A 是各个不同)(mMjj边界连积的和名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - q11)(iqjjjmMA0)()(11i1qmshareqiqiishareiishareMmMshare0五 在选择算法中混合HIGHER-LEVER的解决方式当遇到既定函数做选择的情况下，决策者需要决定哪个无支配个体作为解。首先，非劣最优目标区域根据特定的问题设定协议，然后用一个清晰地可用的图，这个协议知道找到解终止。 总而言之， 适应度较高的解保留较多而样本，适应度较低的解保留较少的样本甚至被淘汰。进化过程最后一代的最优解就是遗传算法的最终结果。减少解决法案的种类被称为Higher-lever 的结决方案。这个方法并没有缩小寻找的范围，而是减少了非劣最优目标区域寻找最优解的空间。这种适应度解决方式更早前被描述为了接受达成目标的信息，近似的被应用为传统的目标达成方式（ Gembicki 1974）5.1 目标规划法目标规划法解决多目标多约束问题的定义如下)(m i nxfx设 X 为变量， 为可行域， f 为目标函数，代入一下公式可得minx同理gwfiii这里gi是 f 的目标偏好值。wi为权重。对求极限，wi是目标偏差的最小值5.2调整多目标优化方案概括目标信息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 多目标优化函数程序最早描述的是对通过改变个体与个体比较的方法调整目标信息。这使得一个个体优于另一个个体成为可能，即使两个都是无支配个体。这个算法将变得不同并演进了操作面得相关区域。仍然是个最小化的问题，假设两个q 单位的目标向量，)(1yyygqgg,且)(1yyybqbb,且目标向量)(1gggq。同时考虑yg满足一个值， qk,中一个特殊目标。除了一般性的误差，可写成)()(,1, 1;1q,1gygyjgjigiqkjkik，（ A）假设一组可用的目标序列值。甚至，yg不满足任意一个目标，i,e. )( ,q,1gyigii，(B) 或者全部目标，我们可写成）（gjgjqjy,1（C）在公式（ A）中，yg满足目标k+1, ， q 并且，因此将优先于yb，如果他支配yb遵循第一个 k 构成的yg等同于由k 构成的yb。yg将仍在种群中优于yb如果他支配yb遵循剩余的组成个体，或者剩余的种群个体全都不满足目标。通常，yg将优先于yb当且仅当)()()()()q,1()q,1()1()q1(),1(),1(),1(),1(gyyyyyyybbbqbbbgbbbgbbbgpp，在公式（ B）中，yg不满足任何一个目标。然后yg优先于yb，当且仅当它支配yb，i,e, )()(gyyybbgp这种关系的应用优于仅对其进行描述。设所有的目标趋近无穷大将使得算法演进为整个非劣性域的表述。这种表述或许不够精确，受目标规划的影响，在多目标优化问题中比较容易得到偏好信息不同的目标给定相同的优先级，可以避免使用目标函数的距离测度，而距离测度不可避免的依赖于具体问题中给定的目标值大小。这种方法依赖于决策者提供的目标值及其优先级偏好信息，在某种程度上仍取决于决策者对问题的把握程度，需要决策者来决定。六 通过多目标优化遗传算法提高偏好值精确值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 多目标优化遗传算法可以进一步被推广。决策者的行为可看成一些非绝对意义上的效用函数的连续价值体现。效用函数表达了一种决策者结合目标函数对其中一个目标值的偏好大于另一目标值，最后， 是这个函数建立了遗传算法优化种群的基础。建立线性规划模型进行个体比较， 同时对当前种群的个体进行排序，另一方面， 达成决策者两个不同态度的一致。首先， 假设决策者准确的指导优化的对象，比如财政支出。 第二， 决策者只使得优化个体使用多目标优化优越性最广泛的定义。提供目标信息， 或使用分享技术，通常意味着决策者更详尽的态度， 更少直接的效用函数，一个可能甚至不同于遗传算法的过程，但仍是另一个效用函数。一个多目标的基因优化在一般意义上是，由体现决策者对每代种群序列解的评估的标准的基因算法构成。 决策者通过对非劣性最优解和可用的优先信息的应用来表达其偏好，同时通过选择和繁殖产生下一代种群，重复上述选择和繁殖，指导结束条件得到满足。进化过陈过最后一代中的最优解就是用遗传算法最优化问题所得到的最终结果。多目标优化问题中的多个目标之间通过决策相互制约，对其中一个目标的优化必须以牺牲其他目标为代价，一次通常无法找到一个解同时最优化所有目标，而是找到多个解，这些解间很难客观评价他们的优劣性。即多目标优化问题的解不是唯一的而是存在一个最优解集合。七 最初的结果多目标优化遗传算法最直接的应用是Pegasus 气体涡轮机的优化一个完整的发动机非线性模型 （Hancock,1992)，被应用于 SIMULINK(MATHWORKs,1992b)被用来模仿这个系统，给予初始条件数量和操控者参量集。遗传算法被应用在MATLAB(MATHWORKs,1992a;Fleming ,1993),意味着所有的编码精确地计算环境中运行。每一个算法的控制者参量都是Gray 编码， 14 个字节一行，串成70 个字节长度的染色体。一个自由的初始容量为80 和标准两点简化代理交叉算子以及二进制变化的应用。 初始目标价值是设定发动机根据一些执行要求。有四个目标被应用。t最终输出变化达到70%的时间目标：t0.59s t最终输出变化解决在10%的时间目标t1.08s 超越目标，测量最终输出变化相关的值，目标10% rr在这一步骤后测量输出错误4 秒，最终输出变化相关。目标： err10% 在遗传算法的运行过程中，决策者储存了所有的非支配个体进化到现在的一代。该算法运用一定的选择策略从当前种群中选取两父本，由该父本交叉遗传产生的新个体替换种群中最差的个体，不断重复直到终止条件满足。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 图六图 7名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 图 8一个典型的操作图，在40 代后达到初始目标，在图形6 中体现。在这一阶段为输出误差设置更高的目标在图7 中表现， 包含了图六中解集的子集。继续运行遗传算法，更多的定义将被达到在这边区域中。见图八。图九表现了解决方法的可选择观点。在上面举例说明。八结束语遗传算法通过搜集个体种群适合于多目标优化。它能够找到总体最优条件同时能够处理不连续嘈杂的函数。 多目标优化遗传算法的进步表达了人们希望在细节上决定发动机的设计。从简单的Pareto 基础适应任务方法所引出的重要问题是基于非群体小生境多目标优化遗传算法， 应用遗传算法解决多目标优化问题时，个体之间的优劣关系如何比较， 构成什么样的适度函数是算法最重要最关键的。我们通过将个体的多个目标关系转化为单个可直接比较大小的非线性适应度函数，是算法得到在非劣性概念下的一组非劣最优解或者是有效解。染色体编码和基因操作本身， 在未来有很大继续研究学习的前景。在文中由于时间的关系没有来得及对算子的性能做更深入的研究了解。对特定问题设计的遗传算法，编码表示必须有完备性，和算子搜索能力的完备性，约束处理能力，适应反应问题本质及算子具有良好的探索性和利用性。事实上，利用非劣性集合相 关 的 变 化 能 够 区 别 于 怎 样 决 定 相 关 个 体 间 的 不 同 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 鸣谢首先来自 Progtama CIENCIA,Junta Nacional,portugal 作者丰富的知识支持相关文献数学工程（ 1992a） 。MATLAB 相关指导数学工程（ 1992b）.SIMULINK 使用者指导理查德森，利用处罚函数遗传算法指导。191197，摩根卡夫曼卢卡斯， C 和卡特曼， G多种条件目标矢量最优条件利用基因算法，第一部分理论。范沙德尼亚R(1991),CACSD 运用 多目标优化 方法。博士命题。英国Wales,Bangor大学弗莱明， P.J （1985）运用多目标优化进行电子计算机目标程序设计弗莱明， P.J佛塞卡， C,M，克鲁明， T.P 工具箱与开放结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -