多目标遗传算法探究及其工程案例应用

宋伟 李志鹏

摘要：针对多目标优化问题，本文提出一种多目标遗传算法（MOGA）。该算法引入重启动策略，从而来避免进化种群过早的收敛到某一局部Pareto最优解。一旦进化种群早熟，则在设计变量空间中重新生成一个进化种群，同时提出一种探测算子在非支配解的设计空间中进行探测性的搜索，以提高收敛效率。采用非支配解排序，将每代中的非支配解集存入一外部种群中，同时为了保持外部非支配个体分布的均匀性，进一步根据个体拥挤距离进行同一非支配级个体的比较和选择。最后将该算法用于求解汽车被动悬架结构的多目标优化设计案例，求解结果表明其具有较强的求解工程问题的能力。

关键词：MOGA；重启动策略；Pareto最优解；探测算子；非支配解

中图分类号：TB 文献标识码：A

文章编号：1672—3198（2014）16—0196—03

1引言

寻求非劣解是多目标决策的基本手段，已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解。围绕多目标决策问题，国内外诸多学者进行了探究。向量评价遗传算法（VEGA）是由Schaffer开发的多目标优化程序，其中包括了多判据函数。VEGA系统的主要思想是将群体划分为相等规模的子群体：每个子群体对于m个目标中的某单个目标是“合理的”，对每个目标，选择过程是独立执行的，但交叉是跨越子群体边界的。进化过程中的适应度评价和选择过程在每一代的进化中都要执行m次。VEGA归根结底仍是一种基于单目标的优化选择过程，难以收敛到非劣解集。Coello和Gregorio提出MicroGA-Moo以及他们在2003年提出的改进算法MicroGA2-Moo，算法中采取一些较复杂的处理方法，使种群多样性和Pareto最优解分布的均匀性较小地受到小规模群体的影响，如在MicroGA-Moo中融入较多敏感参数，并且事先设定各敏感参数值，而在其改进算法中又融入并行进化过程来选择最优遗传交叉算子，实际上算法效率没有很好地提高。Fonseca和Fleming提出了一种基于Pareto群体分级的多目标遗传算法（FFGA），建立了个体的级别与当前群体中被该个体占优的染色体数目的关系，同时Fonseca使用了一种基于共享机制小生境技术来使群体均匀分布在Pareto解集上，FFGA算法简单，易于实现，但它的效率依赖于共享因子的选择，且对之非常敏感。

本文基于上述各算法优缺点，提出基于Pareto排序分级的多目标Pareto遗传算法，主要针对算法过程中的Pareto排序问题、适应度值计算问题、种群多样性保持问题、约束处理等。将改进后的算法应用于求解汽车被动悬架结构参数多目标优化设计案例，求解结果验证了改进算法的有效性。

2多目标遗传算法（MOGA）实现流程

针对基本遗传算法对于工程中的复杂非线性MOP求解的局限性，本文在基本遗传算法的基础上提出了多目标遗传算法（MOGA）。在MOGA中，不是简单地为各个体分配适应度值，而是针对种群中各个体首先计算它的非支配级和个体拥挤距离，并根据这两个值进行个体间的比较和选择操作。非支配级和个体拥挤距离分别是通过非支配分级操作及NSGA-ΙΙ的个体拥挤距离计算方法得到的。在两个个体进行比较时，首先比较它们的非支配级，非支配级数小的个体要优于级数大的个体。若非支配级数相同，则比较它们的个体拥挤距离，个体拥挤距离大的个体要优于该值小的个体。非支配数为1的个体即为当前的非支配个体，它们将被保存到一个外部种群Pe中。以上的个体比较和选择操作是针对无约束优化问题的，对于带约束的多目标优化问题，则采用Deb等人提出的约束处理方法来处理约束。该方法就是对每个个体计算一个约束违反值，当两个个体进行比较时，首先比较其约束违反值，该值越小的个体越优，约束违反值为零的个体为可行解，当两个个体均为可行解时，则采用无约束问题的个体比较操作进行比较。

