IEC算法及其在多目标优化中的应用(txt+pdf+epub+mobi电子书下载)

作者：赵立江

出版社：暨南大学出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

IEC算法及其在多目标优化中的应用试读：

交互式遗传算法是一类解决隐式性能指标优化问题的进化优化算法，已经广泛地应用于诸多领域。本章将简要介绍交互式遗传算法的提出、基本概念、应用及其核心问题。1.1 引言

在管理决策领域有一类复杂的决策问题——不确定性隐形目标[1～3]决策问题，如汽车造型设计问题、旅游行程规划问题等，由于此类问题的“决策目标（最优化、最经济）难以完全以显示结构化、数量化表示”, “决策者偏好结构未知或不确定”, “问题决策方案数[4]目大，具有NP难解性质”，因而使得此类决策异常复杂。仅仅使用传统的决策方法与决策支持系统，很难对其进行求解。

近几年来，随着智能决策与人工智能技术的发展，一种具有人机交互机制的交互式进化计算（Interactive Evolutionary Computation, [1]IEC）算法在解决此类不确定性隐形目标优化问题方面表现出较大的优势，引起了研究者的广泛关注。

IEC的研究始于1986年Dawkin对基于L-system的生物形态系统的

[7]研究。IEC是一种适应值函数由人来评估完成的EC方法，包括交互式遗传算法（IGA）、交互式遗传规划（IGP）、交互式进化规划（IEP）和交互式进化策略（IES）4种方法。从决策角度看，利用IEC求解问题时，用户通过对决策方案（解）的评估，其偏好信息得到自然的表达，而评估适应值的大小就反映出决策者对该决策方案（解）偏爱的程度。IEC 中的表现型、基因型和适应值之间的关系与决策问题中的方案、属性和准则之间的关系是相对应的，它以决策者内心的偏好函数为适应值函数，并根据决策者对“可行方案”的偏好值（准[2, 则）来引导“属性”值的重组，以进一步搜寻更适合的可行方案3]。[1]

Takagi教授在其综述文章中总结了已应用于实际生活中的IEC的15个领域：图形图像处理、语音处理和韵律控制、音乐设计、网页设计、工业设计、人脸图像、虚拟现实、数据检索、知识获取和数据挖掘、控制和机器人、Internet领域、食品工程、地球物理科学、艺术教育以及写作教育等。

然而，目前IEC中的交互式控制研究者却面临着以下四个研究难点：①适应值具有噪声；②人的偏好随着评价而不断调整；③IEC要求在种群规模小、进化代数少的情况下使用，造成进化效率低下；④用户疲劳问题，它们造成了IEC优化性能低下，成为制约IEC应用发展的瓶颈问题。

所以，如何结合当前的人工智能等技术来解决IEC的进化效率问题和用户的疲劳问题，是一项颇具挑战性的工作，具有重要的理论意义与应用价值。1.2 交互式进化算法的研究现状

IEC的研究始于1986年Dawkin对基于L-system的生物形态系统的研究。目前，IEC主要有交互式遗传算法（IGA）、交互式遗传规划（IGP）、交互式进化规划（IEP）和交互式进化策略（IES）4个研究分支，且大部分集中于IGA的研究。IEC的研究引起了国内外学者极[2～4]大的兴趣，发表了大量的学术论文和相关的专著，下面对IEC的研究进展进行分析。1.2.1 IEC的理论研究

IEC的理论研究主要是针对算法框架的理论分析和算法的收敛性[5]等方面。Rudolph使用随机Mealy自动机进行IEC的理论分析。郝国

[6]生等研究了IEC用户的认知规律，提出了IEC收敛的强条件和弱条件定理，给出了关于IEC全局收敛的4个定理及理性用户是IEC全局收敛的充分条件这一结论，指出IEC的全局收敛需要保留两个“最优”：[7]适应值最优和满意度最优。1.2.2 IEC的应用研究

交互式遗传算法是一种因解决实际优化问题需要而发展起来的进化优化算法，自它的诞生之日起就具有鲜明的应用背景和应用前景。下面介绍IEC算法在各领域的应用情况。1．计算机图形学领域[8]

主要是图形图像处理与人脸图像处理等方面。Yamada等设计了商标图画系统，对商标的大小、位置和颜色进行编码后，利用IGA[9]进行交互式评价来搜索满意的商标；Miki等提出可以让多用户参与[10]的三色旗帜设计系统；Munteanu等提供了一种相干斑抑制的交互式工具，可以让医学专家按照自己的评判准则不断对临床超声波成像图片评价，以获取更好的图像，该工具的核心是通过IGA来在线调整[11]滤波器系数；Sugimoto等利用IGA进化卡通脸图像，并使用部分评价策略以减轻用户疲劳。2．工业设计[12]

工业设计是IEC应用的另一个重要领域。Siew等进行整体微波集成电路低噪声放大器设计，利用IGA搜索相应的设计变量值以满足[13]多个约束和目标；Ecemis等利用IEC进行药物设计，并能在药物发[14]现中充分使用化学家的专业知识；Zhang等利用集成自适应机制的[15]交互式进化策略进行船体的设计；Brintrup等基于IGA设计符合人体[16][17]工程的椅子。IEC还应用于飞机造型设计、微机电系统设计等方面。3．语音处理和韵律控制[18]

Takagi等研究了基于IEC的助听器配戴方法，可以帮助调节适合个人使用的助听器。标志声音在日常生活中应用普遍，例如火车到达、行人穿越道信号、家电等公共或私人场所使用的声音等。Miki等[19]试图利用IGA来设计这些标志声音，并研究了声音的呈现方式对系统性能的影响。4．音乐创作[20]

Unehara等研究了交互式作曲系统，可根据用户的评价搜索满[21]意的音乐；Zhu等研究了情感音乐生成。这些音乐的性能由KTH规则表达，利用交互式遗传算法来优化规则的权重以获取满意的情感音乐。5．多准则决策[22]

