《遗传算法求解多目标问题的有关方法综述》由会员分享，可在线阅读，更多相关《遗传算法求解多目标问题的有关方法综述（7页珍藏版）》请在金锄头文库上搜索。
1、遗传算法求解多目标问题的有关方法遗传算法求解多目标问题的有关方法 将目标函数综合的方法将目标函数综合的方法 遗传算法需要一个标量的适应度信息才能进行计算， 所以很自然的都会想到将所有的目 标函数用加法，乘法或者其他的各种可能想出来的数学方法综合成为一个单一目标。但 是这种方法存在明显的问题，首选是在目标函数取值范围内必须能够提供精确的信息， 以避免其中的一个目标函数会明显优于其他值， 这就要求我们至少在某种程序上可以估 计出每个目标函数的取值，而这对于现实的问题往往会是一个相当昂贵的，无法承受的 过程。但是，如果将所有目标函数综合起来的方法确实可行，那它不仅仅是一个最简单 的方法，而且也将是最
2、有效的方法，因为不再需要其他需要决策者参与的交互过程。而 且如果GA算法成功的找到了适应度最佳的点，那么该点至少是一个可能的最优点。 1. 权重法权重法 这种方法将所有的目标函数乘以不同的权重，再加和起来作为有待优化的单一目标。 ( ) =kiiixf1min 不同的权重将得到不同的结果，而对于如何选取权重知之甚少，所以用这权重法求解的 一种方法就是采用各种不同的权重，从而得到一组解，但是这时仍然需要决策者从这些 可行解中根据自己的要求做出最佳选择。 需要指出的是权重系数虽然可以反应各个目标函数值的重要性，但是却并不成比例关 系。如果我们希望权重可以与目标函数成比例，那就需要将它们转化成统一的
3、单位。 应用 优点与缺点优点与缺点 这种方法是采用遗传算法求解多目标问题的第一种方法。 这种方法的优点就是它的效率 （单纯从计算量的角度考虑），同时可以得到一个很好的非劣解作为其他方法的一个初 值，主要缺点则是在我们没有足够的关于此问题的信息时，无法确定合适的权重系数。 此时得到的任何最优解都是权重系数的函数。大多数的研究都使用简单的线性函数，由 多次不同权重的计算来生成非劣解集。这种方法非常简单，易于使用，但是有时会丢失 非劣解集平面的凹陷部分1，这是一个相当严重的问题。 2.目标规划法目标规划法(Goal Programming) Charnes 2 and Ijiri 3 提出了线性模型
4、的目标规划法，在解决工业问题的计算中起了 相当重要的作用。在这种方法中，决策者需要确定每一个目标函数所要达到的值，这些 要求作为额外的约束条件引入到问题中去。 于是目标函数就转化为最小化这些目标函数 值与相应要求值之间的差距。最简单的表述形式是 4: =kiiiTxf1)(min 更常见的一种形式是再在上式基础上进行加权5，也常称通用用目标规划法 6, 7，这 种方法也被一些人称为目标向量优化 8. 优点与缺点优点与缺点 如果所决定的目标点在可行域内，这种方法可以得到一个非劣解，同时由于明确了所要搜索的目标，所以计算效率很高。但是由于此目标是由决策者给出的，并且由他决定权 重，因此需要预告可以
5、知道搜索空间的形关。并且，如果可行域很难接近，那么这种方 法的效率将会变得非常之低。 另外就是这种方法也许更加适用于目标函数为线性或分段 线性的情况，因为有现成的计算程序。 3. Goal Attainment 由决策者给出各个目标函数值f1,f2,fk低于或高于预期值b1, b2,bk时的权重向 量12,k，最优解x为求解以下问题所得到的结果： Minimize subject to: 0)(xgj j=1,2,.,m )(xfbiii+ i=1,2,k 需要指出的是得到的最优解将向决策者表示他所预期的目标是否可以得到。 为负值 表明目标可以达到，而正值则相反。 优点与缺点优点与缺点 Goa
6、l attainment 法有不少缺点，其中最主要的一点就是在计算过种中有可能会出现错 误的选择。例如，假设有两个点的目标函数值有一个相同，而另一个有差别，但却可能 有相同的goal-attainment 值，这意味着对于GA算法来说二者没有优劣的差别。 4. Constraint 法法 这种方法提出对所有目标函数中首要的一个进行最小化， 而将其余各个目标函数视为在 某种程度上i可以违反的约束条件，然后通过选取不同的i可以得到非劣解集。 (1)对第r个目标函数进行最小化： )(min)(*xfxfrFxr= 附加约束条件为： iixf)( i=1,2,k, ir (2)对于不同的i重复上述过程
7、，直到得到一个决策者满意的解为止。 根据问题的需要也可能要求选取不同的目标函数， 并且可以先用其他的方法针对每一个 目标函数进行优化，求出它的最佳值，以此作为参考来确定i。 Ritzel 和Wayland 1提出优化过种中将除了某一个目标函数之外的其余各项均设为常 数，。 优点与缺点优点与缺点 最明显的缺点就是耗时太多，而且如果某个问题具有太多目标函数时，针对其进行编码 时可能会有很大困难，甚至不可能。这种方法还试图找到一些较非劣解稍次的解，但是 在某些实际问题（如结构优化）中是不合适的。尽管如此，该方法相对简单，使得在研 究的最初阶段还是很常见的。 为了克服在将各个目标函数进行综合时出现的各
8、种问题，相应的又提出了一些方法，这 些方法一般都是基于population policies，或者对目标函数进行特定的处理。 5.A Non-Generational Genetic Algorithm 这是由Valenzuela-Rend on和Uresti-Charre9提出来的一种方法， 在这种方法里每个个 体的适应度都是在增长的，此方法的思想来源于Learning Classifier Systems(LGS) 10，那篇文章的研究表时每次只将个体中最差的一个替换掉的non-generational 的遗 传算法较之传统的遗传算法要好。 在将这种方法应用到多目标优化时， Valenzu
9、ela-Rend on和Uresti-Charre将目标函数值的比较与各个点之间的分布情况作为两个指标进行线 性综合，得到一个单一的优化目标。 Carlos 11针对这一方法中两个指标的计算做了相应的修改，得到的算法比原来有所改 进。 优点与缺点优点与缺点 这种方法实际上只是Bentley 和 Wakefield 12所提出权重平均排序法（weighted average ranking- WAR）的一种更为精细的版本，主要的优点就在于它可以用一种效率 较高的方法来得到较好的解的分布。 主要缺点是没有办法将决策者对于各个指标不同的 关心程序加入进去，因此会影响对于实际问题的应用，而且也没有提供
10、明确的确定各个 附加参数的方法，往往需要进行很精细的调试才行。 基于基于Pareto非劣解概念的方法非劣解概念的方法 Goldberg 10首先提出在多目标遗传算法的优化中引入基于Pareto非劣解概念的适应 度，下图给出这种方法的基本思路，对个体的优劣性进行排序可以分为几个集合，然后 选择父代个体，在以上信息的指引下使整个种群向着Pareto解的最前线移动。 为了防止GA收敛于最前沿的某一个点，在后来的研究中Goldberg还引入了niche的概 念。 优点与缺点优点与缺点 基于Pareto非劣解概念进行排序的方法最大的缺点在于，没有一种有效的算法在一组可 行解中确定各个非劣解集合8。 传统
11、的算法在个体数增加和目标数增多时性能下降很明 显。而且引入niche概念后其中的参数如何确定也是个问题，而整个算法的性能在很 大程度上又依赖于这个参数的选择。但是无论如何，基于此方法的算法仍然是最合适的 用来生成整个Pareto非劣解前沿算法，它的主要优点就在于此方法不用对于非劣解前沿 的形状或连续性没有特殊的要求，而这对于纯粹的数学规划方法却是很严重的问题。 1 Multiple Objective Genetic Algorithm Fonseca 和 Fleming 13提出了基于一代个体数量的排序方法。如果个体xi在 t 这一代有t ip个体优于它，那么它的rank就是： t iipt
12、xrank+=1),( 所有的非劣解的rank都为1， 而那些较次的点则根据在trade-off平面上对应域的种群密度 加上一个惩罚函数。 适应度的计算通过如下方法进行13： 1.根据各个点的rank对个体进行排序 2.用Goldberg 10提出的方法，计算从最优到最差各点和适应度。 3.将具有相同rank的各点的适应度进行平均，这样它们将具有相同的被选中的概率。这 一过程可以使在保证适当的选择率的情况下整个种群的适应度是个定值。 Goldberg 14指出这种分段式的适应度计算法有可能使算法出现早熟的现象。 为了防止 这种情况，Fonseca 和 Fleming提出引入niche信息的方法
13、，与那些基于变量的方法不 同，他们提出的方法是基于目标函数值的。 优点与缺点优点与缺点 MOGA主要的不足是如果niche信息是基于目标函数的，那么两个具有相同目标函数向 量的不同的个是无法在同一代种群是存在的，这显然是我们不希望看到的，因为这样两 个解可能恰恰就是决策者想要得到的结果。这种方法的优点则是效率较高，而且易于实 现。 2 Non-Dominated Sorting Genetic Algorithm Non-dominated Sorting Genetic Algorithm (NSGA)是由Srinivas 和 Deb 15提出的， 这种方法对个体做很多层次的分类。 在进行选
14、择前， 整个种群先根据非劣解性进行排序， 所有的非劣解个体都被归为一类，同时指定一个虚假的适应度（适应度的值可以根据这 些个体占种群个体数的比例来给出）。为了保证种群的分布，这些个体都具有相同的适 应度。然后这一部分个体被取出其余的个体再采用相同的方法进行分类，直到所有的个 体都被分类完毕。然后采用随机的方法选出个体，因为在最前沿的个体具有最大的适应 度，所以被传递到下一代的可能性也就越大。 优点与缺点优点与缺点 这种方法可以搜索非劣解区域，而且可以使种群很快收敛到这一区域。本算法效率的集 中在那个虚假的适应度上，可以解决目标函数为任意数量的问题16，无论是最大化还 是最小化。同时由于是在变量
15、空间进行比较，所以可以允许具有相同目标函数的不同点 的存在。 有些研究者8提出这种算法的主要缺点是相对MOGA而言效率较低 （不仅仅是 计算速度，也包括所生成Pareto非劣解前沿的质量），而且也更依赖于，但也有些研 究表时它可以得到在Pareto非劣解前沿很好的一个分布。 3 Niched Pareto Genetic Algorithm Horn 和 Nafpliotis 17提出一个基于Pareto概念的对比选择方法。 与两两比较的方法不 同，这种方法同时要引入种群中其他的一些个体作为参考（大多数在10个左右），在这 种比较的情况下如果两个个体还是没有优劣的区分， 那才将它们的适应度进行
16、平均18。 与其他方法相比，这个种方法的种群要明显大很多，所以在种群中出现的niche可以抵 消选择个体时噪音的影响18。 Horn 和 Nafpliotis 17 更提出了将目标函数空间和变 量空间结合起来对适应度进行分配的方法，他们称之为nested sharing。 优点与缺点优点与缺点 这种方法并不是整个种群中进行Pareto非劣解的选择，而仅仅是在每次迭代中的一段进 行，所以运行起来很快，而且可以在很多代都保证一个很好的非劣解的前沿区域8。缺 点就是要选择一个很好的参考个体的数目，使得方法在实际应用中较为复杂。 关于模糊数学在多目标遗传算法中的应用也已经有一定的研究，Brian J19,20提出了 用隶属度函数的形式来计算适应度： =NiiffNF1)(1)()()()( mi