在遗传算法进化过程中，当连续M代的外部种群Pe都相同或者相近时，则种群收敛到解空间某一局部最优区域，此时则采用重启动策略，即重新在自变量空间中随机生成一同规模大小的新种群，同时采用探测算子法生成两个新个体，然后将这两个新个体与外部种群中的个体进行非支配关系比较，若新个体没有被外部种群中的任何一个个体支配，则把它加入外部种群中，并去掉其中被它所支配的个体。

3多目标遗传算法（MOGA）实现技术

3.1非支配分级

非支配分级就是根据基于Pareto思想进行非支配排序分级，将个体按照级数从高到低的顺序进行排列。级数高的个体适应度值优于级数低的个体，其中级数为1的个体为当前种群中的非支配个体。在MOGA中采用了一种快速高效的非支配排序方法，该方法的具体实现过程如下：

（1）初始化个体集Di和非支配个体集Fj，令j=1；

（2）对每个个体i计算种群中支配它的个体数目值ndi，同时将被它支配的个体放入个体集Di，并将种群中ndi=0的个体放入第1级非支配个体集Fj中；

（3）令第j+1级的非支配个体集Fj+1=，将Fj中的个体从种群中剔除，再把其中的每个个体的ndi均减去1，在这个过程中如果没有某个个体的ndi=0，则将该个体放到Fj+1中；

（4）j=j+1，若各非支配个体集中的个体包含所有种群个体，则终止，否则转到步骤3。

经过上面的非支配排序分级后，种群中所有个体就都被分配到各个非支配个体集Fj，j=1，2，…。

3.2种群多样性保持策略

针对MOGA多样性保持问题，本文提出采用两个种群来确保种群多样性：一个种群是用来保持进化种群中个体遗传基因多样性的重启动策略；另一个种群则是用来保持外部非支配个体种群多样性的个体拥挤距离比较方法。

3.2.1重启动策略

MOGA中所采用的重启动策略的基本思路与GA的大致相同，但MOGA是用于多目标优化问题的求解，由于多目标优化问题的最优解一般是一组无法相互比较的解，因此它所采用的重启动策略在具体实现时与用于单目标问题求解的GA不同主要体现在以下两方面：

（1）重启动判断条件不同：在MOGA中，若连续M代的外部非支配种群Pe相同或者相似，则认为此时的种群收敛到解空间的局部最优区域，因此重启动判断条件参数为外部种群连续相同的代数M，在本文中，M也称为重启动判断参数，其值为事先设定值；

（2）重启动方式不同：MOGA中不仅在搜索空间内随机生成一规模数相同的新种群，还采用了一种探测算子在非支配解区域进行探测性的搜索，即通过探测算子法得到两个新个体，然后将生成的新种群和两个新个体与外部种群合并进行非支配排序分级。这样既可以提高种群的多样性，同时加强算法的局部搜索能力。

探测算子是一种用来在当前非支配解区域实现探测性搜索的算子。它生成以下两个新个体E1和E2：

公式（3）、（4）中，n表示子目标的个数，l表示当前外部种群中非支配解的个数。

3.2.2个体拥挤距离比较方法

传统上拥挤距离法中的共享参数需要事先设定预设值，本文提出的方法不需要预设参数值。具体操作步骤如下：首先分别计算各级Fj中各个体的拥挤距离，按照拥挤距离从大到小的原则对各级非支配个体集中的个体进行排序，拥挤距离大的个体适应度值优于拥挤距离小的个体。个体的拥挤距离即计算该个体相邻的两个个体在各个目标上的欧式距离之和来表示的。计算个体拥挤距离时，首先按照各子目标将个体在该子目标值下以从大到小的顺序进行排列，再根据公式（5）在每个子目标上都进行一次计算：

3.3最优个体保持策略