Hsu等基于IGA提出了一个多准则决策模型，指出IGA可以与决[23]策支持系统集成以解决非结构化决策问题；Liang等提出了一个基[24]于IEC的IDSS结构模型；Fukada等研究了基于IGA的房间设计决策支持系统，设计房间墙面、窗户、地毯、落地灯、沙发和坐垫等的配色方案。6．控制与机器人[25][26]

Eperj esi利用IEC进行机器人的步态优化；Moshaiov等基于[27]IEC技术研究了机器人多目标路径规划；Onisawa等利用IGA提取模[28]糊规则，并应用于小汽车的行驶控制；Nojima等利用模糊状态值函数和IGA进行训练，以获得与人友好的伙伴机器人的握手行为。7．虚拟现实[29]

Takekata等利用IEC优化一组触觉参数，并应用于生成3D模型[30]表面纹理；粒子系统在虚拟现实中有重要的应用，Hastings等提出了一个NEAT粒子系统，可以让没有编程能力或艺术技巧的普通用户使用IEC进化粒子系统的特效。8．其他[31][32][33]

IEC还被应用于数据检索、数据挖掘、用户界面设计、心[34][35][36]理健康测评、辅助教育、地质反演等方面。1.3 交互式遗传算法研究的核心问题

IEC在处理问题时，面临以下四个研究难点：（1）适应值噪声问题。IEC要求人参与评价个体表现型对应的系统输出（如声音、图形/图像），以得到个体的适应值。由于人评价时难以记住所有评价过的个体适应值，也就很难维持一个统一的评价标准，所以人评价的适应值具有波动性，即产生了适应值评价噪声。（2）人的偏好不断调整的问题。由于决策目标的不确定性，使得人（决策者）对自己的偏好在一开始难以明确，需要在与系统不断的交互评价过程中逐渐加以确认，即决策者在评价过程中不断地改变自己原有的偏好/倾向，产生出决策者的偏好不断调整的情况。（3）算法进化效率低下的问题。由于IEC要求在种群规模小、进化代数少的情况下使用，这就造成了算法的性能不高的问题。（4）人的疲劳问题。由于人要不断地与计算机交互来评价个体适应值，与不知疲倦的计算机相比，人具有容易疲劳的特点，人只能对较小规模的进化种群进行评价，且进化代数不能太多。

所以，要使得IEC能够更好地求解问题，需要从人评估的波动性（噪声）、人的偏好不断调整、算法的进化效率低下及用户评估疲劳等关键技术难题入手，结合适当的技术、方法，研究新的交互式进化优化理论与方法。1.3.1～1.3.3将从IEC的四个研究核心综述相关的研究工作的进展及其与本研究的关系。1.3.1 IEC与适应值噪声

IEC是从EC演化而来，所以EC中许多研究成果对IEC均有很好的借鉴意义。研究表明，一般进化计算（EC）中适应值噪声的来源主[15,16]要有以下两个方面：一是个体适应值的测量，即由测量误差或干扰信号形成含噪声的适应值；二是优化问题本身和环境的变化，即优化问题本身就是一个不断变化的动态目标问题，或者系统的参数会随着环境的改变而逐渐发生变化，从而影响优化问题的最终结果。

噪声对进化过程的干扰主要是体现在对选择的操作上，使得种群中优势个体被淘汰，而劣势个体可能会被误认为是优势个体而繁衍生存。因此，噪声容易造成进化过程的学习效率低，无法正确保留已学习的信息，算法的开发和搜索能力受限，种群适应值不能随进化代数[17]增加而增长。

从数学角度来看，一个含有噪声的适应值函数可以表示成下面的

[16]形式：

其中，X表示由算法控制的参数向量（即设计变量）, f（X）是不随时间变化的适应值函数，z是附加的噪声，服从正态分布（也有[18]文献研究了服从柯西分布的噪声）。而在实际的优化计算过程中，（1.1）式被近似表示成一组随机采样的平均值，即：

其中，N是采样的规模，（X）是F（X）=f（X）的估计。

针对噪声的影响，一般EC适应值噪声补偿策略主要有以下三种[16]：1．显式平均法(Explicit Averaging)

从（1.2）式可以看出，增加采样点的规模N，然后取所有采样的平均值（等价于减少适应值估计的偏差）可以减少噪声的影响。然而，采样增加表示适应值的计算次数也相应增加，从而也就增加了计算开销。因此，需要在不降低算法性能的情况下，尽量减少采样点。[19, 20]Aizawa和Wah建议采样规模应该在求解过程中自适应变化。文[21, 22]献则通过建立局部模型，计算未知适应值个体邻域中所有个体适应值的平均值，作为该未知个体适应值的办法，来减少适应值计算开销。2．隐式平均法(Implicit Averaging)

在搜索空间中，进化算法会在有前途的区域重复采样，从而使种群中有许多相似的个体。当种群规模很大时，噪声对评价个体的影响，会被这些相似个体所补偿，这种作用被称为隐式平均法。因此，在优化求解过程中为了减小噪声的影响，一个简单的方法就是使用大规模[23][24]的种群。文献从理论上证明，当种群规模为无限大时，比例选[25]择算子将不受噪声的影响。文献则研究了有限种群规模的情况，对于高斯噪声的影响，证明了增加种群规模，可以减少对Boltzmann选择的影响。3．改进的选择算子(Modifying Selection)

Markon等提出基于阈值的选择操作，即两个个体适应值的差异达到一定阈值时才能确定其占优性，否则很难评价在噪声下两个适应[26][27]值相近个体的优劣。文献则提出随机化选择过程，来处理由于噪声造成的额外不确定性。

