基于遗传算法的多目标优化算法(matlab实现)

1 理论基础

1.1 多目标优化及Pareto最优解

        多目标优化问题可以描述如下：         其中，f(x)为待优化的目标函数；x为待优化的变量；Ib和ub分别为变量x的下限和上限约束；Aeq*x=beq为变量x的线性等式约束；A*x≤b为变量x的线性不等式约束。         在图1所示的优化问题中，目标函数f1 和f2是相互矛盾的。因为A1B2,也就是说，某一个目标函数的提高需要以另一个目标函数的降低作为代价，称这样的解A和解B是非劣解(noninferiority solutions),或者说是Pareto最优解(Pareto optima)。多目标优化算法的目的就是要寻找这些Pareto最优解。

 图1 多目标优化问题

1.2 函数gamultiobj

        目前的多目标优化算法有很多，Kalyanmoy Deb的带精英策略的快速非支配排序遗传算法(nondominated sorting genetic algorithm I,NSGA-II)无疑是其中应用最为广泛也是最为成功的一种。MATLAB R2009a版本提供的函数gamultiobj所采用的算法就是基于NSGA-Ⅱ改进的一种多目标优化算法(a variant of NSGA-ⅡI)。函数gamultiobj的出现，为在MATLAB平台下解决多目标优化问题提供了良好的途径。函数gamultiobj包含在遗传算法与直接搜索工具箱(genetic algorithm and direct search toolbox,GADST)中，其位置如下：MATLAB安装目录\toolbox\gads\gads,这里称函数gamultiobj为基于遗传算法的多目标优化函数，相应的算法为基于遗传算法的多目标优化算法。本案例将以函数gamultiobj为基础，对基于遗传算法的多目标优化算法进行详细分析，并介绍函数gamultiobj的使用。

1.3 函数gamultiobj中的一些基本概念

        在讲解函数gamultiobj之前，有必要介绍基于遗传算法的多目标优化算法中的一些概念，其他的概念如个体、种群、代、选择、交叉、变异和交叉后代比例等，这里不做介绍。事实上，由于函数gamultiobj是基于遗传算法的，因此，遗传算法中的很多概念和这里的函数gamultiobj是相同的，这也是函数gamultiobj位于GADST内的原因。         1.支配(dominate)与非劣(non-inferior)在多目标优化问题中，如果个体p至少有一个目标比个体q的好，而且个体p的所有目标都不比个体q的差，那么称个体p支配个体q(p dominates q),或者称个体q受个体p支配(gis dominated by p),也可以说，个体p非劣于个体q(p is non-inferior to q)。         2.序值(rank)和前端(front)         如果p支配q,那么p的序值比q的低。如果p和q互不支配，或者说，p和q相互非劣，那么p和q有相同的序值。序值为1的个体属于第一前端，序值为2的个体属于第二前端，依次类推。显然，在当前种群中，第一前端是完全不受支配的，第二前端受第一前端中个体的支配。这样，通过排序，可以将种群中的个体分到不同的前端。         3.拥挤距离(crowding distance)         拥挤距离用来计算某前端中的某个体与该前端中其他个体之间的距离，用以表征个体间的拥挤程度。显然，拥挤距离的值越大，个体间就越不拥挤，种群的多样性就越好。需要指出的是，只有处于同一前端的个体间才需要计算拥挤距离，不同前端之间的个体计算拥挤距离是没有意义的         4.最优前端个体系数(ParetoFraction)         最优前端个体系数定义为最优前端中的个体在种群中所占的比例，即最优前端个体数=min{ParetoFraction×种群大小，前端中现存的个体数目},其取值范围为0～1,详细讲解见3.2节中的函数trimPopulation。需要指出的是，ParetoFraction的概念是函数gamultiobj所特有的，在NSGA-Ⅱ中是没有的，这也是为什么称函数gamultiobj是一种多目标优化算法的原因。

2 素例背景

2.1 问题描述

        待优化的多目标问题表述如下：

2.2 解题思路及步骤

        这里将使用函数gamultiobj求解以上多目标优化问题。同函数ga的调用一样，函数gamultiobj的调用方式也有两种：GUI方式和命令行方式。 1:通过GUI方式调用函数gamultiobj         通过以下两种方式可以调出函数gamultiobj的GUI界面：         (1)在MATLAB主界面的左下角依次单击：APP→Optimization→在Slover中选择“gamultiobj—Multiobjective optimization using Genetic Algorithm"。

        (2)在命令行调用GUI：

optimtool('gamultiobj')

        可以看到，函数gamultiobj的GUI界面与函数ga的GUI界面大致相同，仅在以下几个方面存在区别，         (1)前者比后者多了Distance measure function和Pareto front population fraction两个 参数。         (2)前者比后者少了参数Elite count,这是因为函数gamultiobj的精英是自动保留的;前者比后者少了Scaling function,这是因为函数gamultiobj的选择是基于序值和拥挤距离的，故不再需要Scaling的处理；函数gamultiobj没有非线性约束。         (3)绘图函数不同及下列设置的默认值不同：种群大小(Population size)、选择函数 (Selection function)、交叉函数(Crossover function)、最大进化代数(Generations)、停止代数 (Stall generations)、适应度函数值偏差(Function tolerance)。         函数gamultiobj GUI界面的其他介绍和使用方法可以参考普通遗传算法，这里不再介绍。 2:通过调用函数的形式使用gamultiobj         以下内容引用自官方文档：

gamultiobj是使用遗传算法解决多目标优化问题的函数。它试图解决以下形式的多目标问题：

min F（X） subject to: AX