基于PARETO的改进遗传在多目标模型的研究

林虹虹

摘 要：该文先介绍PARETO解及多目标的相关概念，再通过自适应更新机制、精英保留策略等方法来提高遗传搜索效率，并且对多目标函数的结构进行改进设计，结合IAGAMO模型，以全局搜索机制作为研究基础，针对遗传算法实际应用缺陷进行了分析，着重论述通过全局搜索机制对提高局部搜索中遗传算法的影响，从而加速了IAGAMO混合算法的运算速度以及收斂效率。最后将PARETO的IAGAMO算法在生产实例进行仿真验证，结果所获得PARETO解的数据较符合生产的实际应用。因此，PARETO以其巨大的技术优势，有效提升了搜索效率，在多目标搜索以及解集的优化中发挥了重要的作用，因此具有广阔的发展空间。

关键词：多目标优化 遗传算法 PARETO

中图分类号：TP301.6 文献标识码：A 文章编号：1674-098X（2015）09（c）-0046-02

The Research on the Multi-objective Case Using Improved GA Based on PARETO

Lin Honghong

（Engineering occupation technical college of Guangdong，Guangzhou Guangdong，510630，China）

Abstract：This article first introduces the concepts of PARETO solutions and multi-target，and then through an adaptive update mechanism， elitist and other methods to improve the efficiency of genetic search， and the structure of multi-objective function to improve the design， combined with IAGAMO model， through the adaptive cross， features of the PARETO optimal solution， variability update mechanism and mixing in elite global search mechanism strategy to further address the lack of genetic algorithms to search for local solutions， and it to improve the IAGAMO hybrid convergence speed and computational efficiency. Finally， PARETO of IAGAMO algorithm simulation instance in the production， the results obtained are compared with data PARETO solution compatible with the application of production.Therefore，PARETO not only to better improve the efficiency of multi-objective optimization search solution set， but also with a wide range of produce promotional value.

Key Words：Multi-objective Optimization；Genetic Algorithm；PARETO

近年来，多目标优化问题求解已成为演化算法的重要研究方向。由于传统优化方法的局限性，导致该研究进展缓慢，而且多目标与单目标优化问题也存在较多不同，其中单目标问题只需优化一个目标或一个最优解；但是多目标的目标值却经常形成互相冲突，即当目标是达到最优时，其化目标不一定是最优，甚至有可能是最差的，形成多目标化问题（Multi-objective Optimization Problem，MOP）。

遗传算法可以对整个群体进行进化运算操作，着重于个体的集合，是求解软性多目标规划的重要方法，运用遗传算法对多目标模型求解可以得到相对较好的解集，因此本文主要通过不同决策变量的研究设计、定义，再依据多目标PARETO解的概念，进一步地改进设计的遗传多目标模型（IAGAMO）。

1 多目标优化现状

现阶段，多目标问题优化的应用越来越广，而多目标求解中也往往存在相互竞争、相互冲突，其中一个目标的改进可能引起其他目标性能的降低，所以不存在解使得各个目标函数同时达到最优，因此我们只能寻找在多个目标协调中相对最优的解。而传统的多目标优化问题解决方法主要是依靠设计人员进行排序或加权进行优化，然后再利用传统的单目标优化求解方法进行求解，因此存在不少缺点，例如：（1）该方法需要决策者对该问题要有充分的认识和了解、合理的权值、敏感的参数、稳定的可靠性。（2）决策者在做决定的时候，往往希望能有多种选择的方案，而该方法恰恰只能提供唯一的解。

2 遗传多目标概念

一般的多目标优化问题可以定义如下[1-2]：

MinT

S.t i=1，2…，k （1）

其中T。

传统多目标问题优化方法，一般情况下只能得到局部最优解，加上系统仿真过程较费时，使得整个优化过程都会变得很慢。

在多目标研究中，即当且仅当模型只有单目标时，可以较快寻找到最好的解。若存在多个目标时，由于目标之间存在无法比较和冲突现象，会导致最后解不一定是所有目标下最优的解。因此存在多个目标解的时候，一般也存在一系列无法简单进行比较的解。这种解称作PARETO最优解（PARETO optimal solutions） 或非支配解（Nondominated Solutions）。

对于每个PARETO最优解都具有在不同程度上满足各目标的“优越性”。因此只需在实际应用中选择PARETO最优解中一个较为合适的折衷解即可。所以在求解多目标优化的过程中，就比须解决两个问题：一个是如何求得PARETO最优解；另一个是如何根据实际情况，在多个的PARETO最优解中选择最合适的最大的PARETO最优解。

遗传算法有较好的搜索性和并行性特点，因此多目标遗传算法可以同时求出多个PARETO解，并且对于PARETO解集中的解进行选择、交叉、变异等遗传操作，最终求出多目标优化问题的最优解。所以只能在单次模拟运算中搜索PARETO最优集，因此它非常适用于多目标规划问题。

3 遗传的多目标改进研究

遗传算法具有全局搜索能力较强优势，故作为指导性搜索算法，本文则结合精英混合局部搜索能力强及遗传算子自适应的更新的特点，克服遗传算法的不足，增强混合遗传算子在全局和局部范围的搜索能力和效率。

3.1 编码

在编码过程中，主要采用实数编码，用以降低解的搜索时间过程，提高IAGMO算法收敛速度。

3.2 初始化群体