在IEC中，个体的适应值由人主观评价得到，而人很难在评价过程中维持一个统一的评价标准，再加上人在与计算机交互过程中容易疲劳，从而造成对个体的适应值评价会有波动，形成适应值噪声。这种噪声类似于一般进化算法中噪声来源的第一种情况，即个体适应值的测量噪声。

由于IEC中人是最宝贵的资源，不能采用人对个体的重复评价，然后取均值的方法减少适应值噪声，因此一般进化算法中增大采样和种群规模的方法均不能直接用于处理IEC中的噪声问题。改进选择算子的方法虽然对采样次数没有要求，但是由于IEC要求在较少的代数内收敛，而基于阈值的选择等方法会延长种群的收敛代数，因此，这种方法也不适用于处理IEC噪声。

所以，如何结合IEC方法本身的特点，建立IEC的噪声模型和发展相应的降噪策略，将是一项充满挑战性的工作。1.3.2 IEC与用户偏好获取模型

偏好的概念主要应用在多准则决策中，表示不同用户对不同目标、属性或因素的重视程度。而IEC主要应用于服装设计、乐曲创作、工业设计和数据挖掘等一类性能指标难以用显式函数表示的系统优化问题，这类问题在一定程度上也具有多目标的性质，可以看作一个多目标决策过程。从决策角度研究IEC，主要有许芳诚等人。他们研究了基于IEC的多准则决策模型，并将其用于旅游行程规划和乐谱设计[2,28]。

实际上，IEC用户评价的个体适应值，就是该用户对此方案（解）的总体满意程度，然后进化算法再根据此用户的满意值在参数空间中进一步搜索更好的方案（解），直到找到用户满意的最终方案（解）。所以，IEC用户评价出的进化个体适应值实际上是对不同目标、属性或因素的一个综合值，但没有给出用户对不同目标、属性或因素的重视程度量值（如图1.1所示）。因此，如果能够求解图1.1所示的各个因素的权重，也就可以建立起IEC用户的偏好模型，从而可以辅助问题求解。图1.1 个体适应值（偏好）在不同因素上的分解模式

IEC用户偏好获取的另一个困难在于，由于人对事物认知过程的不确定性，用户很难在一开始就完全明确其偏好，而要在交互求解过程中，逐渐建立起偏好，因而出现IEC用户偏好不断调整的情况。这种偏好的调整，反映在各个因素的重视程度上，那就是各权重不断发生变化。[29]

目前，学者们主要是对个体的整体偏好进行研究，如文献提出的基于神经网络的分阶段估计方法，以辅助IEC求解；而缺乏逆向的总体适应值在各个因素上的分解值这方面的研究，再加上用户的偏好不断调整，所以，如何建立IEC用户偏好获取模型将是一项极具挑战性而又重要的工作。

在多准则决策中，有许多方法可以借鉴，如权重和法、效用函数[30,31]法、层次分析法（AHP）等；而人工智能中神经网络、分类器等技术可用于偏好的学习及适应值预测。如何使用适当的多准则决策方法和人工智能技术，并结合IEC方法操作的特点，成为获取IEC用户偏好的关键。1.3.3 IEC的进化效率及用户疲劳问题

实际上，IEC的进化效率与用户疲劳问题是一对相互影响的问题：由于IEC用户容易疲劳，所以IEC算法的种群规模常常限制在10个个体左右，而进化代数常限定在10～29代，从而造成IEC的进化效率低下问题；反过来，正是由于IEC算法的进化效率低下，使得用户需不断参与适应值的评价，从而造成用户的疲劳。我们在前面讨论了IEC[4～14]的一些改进策略，然而，提高IEC的进化效率、降低用户的使用[1]疲劳，是IEC研究中一个远没有解决的问题。而EC研究中，多种群协同进化思想可以极大提高EC算法的性能。近来，基于智能体计算技术及其与EC算法的结合的研究，得到广大研究者的关注。下面将从这两个方面来讨论相关的研究进展及其与IEC研究的关系。

多种群协同进化算法考虑个体之间及个体与环境之间的关系，种群中个体的进化受其他个体及进化环境影响，对个体进行适应值评价时需要利用其他个体的信息，即个体适应值不再仅由目标函数决定，同时还由其他个体决定。多种群协同进化算法依据其生物学基础不同，主要分为竞争型协同进化算法和合作型协同进化算法。

多种群协同进化算法最早的研究，可以追溯到1991年Hillis提出[32]的宿主与寄生物模型及Husbands的车间作业调度多物种协同进化[33]模型，这两种具体的协同进化算法模型统称为竞争型协同进化算法模型，都考虑了多个物种之间的相互作用。其应用研究成果表明，考虑物种之间相互作用的协同进化算法，相较于不考虑相互作用的进化算法，可以更好地维持进化种群的多样性，得到更好的进化结果[34]。

合作型协同进化算法主要是针对复杂协同适应性问题提出的一类进化算法。其编码方法与传统进化算法编码方法截然不同：个体不再对所有变量进行编码，而是对部分变量进行编码。在进行适应值评价时，单个种群个体仅是待优化系统的一个部分，对其无法采用传统绝对适应值评价方法，必须利用其他部分信息，构成一个整体，才可利用目标函数进行适应值评价。即在合作型协同进化算法中，种群之间[34, 35]是相互受益、相互制约、相互协同、共同进化的。1.4 本章小结

随着研究的不断深入，IEC方法也应该充分结合人工智能中的一些新概念、新技术，以获取新的改进思路。近来，分布式人工智能中基于智能体的计算已经应用于计算机学科的各个领域，这些能够感知环境并反作用于环境的物理的或虚拟的智能体涌现出相当大的智能，[36～39][36～39]可以对复杂问题进行有效求解。受到文献的启发，黄永青[40]等提出了交互式多智能体进化算法，获得了较好的运行性能。梁[40]昌勇、陆青等在汽车造型设计中提出了交互式基于共享机制的改进的小生境遗传算法，在算法整体效能和收敛速度上也得到了有效提高，但对用户的进化个体评价，仍然未解决评价噪声问题。

