进化算法思想源自对生物进化的模拟或行为的模仿。一般来说，先将求解问题建立数学模型（函数模型），函数中的一个解当做一条染色体，然后染色体在一次次选择、交叉、变异后获得一组最优解或满意解。这就是进化算法的一般进化过程。该类算法主要包括遗传算法（GA）、进化策略（ES）和进化规划（EP）等。这些算法侧重点不同。各自有不同的生物进化背景。各自强调了生物进化过程中的不同特征。但它们也有共同点。即均借助生物进化的思想和原理来解决现实存在问题[64]。
早在1985年。Schaffer首次提出了基于矢量评价遗传算法（Vector Evaluated Genetic Algorithm。VEGA）[65]。开启了使用进化算法求解多目标优化问题的先河。在此之后。进化算法经历了三个重要阶段。
1.第一阶段：进化多目标优化萌芽阶段（1985年—1999年）
最初的进化多目标优化算法采用非Pareto方法或Pareto方法。非Pareto方法并不采用Pareto最优原理。获取解的过程相对简单且易于实现。缺点是不能产生完整的Pareto最优解集。采用Pareto方法过程相对复杂。但利用非支配排序等方法可使种群更有效地逼近Pareto最优解集[64]。在第一阶段中具有代表性的算法有VEGA、多目标遗传算法（Multi-Objective Genetic Algorithm。MOGA）[66]、小生境Pareto遗传算法（Niched Pareto Genetic Algorithm。NPGA）[67]和非劣解排序遗传算法（Non- dominated Sorting Genetic Algorithm。NSGA）[68]。
（1）VEGA 1985年。Schaffer首次提出VEGA。它是一种修改选择机制的简单遗传算法。在每一轮次进化中。各个目标函数按照一定比例进行选择。生成多个子种群。然后进行交叉、变异操作。最后将种群混合形成新的种群。这种个体混合方式相当于将各个目标函数进行加权处理。而这种加权系数与当前轮次有关。因此VEGA很难将优良个体稳定遗传到下一代。虽然VEGA获得的最优解与后来的进化多目标算法比较存在一定差距。但它开启了进化多目标优化算法的先河。
（2）MOGA 1989年。Goldberg提出了采用非支配排序和小生境技术处理进化多目标优化问题。1993年。Fonseca和Fleming受到这一思想的启发。提出了MOGA算法。MOGA算法的主要思想是个体划分等级和适应度分配方式。个体划分等级的具体实现为：①将个体的非支配个体的秩设置为1；②其他个体的秩设置为其被支配个体数目加上1。适应度分配方法的具体实现为：①将个体按照秩的大小进行排序；②采用Goldberg提出的线性和非线性插值方法进行分配。相同等级的个体适应度值相同；③相同序号的个体的适应值共享（即除以相同序号获得新的适应值）。对不同序号个体分配固定不变的适应值。MOGA算法的优点是算法比较容易实现且效率较高；其缺点是依赖共享函数。容易产生较大选择压。导致算法早熟不收敛。
（3）NPGA 1994年。Jeffrey Horn等学者提出了NPGA。NPGA设计了一种基于Pareto支配关系的锦标赛选择机制。算法的主要思想是：在种群中选择两个个体和一个大小合适的比较集。如果只有一个个体不受比较集支配。则此个体直接被遗传到下一代；如果两个个体同时支配或被支配比较集，则采用小生境技术选择其中一个个体遗传到下一代[63]。NPGA面临的主要问题是比较集规模的选取和小生境半径的估值。
（4）NSGA 1994年，Srinivas和Deb在IEEE的《Evolutionary Computation》杂志上提出了NSGA[68]。NSGA同样受到了Goldberg的非支配排序思想的影响。在NSGA中，首先选出第一层非支配个体集，然后把剩下的个体集进行第二次非支配排序，按照此方法将所有个体集进行分层。将处于第一层的个体集赋予最大的适应值，以保证在选择时有较大概率遗传下去。NSGA的计算复杂度为0（MN3），其中M为目标个数，N为种群大小，随着种群增大其复杂度增高。
在进化多目标优化算法探索的第一阶段，非支配排序和共享函数为其主要特征。当然，由于研究处于萌芽阶段，也存在一些问题：首先，通过非支配排序进行选择，算法时间复杂度较大，这一问题在NSGA中可以深刻体现；第二，采用共享函数需要知道研究数学模型的相关特性，例如多峰或单峰、解空间分布等信息，因此对研究未知数学模型存在局限性。在此后研究中，这些问题都是研究者讨论和研究的重点问题。
2.第二阶段：进化多目标优化迅速发展阶段（1999年—2003年）
20世纪末期，进化多目标优化算法进入高速发展阶段。在这一时期，大部分经典进化算法都采用精英种群保留策略，因此，精英种群保留策略成为这一阶段的主要特点。精英种群保留策略是在进化过程中采用外部种群保存非支配个体的方法。如果将所有的非支配个体都保存在外部种群中，显然会受到种群大小的限制，因此，在设计外部种群时需要解决以下几个难题：①外部精英种群大小的设置。精英种群过小，无法完整保存优秀个体；精英种群过大，增加算法的时间复杂性。②外部精英种群大小超过预设值后，如何去除相对较劣个体？若内部种群进化后的个体和外部精英种群个体存在非支配关系且外部精英种群容量已经达到最大值时，需要一种新的选择机制对非劣解进行比较，进而保留优秀个体。在此阶段代表性进化算法有：强度Pareto进化算法（Strength Pareto Evolutionary Algorithm，SPEA）[69]、SPEA2[70]、NSGA-II[71]、Pareto档案进化策略进化算法（Pareto Ar-chived Evolution Strategy，PAES）[72]、Pareto包络选择算法（the Pareto-Envelope based Selection Algorithm，PESA）[73]、微遗传算法（Micro-Genetic Algorithm，Mi-cro-GA）[74]。
（1）SPEA和SPEA2 在1999年，Zitzler等学者提出了SPEA。SPEA在MOEA发展历程中具有里程碑式的意义，虽然在之前已经有学者提出过精英种群保留策略，但是文献[69]是第一篇在IEEE主办的《Evolutionary Computation》发表相关思想的文章。除了精英种群保留策略外，SPEA还采用聚类分析方法对非劣解进行修剪。当然SPEA同样存在一些缺陷，例如：在适应度赋值过程中，如果被相同个数存档成员支配的个体适应值相同，这样就可能在外部个体只包含一个成员时，无论种群个体之间是否存在支配关系，所有种群个体都具有相同适应值。同样，由于采用聚类分析方法，一些较优个体可能被删减掉。针对SPEA存在的缺陷，Zit-zler等学者在2001年又提出了SPEA2。SPEA2在适应度赋值、个体密度值计算方法和外部存档维护方面对SPEA进行改进。为了避免被相同的外部存档成员支配的个体有相同的适应值，在SPEA2中，适应值大小取决于个体所支配的解和支配它的解。而在外部存档维护方面，SPEA2中存档大小始终是一个固定值，同时，在存档维护中避免了将边界解从存档中剔除。大量实验结果表明：SPEA2算法无论在趋近Pareto最优解还是在解的均匀性方面都表现良好。特别值得指出的是，在个体均匀分布上SPEA2具有非常优秀的表现。
（2）NSGA-Ⅱ 2002年，Deb等学者改进了NSGA，提出了著名的进化算法NSGA-Ⅱ。NSGA-Ⅱ是进化多目标领域被SCI引用最多的文章，同时也是其他学者进行对比研究最多的进化算法之一。NSGA-Ⅱ主要采用非支配排序和拥挤距离策略。其主要流程是：①种群采用非支配排序，计算个体适应值；②通过二联赛方法选出一部分种群进行交叉、变异操作；③将遗传操作后的部分种群与原始种群进行非支配排序和拥挤距离策略，选择出较优个体保留；④如此循环直至满足结束条件。NSGA-Ⅱ之所以能被众多学者认可，主要是其在趋近Pareto最优解方面具有良好表现，当然Deb提供NSGA-Ⅱ源代码下载也是其广泛传播的重要因素。
（3）PAES和PESA 2000年，Knowles和Corne提出了PAES。PAES对外部档案的维护主要采用自适应网格法。自适应网格法的基本思想是利用外部档案的所有非劣解，将目标空间分割成很多小网格，每当插入到外部档案中的新个体位于现有网格之外时，将重新划分网格和计算每个网格中的个体数目。随后，Corne等学者基于这种自适应网格法提出了PESA。PESA的创新之处在于采用拥挤系数，设置内部种群和外部种群。在进化过程中，将内部种群中的非支配个体并入外部种群中，然后采用拥挤系数将外部种群中较劣个体淘汰。拥挤系数指与某一个体在同一个网格的个体数量。如果拥挤系数越大，说明在同一个网格中个体数目越多，淘汰机率将会越大。如果拥有相同的拥挤系数，将随机淘汰个体。相比于PAES，PESA在一定程度上提高了算法的效率。
（4）Micro-GA 2001年，Coello Coello和Toscano Pulido提出了Micro-GA[74]。Micro-GA采用小种群思想和重新初始化策略。具体流程如下：①随机产生种群并加入种群内存中，种群的内存包括可替代种群和不可替代种群两部分。可替代种群在进化中随着算法运行而改变，而不可替代种群在进化过程中保持不变，以此用以保证种群的多样性。②在最终种群中选择两个非劣个体与外部种群个体进行比较。如果其中一个或者两个个体都是非支配个体，则将其放入外部种群，并从外部种群中删除当前较劣个体。值得指出，小种群思想在之后的进化多目标算法中也得到广泛应用。
第二阶段进化多目标优化发展百家争鸣，涌现出了一批优秀的算法，例如NS-GA-Ⅱ和SPEA2等。我们可以看到此阶段的进化多目标的特点是以非支配关系和精英保留策略为主要思想，同时融入一些新的方法和策略，例如拥挤距离策略、个体密度值计算方法和小种群策略等。
3.第三阶段：进化多目标发展的多样性阶段（2003年至今）
之前虽然涌现出一大批优秀进化多目标算法，但是随着研究的深入，一些新的问题亟待解决。首先是高维（一般指4维目标向量以上）多目标问题的研究。之前多目标算法在解决低维多目标问题时表现良好，但是面对高维多目标优化问题时经常出现维数灾难。其次是动态多目标问题的研究。这是当前进化多目标的热点研究方向，在很多实际问题中都需要采用动态优化，因此具有很高的实际应用价值。最后是新的机制和多种算法融合（即混合进化多目标优化算法）的研究。此研究主要有两个方向：一个方向是从之前的研究中改进已经存在的机制，另一方向是提出新的机制。
（1）高维进化多目标研究 当前高维进化多目标研究呈现多元化趋势。一部分学者依然以Pareto非支配排序作为算法的核心思想，然后结合其他方法或机制达到缩小搜索空间或降低目标维度的目的；另外还有一些学者对Pareto非支配排序进行修改或放宽，采用优胜关系[75]、k-占优[76]和α-支配[77]等；最后还有一批学者彻底脱离Pareto非支配排序思想，采用一些创新的评价方法对种群进行比较和选择，产生了基于评价指标的方法[78]等。
采用Pareto非支配思想结合其他方法解决高维进化多目标研究中，Masahiro首先提出了决策者偏好进化多目标优化的思想，其主要思想是决策者根据实际需求选择一部分Pareto最优解集，而不是整个Pareto最优解集。通过这种方式可以有效减小搜索空间，但是这种方式存在局限性，其主要缺点是需要知道决策者的个人偏好，而对于大部分函数优化问题并不存在个人偏好。2010年，在国内，杨咚咚和焦李成等在文献[79]中提出通过克隆选择算法求解偏好多目标优化问题，文中提出利用决策者提供的偏好信息为抗体分配偏好等级，根据获得值比例克隆抗体以此增加抗体选择压力，加快收敛速度。(www.xing528.com)
在对Pareto非支配排序进行修改和放宽的研究中，Drechsler等[75]提出优胜关系方法确定非支配解集中个体的优先顺序。其主要思想如下：如果存在非支配个体p、q和r，如果p在大部分目标向量中比q更优，那么说明p优胜于q，但是必须指出，这种优胜关系不存在传递性，可能出现p优胜于q、q优胜于r、r优胜于p的情况。Di Pierro等学者在文献[76]中提出了k-占优，在高维多目标优化中，由于个体间很难存在完全的非支配关系，非支配解个数会急剧膨胀，此时将某些维度进行暂时搁置，对其他目标向量进行非支配排序以剔除相对较劣解。Ikeda等学者提出α-支配，假设存在个体p和q，将其通过一组α权值综合起来，在某个目标上p比q稍微具有优势，但从整体比较q比p优，则认为q比p占优。
在高维进化多目标研究中，一些学者完全脱离Pareto非支配排序思想，也取得不错进展。一些学者从加权系数的思想得到启发，将多个目标通过加权方式变换成单一目标进行评价，这种方法具有计算复杂性低、效率高等优点，但种群多样性无法保证。Zitzler等[80]建立基于评价指标的进化算法框架，采用二元性能评价准则作为指标函数进行个体筛选。2011年，Bader和Zitzler又提出基于快速超体积思想的算法HypE[81]，通过采用蒙特-卡洛模拟法逼近真实的超体积值。实验结果表明：HypE比现有大部分进化多目标优化算法更高效。2007年，Hughes提出了MSOPS-II[82]，在两个方面对MSOPS进行扩展：首先，提供自动目标向量生成，消除初始先验设计干预；第二，重新定义适应度分配方法简化分析并考虑了更全面的约束处理。
（2）动态进化多目标研究 采用进化算法求解动态多目标问题，已成为进化多目标研究的热门方向。动态进化多目标研究与之前的研究（静态进化多目标研究）不同之处在于：目标函数不仅与决策变量有关，而且目标函数会随着时间或环境的变化而改变。对于动态优化问题的研究国内外主要集中在动态进化单目标优化，而对于动态进化多目标优化研究成果较少。但不可否认，由于在组合优化、城市运输、数据挖掘和工程设计等方面有广泛应用需求，动态进化多目标研究成果将会越来越丰富[83]。目前研究成果大部分是针对动态进化单目标问题，但动态单目标问题的研究方法可以运用到动态多目标中，所以本论文重点依托动态单目标研究成果讨论动态多目标问题。
对多目标优化算法来讲，保持种群多样性是算法能否在决策空间中探索更多可行解的重要保证。对动态进化多目标问题，随着时间或者环境变化最优解可能时刻发生变化，因此对于种群多样性要求更高。在保持种群多样性方面，早期学者提出例如随机迁移策略、超变异方法、变量局部搜索技术等，但随着研究深入，更多优秀方法被提出。2003年，Yang[84]提出使用特殊染色体维持进化种群多样性。2004年，Eriksson和Olsson[85]通过事先对进化个体进行适应值估计，然后运用自适应调节机制维护种群多样性[83]。
在动态进化多目标优化中，研究者经常采取存储历史最优解并在恰当时候重启最优解的方式。研究者认为，采用历史记忆存储的方式一般适用于具有周期性或者规律性的动态函数。通过这种历史记忆的方式可以大大加快收敛速度，提高算法的搜索能力，但面临的问题是如何记忆最优解和如何有效利用历史最优解。对于第一个问题，记忆最优解通常采用两种方式：利用冗余表示的隐式记忆和引用额外内存存储最优解的显示记忆。在此方面，Ryan[86]提出了利用额外二倍体隐式记忆方法，该方法的主要思想是：设定一个条件，如果满足该条件，则让选择基因为1，否则为0。其仿真实验结果表明：对于周期性变化的动态函数其思想优于一般方法。同时，Hadad[87]提出了利用多倍体的记忆进化方法。Ryan和Collins[88]提出了基于分等级结构记忆方法等。对于第二个问题如何有效利用历史最优解，周期性和规律性动态函数可以通过挖掘其特点进行取样，但无规律动态函数采用这种方式优化难度较大。
总的来说，动态进化多目标优化还处于初级发展阶段，研究成果并不多，需要在今后的研究中进一步探索。
（3）混合进化多目标和新的机制研究 最近几年，粒子群算法、蚁群算法、人工免疫算法、模拟退火算法、差分进化算法、分散搜索等一些新的进化范例先后被引入求解多目标优化问题[63]，同时对传统的Pareto占优机制的改进也成为研究热点。混合进化多目标算法从狭义理解为多种进化算法融合产生的算法；但从广义来说，可以解释为某种进化算法融入某些进化机制形成的混合算法。下面将介绍一些引入新的进化范例后产生的混合进化多目标算法和一些新的机制。
现阶段，混合进化多目标优化以粒子群为范例的混合算法较多。在多目标情况下，每一个粒子历史最优解不再唯一，可能同时存在多个互不支配的历史最优解，因此如何选择粒子的历史最优解成为研究热点。Parsopoulos等[89]学者提出一种向量估计粒子群算法，其主要思想是提出两个粒子群，一个粒子群被用来调整粒子的速度，另外一个粒子群用以确定跟踪的最好粒子。Mostaghim等[90]学者提出Sigma方法为所有粒子确定全局最好位置。根据Sigma方法，如果粒子的Sigma值与某个存档的粒子Sigma值最接近，选择该存档粒子为其全局最优解。2004年，Coello Coello等学者[91]提出具有里程碑意义的多目标粒子群算法MOPSO，其主要思想是采用外部存档种群指导该种群之外其他粒子的飞行，将PAES中的自适应网格法用于外部存档种群的维护[83]。2009年，Bui等[92]提出一种在噪声环境下遗传结合粒子群的混合进化多目标算法的局部模型，使用这一模型，搜索空间被确定性地分成了几个无重叠的超球体。这种机制允许进化在局部超球体中过滤噪声，而无需采用全局处理方法。
与其他混合进化多目标算法相比，多目标蚁群算法起步较晚，研究成果相对较少。文献[93]提出一种多目标蚁群搜索算法用于优化配电系统战略规划，该算法采用多种群机制并引入了遗传算法的共享机制协调各个种群。文献[94]提出一种多目标Pareto蚁群算法用于优化资产选择问题，算法的主要思想是引入信息素向量，每个信息素向量的元素数和目标数相同，在寻优的初始阶段随机取各个目标向量的权系数，从而协调各目标之间的关系[95]。
人工免疫系统（Artificial Immune Systems，AIS）是一种受免疫学启发，模拟免疫学功能、原理和模型来解决复杂问题的自适应系统。Yoo等[96]最早将AIS思想引入多目标优化中，设计了基于免疫思想的遗传算法。Cutello等[97]学者将克隆选择原理的局部交叉和变异引入到（1+1）PAES，提出了免疫PAES。在国内，人工免疫多目标研究也取得不错成绩。焦李成研究小组先后提出了免疫支配克隆多目标算法（IDCMA）和非劣解临域免疫算法（NNIA），其中NNIA是人工免疫多目标优化算法中具有代表性的算法之一。
在新的机制方面，Laumanns和Deb等[98]学者提出了ε占优的概念，其采用空间超格思想，一个格子中只能存放一个个体，决策者可以动态调整格子数目与大小使每个格子只保留一个个体。通过采用ε占优，原来的个体占优机制就变成了基于格子的占优机制。2009年，Alfredo和Coello Coello等[99]学者对ε占优进行改进，提出了基于Pareto自适应的ε占优机制。同时，Brockoff和Zitzler等[100]学者采用局部占优机制对高维度多目标优化问题进行降维，实验结果表明：对于目标维度越高，其降维效果越明显。2007年，Kodurud等[101]学者提出了模糊占优机制，其主要思想是采用模糊支配函数对每个占优目标进行加权，所有目标加权之后求和即该个体的模糊占优程度。
通过对进化多目标和新的机制的研究，发现在新阶段中进化多目标研究呈现以下特点：首先，进化多目标研究进入新进化范例引入阶段。对于传统的遗传算法其研究已经走到一个瓶颈，因此新的进化范例引入必不可少。第二，新机制的研究。新机制的研究不仅包括最新提出的机制，同时也包含存在但没有应用过的机制和改进之后的机制。第三，多种算法思想的融合。每一种进化算法都有自身优势和劣势，因此如何扬长避短是现在大多数学者研究的方向。
尽管多目标优化的研究已经取得了丰硕的成果并且不断有新的进化范例应用其中，但多目标优化仍然面临着许多有待研究的课题，例如通用的进化模型、在有限时间的收敛问题、时间复杂度问题、测试问题的构造方法、多目标优化并行实现研究、不确定多目标优化问题、多目标优化性能评价指标以及多目标优化问题的理论和应用研究等。纵观当前主流进化算法，即以遗传算法、遗传编程、进化策略和进化规划为代表的进化算法，以及近年兴起的基因表达式编程（Gene EXpression Pro-gramming，GEP），虽然它们个体和变异操作表示有明显不同，但其结构上有共性、可持续性方面面临共同的问题和困难。研究现有文献资料并将其与自然进化相比发现：
1）在自然系统中，理论上个体有可能与同一种群中的其他符合要求的个体产生新子代，但实际情况是个体间的结合受地域等因素限制。进化算法和自然进化系统存在着一定差异。
2）在绝对的选择压力下，只有更好的群体才能生存下来，这导致群体的平均适应性不断地增加直到停滞为止。在以后的进化阶段，适应能力低的个体很难生存下去。在自然进化系统中，环境的多样性允许不同适应水平的个体生存。
3）进化算法一般都包括能加强搜索能力的选择操作和探索新的搜索领域的一个或多个变异操作，它必须处理解空间的不断探索与稳定的关系，否则将导致早熟收敛或者类似于枚举。在自然进化中，多样化机制是变化多端的，关系的平衡可以通过进化过程本身得到适当控制。
4）进化算法需对相关参数（如突变、交叉概率）作很好的调整才能进行很好的搜索，而这些参数即使通过大量的测试，也往往只适用于某一类问题的解决。在自然进化系统中，物竞天择的机制完成交配等遗传、繁殖及生存过程，而突变的实现则基本是取决于生物生存外部环境。
5）进化算法中，新生个体的产生方式充满了随意性，特别是通过随机生成的方式产生的个体；而通过交叉与变异操作产生的新个体，往往与父代个体的基因有很大的差异，这就造成遗传信息继承不稳定的局面。而自然进化系统中，不同物种间基因差异比较小，但在智力、体型、适应能力等方面表现出了巨大差异。新生个体的基因与父代之间有很大的共同部分，子代继承了整个种族进化过程中的绝大多数信息。据《Science》杂志报道：无论是基因的数量，还是碱基对的数目，家猪基因组和人类基因组都很相似，基因也大部分相同，差异性不超过5%～10%；拟南芥与水稻公共基因有80%。2005年9月1日出版的《Nature》杂志报道：黑猩猩和人类基因组的DNA序列相似性高达99%，即使考虑到DNA序列插入或删除，两者的相似性也有96%，人类只比黑猩猩多50个特殊基因，而且人类与黑猩猩有29%的共同基因编码生成同样的蛋白质。人类基因组计划的研究成果同样显示：个体间只有极少数的基因不同，但这种细小的差异却造成个体间智力水平差异显著。
6）针对一组单目标组合优化问题的研究成果显示：分布在方案集中的信息对于促进算法搜索到目标结果具有积极作用[103，104]。同时有研究成果表明：种群中个体分布对获得问题的最优解具有重要影响[105]；此外，文献[106]在研究局部化模型时，采用了多个互不相交的超球体模型过滤噪声，并取得了良好效果。总体而言，当前研究工作对决策变量映射到目标函数空间后的分布情况比较关注，对如何有效利用决策空间中客观存在的最优解分布信息的方法研究较少。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
