改进的多目标遗传算法在结构优化设计中的应用.doc

改进的多目标遗传算法在结构优化设计中的应用

关志华作者简介：关志华（1971-），男，天津大学管理学院99秋季博士，主要研究方向为多目标进化算法及其应用。

（天津大学管理学院9013信箱天津300072）
万杰
（河北工业大学管理学院天津300000）

摘要本文探讨了多目标遗传算法（MOGA）存在的问题，并提出了相应的改进策略。这些策略包括：小生境技术、适应度共享策略、交叉限制、改进的终止准则等。通过采用这些策略对MOGA进行改进，使之可以克服在终止准则和小生境形成上的缺陷，从而使算法既可以对问题空间进行更广泛的搜索又可以可靠的、迅速的收敛于优化解，为最终决策提供了帮助。最后，给出了改进的MOGA在结构优化设计中的两个应用实例。
关键词多目标优化问题，结构优化设计，遗传算法

1引言
带有m个目标函数的多目标优化问题(MOOP)的数学表达式如下：

由于在MOOP中，多个设计变量有时是相互矛盾的。所以，这里的最小化（Minimize）问题，从实际意义上来说，其实是指当综合考虑所有的目标函数时的优化解（Pareto解）。尽管也许全部的目标函数都不能优化到它们各自作为单目标函数时的最优解，但是，在多目标情况下，对其中任意一个单个的目标函数的优化都不能以降低其它函数的优化解为代价。这就是多目标优化不同于单目标函数优化的地方，也正是它的难点。这里，为了区别进化过程中的Pareto解集和MOOP最终得到的Pareto解集，我们把进化过程中的Pareto解集称为近优解集（non-inferior），而在其它文献中这两个名词通常表示同一概念。
适用于多目标优化问题的遗传算法（MOGAs）是在经典遗传算法（GAs）的基础上修改得到的。多目标优化问题的遗传算法在适应度分配策略上不同于经典遗传算法。本文探讨了现有的MOGAs的主要缺点，并在此基础上提出了一些改进策略。
在使用MOGA进行多目标问题优化时，为了得到最终的解集，MOGA必须对尽可能多的近优解集进行分析，而这些解是均匀的分布在解空间中的，这就会使MOGA的效率降低。但是，只有求得大量的解才可能得到一个连续的、平滑的Pareto曲面，从而使MOGA可以尽快地收敛于优化解。当然，收敛速度同时也依赖于终止准则的选取。在单目标优化问题中，终止准则可以定为：“在N代进化中适应度值没有改进”或直接定为“进化N代”，而在MOGA中却不能如此简单的定义，因此，需要有一种策略来检测MOGA是否已经得到了Pareto解集。
目前,MOGA存在如下主要问题:
(1)如何指导种群跳出相邻的小生境（niche）从而尽可能的搜索更多的Pareto集。要做到这一点，必须同时满足两个相互矛盾的条件，1）算法必须能够识别近优解集中的群体或个体簇是来源于哪个小生境。因为在进化初期会产生许多小生境，随着进化过程的进行，这些小生境将会扩张超出其边界，这有可能会导致MOGA难以收敛或导致进化过程更接近随机搜索过程，从而效率低下。通过在父代选择阶段采取一些改进策略可以避免这个问题。2）算法必须能阻止这些小生境中的群体过分地集中一些适应值较高的个体附近，而使得小生境过分收缩。从而可能会导致过早地收敛与近优解集。要避免这个问题，可以禁止同一个小生境中的父代交叉。这两个条件一个要尽量抑制小生境的扩张，另一个又要为保持小生境群体的多样性而使它在一定范围内扩张。也就是在一定范围内的多样化。
(2)怎样加入一些特定的终止准则，这些特定的终止准则可以有效的检测出进化过程中是否产生了Pareto集，并且检测出这些Pareto集是否是均匀分布的。均匀分布的Pareto集中的解不应该在某些区域中解过于集中；而在另一些区域中过于分散。这些Pareto解过于集中和过于分散的区域往往是小生境正在形成的区域，如果这时终止算法的话，就可能使算法过早地收敛于局部优化解而得不到全局的优化解。
(3)如何使设计者有一个相对自由地选择来对它感兴趣的特定区域进行放大，以便进一步对特定区域进行优化。这样做的好处是：设计者可以在某个特定的阶段选择特定的区域，从而可以人为地控制这个阶段的种群大小，以较小的种群获得较好的结果和较快的收敛效果，使算法运行效率较高。它的不足之处在于较小的种群规模可能无法覆盖整个可行域。

改进的MOGAs

2.1改进的终止准则
改进的终止准则可按如下步骤进行：
从当前近优解集中指定一个佳点（或由设计者直接指定），计算每个个体与这个佳点的距离，形成一个距离矩阵；
计算这个距离矩阵的均值和标准偏差；
随着进化代数的增加，近优解集中的点逐渐聚拢，因此，距离矩阵中的元素值逐渐减小，这个过程可以由其均值反映出来；而个体的分布程度可以由标准偏差的增大反映出来。
如果均值的减小到小于某一个给定值，则可以认为算法收敛并终止算法。否则，转向步骤a)。
2