在IEC中，当单个用户使用多个种群进化时，用户的评价工作量将成倍增加，如何结合适当的评价策略，发展多种群交互式进化算法成为改进IEC的重要思路之一。

而当有多个用户同时利用IEC对问题进行求解时，可以借鉴其他种群的有益信息，即其他用户的优化结果，所以如何结合多种群协同进化的思想，构造多人参与问题求解的协同交互式进化模型与算法，将是对IEC进行改进和拓展的另一个重要研究思路。

这也显示出，将IEC与基于智能体的计算方法相结合，综合运用进化计算、决策理论、人工智能中的新技术和方法，可以发展新的高性能算法，因此有必要在此基础上做进一步的深入研究。参考文献[1]Takagi H.Interactive Evolutionary Computation:Fusion of the Capabilities of EC Optimization and Human Evaluation[C].In:Proceedings of the IEEE International Conference on Intelligent Engineering System, San Diego,2001.Vol.89, No.9, pp.1275-1296.[2]许芳诚．智能型多准则决策支持研究：以交谈式遗传算法为基础的模型[D]．桃园：国立中央大学，2000.[3]Cheng-Fang Hsu, Jiah-Shing Chen.A Study on Multi Criteria Decision Making Model:Interactive Genetic Algorithms Approach[C].In:IEEE SMC'99 Conference Proceedings,1999, Vol.3, pp.634-639.[4]Ohsaki M., Takagi H., Ohya K.An Input Method Using Discrete Fitness Values for Interactive GA[J].J ournal of Intelligent and Fuzzy Systems,1998,6 (1):pp.131-145.[5]Lee Y.J., Cho B.S.Sparse Fitness Evaluatin for Reducing User Burden in Interactive Genetic Algorithm [C].In:Proc of FUZZ-IEEE'99,1999, Vol.2, pp.998-1003.[6]Biles A.J., Anderson G.P., Loggi W.L.Neural Network Fitness Functions for a Musical IGA[C].In:IIA'96/SOCO'96 Int ICSC Symposial on Intelligent Industrial Automation and Soft Computing,1996.pp.39-44.[7]Kitamoto A., Takagi H.Learning Criteria for Similarity-based Image Retrieval Using Simulated Breeding by Pipeline-type Genetic Algorithms [C].In:Tech Rep IEICE, Japanese,1996.pp.17-22.[8]Cho S.B.Applying Interactive Genetic Algorithm to Content-based Image Retrieval:A Preliminary Result[C].In:Workshop on Interactive Evolutionary Computation, Fukuoka, Japan, Mar.,1998.pp.19-24.[9]Boschetti F., Takagi H.Visualization of EC Landscape to Accelerate EC Conversion and Evaluation of Its Effect[C].In:Congress on Evolutionary Computation (CEC2001),2001.[10]Takagi H., Kishi K.On-line Knowledge Embedding for an Interactive rdEC-based Montage System [C].In:3 Int Conf on Knowledge-based Intelligent Information Engineering Systems (KES'99), Adelaide, Australia,1999.pp.280-283.[11]巩敦卫，郝国生，周勇等．分层交互式进化计算及其应用[J]．控制与决策，2004,19(10):1117～1120.[12]胡静，陈恩红，王上飞．交互式遗传算法中收敛性及用户评估质量的提高[J]．中国科学技术大学学报，2002,32(2):210～216.[13]蒋珊珊，曹先彬，王煦法．基于IGA的用户Agent模型与设计[J]．模式识别与人工智能，2004,17(2):244～249.[14]王上飞，王胜惠，王熙法．结合SVM的交互式遗传算法及其应用[J].数据采集与处理，2003,18(4):429～433.[15]X.Yao.Evolving Artificial Neural Networks[C].In:Proc IEEE,1999, Vol.87, pp.1423-1447.[16]Y.Jin.Evolutionary Optimization in Uncertain Environments—A Survey [J].IEEE Transactions on Evolutionary Computation,2005,9(3):pp.303-317.[17]D.Büche, P.Stoll, R.Dornberger, and P.Koumoutsakos.Mult-i obj ective Evolutionary Algorithm for the Optimization of Noisy Combustion Process[J]. IEEE Transactions on System, Man, and Cybernetics—Part C:Applications and Reviews,2002,32.pp.460-473.[18]V.D.Arnold.On Effects of Outliers on Evolutionary Optimization[C].In:Intelligent Data Engineering and Automated Learning, Ser LNCS 2609 Berlin, Germany:Springer-Verlag,2003.pp.151-160.[19]N.A.Aizawa, W.B.Wah.Dynamic Control of Genetic Algorithms in a Noisy Environment[C].In:Proc conf Genetic Algorithms,1993.pp.48-55.[20]N.A.Aizawa, W.B.Wah.Scheduling of Genetic Algorithms in a Noisy Environment[J].Evolutionary Computation,1994, Vol.2, No.2, pp.97-122.[21]J.Branke, C.Schmidt, H.Schmeck.Efficient Fitness Estimation in Noisy Environment[C].Genetic and Evolutionary Computation, L.Spector et al, Eds San Mateo, CA:Morgan Kaufmann,2001.pp.243-250.[22]Y.Sano, H.Kita.Optimization of Noisy Fitness Functions by Means of Genetic Algorithms Using History of Search [C].Parallel Problem Solving from Nature Ser LNCS, M.Schoenauer et al, Eds Berlin, Germany:Springer-Verlag,2000,1917.pp.571-580.[23]M.J.Fitzpatrick, I.J.Grefenstette.Genetic Algorithms in Noisy Environments [J].Mach Lear,1988(3):pp.101-120.[24]L B.Miller, E.D.Goldberg.Genetic Algorithms, Selection Schemes, and the Varying Effects of Noise[J].Evol Comput,1996,4(2):pp.113-131.[25]M.L.Rattray, J.Shapiro.Noisy Fitness Evaluation in Genetic Algorithms and the Dynamics of Learning[C].Foundations of Genetic Algorithms, R.K. Belew and M.D.Vose, Eds San Mateo, CA:Morgan Kaufmann,1997.pp.117-139.[26]S.Markon D.Arnold, T.Bäck, T.Beielstein, and H.G.Beye.r Thresholding—A Selection Operator for Noisy ES[C].In:Proc Congr Evol Comput, 2001.pp.465-472.[27]J.Branke, C.Schmid.t Selection in the Presence of Noise[C].Lecture Notes in Computer Science, Vol.2723, Proc Genetic Evol Comput Conf, E Cantu-Paz, Ed,2003.pp.766-777.[28]陈稼兴，许芳诚．以交互式遗传算法为基础的多准则决策支持模型：旅游行程规划个案研究[J]．管理学报，2001,18(4):639～665.[29]周勇，巩敦卫，郝国生等．交互式遗传算法基于NN的个体适应度分阶段估计[J]．控制与决策，2005,20(2):234～236.[30]彭勇行．管理决策分析[M]．北京：科学出版社，2000.[31]岳超源．决策理论与方法[M]．北京：科学出版社，2003.[32]Hillis D.W.Co-evolving Parasites Improve Simulated Evolution as an Optimization Procedure[C].In:Langton C.G., Taylor C., Farmer J.D., et al eds.Artificial Life Ⅱ Redwood City; Addison-Wesley,1991.pp.313-324.[33]Husbands P., Mill F.Simulated Co-evolution as the Mechanism for Emergent Planning and Scheduling [C].In: Belew R.K.BLBe, editor.Proceedings of the Fourth International Conference on Genetic Algorithms, San Mateo:Morgan Kaufmann Publishers,1991.pp.264-270.[34]Potter M.A.de Jong K.A.A Cooperative Coevolutionary Approach to Function Optimization[C].In:Proceedings of the Third Conference on Parallel Problem Solving from Nature, New York,1994.pp.249-257.[35]Potter M.A.The Design and Analysis of a Computational Model of Cooperative Coevolution[D].Fairfax:George Mason University,1997.[36]韩靖，蔡庆生．AER模型中的智能涌现[J]．模式识别与人工智能，2002,15(2):134～142.[37]钟伟才，刘静，刘芳等．组合优化多智能体进化算法[J]．计算机学报，2004,27(10):1341～1353.[38]钟伟才，薛明志，刘静等．基于AER模型的Mult-i Agent遗传算法[J].模式识别与人工智能，2003,16(4):390～396.[39]钟伟才，薛明志，刘静等．多智能体遗传算法用于超高维函数优化[J].自然科学进展，2003,13(10):1078～1083.[40]黄永青，陆青，梁昌勇等．交互式多智能体进化算法及其应用[J]．系统仿真学报，2006,18(7):2030～2032,2055.[41]赵立江，黄永青．基于遗传算法的混合属性聚类初始点选择研究[J]．广西师范大学学报，2008,26(3):194～197.[42 ] A.Witkin and M.Kass.Spacetime Constraints [C].Proceedings of SIGGRAP H,1988.pp.159-168.2主要的多目标进化算法

现实世界的许多具体优化问题通常由多个目标组成，而这些目标[1]本身往往可能是相互矛盾和冲突的。Van Veldhuizen等人从决策者的角度将多目标进化分为三类：①先验法，即决策者首先将多目标合成数量成本函数，然后由算法搜索最优解；②渐进法，即决策者和算法是互动的，前者为后者提供目标的优先关系，而后者为前者提供新解以产生更好的目标间优先关系；③后验法，即算法为决策者提供一组候选解供决策者选择。目前大多数多目标进化算法属于后验法。另外，近年来出现的算法都有一些共同的特征，例如倾向构造一个外部种群以保留算法获得的非劣解，当外部种群的实际规模超过规定值时，采取适当措施移出部分解，以维持该种群中解方案的均匀性。这些典型的算法主要包括PAES、SPEA、SPEA2、NSGA和NSGA-Ⅱ算法等。

掌握和学习一些最新的主要多目标进化算法可以帮助研究人员正确认识和理解多目标优化问题的求解思路，也可以很好地区分各种多目标进化的设计过程及其操作算子的相同点和不同点。通过对这些算法的过程和性能的学习，可以加深对多目标进化算法实质和机理的理解，便于今后设计和改进此类算法的过程、操作算子以及其他可以提高算法性能和效率的操作行为方式。2.1 常见的多目标进化算法

多目标优化问题对于科学家和工程师来说是一个非常重要的研究课题，不仅因为大多数现实问题具备多目标的特征，而且还往往由于该领域仍有一些悬而未决的问题有待解决。一般来说，在科学研究和工程实践中许多优化问题都与多目标优化相关。多目标问题中各目标之间通过决策变量相互制约，对其中一个目标性能的优化必须以其他目标作为代价，而且各目标的度量单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别是，多目标问题的解方案不是唯一的，而是存在一个最优解集合，即所谓的Pareto最优解集或非劣解集。所谓Pareto最优解就是不存在比这个解方案至少一个目标更好而其他目标不低劣的更好的解，也就是不可能优化其中部分目标而使其他目标不劣化。Pareto最优解集里的元素就所有目标而言，彼此之间不可进行性能优劣比较。因此，对多目标问题的求解是科学家们在解决实际应用问题中所遇到的一个挑战。

过去的几十年间在学界涌现出20多种相关方法来处理具有多个子目标的函数优化问题。其大多数方法沿袭了一条固定模式的技术解决路线，即使用对策权衡原理对各子目标的相对重要性进行折中后，再组合成一个单目标来处理。但始终困扰运筹学理论界的一个问题是，多目标优化并不存在类似于单目标优化那样的纯“最优解”。最后导致一个问题：如果用几种传统方法来求解，结果可能会是五花八门的。因为通常有关问题决策的最优解是与所谓的“决策者（人）”直接相关的，此时用科学方法来实施优化的意义并不明显。

组合优化作为进化算法最基本的也是最重要的研究和应用领域之一，它所取得的巨大成功是启迪人们将人工模拟进化理论从单目标优化领域延伸到多目标优化领域。进化算法具有求解多目标优化问题的优点。早在1967年，Rosenberg在其博士学位论文中曾提到可以采用遗传搜索的方式来求解多目标的优化问题。直到1985年，Schaffer才提出第一个多目标进化算法，即VEGA，开创了用进化算法处理多目标优化问题的先河，但VEGA在本质上仍然是加权和方法，之后相继出现了许多种多目标进化算法。大多数成功的多目标进化算法都能很好地解决古典运筹学所能处理的多目标优化问题，不仅如此，它们还具备一般进化算法具有的独有特征，如可以处理的问题属于不可微的、不连续的、多维的、有约束条件或者高度非线性的组合优化问题。

到了20世纪90年代中期，多目标进化算法开始真正引起人们的兴趣，相关的论文数量急剧增加，在人工生命和进化计算学科中多目标进化算法成为一个相当热门的研究领域。2001年3月在瑞士的苏黎世大学召开了国际上第一次进化多准则优化的会议，2001年5月在韩国汉城（首尔的旧称）召开的国际进化计算大会上开始出现专门的多目标进化算法会议专题。目前，走在该领域研究前列的国家和地区有美国、欧洲、墨西哥和印度等。分析有关文献中经常使用的适应度函数类型，人们可以大致看出多目标进化算法应用的主要领域囊括了电子工程学、环保学、金融学、经济学、几何学、物理学、信息及资源[4]管理等。2.1.1 算法分类图2.1 多目标进化算法的分类

尽管涌现出许多种多目标进化算法，但可以依据某一特征将它们分门别类。前文已经提到过，Van Veldhuizen从决策的观点出发，对现有的多目标进化算法根据所使用的解决方法进行了大致分类。他使用的主要依据是最优解的形成与决策过程的交互方式，即先验偏好链接、进程偏好链接和后验偏好链接，形成的多目标进化算法分类图的层次结构如图2.1所示。

从统计数据可以发现，目前比较流行的是后验法，使用数量几乎是另外两种的2倍多。另外，在后验法这类算法中，使用Pareto选择策略的算法是其他选择策略的2倍，而且使用的进化方法为遗传算法的是其他方法，如进化规划、进化策略等的9倍。因此，可以说基于Pareto的遗传算法在多目标进化算法设计和应用中占据最主要的地位。2.1.2 选择机制

由于进化算法是对整个群体进行进化运算操作，它着眼于个体的集合，而多目标优化问题的Pareto最优解也是一个集合，因而从直观上来看，进化算法是求解多目标优化问题的Pareto最优解集合的一种有效方法。

一方面，求解多目标问题的进化算法的基本结构与求解单目标问题的遗传算法的基本结构大致相似；另一方面，在利用进化算法进行多目标问题求解时，需要考虑如何评价Pareto最优解以及如何设计适合于多目标问题的选择算子、交叉算子和变异算子等问题。因而算法在设计实现时有其独特的地方。

除了保留和维持一定规模的外部种群外，基于Pareto最优性的多目标进化算法必须根据个体间的Pareto优于关系和个体信息（如密度值）来产生个体的适应度函数值，这是单目标优化不会遇到的问题。除此之外，和单目标优化不同的方面在于多目标进化算法基本上不采用基于适应度值的选择方式（如轮盘赌法），而是采用基于局部竞争的选择机制，其中在遗传算法中主要倾向于锦标赛选择，在进化策略中倾向于μ+λ或（μ, λ）选择。以上这些因素使得多目标进化算法过程的设计构造和实现变得更复杂。

对于如何求解多目标问题的Pareto最优解，目前已经提出了多种基于遗传算法的求解方法。下面根据使用的选择机制介绍几类主要的方法，它们分别是并列选择法、权重系数变化法、排序选择法、共享函数法和外部辅助选择法。对于具体的应用问题，选用哪种方法取决于对该问题的理解程度及决策人员的偏好。这里的分类方法与2.2节和2.3节的分类有所不同，后两节是根据进化过程中积木块是显式还是隐式的属性对算法进行系统分类，并且给出较详细的介绍。这里则侧重于多目标进化算法使用的选择机制和方式的不同，对它们进行初步的阐述。1．并列选择法

并列选择法的典型代表是Schaffer提出的“向量评估遗传算法”[5]。这是一种非Pareto方法，它先将群体中全部个体按子目标函数的数目平均分成若干子群体，对各子群体分配一个子目标函数，各子目标函数在其相应子群体中独立进行选择操作后再组成一个新的子群体；然后将所有新生成的子群体合并为一个完整的群体，再进行交叉和变异操作。如此循环执行“分割并列选择—合并”过程，最终求出问题的非劣解。

这种并列选择方法可能产生个别子目标函数的极端最优解，而要找到所有目标函数在某种程度上较好的均衡最优解却较困难。2．权重系数变化法

权重系数变化法的例子如Hajela和Lin提出的“可变目标权重聚合法”。这也是一种非Pareto方法，在为适应度赋值时使用加权和法，对每个目标赋一个权重。为了并行搜索多个解，权重本身并不固定，问题解和权重同时实施进化操作。由于要保证收敛速度和遗传搜索的稳定性，该方法需要使用配对约束。

这种方法的优点是计算效率比较高，同时可以得到一个很好的非劣解作为其他方法的初值；主要缺点则是在没有足够的关于此问题的信息时，无法确定合适的权重系数，此时得到的任何最优解都是权重系数组合函数的优化结果。使用简单的线性函数，根据多次不同权重的计算来生成非劣解集。这种方法实现简单、易于使用，但是有时会丢失非劣解集平面的凹陷部分，在某些应用中，这种缺陷问题可能会对求解结果产生十分不利的影响。3．排序选择法

排序选择法的例子比较多，如Fonseca和Fleming提出的“多目标遗传算法”以及Srinivas和Deb提出的“非劣分类遗传算法”都属于排序选择法。此类方法根据“Pareto最优个体”的概念来对群体中的所有个体进行排序，依据这个排列次序来实施进化过程中的选择运算，从而使排在前面的Pareto最优个体有更多的机会遗传到下一代群体。这样，经过一定代数的循环之后，最终可以求出多目标优化问题的Pareto最优解。

Pareto最优个体是指群体中这样的一个或一些个体，即群体中的其他个体都不比它或它们更优越。需要说明的是，在群体进化过程中某一代所产生的Pareto最优个体不一定对应于多目标优化问题的真正Pareto最优解，它们只是在有限群体里进行优劣比较的结果。当然，当进化算法运行结束时，人们需要的是已经获得的Pareto最优个体，它们是经过整个算法运行后找到的最优解，当然仍是针对有限群体进行优劣比较的结果，所以将它们所对应的解作为多目标问题的Pareto最优解或者近似解是完全合理的。

对群体中的所有个体进行Pareto最优个体排序的过程如下：（1）设置初始序号，r←1。（2）确定群体中的Pareto最优个体，定义这些个体的序号r。（3）从群体中去掉Pareto最优个体，并更改序号←r+1。（4）转到（2），直到处理完群体中的所有个体。

由上述Pareto最优个体的排序算法可知，排序选择法仅度量了各个个体之间的优越次序，而未度量各个个体的分散程度，因而容易生成很多个相似的Pareto最优解，难以生成分布较广的Pareto最优解集合。4．共享函数法

求解多目标优化问题时，一般希望所得到的解方案尽可能地分散在整个Pareto最优解集合内，而不是集中在Pareto最优解集合内的某一个较小的区域。为了达到这种要求，可以利用小生境遗传算法的技术来求解多目标优化问题。这种求解多目标问题的方法称为共享函数法，它将共享函数的概念引入到求解多目标问题的进化算法中。这类算法的典型代表是Horn等人提出的“小生境Pareto遗传算法”，另外还有一些其他的变形形式。

在利用通常的进化算法求解最优化问题时，算法并未限制相同个体或类似个体的数量。但是当在进化算法中引入小生境方法之后，就要对它们的数量加以限制，以便产生种类较多的不同的最优解。对于某一个个体而言，在它的附近还存在多少种、多大程度相似的个体是可以度量的，这种度量值就是小生境数（Niche Count）。

在计算出各个个体的小生境数之后，可以使小生境数较小的个体有更多的复制机会被遗传到下一代群体，即相似个体较少的个体有更多机会被遗传到下一代群体，这样就增加了群体的多样性，相应地也会增加解的多样性。

进化算法中的共享选择方法综合运用联赛选择和共享函数的思想，由此来选择当前群体中的优良个体遗传到下一代群体中，共享函数法的过程描述如下：（1）从群体中随机选取k个个体组成个体比较集合C，其中k是预先指定的一个表示比较集合规模的常数。（2）从群体中随机选择两个个体组成个体联赛集合T。（3）分别比较个体联赛集合T中的两个个体与个体比较集合C中各个个体之间的优胜关系，根据这个比较结果，按下述方法从个体联赛集合T中选择出一个个体遗传到下一代群体。

①如果集合T中的一个个体（记为X）比集合C中的所有个体都优越，而集合T中的另一个个体都不比集合C中的所有个体优越，则将个体X遗传到下一代群体中。

②如果由上面的一种情况未能选择出一个个体，则利用共享函数的概念从集合T中选择出一个小生境数较小的个体遗传到下一代群体中。

使用该选择操作方法的优点是能够得到多种不同的Pareto最优解，但由于每次进行选择操作时都需要进行大量的个体之间优越关系的评价和比较运算，使得算法的搜索效率较低。5．外部辅助选择法

目前外部辅助选择法在多目标进化算法的设计中使用较多，且在实现应用中也很受欢迎。典型代表就是Zitzler和Thiele提出的“强度Pareto进化算法”[2]。这类方法具有四个与众不同的特征：（1）将每代的非劣个体储存在外部的一个附属可更新群体里。（2）群体中个体的适应度与外部辅助集内优于该个体的数目有关。（3）利用Pareto优越关系保持群体多样性。（4）使用聚类方法保证外部集合的非劣个体数目不超过规定范围，并且不破坏其分布特征。

外部辅助选择法的流程如下：（1）产生初始群体P和一个空的外部辅助的非劣集合P′。（2）将P中非劣个体复制至P′。（3）将P′中的劣解方案删除，第一代不存在劣解。（4）如果外部辅助存储的非劣解个体数目超过预定数N′，则对P′进行聚类处理，使其规模不超过N′。（5）计算P和P′中每个个体的适应度值。（6）从P∪P′（两集合并集）中进行选择操作直至配对池满，使用二进制联赛选择机制。（7）应用与所求问题相关的交叉和变异操作算子。（8）如果达到规定的最大进化代数则停止运行，否则转步骤（2）。

外部种群P′已成为许多多目标进化算法中不可分割的部分，为了让外部种群中的个体能够分布均匀，必须对外部种群进行调整。通常的做法是在非劣解直接进入外部种群时进行有关操作。如果在插入新解后，外部种群大小超过规定值，则需按如下条件将P′中的部分个体移出来，保证P′的最大规模始终保持不变。（1）新解支配外部种群的部分解。（2）根据外部种群中个体的某些信息决定移出哪些解方案。

例如在PAES中，如果非劣解增加了种群内个体的多样性，则取代种群中位于最拥挤区域内的一个解。在Knowles等人提出的自适应存档（Archiving）算法中，新的非劣解如果位于现有区域外或最拥挤格子外，它将取代位于最拥挤格子内的一个解。除了根据个体所在格子内的个体数目这一信息外，个体间的距离也要加以考虑，主要是用于外部种群的调整，在SPEA算法中当外部种群大小超过规定值时，将新解和保留解共同进行聚类处理，保持外部种群的规模不变。2.2 隐式积木块类型算法

众所周知，第一个公认的多目标进化算法是Schaffer在1984年提出的VEGA。尽管从现今的角度来看，该算法的过程原理比较简单，但是它问世最早，开创了一个领域的先河，最早提出采用遗传算法求解多目标问题，并提供了具体的过程算法细节。因此，Schaffer的研究工作具有开创性的意义，其算法在众多文献中被广为引用。

在Schaffer的研究工作提出之后的一段时间内，只是出现了一些改进的研究成果，基本上属于停滞不前的阶段。这主要是由于在20世纪80年代中后期计算机的资源受限，当时计算机的计算能力和内存资源很有限，使得研究人员不能对多目标进化算法展开广泛和深入的研究，因而，那个时期的研究工作进展不大。后来，随着计算机能力的扩展和提高，越来越多的研究人员开始对多目标进化算法的性能针对一些函数数值例子进行实验。由于与其他学科如物理、化学等一样可以进行实验研究，能够在一定程度上有一个直观、可信的结果，从而极大地启发了人们的研究热情。

当然，在20世纪90年代早期，计算机的资源还不是很丰富，执行算法时要考虑内存使用方面的优化问题。例如当时的实现算法通常采用位操作，将群体存储为无符号的整型变量。由于多目标进化算法与单目标进化算法的特点有所不同，需要对多个目标函数进行评估并存储相关数值，因而需要拥有更快的计算速度和占用更多的内存资源。在20世纪90年代的中后期计算机能力得到了彻底的提高，研究人员对多目标进化算法的全面设计和分析研究有了硬件基础，多目标进化算法开始真正形成一个研究领域。

从研究思路的角度来看，早先的多目标进化算法是对单目标进化算法的一种简单扩展，在实现方式上也是沿袭SGA的操作算子。在SGA基础上进行扩展是早期设计和实现多目标进化算法的主要贡献。这种扩展具有很多优点，例如可以对已有的程序代码进行改造，特别是可以对SGA多年采用的经典操作算子代码直接加以移植使用。对SGA的扩展和移植可以容易地实现一种多目标进化算法，代码改进的工作量不是很大，内存利用率得到提高，并且便于理解算法的过程。另外，SGA中很多最新研究结果和设计思想也可以移植到多目标进化算法的设计过程中，部分文献和研究工作就是基于这一思路的。

将多目标问题和多目标进化算法进行系统分类，对开展研究和工程应用具有指导意义。系统分类可以帮助研究人员确定如何组合多目标进化算法的操作算子，并针对具有某些特征的多目标问题正确地设置参数，以便高效地执行算法和产生较好的解结果。

对多目标进化算法进行分类的方式有多种，主要依据是算法的一般信息、采用的操作算子和算法特征。例如2.1节是针对进化过程中的选择方式的不同进行算法分类。下面根据多目标进化算法操作中使用积木块的类型不同对算法进行分类。图2.2为多目标进化算法过程的伪代码描述，反映本领域中大多数多目标进化算法的共同特征。这种MOEAs结构代码可以帮助研究人员理解一种多目标进化算法框架和基本的操作算子，另外也展示了多目标进化算法的内部工作过程和机理。图2.2 多目标进化算法结构的伪代码

根据进化计算的模式定理，遗传算法在运算过程中利用定义长度短、阶次低、平均适应度高的优良模式，不断建立高适应度的字符串，从而逐渐逼近问题的最优解。这类模式在遗传算法中非常重要，它是遗传算法得以推广应用的数学理论基础。人们将这种具有低阶、短定义距和高适应度的模式称作积木块（Building Block, BB）。通俗地说，积木块就是指长度较短、性能较好的基因片断。正如搭积木一样，这些优良的模式在遗传操作过程中相互拼搭、结合，产生出适应度更高的串，从而找到更优的可行解，这正是著名的积木块假设提示的内容。这里顺便介绍一下积木块假设的内容。积木块假设是指低阶、短距和高适应度的积木块模式在遗传算子作用下相互结合，能生成高阶、长距、高适应度的模式，最终形成全局最优解。优化目标函数编码组合中常存在着某种规则性，它们都可以由重组积木块开拓搜索范围。遗传算法的计算能力依赖于这种寻找最优解点的积木块的组合。

通常在染色体编码中具有优良积木块的个体，在计算适应度时会表现出优秀的行为。多年来，积木块和模式定理一直被认为是为优化问题提供优良解的关键，因此根据已有的积木块研究结果，可以将多目标进化分为两类。这两类算法就是隐式操作积木块的类型和显式操作积木块的类型。本节和下一节将对这两类算法所包含的具体算法进行介绍。此外，还有一些基于决策者预期目标的目标向量方法，如目标规划、目标实现和最小最大方法等。这类方法的优点是计算效率高，缺点是各优化指标的预期目标一般难以确定，且对非凸搜索空间不适用。

大多数多目标进化算法是基于隐式积木块的方法，这类方法的优点是在解决某些多目标问题时可以提高效率和计算性能。基于隐式积木块的多目标进化算法并不在群体中直接地显式辨识出优秀积木块模

试读结束[说明：试读内容隐藏了图片]

下载完整电子书