Matlab 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Matlab
标  题: 遗传算法求解多目标问题的有关方法
发信站: BBS 哈工大紫丁香站 (Tue May 25 16:10:25 2004)

转于饮水思源站


将目标函数综合的方法
遗传算法需要一个标量的适应度信息才能进行计算，所以很自然的都会想到将所有的目标

函数用加法，乘法或者其他的各种可能想出来的数学方法综合成为一个单一目标。但是这

种方法存在明显的问题，首选是在目标函数取值范围内必须能够提供精确的信息，以避免

其中的一个目标函数会明显优于其他值，这就要求我们至少在某种程序上可以估计出每个

目标函数的取值，而这对于现实的问题往往会是一个相当昂贵的，无法承受的过程。但是

，如果将所有目标函数综合起来的方法确实可行，那它不仅仅是一个最简单的方法，而且

也将是最有效的方法，因为不再需要其他需要决策者参与的交互过程。而且如果GA算法成

功的找到了适应度最佳的点，那么该点至少是一个可能的最优点。

1. 权重法
这种方法将所有的目标函数乘以不同的权重，再加和起来作为有待优化的单一目标。
优点与缺点
这种方法是采用遗传算法求解多目标问题的第一种方法。这种方法的优点就是它的效率（

单纯从计算量的角度考虑），同时可以得到一个很好的非劣解作为其他方法的一个初值，

主要缺点则是在我们没有足够的关于此问题的信息时，无法确定合适的权重系数。此时得

到的任何最优解都是权重系数的函数。大多数的研究都使用简单的线性函数，由多次不同

权重的计算来生成非劣解集。这种方法非常简单，易于使用，但是有时会丢失非劣解集平

权重的计算来生成非劣解集。这种方法非常简单，易于使用，但是有时会丢失非劣解集平

面的凹陷部分，这是一个相当严重的问题。

2.目标规划法(Goal Programming)
Charnes  and Ijiri 提出了线性模型的目标规划法，在解决工业问题的计算中起了相当重

要的作用。在这种方法中，决策者需要确定每一个目标函数所要达到的值，这些要求作为

额外的约束条件引入到问题中去。于是目标函数就转化为最小化这些目标函数值与相应要

求值之间的差距。
优点与缺点
如果所决定的目标点在可行域内，这种方法可以得到一个非劣解，同时由于明确了所要搜

索的目标，所以计算效率很高。但是由于此目标是由决策者给出的，并且由他决定权重，

因此需要预告可以知道搜索空间的形关。并且，如果可行域很难接近，那么这种方法的效

率将会变得非常之低。另外就是这种方法也许更加适用于目标函数为线性或分段线性的情

况，因为有现成的计算程序。

3. Goal Attainment
由决策者给出各个目标函数值f1,f2,………fk低于或高于预期值b1, b2,………bk时的权重

向量ω1ω2………,ωk，最优解x为求解以下问题所得到的结果：
Minimize α
subject to:       j=1,2,……..,m
        i=1,2,………k
需要指出的是得到的最优解α将向决策者表示他所预期的目标是否可以得到。α为负值表

明目标可以达到，而正值则相反。
明目标可以达到，而正值则相反。
优点与缺点
Goal attainment 法有不少缺点，其中最主要的一点就是在计算过种中有可能会出现错误

的选择。例如，假设有两个点的目标函数值有一个相同，而另一个有差别，但却可能有相

同的goal-attainment 值，这意味着对于GA算法来说二者没有优劣的差别。


4.ε –Constraint 法
这种方法提出对所有目标函数中首要的一个进行最小化，而将其余各个目标函数视为在某

种程度上εi可以违反的约束条件，然后通过选取不同的εi可以得到非劣解集。
(1)对第r个目标函数进行最小化：

附加约束条件为：
   i=1,2,……k, i≠r
(2)对于不同的εi重复上述过程，直到得到一个决策者满意的解为止。
根据问题的需要也可能要求选取不同的目标函数，并且可以先用其他的方法针对每一个目

标函数进行优化，求出它的最佳值，以此作为参考来确定εi。
Ritzel 和Wayland [1]提出优化过种中将除了某一个目标函数之外的其余各项均设为常数

。
优点与缺点
最明显的缺点就是耗时太多，而且如果某个问题具有太多目标函数时，针对其进行编码时

可能会有很大困难，甚至不可能。这种方法还试图找到一些较非劣解稍次的解，但是在某

些实际问题（如结构优化）中是不合适的。尽管如此，该方法相对简单，使得在研究的最

些实际问题（如结构优化）中是不合适的。尽管如此，该方法相对简单，使得在研究的最

初阶段还是很常见的。


5.A Non-Generational Genetic Algorithm
这是由Valenzuela-Rend on和Uresti-Charre[9]提出来的一种方法，在这种方法里每个个

体的适应度都是在增长的，此方法的思想来源于Learning Classifier Systems(LGS) [10

]，那篇文章的研究表时每次只将个体中最差的一个替换掉的non-generational 的遗传算

法较之传统的遗传算法要好。在将这种方法应用到多目标优化时，Valenzuela-Rend on和

Uresti-Charre将目标函数值的比较与各个点之间的分布情况作为两个指标进行线性综合，

得到一个单一的优化目标。
Carlos [11]针对这一方法中两个指标的计算做了相应的修改，得到的算法比原来有所改进

。
优点与缺点
这种方法实际上只是Bentley 和 Wakefield [12]所提出权重平均排序法（weighted aver

age ranking- WAR）的一种更为精细的版本，主要的优点就在于它可以用一种效率较高的

方法来得到较好的解的分布。主要缺点是没有办法将决策者对于各个指标不同的关心程序

加入进去，因此会影响对于实际问题的应用，而且也没有提供明确的确定各个附加参数的

方法，往往需要进行很精细的调试才行。
--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝


※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.229.*]