（系统工程专业论文）改进的粒子群计算智能算法及其多目标优化的应用研究.pdf

浙江大 受硕 卜 学价论u 摘要 优化技术是一种以数学为基础， 用于求解各种实际问题的应用技术。 随着现 代科学的发展， 各学科之间的相互渗透， 新的交叉学科不断形成， 新的思维方式、 新的计算方法， 特别是计算机科学与技术的迅速发展为优化技术的研究与发展注 入了活力， 也为其提供了更广阔的研究空间。 人们认识与改造世界的能力日 益扩 大， 对科学技术也提出了更新、 更高的要求， 其中对高效的优化技术和计算方法 的要求日益迫切。同时， 对于实际系统， 例如工程领域， 特别是人工智能与控制 领域， 不断涌现出多目 标、非线性、 不可微甚至混杂的系统， 经典优化方法不能 有效求解的优化问题，必须采用计算智能技术。 本文主要研究成果与贡献如下: 1 .简要的回顾了计算智能的理论和技术发展史并介绍了计算智能的研究背 景。 总结了多目 标优化的传统解决方法和基于进化计算的解决方法，并 重点介绍了遗传算法和粒子群算法在多目 标优化领域的研究现状。分别 总结了混合整数规划和不确定系统的研究现状。 2 ，对于粒子群算法进行了详尽的分析和综述，粒子群优化算法 ( p s o )是 一种新兴的仿生学算法，因为和遗传算法相似的全局收敛性但更快得多 的收敛速度而备受关注。 在介绍了基本的p s o算法的基础上，引入了近 几年来p s o的改进算法及其应用领域， 将几种改进算法进行综合， 和遗 传算法进行比较，实例验证了综合 p s o算法的优越性，并讨论了将来 p s o可能的研究方向。 3 . 在杂交粒子群算法( h p s o ) 的 思想 基础上， 提出了 一 种新的 优化算法来 解 决多目标优化命题。 同时采用了适应度函数法来处理优化中的约束问题。 最后运用标准测试函数和一个对比实例验证了该方法的有效性。 4 .在总结了目 前混合整数规划的求解方法的基础上，引入了最小偏差法和 g a ms 工具，提出了一种将两者结合起来求解多目 标混合整数规划的方 法。并展望了p s o在混合整数规划领域的研究前景。 5 .在总结了现有区间数排序方法的基础上，通过实例分析，验证了一种新 的排序方法p + 准则对线性不等式约束进行处理的有效性。 对目 标函 数含 浙江大学硕十学位论文 有区间数参数的线性规划问题，根据决策者对较高的期望值和较小的不 确定性两者的偏好，对区间数进行选取，将单目标函数转化为多目 标函 数。 关键词 规划， :计算智能 混杂系统， ，多目标优化 不确定系统， ， 粒子群， 遗传算法， 最小偏差， 混合整数 区间数规划 浙江大学硕士学位论文 ab s t r a c t o p t i m i z a t i o n i s a k i n d o f a p p l i c a t i o n t e c h n o l o g y w h i c h i s b a s e d o n m a t h a n d s o l v e s a l l k i n d s o f p r a c t i c a l p r o b l e m s . wit h t h e d e v e l o p m e n t o f t e c h n o l o g y a n d p e n e t r a t i o n o f s u b j e c t s , n e w c r o s s s u b j e c t s c o m e i n t o b e i n g a n d n e w t h i n k i n g s t y l e , n e w c o m p u t a t i o n m e t h o d s , e s p e c i a l l y t h e d e v e l o p m e n t o f c o m p u t e r s c i e n c e a n d t e c h n o l o g y e n e r g i z e t h e s t u d y a n d d e v e l o p m e n t o f o p t im i z a t i o n t e c h n o l o g y a n d s u p p l y w o r l d , m o r e s p a c e o f s t u d y . wi t h t h e e x p a n s i o n o f p e o p l e u n d e r s t a n d a n d r e b u i l d t h e p e o p l e h a v e b r o u g h t f o r w a r d t o n e w e r a n d h i g h e r r e q u e s t a b o u t s c i e n c e a n d t e c h n o l o g y , e s p e c i a l l y a b o u t h i g h e ff i c i e n t o p t i m i z a t i o n t e c h n o l o g y a n d c o m p u t a t io n m e t h o d s . a t t h e s a m e t i m e , f o r p r a c t i c a l s y s t e m , s u c h a s e n g i n e e r i n g f i e l d , e s p e c i a l l y a rt i f i c i a l i n t e l l i g e n c e a n d c o n t r o l f i e l d , m u l t i - o b j e c t i v e , n o n l i n e a r , n o n d i f f e r e n t i a b l e a n d i n t e r m ix s y s t e m s c o m e f o r th . s o m e p r o b l e m s w h i c h c a n t b e s o l v e d b y c l a s s i c o p t i m i z a t i o n m e t h o d s m u s t b e s o l v e d b y c o m p u t a t i o n i n t e l l i g e n c e t e c h n o lo g y . t h e m a i n c o n t r ib u t i o n s o f t h i s t h e s i s a r e l i s t e d a s f o l l o w in g : 1 . l o o k b a c k t h e t h e o r y a n d t e c h n o l o g y d e v e l o p m e n t h i s t o ry o f c o m p u t a t i o n a l i n t e l l i g e n c e a n d i n t r o d u c e it s s t u d y b a c k g r o u n d . s u m m a r i z e t r a d i t i o n a l m e t h o d s f o r m u l t i - o b j e c t i v e s o p t i m i z a t i o n a n d m e t h o d s b a s e d o n e v o l u t i o n a l c o m p u t a t i o n , e s p e c i a l l y e m p h a s i z e t h e c u r r e n t r e s e a r c h p r o g r e s s o f g e n e t i c a n d p s o m e t h o d s . s u m m a r i z e m i x e d i n t e g e r p r o g r a m m i n g a n d u n c e rt a i n t y s y s t e m o p t i m i z a t i o n r e s p e c t i v e ly . 2 . s y n t h e s i s p a r t i c l e s w a r m o p t i m i z a t i o n ( p s o ) m e t h o d . p s o i s a n e w e v o l u t i o n m e t h o d . i t i s a t t a c h e d i m p o r t a n c e b e c a u s e i t h a s g e n e r a l c o n v e r g e n c e s i m i l a r t o g e n e t i c m e t h o d a n d f a s t e r c o n v e r g e n c e v e l o c i t y . a ft e r i n t r o d u c e b a s a l p s o me t h o d , s y n t h e s i s mo d i f i e d p s o a n d t h e i r a p p l i c a t i o n fi e l d s a r e p r o v i d e d .s e v e r a l m o d i fi e d p s o m e t h o d s , c o m p a r e t h e 3 r e s u l t s w i t h g e n e t i c a l g o r i t h m , a s a m p l e v e r i f i e d t h e e ff i c i e n c y o f p s o d i s c u s s t h e d e v e l o p m e n t o r i e n t a t i o n o f p s o . ah 必r i d p a r t i c l e s w a r m o p t i m i z a t i o n ( h p s o ) me t h o d i s i n t r o d u c e d a n d a mo d i f i e d h p s o ( mh p s o ) m e t h o d i s p r o p o s e d t o c o p e w i t h m u l t i - o b j e c t i v e s i i i 浙江大学硕士学位论文 o p t i m i z a t i o n p r o b l e m s . a c o n s t r a i n t s i n o p t i m i z a t i o n f i t n e s s f u n c t i o n me t h o d i s a l s o s t u d i e d t o s o l v e p r o b l e m s . i t i s p r o v e d t o b e e f f i c i e n c y b y t e s t i n g b e n c h m a r k p r o b l e m s . 4 . s u m m a r i z e s o l v i n g m e t h o d s f o r m ix e d i n t e g e r p r o g r a m m i n g . i n t r o d u c e m i n i m i z e w a r p m e t h o d a n d g a ms s o ft w a r e . a n e w m e t h o d i s p r o p o s e d t o s o l v e m i x e d i n t e g e r p r o g r a m m i n g t h r o u g h c o m b i n i n g m i n i m i z e w a r p a n d g a m s . p r o s p e c t t h e d e v e l o p m e n t o r i e n t a t i o n o f m i x e d in t e g e r p r o g r a m m i n g . 5 . s y n t h e s i s c u r r e n t m e t h o d s o f r a n k i n g i n t e r v a l c o e f f i c i e n t s . a n e x a m p l e v e r i f i e s a n e w r a n k i n g m e t h o d u r u l e i s e f f i c i e n t t o l i n e a r i n e q u a l i t y c o n s t r a i n t s . f o r t h o s e p r o b l e m s w h o s e o b j e c t i v e f u n c t i o n s h a v e i n t e r v a l p a r a m e t e r s , w e c h o o s e in t e r v a l c o e ff i c i e n t s a n d t r a n s f e r o b j e c t i v e fu n c t i o n s fr o m s i n g l e o b j e c t i v e t o m u l t i - o b j e c t i v e s b y d e c i s i o n m a k e r s f a v o r i t e h i g h e x p e c t a t i o n a n d l o w u n c e rt a i n t y . a n e x a m p l e i s s o l v e d b y h y b r i d p s o a l g o r i t h m a n d t h e r e s u lt s v e r i 斤t h e e f f i c i e n c y o f t h e m e t h o d . k e y wo r d s : c o m p u t a t i o n a l i n t e l l i g e n c e , m u l t i - o b j e c t i v e s o p t i m i z a t i o n , p a r t i c l e s w a r m , g e n e t i c a l g o r i t h m , m i n i m i z e w a r p , m ix e d i n t e g e r p r o g r a m m i n g , u n c e rt a i n t y s y s t e m , i n t e r v a l c o e ff i c i e n t p r o g r a m m i n g i v 本项目 得到国家自 然科学基金资助 基金名称:一类具有模栩不确定的工业系统 鲁棒优化及智能优化算法研究 项目 编号:6 0 4 7 4 0 6 4 浙江大学硕十学位论文 第一章 绪 论 摘要: 本章简要的回顾了计算智能的理论和技术发展史， 叙述了计算智能的研究 背景。 然后总结了多目 标优化的传统解决方法和基于进化计算的解决方法， 并重 点介绍了遗传算法和粒子群算法在多目 标优化领域的研究现状。 接下来分别总结 了混合整数规划和不确定系统的研究现状， 最后对本论文的工作做了全貌性的描 述。 关键词: 计算智能，多目 标，进化计算，混合整数规划，不确定系统 1 . 1 引言 优化技术是一种以数学为基础， 用于求解各种实际问题的应用技术。 它广泛 应用于工业、农业、国防、工程、交通、金融、化工、能源、通信等许多领域， 如在资源利用、 结构设计、 调度管理、 后勤供应等许多领域中产生了巨 大的经济 效益和社会效益。 优化在结构力学、 生命科学、 材料科学、 环境科学、 控制论等 其他科学研究领域也有广泛应用。 优化作为人们一个强有力的思想方法， 己 迅速 发展成为一门 重要的应用数学学科， 并且与分析、 几何、 代数、 概率及计算机科 学、系统科学、自 动化等有密切联系，同时相互促进。国内外的应用实践表明， 在同 样条件下， 经过优化技术的处理， 对系统效率的提高、能耗的降低、 资源的 合理利用及经济效益的提高等均有显著的效果，而且随着处理对象规模的增大， 这种效果也更加显著。 这对国民经济的各个领域来说， 其应用前景无疑是巨大的。 当一个优化问题模型只包含一个目 标方程的时候，我们称之为单目 标优化; 然而在实际的问题中， 却存在着需要同时考虑多个目 标函数的同时优化问题， 我 们称之为多目标优化。 在单目 标优化中， 最优解通常是唯一的， 而多目 标优化的 最优解通常是一个解集， 这些解是把所有的目 标函数都综合考虑后所得到的广义 上的优化解. 随着现代科学的发展， 各学科之间的 相互渗透， 新的交叉学科不断形成， 新 的思维方式、 新的计算方法， 特别是计算机科学与技术的迅速发展为优化技术的 研究与发展注入了活力， 也为其提供了更广阔的研究空间。 人们认识与改造世界 浙江大学硕士学位论文 的能力日 益扩大， 对科学技术也提出了更新、 更高的要求， 其中对高效的优化技 术和计算方法的要求日益迫切。同时， 对于实际系统， 例如工程领域， 特别是人 工智能与控制领域， 不断涌现出多目标、 非线性、 不可微甚至混杂的系统， 经典 优化方法不能有效求解的优化问题，必须采用智能技术。 1 . 2 计算智能的研究综述 美国 学 者b e z e d k j . c 于1 9 9 2 年 在 a p p r o x i m a t e r e a s o n in g ) 学 报 上 首次 给 出了 计 算智能( c o m p u t a t i o n a l i n t e l l i g e n c e , c i ) 的定 义: 计算智能是依 据工作 者 所提供的数值化数据来进行计算处理的。1 9 9 4 年6 月底到7 月初， i e e e 神经网 络委员会在o r l a n d 。 召开了i e e e首次国际计算智能大会 ( w o r l d c o n f e r e n c e o n c o m p u t a t io n a l i n t e l l i g e n c e ) 。 这 次 会议 首 次 将进 化 计算、 人i 神 经网 络 和 模 糊 系 统这三个领域合并在一起，形成了“ 计算智能”这个统一的技术范畴。 ，计算智 能的研究由此被提升到一个前所未有的高度。 计算智能的提出对促进人工智能领 域中各种理论和方法的集成，对推动人工智能的发展起到了非常重要的作用。 计算智能是从模拟自 然界生物体系和人类智能现象发展而来， 用计算机模拟 和再现人类的某些智能行为， 并用于改造自 然的工程实践的一种新型人工智能研 究领域。 计算智能领域非常广泛， 从方法上讲， 目 前计算智能主要包括进化计算、 人工神经网络和模糊系统三个领域; 另外目 前受到普遍关注的人工生命也属于计 算智能的研究领域。 计算智能的最大特点就是不需要建立问题本身精确的数学模 型， 适合于解决那些因为难以建立有效的形式化模型而用传统人工智能技术又难 以有效解决甚至无法解决的问题。 在我国国民经济的各个领域中 存在着相当多的涉及因素多、 规模大、 难度高 和影响广的优化命题， 在运输中的最优调度、 生产流程的最优编排、 资源的最优 分配、 农作物的合理布局、 工程的最优设计以 及国土的最优开发等等。 这类大规 模优化命题中， 绝大部分都是关系到国计民生的重大问题。 如建筑工程设计领域 中坝体断面的优化设计、 水利优化设计、 水库蓄洪量的最优设计等都是一些变量 维数高、 非线性强且不易求解的优化命题。 当传统数学规划算法在求解这些问题 遇到困难时，计算智能往往能显示出其不可比拟的优越性。 我们知道， 传统的优化方法主要有三种: 枚举法、 启发式算法和基于梯度的 浙江大学硕_ l 学位论文 搜索算法。 1 . 枚举法。对于可行解的数目 有限时，理论上枚举法可以得到精确的最优 解。对于连续函数，则要求先进行离散化处理，解的精确性取决于离散化 的细度。主要缺点是当枚举的空间比较大时，该方法的求解效率较低，有 时所需的计算资源是无法满足的。 2 . 启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解 或者近似最优解。该方法效率比较高，但是对每一个具体问题都要找到其 特有的启发式规则，这个启发式规则一般无通用性，不适合求解其他问题。 3 . 基于梯度的搜索算法。一般优化问题的求解，用的最多是基于梯度的搜 索算法。我们熟悉的牛顿法、最速下降法、共扼梯度法等算法都属此类。 求解问题的效率较高，算法也有通用性。但是搜索到最优解的概率依赖于 初始点的选取。 随着问题种类的不同和问题规模的扩大， 要寻求一种能够以有限的代价来解 决优化命题的通用算法。 计算智能为我们提供了一个有效的途径。 归纳起来， 计 算智能有着以下一些优点: 1 .自 组织、自 适应和自 学习性。该特性的存在，消除了算法设计过程中的 一个最大障碍，即需要事先描述问 题的全部特点，并要说明针对不同问 题的不同特点算法应该采取的措施。因此，利用进化计算的通用计算能 力，我们可以解决那些复杂的非结构化问题。 2 .本质并行性。算法的并行性在计算机的性能飞速发展的今天有着特别重 要的 意 义。 超大 规 模 集成电 路 ( v e ry l a r g e s c a l e i n t e g r a t i o n , v l s i ) 技 术使得专门用于计算的多节点互连成为可能，并且根据节点数目成倍的 提高计算的效率。 3 .记忆的分布性。计算智能在信息处理上是并行的，在信息的存储和表达 上是分布的。进化计算中种群的数目 大小对问题的求解除速度之外并没 有根本上的影响，从而提高了容错性和鲁棒性。 4 ，其他特性。除了上述几个共同优点，计算智能能根据具体算法还有自身 的一些良 好性能。比如进化计算一般对函数的连续性和导数没有严格的 要求，对于多目标优化问题能给出一组的p a r e t o 非劣解等等。 浙江大学硕士学位论文 正因为计算智能提供了一种求解复杂系统优化的通用框架， 具有很强的鲁棒 性， 所以广泛应用于许多学科。 某些学者研究了进化计算的突现行为( e m e r g e n c t b e h a v i o r ) 之后声称， 进化计算与混沌理论、 分形几何将成为人们研究非线性现 象的复杂系统的三大方法， 并将和神经网络一起成为人们研究认知过程的重要工 具。 下面我们对计算智能的三个领域的基本理论做一个简单的介绍: 模糊系统 为了表示和处理现实世界中的许多不精确和不确定性， z e d e h于 1 9 6 5 年提 出了 模糊集合理论。 在模糊集合中， 集合的边界并不清晰， 集合成员的资格也不 是肯定或否定， 它采用隶属函数来描述现象差异的中间过渡， 从而突破了古典集 合中属于或不属于的绝对关系。 在模糊集合中， 每个个体被分配一个值以表示它 隶属于该集合的程度， 这个值反映的是该个体与模糊集合所表示的概念的相似程 度:隶属度越大，属于该集合的程度也越大，反之亦然。 模糊系统以模糊集合理论、 模糊逻辑推理为基础， 它试图从一个较高的层次 模拟人脑表示和求解不精确知识的能力。 在模糊系统中， 知识是以规则的形式存 储的， 它采用一组模糊i f -t h e n规则来描述对象的特性， 并通过模糊逻辑推理 来完成对不确定问题的求解。 模糊系统善于描述利用学科领域的知识， 具有较强 的推理能力。近 1 0多年来，模糊系统已被广泛的应用于专家系统、智能控制、 故障诊断等领域， 并取得了一些令人振奋的成果。 但它在模糊规则的自 动提取及 隶属函数的自 动生成等问题上还需要进一步的研究。 人工神经网络 人工神经网络系统是由大量简单的处理单元， 即神经元广泛的连接而形成的 复杂网络系统。在人工神经网络中，计算是通过数据在网络中的流动来完成的。 在数据的流动过程中， 每个神经元从与其连接的神经元处接收输入数据， 对其进 行处理以后，再将结果以输出数据流的形式传送到与其连接的其他神经元中去。 算法不断的调整网络的结构和神经元之间的连接权值， 一直到神经网络产生所需 要的输出为止。 通过这个学习过程， 人工神经网络可以不断的从环境中自 动的获 取知识， 并将这些知识以网络结构和连接权值的形式存储于网 络之中。 人工神经网络具有良 好的自 学习、自 适应和自 组织能力， 以 及规模并行、 分 浙江大学硕士学位论文 布式信息存储和处理等特点， 这使得它非常适合处理那些需要同时考虑多个因素 的、 不完整的、不准确的信息处理问题。目 前， 人工神经网络已经受到学术界的 高度重视， 并在众多领域得到了越来越广泛的应用。 但应该看到， 在神经网络的 设计过程中， 对各种参数的设置及网络结构的确定都带有很强的经验性， 无完整 的理论可循， 其规模也远未达到人脑所具有的上百亿个神经元的规模。 而且， 人 工神经网络是基于脑模型的， 它的研究受到脑科学研究的限制， 在没有对人脑的 思维规律和认知过程有一个清楚的了解之前，很难真正实现对人脑的模拟。 进化计算 在几十亿年的进化过程中， 自 然界中的生物体己经形成了一种优化自 身结构 的内在机制， 它们能够不断的从环境中学习， 以 适应不断变化的环境。 对于大多 数生物体而言， 这个过程是通过自 然选择和有性生殖来完成的。自 然选择决定了 群体中哪些个体能够存活并繁殖: 有性生殖保证了后代基因的混合与重组。 进化 计算受这种自 然界进化过程的启发， 它从模拟自 然界的生物进化过程入手， 从基 因的层次探寻人类某些智能行为发展和进化的规律， 以解决智能系统如何从环境 中学习的问题。 进化计算的理论基础是达尔文的进化论， 它是计算机科学和生物 遗传学相互结合渗透而形成的一种新的计算方法。 进化计算对待求解问题本身一无所知，但只要给出了表示方案、适应函数、 遗传算子、 控制参数、 终止准则等内容， 算法就可以按不依赖于问题本身的方式 对未知空间进行有效的搜索，最后找出问题的解。进化算法还具有简单、通用、 稳健性强和适合于并行处理等特点， 及自 组织、自 适应、自 学习等智能特性，己 被成功的应用到那些难以 用传统的方法进行求解的复杂问题之中。 特别是在系统 识别、 故障诊断、 机器学习及神经网络设计等领域， 进化计算己经显示出它的魅 力。 然而， 作为一个新的、 跨学科的研究课题， 进化计算的理论研究还有待进一 步完善， 其中包括基础理论、 编码机制、 控制参数的选择策略、 收敛性分析等等。 1 . 3 多目 标优化研究综述 研究多于一个目 标函数在指定区域上的优化， 又称多目 标优化。 在很多实际 问题中， 例如经济、管理、军事、 科学和工程设计等领域， 衡量一个方案的好坏 往往难以用一个指标来判断，而需要用多个目 标来比较，而这些目标有时是不 浙江人学硕士学位论文 甚协调，甚至是矛盾的。因此有许多学者致力于这方面的 研究。1 8 9 6年法国经 济学家v 帕雷托最早研究不可比较目 标的优化问题，之后，j . 冯 诺伊曼、h .w. 库恩、a . w.塔克尔 、a m旧夫里翁等数学家做了深入的探讨，但是尚未有一个 完全令人满意的定义。多目 标优化的数学模型的一般表达式为: 石( x ) , 几( x) , . . ， 天( x ) g , ( x ) 0 h , ( x ) = 0 i = 1 , 2 , . . . , m i = 1 , 2 . . .p ( 1 . 1 ) 其 中 i , ( x ) , 九 ( x ) , . ., f ( x ) 为 优 化目 标 ， g ; ( x ) 和h j ( x ) 分 别 为 不 等 式 约 束 和 等 式约束。 在上 述多目 标函 数的 优化问 题中 ， 各 个目 标函 数石 ( x ) , 儿 ( x ) ,. . . , 几( x ) 的 优化往往是相互矛盾的， 不能期望它们的极小点重复在一起， 即不能同时达到最 优解; 甚至有时还会产生对立的情况， 即对一个目 标函数是最优点， 对另一个目 标函数却是差点。 这需要在各个目标函数的最优解之间进行协调， 相互之间作出 适当“ 让步， ，以便取得整体最优的方案。而不能像单目 标函数的优化那样，通 过简单比较函数值大小的方法去寻优。 由此可以看出， 多目标函数的优化问题要 比单目 标函数的优化问题复杂的多。 多目 标优化发展至今， 很多学者已 经研究了大量的求解方法， 纵观这些方法， 我们可以把它们归为两类: 一类是化多为少的方法， 基本思想是将多目 标转化为 比 较容易求解的单目 标， 它是一种基于单目 标的多目 标求解方法: 另一类是多个 目 标的平行求解方法，目前此类方法主要是基于计算智能的多目 标求解方法。 下 面对这两种方法分别进行一个简单的介绍。 1 . 3 . 1基于单目标的多目 标求解方法 这类求解方法本着将多目 标转换为单目 标的思想， 将比较难统一的多个目 标 问题， 转化为一个利用现有的优化方法比 较容易求解的单目 标问题， 在很多情况 下取得了 满意的效果。 根据目 标转化的原理不同， 我们又可以分为以 下几种方法。 ( 1 ) 约束法 约束法的基本思想是在多个目 标中选定一个主要目标， 而对其它目 标设定一 个期望值，在要求结果不比此期望值坏的条件下，求主要目标的最优值。 浙江大学硕士学位论文 嗯 f ( x ) , f 2 ( x ) , . . , f ( x ) ) ( m i n ” x e d、 t j 2 ( 尤) s 五( x) f , ., f ( x ) f , ( 1 . 2 ) ( 2 ) 分层序列法 分层序列法的基本思想是: 把多个目 标按其重要程度排序， 先求出第一个目 标的最优解， 再在达到此目标的条件下求第二个目 标的最优解， 依此类推直到最 后一个求解结束即得到最优解。 黔 f ( x ) , f 2 ( x ) ， 一， f c x ) ) ” (1 ) 厂= 黔f (x ) (2 ) f 一 * ed ()槛)s.r,)f l (x ) ( 1 . 3 ) ( 3 ) f = x e d (li= jl , ( x )s j , .i = ),2 , ，。 一 】 几( x) 采用此方法一般都能取得比较满意的最优解，但是该方法也存在一个缺点， 那就是当前面的问题的最优解是唯一的时候，后面的求解就失去意义了。 ( 3 ) 功效系数法 功效系数法的基本思想是对不同类型的目 标函数统一量纲， 分别得到一个功 效系数函数，然后求所有功效系数乘积或者加权的最优解。 m mx e d拭( x ) , 儿 ( x ) , . . , 人 ( x ) 丛猛 (f m,. = f , . . = m in f , ( x ) m d f , ( x ) ( 1 . 4 ) = d , ( x ) = 一 f , ( x ) 一 刀m 。 1 0 ,1 1 1 i = 1 , 2 , . . , n 故原目标函数可以转化为以下目 标函数: m axx ed 县 d f (x ) 或 m axx .d 菩 d 1 (x ) ( 1 . 5 ) ( 4 ) 评价函数法 评价函 数法是一种最常见的多目 标求解方法， 就是用一个评价函 数来集中反 映各不同目 标的重要性等因素， 并极小化此评价函数， 得到问题的最优解。 常见 的有以下几种方法: 理想点法 浙江大学硕 l 学位论文 理想点法的基本思想是: 先找出评价方案的 “ 最优点” 各测点距 “ 最优点”的距离，使距离最小，来求得最优解。 m i n i f , mlx e n几 ( x ) ,. . , f ( x ) ) 位置， 然后通过找出 ( 1 . 6 ) ” 刀= m in f j (x ) j = 1 ,2 ,. ., n 定义评价函数: h ( f (x ) = h (i ,., f ) 一 丫 i :一，( f j (x ) - f j ) 1 ( 1 .7 ) 然 后 求 解 非 线 性 规 划 问 题 : 臀 h ( f ( x ) ) 平方和加权法 平方和加权法体现了通常的“ 自 报公议” 原则， 那些强调各自目 标重要者预 先给出一个尽可能好的估计， 然后 “ 公议” 给出一组表明各目 标性的权系数， 最 后求解非线性规划给出解答。 先设定单目标规划的下界 ( 理想中的最优值) ，即 刀 臀f ; ( x ) j 一 1 ,2 ,., n( 1 .8 ) 定义评价函数: h ( f ( x ) 二 “ ( j 1 ,., f ) 一 y , . , a .j ( f j ( x ) 一 f /o ) z( 1 .9 ) 求 解 非 线 性 规 划 问 题 : 臀 h ( f ( x ) ) ( 1 .1 0 ) 线性加权法 事 先 按 照目 标函 数石 ( x ) , 几 ( x ) , . , 几 ( x ) 的 重 要 程 度 给出 一 组 权 系 数凡， 满 足 凡 : o , j 一 ,2 ,., n ; 艺 :二 ， “ ， 一 ， 再定义评价函数: h ( f ( x ) ) 一 ” ( f ,., f ) 一 i 丸 a j f j ( x ) ( 1 . 1 1 ) 求 解 非 线 性 规 划 问 题 : 臀 h ( f (x ) ( 1 .1 2 ) m in i - m a x ” 法( 极小 极 大 法) 定义评价函数: h ( f ( x ) ) = h ( f . . . . . .f ., ) = nl ax i s ) 5 n 兀( x ) ( 1 . 1 3 ) 求解非线性规划问题: 浙江大学硕士学位论文 m in h ( f (x )x .d) 一 m in x e d 嘿f j ( x ) ) 乘除法 这种方法一般适用于两个目标的优化命题，如: ( 1 . 1 4 ) m m m ax f ( x) 儿( x) 厂( x) 0 , 儿( x) o , xc d ( 1 . 1 5 ) 则定义评价函数h ( f ( x ) ) = f ( x ) / f ( x ) 求解非线性规划问题: 臀 h ( f ( x ) ) 一 m a x f ( x ) l f , ( x )x e d ( 1 . 1 6 ) 以上方法都是基于单目 标的多目 标优化方法， 这些方法已经在很多领域结合 实际问 题取得了很好的应用效果。 但是， 将多目 标转化为单目 标， 一般需要决策 者给出一些相关信息，比如权值， 而且得到的解只有一个， 这个解也只是多目 标 非劣解集中的一个有效解，只是在以当 前的评价函 数为依据的 情况下的最优解。 对于那些无法精确的建立优化问题的数学模型而又要并行的得到多目 标优化的 非劣解集的问题，只能用下面介绍的多目 标法。 1 . 3 . 2基于进化计算的多目 标求解方法 在实际的工程多目 标优化设计中， 其目 标函数往往是非线性、 非凸、 不可微 甚至不连续的， 采用传统的优化技术已 不能解决这类优化设计问题， 研究可靠解 决这类问题的全局优化算法将具有重大意义。 目 前针对此类多目 标优化问题进行 求解的方法，主要采用的是计算智能方法。 计算智能的三个研究领域进化计算、 人工神经网络和模糊系统在多目 标优化 方面均取得了不错的成果，由于篇幅的限制， 本文只针对其中的一个分支， 也是 本文的研究重点一一进化计算在多目 标优化领域的研究做一个介绍。 首先，我们先来看看进化计算的发展历程。上世纪 6 0 年代初，柏林工业大 学的r e c h e n b e r g i .和s c h w e f e l h . p .( 1 9 7 3 ) 在进行 风洞实 验时，由 于设计中 描 述物 体形状的参数难以用传统方法进行优化， 因而利用生物变异的思想来随机改变参 数值， 并取得了较好的效果。 随后他们对这种方法进行了深入的研究， 形成了进 浙江大学硕一 卜 学位论文 化计算的 一个分支， 进化策略( e v o l u t i o n a ry s t r a t e g y , e s ) . 1 9 9 6 年f o g e l l . j . 等 人在设计有限状态机( f i n i t e s t a t e m a c h i n e , f s m) 时提出了 进化规划( e v o l u t i o n a ry p r o g r a m m i n g , e p ) ，他们借助进化的思想对f s m进行优化设计。由 于缺乏一种 通用的编码方案， 人们只能依赖变异而非杂交来产生新的种群， 早期算法收效甚 微。 1 9 7 5 年 美国 密歇根大 学的h o ll a n d j . h .开 创 性巨 著“ a d a p t a t i o n i n n a t u r a l a n d a r tif ic i a l s y s t e m s ”出 版， 遗传 算 法 ( g e n e t ic a lg o r it h m , g a ) 作为 进 化 计 算的 一 个重要分支被提出，交叉取代了变异成为主要的遗传操作。进入9 0 年代，斯坦 福 大 学 的k o z a j . r . 又 提出了 遗 传 程 序 设 计( g e n e t i c p r o g r a m m i n g , g p ) 的 概 念。 “ 程序” 的大小、 形式和结构不是预先能够确定的， 而是在世代演化中动态的变 化。 遗传程序设计的应用潜力已 经受到许多学者的 特别关注。迄今为止， e s , e p , g a和g p构成了e c的四个主要分支，并且呈现相互渗透融合，差别逐渐 缩小之态， 形成了一套较为完整的进化计算理论体系， 其核心是遗传算法的构架。 在这一理论体系之内，还有一些最近发展起来的分支，如蚁群算法 ( a n t a l g o r i t h m , a a ) ( 1 9 9 2 ) ， 粒子群 算法( p a rt i c l e s w a r m a l g o r i t h m , p s o ) ( 1 9 9 5 ) , 鱼群算法 ( f i s h s w a r m a l g o r i t h m, f s a) ( 2 0 0 2 )和菌落算法 ( f o r a g i n g b a c t e r ia ( 2 0 0 2 ) ) 等。 下面将重点介绍一下进化计算的两个代表性算法， 遗传算法和粒子群算法在 多目 标优化问题中的研究现状。 1 . 3 . 2 . ，基于遗传算法的多目 标优化研究综述 遗传算法( g a ) 是模拟遗传选择和自 然淘汰的生物进化过程的计算模型， 是 由m ic h i g a n 大 学h o l l a n d 教授 于1 9 7 5 年 首次 提出 的。 遗 传 算 法是当 前 较为 成 功 的、广泛应用于复杂工程优化的算法之一。g a引进了基因和染色体的概念， 将 问题的有关参数组成一个可行解代码 ( 即染色体) ，同时将大批的染色体 ( 一代 种群) 置于“ 环境”中， 通过适度值函数求出各染色体的适度值， 根据适者生存 的概念进行自 然选择， 适度值高的染色体被保留 并以一定的 概率在下一代得到繁 殖，而适度值低的染色体减少繁殖数量甚至被淘汰。 目前遗传算法用于多目标优化的方法主要可以分为基于 p a r e t o和不基于 p a r e t o 两类 崔逊学，方廷健 ( 2 0 0 2 ) : 前者能够在一次进化过程中 迅速的找到 浙江大学硕 七 学位论文 ( 或近似找到) 多个p a r e t 。 非劣解， 充分发挥了进化算法的群体优势， 这是目 前 主要的使用方法; 后者又可分为目 标函数聚合法和非聚合法， 在某些场合有着独 特的效果。 下面从这两方面介绍一下g a在多目 标优化领域的主要研究成果及其 应用。 1 9 8 5年 s c h a ff e r 第一次提出 用遗传算法处理多目 标优化问 题 s c h a ff e r j .d ( 1 9 8 5 ) ， 他提出的“ 向 量评估 遗传 算法” 是一种非p a r e t 。 方法， 先将群体中 全部个体按子目 标函数的数目 均等分成若干子群体， 对各子群体分配一子目 标函 数， 各子目 标函数在其相应子群体中独立进行选择操作后组成一新的子群体; 将 所有新生成的子群体合并为一完整群体再进行交叉和变异操作。 h a j e l a等人提 出 的“ 可 变目 标 权重聚 合法” h a j e l a p , l i n c .y ( 1 9 9 2 ) 也 是一 种非p a r e t 。 方 法， 使用加权和法， 每个目标赋一权重， 但权重本身并不固定， 问题解和权重同