在MOGA中，当代种群中的非支配个体之间在不设置权值的情况下是无法比较优劣的，因此执行精英策略时一般将该代的所有非支配个体都保留到下一代的进化种群中。

4性能测试及评价

本文将MOGA应用于求解汽车被动悬架结构参数优化的案例中。汽车悬架是把车架（车身）与车桥（车轮）弹性连接起来的所有装置的总称。作为连接车身与车轮的传力部件，它的特性直接影响着汽车乘坐舒适性、操作稳定性和行驶安全性等性能，并且这一特性对汽车各方面性能的影响是相互矛盾的，即优化问题的各子目标间相互矛盾，故需要对悬架结构参数进行多目标优化设计。

4.1多目标优化问题的建立

悬架按照其控制力的施加形式一般可分为被动悬架、半主动悬架和主动悬架。其中被动悬架由于结构简单、性能可靠以及成本低等特点，是目前应用的最为广泛的类型。但是被动悬架设计完成后，其刚度参数和阻尼系数参数是确定的，因此需建立数学优化模型对其参数进行优化以尽可能获得更优的性能。一般情况下对于被动悬架来说，要获最佳的乘坐性能，悬架应该“软”一些，但要获得好的汽车操控性能，悬架又应该“硬”一些。这两者之间是相互矛盾的，但又都是汽车性能比较重要的方面，于是对被动悬架参数进行优化设计时，这两个方面都应该考虑到。另外行驶安全性也是与悬架相关的汽车性能的重要方面，在优化设计时也应考虑。

鉴于汽车本身为复杂的振动系统，为了便于数学分析，通常采用简化模型。图1所示为一个二自由度1/4汽车振动的简化模型。其中m1和m2为轮胎和车体的质量，k1和k2分别为轮胎和悬架的刚度，r2为悬架的阻尼系数，ζ、x1和是评价乘坐舒适性的主要指标，悬架动行程x2-x1不仅会影响乘坐舒适性，而且还要受悬架工作空间的限制，轮胎位移x1-ζ主要与操纵稳定性和行驶安全性相关。因此在优化时选择这三个响应的均方值作为优化目标，而悬架参数m由图2可知，本文提出的MOGA算法的种群进化700代是得到的Pareto最优解集的分布较均匀。由表1及表2可知，与初始设置参数下的被动悬架相比，车身加速度的均方根值减少幅度较大，最多达到17%，悬架行程和轮胎位移则最多可分别达到9%和5%。因此上述优化结果证明了MOGA对于多于三个子目标的工程优化问题具有较强的求解能力，算法是可行的、有效的。

参考文献

[1]Schaffer J D.Multiple objective optimization with vector evaluated genetic algorithms[C].In：Proc.Of 1st Int.Conf.On Genetic Algorithms and Their Application，Lawrence Erlbaum Associates，1985：93100.

[2]Gregorio T P and Carlos A.The micr0 genetic algorithm 2：towards online adaptation in evolutionary multiobjective optimization[C]. In： Evolutionary，MultiCriterion Optimization Second International Conference（EMO 2003）.Faro，Portugal，2003：252266.

[3]Fonseca C.M.，Fleming P.J.，Genetic Algorithms for multiobjective optimization：formulation，discussion and generalization[C].In S.Forrest Ed.Proceedings of Fifth International Conference on Genetic Algorithms（San Mateo，California，1993），University of Illinois at UrbanaChampaign：Morgan Kaufman Publishers，1993：416423.

[4]Deb K，Pratap A，Agarwal S，et a1.A fast and elitist multiobjective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182197.

[5]Deb K.An efficient constrainthanding method for genetic algorithms[J].Computer Methods Appl.Mech.Eng.，2000，186（24）：311338.

[6]Deb K，Pratap A，Agarwal S，et a1.A fast and elitist multiobjective genetic algorithm：NSGA II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182197.

[7]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.

[8]余志生.汽车理论（第2版）[M].北京：机械工业出版社，1990.