首先随机生成S×N个样本，然后将它们分成N个子群体，每个子群体包含Smin个（一个决策变量解）样本。其中Smin为最小规模保护限制，引入这一概念是为了保护群体的进化能力，使之不会被过早地淘汰。

3.3 适应度值计算

由于多目标问题模型属于多维模型，因此在本文将约束条件和目标函数的以矩阵的方式设计，举例如下，首先对约束条件的x系数和边界作矩阵排列，如：

x1+x2<=100

30×x1+40×x2<=300 （2）

根据（2）式，决策变量x矩阵设计为：[1，1；30，40]，而约束条件的边界矩阵为：[100；300]，至此目标函数的迭代计算则依次计算约束条件函数及目标函数，伪码如下：

[subjected_value]=Subject_fitness（x） （3）

[fitness_value]=fitness（subjected_value） （4）

3.4 混合策略分析

针对选择机制，主要采用混合选择机制，结合轮盘赌以及期望值方法。通常选择机制都会采用轮盘赌方法，依照实际个体数进行确定，若个体数过少，则依照随机数进行选择时会出现误差，造成无法将个体适应度正确反映出来。为了有效降低这种选择误差，通常会使用期望值方法。

（1）通过下述计算公式对每个个体进行计算，求出其在下一代生存中期望数目。 （5）

（2）若在选择过程中，某一个体被选中参与交叉，那么在下一代生存中，其期望数目需降低0.5；若被选中个体不参与交叉，则其在下一代生存中期望数目降低1。

（3）若完成上述计算后，个体期望小于0，则选择项中不包含该个体。

3.5 遗传交叉、变异自适应策略

在种群适应度比较集中时，使交叉概率比变异概率，当群体适应度比较分散时，使和增大。因此Srinvivas等提出了一种自适应遗传算法（Adaptive GA，AGA），和能够随着个体的适应度自动变化。但经测试研究，Srinvivas提出的自适应交叉、变异公式容易致和偏离正常选择的概率范围，导致遗传迭代的结果易于“早熟”，即欺骗结果。

依照研究人员的研究成果，迭代初期，遗传算法搜索能力会受到交叉概率选择的影响，若交叉概率提升，则遗传算法搜索能力便得到提升。而迭代后期，收敛速度会受到交叉概率的影响，降低交叉概率则收敛速度得到提升。遗传代数双曲线下降时，全局最优解以及收敛速度会受到自适应交叉概率的影响而效果最佳。公式如下：

（6）

式（6）中pc为自适应交叉算子，pc1和pc2为固定交叉概率值，t为遗传迭代次数，为最大遗传代数；迭代初期选择该种自适应交叉概率，可以保证交换率，加速进化，防止遗传算法迟滞。而在迭代后期选择该种自适应交叉概率则能够保证降低交换率，使其逐步降低至常量，令收敛速度平滑。以此确保搜索空间连续、平稳，从而降低全局最优解的获得难度。

自适应变公式随着遗传代数指数的改变而发生改变，其变异公式为：

（7）

式（7）中pm为自适应变异算子，pm1和pm2为固定交叉变异值，λ则是常数，其取值以种群分布决定，其取值一般大于5小于10。在迭代初期，这种变异概率能够保证进行个体性能较差过程中，形成足够的变异率，以此增加扰动，令解空间扩大。而迭代次数的提升、变异率的降低使得最终平滑收敛。

3.6 精英保留

在遗传算法中，将基因结构优良、基因特性优良的个体归为精英个体。若新一代群体中加入了精英个体，那么为维持群体规模，则需要在新一代群体中选出适应度值最小的个体，将其淘汰。在遗传算法的优化改进中，精英保留策略能够影响全局收敛能力，并且该策略已经从理论上得以证明，可以对全局收敛能力造成影响。

4 实例分析

以某试验基地作为案例分析实例，对该试验基地第一生产阶段中的数据模型予以分析。首先依照多目标设计要求，针对问题设计模型，要求在75天内完成200亩工作量，且保证时间、成本的最低。

依照实际要求，多目标模型可以表述为以下公式。

（8）

上述公式中，x1，x2分别表述作业决策的变量，但是依照作业时间以及实际作业总量，约束条件为

St. ；，

（9）

根据式（8）式（9）的多目标的数学条件描述，在IAGAMO模型参数设置中：交叉算子pc取0.8，变异算子pm取0.2，最大迭代次数max_gen则取150。

5 结语

在PARETO求解优化中，遗传算法是主要研究方向。所以在文章中主要以遗传算法作为基础思想，以PARETO最优解为前提，加上自适应的交叉、变异更新机制和精英混合策略的全局搜索机制研究，进而解决了遗传算法在局部解搜索的不足，提高IAGAMO混合算法的運算效率及收敛速度。并且在实际生产模型应用中，比较IAGAMO模型与传统的单目标数学模型实例，得出本文所提出的观点：基于PARETO的IAGAMO算法模型在多目标问题研究中，不仅能较好地提高多目标问题优化解集的搜索效率，而且具有广泛的生产推广价值。

参考文献

[1] 马振华，刘坤林，陆漩，等.现代应用数学手册（运筹学与最优化理论卷）[M].北京：清华大学出版社，2001.

[2] 朱学军，陈形，李峻.多个体参与交叉的PARETO多目标遗传算法[J].电子学报，2000（1）：106-109.