（控制理论与控制工程专业论文）多目标人工免疫算法及其在无功优化中的应用.pdf

7 一0j - t at h e s i si nc o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g m u l t i o b j e c t i v ea r t i f i c i a li m m u n ea l g o r i t h ma n d i t s a p p l i c a t i o n si nr e a c t i v ep o w e ro p t i m i z a t i o n b yw a n gx i a o l e i s u p e r v i s o r ：p r o f e s s o rg a o x i a n w e n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 1 k l 1 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二匕 思。 学位论文作者签名：羔疑磊 日 期：娜罗，7 可 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 两年口 签名扒 日期：20 08 7 孑 u l ， ， 0 ，则与其强1 1 1 关的节点构成全系统稳定程度最差或 最易发生不稳定的区域。 显然在这些点上进行无功补偿能够有效地增加九i 。的值，从而使系统能够最快达到 稳定。 2 3 2 多目标无功优化模型 ( 1 ) 目标函数 无功优化的目标函数考虑以下i 种： 1 ) 有功网损 从经济性方面考虑，最经常采用的目标是有功网损最小： m i n p , = q ( 2 + - 2 v , c o s 吃) ( 2 8 ) 式中虬为所有节点号集；p ，、e ，一节点f 利+ 诲点之间的电导、电纳；岛一节点 i 和，之间的相角差；表示节点i 的咆压； 2 ) 节点电压水平 节点电压值是系统安全性和电能质量的重要指标之一。在以往的无功优化计算中， 往往是把电压幅值当作约束条件。这样做通常会使优化后电压幅值靠近其上限值。因此， 本文选择电压与指定电压的偏差作为目标函数之，求使电压保持在满意的水平上，可 表示为如下形式： 面删= 善 磋 亿9 ， 式中为节点i 的电压幅值；+ 为节点f 的期望电压幅值，通常巧= ( 杉一+ 巧曲) 2 ； k 麟表示在节点f 上允许的最大电j k 偏差，即a v , m 找= 。“一i n i n ；帆为系统的负荷节 点数。 3 ) 系统电压稳定性 电压稳定裕度旯是从一个潮流解的变量和参数米计算的电压稳定性指标。因此，将 最小的电压稳定指标旯作为目标函数之一，以使系统的电压稳定裕度最大，即： 一1 2 一 东北大学硕士学位论文 第2 章无功优化数学模型的建立 ： m a x ) = 九1 j n( 2 t o ) ( 2 ) 等式约束条件 等式约束条件，即潮流约束方程： 节点有功功率约束 尼，= 易，+ 巧( qc o s 0 , j + 岛s i n o v ) ( 2 1 1 ) j n | 节点无功功率约束 q g ，+ q ( ，= q 伪+ ( q s i n0 , j 一岛c o s o , , ) ( 2 1 2 ) j n 。 ( 3 ) 不等式约束 发电机节点电压约束 ，m 。圪，吃，m 。，f _ l ，g ( 2 1 3 ) 变压器分接头位置变化范围约束 。i 。k n k 7 ) 。，f = l ， 0( 2 1 4 ) 无功补偿即无功装设容量的约束 q t m i 。q ，q 一，待1 ，n c ( 2 1 5 ) 负荷节点电压安全约束 圪，。i 。圪，。“，f = 1 ，2 ( 2 1 6 ) 发电机节点无功范围约束 q f 记。i 。q ，线m 馘，i = 1 ，g ( 2 1 7 ) 式( 2 8 ) 到( 2 1 7 ) 中，为的系统有功网损，圪和姥，分别为节点f 处发电机的 有功功率和无功功率，和q d ，分别为节点i 处所带负荷的有功功率和无功功率，q ，、 e ，和岛分别为节点f 和j 之间的电导、电纳和相角差，表示节点i 的电压，n s 为所有 节点号集，m 为系统的负荷节点数，为与节点i 相连的节点集，g 、c 、坼和m 分别为系统中发电机数、无功补偿节点数、有载调压变压器数和负荷节点数。 【q 砗】r 为发电机端电压、无功补偿量和变压器变比，是无功优化问题的控制变 量，其约束可以通过设定控制变量的边界自动满足；【圪q 】r 为负载节点电压和发电 机无功出力，是无功优化问题的状态变量。 ( 4 ) 综合考虑经济性和安全性的电力系统多目标无功优化模型可表示为： m i n f ，五，石】= m i n p l ( x , ，而) ，a v ( x l ，恐) ，一丸i 。( 五，恐) 】 s 2 h ( x t ，x 2 ) = 0 ( 2 1 8 ) g ( 五，x 2 ) 0 式中，办( 一，j c 2 ) = 0 是等式约束；g ( 五，x o 0 是不等式约束：五是控制变量向量，包 一13 东北大学硕士学位论文第2 章无功优化数学模型的建立 括发电机端电压、无功补偿量q ( ，和变压器变比畅，可表示为： 葛= 【v g i ，q c , 鲰，k m 】 ( 2 1 9 ) 屯是状态变量，包括负荷节点电压吃和发电机的无功出力珑，可表示为： x f = ，骁级；】 ( 2 2 0 ) 2 4 本章小结 本章首先对电力系统的无功优化进行了简单的介绍，对无功优化的模型进行了分析 研究，在经典的单目标优化模型的基础上，综合考虑系统的安全性、经济性和运行约束 条件，提出了一种更为全面、实用的多目标无功优化模型。模型中同时考虑了网损、电 压水平以及电压稳定性指标。考虑电压稳定指标的多目标无功优化模型可以综合优化系 统的经济效益和安全效益。 一1 4 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 第3 章人工免疫算法的基本原理和模型 从生物学诞生起，人们就对生物界有着浓厚的兴趣，从2 0 世纪中叶开始，人们就 已经开始注意到生物系统功能及结构的模仿，由此产生了许多新的研究领域。例如，人 工神经网络、模糊控制等各种进化算法。 生物免疫系统是一个复杂的自适应系统，其复杂程度堪与大脑相比较，有“第二大 脑之称。免疫系统能够识别出病原体，具有学习、记忆和模式识别能力，因此可以研 究借鉴其信息处理机制来解决工程和科学问题，由此诞生了基于免疫原理的智能方法研 究这一有意义的新的研究方向。人工免疫算法( a r t i f i c i a li m m u r l ea l g o r i t h m ，a i a ) 正 是基于生物免疫系统识别外部病原体并产生抗体对抗病原体的学习机制而提出的。 3 1 人工免疫系统的生物学基础 3 1 1 生物免疫系统的组成和功能 人工免疫算法是在免疫学尤其是理论免疫学的基础上发展起来的，因此离不开对生 物免疫系统的理解和研究，也与免疫学的发展密不可分 3 2 】。 3 1 1 1 免疫学的一些相关概念 免疫：生命体受到外来病毒或分子刺激后所产生的一系列复杂变化。免疫的作用是 识别和排除非已物质，以维持机体的生理平衡。正常情况，免疫应答的结果对机体有利， 起到免疫保护、免疫稳定和免疫监视等生理性保护作用。 抗原( a n t i g e n ，a g ) ：通常指外来感染性病毒物质或分子，以及胚胎期末在与免疫 系统接触中发生改变的自身物质，即自身抗原。 b 细胞：产生于骨髓并在骨髓中发育成熟的淋巴细胞。b 细胞经由激活，分化为多 个血浆细胞，每一浆细胞能分泌多个相同类型的免疫球蛋白，b 细胞的作用是产生抗体， 并对入侵抗原作出应答。 抗体( a n t i b o d y ，a b ) ：b 细胞接受抗原刺激后，所分泌的具有免疫功能，并能与 抗原发生特异性结合的免疫球蛋白。抗体的作用在于识别和清除抗原。 t 细胞：骨髓中分泌的部分淋巴液被分配到胸腺，这些淋巴液在胸腺中发育成熟后 则为t 细胞。t 细胞的作用在于调整其它细胞的行为和袭击体内的感染性细胞。 免疫记忆：免疫系统的一个重要特征是好交往性，其不仅能记忆已出现抗原的结构， 而且对相同抗原的再次入侵或相似抗原的出现作出快速反应，能成功地毁灭被识别的抗 原。免疫记忆是免疫系统的重要特征，有助于加快再次免疫应答过程。 亲和力( a f f i n i t y ) ：抗体的表位与抗原的对位的匹配程度。 一1 5 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 3 1 1 2 免疫系统的组成 免疫系统是一种由众多细胞、分子和组织等子系统构成的复杂系统，这些子系统之 间存在着复杂的相互联系，具有能识别“自己”和“非己 ，清除和消灭异物的功能。 免疫系统的构成要素如图3 1 所示。 免疫系统 免疫器官f 中枢免疫器官 妻薰囊 免疫细胞 外周免疫器官 免疫活性叫鬻塞一 第三群细叫船粤 免疫叫畿罢胞 f 抗体 免疫分子 补体 【单核及淋巴因子 图3 1 免疫系统的组成 f i g 3 1e l e m e n t so ft h ei l l l m b n es y s t e m 3 1 2 免疫应答过程及原理分析 病原体进入机体后，免疫细胞对病原体分子的识别、活化、分化和效应过程，称为 免疫应答( i n l m b l l er e s p o n s e ) 。 3 1 2 1 免疫应答的分类 免疫应答中的两种类型免疫系统有两种免疫应答类型：固有免疫应答( i n n a t e i n l l n l 1 n er e s p o n s e ) 和适应免疫应答( a d a p t i v eh l l i i l l l n er e s p o n s e ) ： ( 1 ) 固有免疫应答又称非特异性免疫应答( n o n s p e c i f i ci i t l m h n er e s p o n s e ) ：对所 有侵入人体的细菌和病毒都有积极而快速的防卫作用，其执行机构有：皮肤、粘膜的阻 挡作用和局部细胞分泌的杀菌物质的化学作用；吞噬细胞吞噬病原体的作用；自然杀伤 ( n a t u r a lk i l l e r ，n k ) 细胞对感染病毒细胞的杀伤作用等等。固有性免疫响应的特点是 直接性、快速性和广谱性。 ( 2 ) 适应免疫应答又称特异性免疫应答( s p e c i f i ci m _ r n u n er e s p o n s e ) ：免疫系统只 对特定的一种或几种异物产生强烈而有效的响应，人体内执行特异性免疫应答的物质是 t 淋巴细胞和b 淋巴细胞以及它们产生的抗体等各种分子。适应性免疫应答最主要的特 点是特异性和实用性。在适应性免疫应答中进行适应地学习以识别特异抗原，并对其保 持记忆，以便下次快速做出应答。 一】6 一 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 3 1 2 2 适应免疫应答的过程 适应免疫应答的过程分为以下几个阶段： ( 1 ) 抗原提呈：进入机体的抗原经过抗原处理后展示给t 细胞，并与t 细胞受体 结合，此过程是几乎所有淋巴细胞活化的必需步骤； ( 2 ) 特异识别：免疫细胞( 主要是b 细胞) 与抗原的亲和度识别； ( 3 ) 细胞活化、分化：与抗原亲和度达到一定程度的b 细胞将被活化，产生抗体； ( 4 ) 适应学习：b 细胞在辅助t 细胞和抑制t 细胞的作用下进行适应学习，逐渐 得到与抗原亲和度更高的b 细胞，由其产生抗体对抗抗原。适应学习过程中产生新的b 细胞需要经过一个耐受过程，而适应学习的基本原理是克隆选择原理。 3 1 2 3 免疫应答原理 解释适应性免疫应答过程的代表性原理是奥地利免疫学家伯内特( n k b u m e t ) 于 1 9 5 7 年提出的细胞克隆选择学说，以及著名的美国免疫学家耶纳( n k j e n n e r ) 于1 9 7 4 年提出的独特型免疫网络假说。 ( 1 ) 克隆选择原理 克隆选择原理【4 6 1 1 4 7 】的基本思想是只有那些能够识别抗原的细胞才能被免疫系统选 择保留下来，并进行扩增，而那些不能识别抗原的细胞则不被选择，也不进行扩增。克 隆选择原理如图3 2 所示。 克隆选择原理包含着免疫细胞应答抗原的几种机理，即应答抗原能力强的免疫细胞 被确定性地选择进行应答，在此称为克隆选择；被选择进行应答的免疫细胞依据其应答 抗原能力强弱，繁殖一定数目的克隆细胞，免疫细胞繁殖克隆的数目与其亲和力成正比， 这种机制称为细胞克隆；部分克隆细胞变为记忆细胞或长寿细胞，被保存于免疫系统中 并更新已有的低亲和力记忆细胞，在此称为记忆细胞获取；记忆细胞产生免疫记忆，即 能记忆已入侵的抗原的模式，其作用在于对同一抗原再次出现或相似抗原的出现作出快 速反应；克隆细胞在其母体的亲和力影响下，按照与亲和力成反比的概率对抗体的基因 多次重复随机突变及基因块重组，进而产生种类繁多的免疫细胞，并获得大量识别抗原 能力比母体强的b 细胞，这些识别抗原能力较强的细胞能有效缠住入侵的抗原，这种 现象称为亲和成熟。通过这种机制来保持在以后应答中产生高亲和度的抗体。 一1 7 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 _ 夕岔耄蓉三蓉 勰秽岔 芝否 日 匕专 记忆细胞 浆细胞 图3 2 克隆选择原理 f i g 3 2c l o n a ls e l e c t i o np r i n c i p l e ( 2 ) 独特型免疫网络原理 在免疫系统中，通过抗原的对位与抗体的表位以及抗体之间的表位与对位进行识别 与被识别，抗体不仅识别抗原，同时又识别其它抗体和被其它抗体识别，因此抗体具有 识别和被识别的特性( 二重性) 。抗体表面的表位又称为独特位或独特型( i d i o t y p e ) 抗原 决定基，其作用在于被其它抗体识别。通过抗体表面的受体，即对位p a r a t o p e ，抗体识 别抗原，抗体与抗体之间相互识别和被识别，并形成了独特型免疫网络，如图3 - 3 。 s t i m u l a t i o n i d i o 图3 3 独特型免疫网络原理 f i g 3 3p r i n c i p l eo f t h ei d i o t y p ei m m u n en e t w o r k 在此网络中，被识别的抗体受到抑制，识别抗原及其它抗体的抗体得到促进和增殖， 这种机制便构成了独特型免疫网络调节。这独特型免疫网络原理主要包含两种抗体作用 机制，即克隆抑制及抗体的动态平衡维持( 简称为动态平衡维持) 。 从免疫网络理论描述获知，其包含的两种机制在免疫网络中起重要作用，克隆抑制 一1 8 一 墨芦 l r j 、， 一9一 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 能缩小抗体群的规模，促成抗体进化的作用，使得高亲和力或识别其它抗体能力强的抗 体得到保存。动态平衡维持使免疫系统中抗体的总数目获得控制，同时多种抗体的数目 达到平衡，相似或相同抗体出现的数目较少以及自我抗体的出现增强了免疫网络的动态 平衡，这两种机制在免疫应答中起到调节免疫细胞群的作用。 3 2 人工免疫算法理论 3 2 1 人工免疫算法的概述 人工免疫算法是模拟生物免疫系统智能行为而提出的仿生算法，它是一种确定性和 随机性选择相结合并具有勘测与开采能力的启发式随机搜索算法【4 引。人工免疫算法正是 对生物免疫系统机理抽象而得的，算法中的许多概念和算子与免疫系统中的概念和免疫 机理存在着对应关系。人工免疫算法与生物免疫系统的对应关系如表3 2 、3 3 所示。 表3 2 免疫系统概念与人工免疫算法的对应关系 t a b l e3 2i m m u n es y s t e mc o n c e p t sc o r r e s p o n d st oa 从 免疫系统概念人工免疫算法概念 抗原优化问题( 最优解) 抗体( b 细胞)优化问题的可行解 亲和度可行解质量 表3 3 免疫系统机理与人工免疫算法的对应关系 ! 生! 曼! ：! 堕堕竖墨曼墨z 兰笙里璺曼呈垒塑i ! 里墨里里墅堕翌旦翌坐塑垒坠 免疫系统人工免疫算法 根据上述的对应关系，模拟生物免疫应答的过程形成了用于优化计算的人工免疫算 法。算法主要包含以下几大模块： ( 1 ) 抗原识别与初始抗体产生：根据待优化问题的特点设计合适的抗体编码规则， 并在此编码规则下利用问题的先验知识产生初始抗体种群； ( 2 ) 抗体评价：对抗体的质量进行评价，评价准则主要为抗体亲和度和个体浓度， 评价得出的优质抗体将进行进化操作，劣质抗体将会被更新； ( 3 ) 克隆选择：利用免疫选择、克隆、变异、克隆抑制、种群刷新等算子模拟生 一】9 一 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 物免疫应答中的各种免疫操作，形成基于生物免疫系统克隆选择原理的进化规则和方 法，实现对各种最优化问题的寻优搜索。 一 人工免疫算法是模拟生物免疫系统功能和原理来解决复杂问题的自适应智能系统， 它保留了生物免疫系统所具有的若干特点，包括【4 9 5 1 】： ( 1 ) 全局搜索能力：人工免疫算法同样是一个具有全局搜索能力的优化算法，算 法在对优质抗体邻域进行局部搜索的同时利用变异算子和种群刷新算子不断产生新个 体，探索可行解区间的新区域，保证算法在完整的可行解区间进行搜索，具有全局收敛 性能。 ( 2 ) 多样性保持机制：人工免疫算法借鉴了生物免疫系统的多样性保持机制，对 抗体进行浓度计算，并将浓度计算的结果作为评价抗体个体优劣的一个重要因素，使浓 度高的抗体被抑制，保证抗体种群具有很好的多样性，这也是保证算法全局收敛性能的 一个重要原因。 ( 3 ) 鲁棒性强：人工免疫算法不针对特定问题，而且不强调算法参数设置和初始 解的质量，利用其启发式的智能搜索机制，即使起步于劣质解种群，最终也可以搜索到 问题的全局最优解，对问题和初始解的依赖性不强，具有很强的适应性和鲁棒性。 ( 4 ) 并行分布式搜索机制：人工免疫算法也可以实现并行处理。而且，人工免疫 算法的优化进程是一种多进程的并行优化，在探求问题最优解的同时可以得到问题的多 个次优解，即除找到问题的最佳解决方案外，还会得到若干较好的备选方案。 3 2 2 人工免疫算法的算子设计 与g a 等其他智能优化算法类似，人工免疫算法的进化寻优过程也要依靠算子来实 现。人工免疫算法的算子包括：亲和度评价算子、个体浓度评价算子、免疫选择算子、 克隆( 个体增殖) 算子、变异算子、克隆抑制算子和种群刷新算子。 定义3 1 亲和度评价算子亲和度是指抗体与抗原的匹配强度。反应在优化问题上， 亲和度评价算子通常是一个函数a f f ( x ) ：s 一 0 ，1 ，a f f ( x ) 与f o c ) 成反比，其中s 为问题 的可行解区间。 通常函数优化问题可以用函数值或对函数值的简单处理( 如取倒数、相反数等) 作 为亲和度评价，而对于组合优化问题或应用中更为复杂的优化问题，则需要具体问题具 体分析。 定义3 2 抗体浓度评价算子抗体浓度( d e n ( x ) ：s 专 o ，1 】) 是指抗体在种群中与其相 似抗体所占的比例，它表征抗体种群的多样性好坏，抗体浓度过高意味着种群中非常类 似的个体大量存在，则寻优搜索会集中于可行解区间的一个区域，不利于全局优化。因 此优化算法中应对浓度过高的个体进行抑制，保证个体的多样性。 一2 0 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 抗体浓度通常定义为在一定领域内，与其相似抗体的比例，可表示为【5 2 】： d e n ( 口6 f ) = 专萎s ( 口包，呜) ( 3 1 ) 其中s ( a b , ，动，) 表示抗体间的相似度，其可表示为： 躐圳= f ：i ，淼高三三 2 ， 其中吒为相似度阂值，n 为抗体数量；口色为种群中的第i 个抗体；a f f ( a b , ，a b j ) 为 抗体i 与抗体，的亲和度。对于实数编码的算法，抗体抗体亲和度通常可以通过抗体向 量之间的欧氏距离( e u c l i d e a nd i s t a n c e ) 来计算： e 了一 ，a f t ( 口包，呜) = 、( 口龟厂呜 ) 2 ( 3 3 ) 式中a b , 丘和鸩丘分别为抗体珀勺第k 维和抗体，的第k 维，为抗体编码总维数a 定义3 3 免疫选择算子免疫选择算子( 乃：s 寸s ) 是指在给定的选择率口( 0 口 1 ) 下，选择抗体群中坼= r o u n d ( a 1 p 1 ) ( 1 p i 代表种群个数) 个亲和度较高的抗体进入克隆 选择操作。 免疫选择算子可以描述为： ) = ：；，茹i m ( a b 咖) ； ( 3 4 ) 其中z 为坼个激励度较高的个体组成的种群。 定义3 4 克隆算子克隆算子( t c ：s 专s ) 将免疫选择算子选中的抗体进行复制。 克隆算子可以描述为： 乏( 口6 j ) = c l o n e ( a b i ) ( 3 5 ) 式中c l o n e ( a b ，) 为个与驰相同的克隆构成的集合；为抗体克隆数目，也可采用 自适应克隆选择。 定义3 5 变异算子变异算子( t m ：s 专s ) 对克隆算子得到的抗体克隆结果进行变 异操作，以产生亲和度突变，实现局部搜索。实数编码算法变异算子通常采用的是高斯 变异： 口2 5 l = a b , + 元( o ，1 ) x e x p ( - a f f , ) ( 3 6 ) 其中，口巧为变异后的抗体，驰为变异前的抗体；n ( 0 ，1 ) 是均值为0 ，方差为1 的 正态分布随机数；五为比例系数，用于控制变异的衰减程度；够为a f t , 的0 - l 标准化。 定义3 6 克隆抑制算子克隆抑制算子( t r ：s 专s ) 对经过变异后的克隆体进行再 一2 1 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 选择，抑制亲和度低的抗体，保留亲和度高的抗体进入新的抗体种群，并且对相似度高 的抗体也要进行抑制。 。 克隆抑制算子可以描述为：当两抗体之间的相似度大于克隆抑制阈值最时( 一般取 其与相似度阈值仃。相等) ，删除其中适应度较低的抗体，保留适应度高的抗体。 克隆抑制算子体现了人工免疫算法的算子中的很好的多样性保持机制。 定义3 7 种群刷新算子种群刷新算子( t d ：s - - h s ) 是指删除种群中亲和度较低的 虬= r o u n d ( f 1 ipi ) 个抗体，并以随机生成的新抗体替代，从而很好的保持抗体的多样性， 避免陷入局部最优解。 3 2 3 人工免疫算法基本流程和步骤 利用流程图描述的人工免疫算法工作原理如图3 4 所示。 、 图3 4 人工免疫算法基本流程 f i g 3 4b a s i cf l o wc h a r ts h o w i n gt h ea i a 其算法步骤如下所示： ( 1 ) 抗原识别：算法首先进行抗原识别，即理解待优化的问题，提取先验知识： ( 2 ) 产生初始抗体：随机产生一个种群规模为的初始种群； ( 3 ) 适应度评价：计算抗体对抗原的亲和力，以及抗体和抗体之间的亲和力，对 - - 2 2 _ 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 种群中的每一个可行解进行适应度评价； ( 4 ) 计算抗体浓度：抗体的浓度主要用于保持群体的多样性； ( 5 ) 免疫处理：主要有免疫选择、克隆、变异和克隆抑制： a ) 免疫选择：根据种群中抗体的亲和度和浓度计算结果选择优质抗体； b ) 克隆：对免疫选择的抗体进行克隆复制，得到若干副本； c ) 变异：对克隆得到的副本进行变异操作，使其发生亲和度突变； d ) 克隆抑制：对变异结果进行再选择，抑制亲和度低的抗体，保留亲和度高 的变异结果； ( 6 ) 种群刷新，以随机生成的新抗体替代种群中亲和度较低的抗体，形成新一代 抗体，转( 3 ) ； ( 7 ) 判断是否满足算法终止条件，如果满足条件则终止算法寻优过程，输出计算 结果；否则继续寻优运算。 3 2 4 算法的参数分析 从算法的实现可以总结出算法的控制参数有： ( 1 ) 抗体种群大小。抗体种群保留了免疫细胞的多样性，从直观上看，种群越 大，人工免疫算法的全局搜索能力越好，但是算法每代的计算量也相应增大。在大多数 问题中，取3 0 1 0 0 较为合适，一般不超过2 0 0 。 ( 2 ) 免疫选择比例倪。免疫选择的抗体的数量越多，将产生更多的克隆，其搜索 能力越强，但是将大大增加每代的计算量。可以取抗体种群大小的1 0 2 0 ，一般 不要超过3 0 。 ( 3 ) 抗体克隆扩增的倍数。克隆的倍数，决定了克隆扩增的细胞的数量，从而决 定了算法的搜索能力，主要是局部搜索能力。其数值越大，局部搜索能力越好，全局搜 索能力也有一定提高，但是计算量越大。一般取5 1 0 倍。 ( 4 ) 变异比例系数兄。变异率是影响算法收敛性能的重要参数，我们算法主要利 用了其局部搜索能力，实际上变异也会产生脱离局部极小点的效果。一般取0 0 l 1 。 ( 5 ) 克隆抑制阈值坑。抗体数量的多少可由鼠来调节，当区较小时，相似抗体相 应增多，可得到更多的解，但同时每次迭代过程中群体的尺寸相应增大，每代运算时间 延长；而当坑较大时，相似抗体之间的抑制作用加强，抗体的数量减少，缺乏多样性从 而产生早熟现象，般尻取0 0 0 1 0 2 。 ( 6 ) 种群刷新比例。细胞的淘汰和更新是产生抗体多样性的重要机制，因而对 免疫算法的全局搜索能力产生重要影响。每代更新的抗体一般不超过抗体种群的4 0 。 一2 3 东北大学硕士学位论文 第3 章人工免疫算法的基本原理和模型 3 3 人工免疫算法的收敛性测试 为了验证算法在不同情况下的收敛性能，选择一些具有不同类型的测试函数进行函 数收敛性测试。 ( 1 ) 多峰函数： 0 l 芦2 ) = x l s i n ( 4 n x l ) 2o s i n ( 4 n x l + 万) + 1 ，( - 1 x l 芦2 1 ) ( 3 7 ) 这是一个常用于算法检测的多峰一维函数。在给定范围内，它有多个局部极大值。 ( 2 ) r o s e n b r o c k 函数： f 2 l 芦2 ) - 1 0 0 ( x ；x2 ) 2 + ( 1 石1 ) 2 ，( 一2 0 4 8 x l 2 2 0 4 8 ) ( 3 8 ) 这是一个二维函数，它具有一个全局极小点f ( 1 ，1 ) = 0 。该函数虽然是单峰值的函数， 但它却是病态的，难以进行全局极小化。 ( 3 ) c a s t r o 函数： f3(x,x0=05一宇睾踹，c一。x。歹：t。，c3功 该函数是检测各种搜索优化算法的经典的复杂困难函数。该函数在全局范围内的最 大值为1 ，位于最中心的圈脊。在全局最大值附近有多个圈脊，因此函数有无限个局部 极大值，且极大值与全局最大值非常接近，这就要求算法具有较强的跳出局部最优的能 力。 对以上函数分别用遗传算法( g a ) 、微粒群算法( p s o ) 和人工免疫算法( a i a ) 进行优化仿真测试。仿真中各算法的公共参数设置相同，初始种群规模为5 0 ，迭代次数 为1 0 0 ，交叉概率为0 9 ，变异概率为0 0 5 ，f 1 = c 2 = 1 4 9 4 ，克隆选择比例为o 2 ，变异 比例系数兄= o 1 ，克隆数目为1 0 ，抑制阈值o 0 l ，刷新概率为0 2 。仿真结果如表3 铷3 6 所示。 成功次数( n u m b e ro f s u c c e s s ) ：对于测试函数厂1 ，目标值为2 2 5 9 9 8 ，当一次计算 得到最优值大于2 2 5 8 即认为成功，否则认为失败；对于r o s e n b r o c k 函数，目标值为o ， 当一次计算得到最优值小于0 0 0 1 即认为成功，否则认为失败；对于c a s t r o 函数，目标 值为1 ，设定的成功界限为0 9 7 。 表3 4 a 函数仿真结果对比 t a b l e3 c o m p a r i s i o no fs i m u l a t i o nr e s u l t so f f u n c t i o n f j 一 算法测试次数成功次数最优值最差值平均最优值 一2 4 东北大学硕士学位论文第3 章人工免疫算法的基本原理和模型 表3 5r o s e n b r o c k 函数仿真结果对比 算法测试次数成功次数最优值最差值平均最优值 表3 6c a s t r o 函数仿真结果对比 算法测试次数成功次数最优值最差值平均最优值 由测试结果可以看出，标准g a 算法在处理多峰函数等复杂问题时，寻优搜索的寻 优成功次数很少，而且得到的最优解精度也远远低于其他两种算法；p s o 算法在测试中 表现出最好的收敛速度，但算法成功率也不太高，而且p s o 算法对初始种群有很强的 依赖性，容易陷入局部最优解；a l 在寻优中表现出很强的能力，在保持很高的成功率 的同时，也达到了很好的寻优精度。 3 4 本章小结 本章介绍了生物免疫系统组成、免疫应答过程，根据并对人工免疫算法的概念、算 法流程图和算法特点进行了详细介绍。并且分析了人工免疫算法相对于其他进化算法的 优势，通过函数测试对算法的优化性能进行了验证，仿真结果表明人工免疫算法具有很 强的优化能力，不易陷入局部最优值，而且有很高的收敛精度。因此人工免疫算法具有 很好的研究和应用价值。 一2 5 东北大学硕士学位论文笫3 章人工免疫算法的基本原理和模型 东北大学硕士学位论文 第4 章改进的多目标人工免疫优化算法 第4 章改进的多目标人工免疫优化算法 近年来，进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 在求解多目标优化问题方面已取 得很大进展，它之所以被广泛地用于求解多目标优化问题是由于其群体搜索性，在一次 迭代过程中有可能获得多目标优化问题的多个解。用进化算法求解多目标优化问题时， 希望最后所得的“最优解”收敛到最优解集中的每一个解，故需要综合考虑以下问题： ( 1 ) 如何评价并保存p a r e t o 最优解； ( 2 ) 如何设计适合于多目标优化问题的选择算子、交叉算子、变异算子等问题； ( 3 ) 如何能在较长时间内维持群体的多样性； ( 4 ) 如何保留最优个体及进行个体的更新； 人工免疫算法在优化方面表现出了很多的优势，近年来，人工免疫算法已成为解决 优化问题的一个重要工具【5 3 】【5 4 1 ，但将其应用于多目标优化的研究还并成熟，因此还有许 多的工作要做。 4 1 多目标优化的基本概念 4 1 1 多目标优化问题数学描述 一般的多目标优化( m u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e m ，m o p ) 函数和相关的一些等式和不等式约束组成，数学上可作如下描述【5 5 】： m i nf ( x ) = ( 石( x ) ，正( x ) ，五( x ) ) j j g f ( x ) o ，f = l ，2 ，p h i ( x ) = 0 ，j = 1 ，2 ，q 问题由一组目标 ( 4 1 ) 其中，x = k ，x 2 ，吒】7 是r ”空间的聍维向量，称x 所在的空间d 为问题的决策空 间，z ) ( f = 1 ，2 ，k ) 为第f 个子目标函数，k 维向量( z o ) ，以( x ) ，以( x ) ) 所在的空i 日j 称为问题的目标空间，蜀( x ) 为第f 个不等式约束，办，( x ) 为第- ，个等式约束。为了不失 一般性，这里我们考虑的是最小化问题，对于最大化或混合的最大最小问题有相似定义。 4 1 2p a r e t o 解集的概念 在单目标优化中问题的最优解己具有明确的定义，不同于单目标优化问题的最优解 概念，多目标优化问题不存在唯一的全局最优解，而是存在一个最优解集合，其特点为 至少存在一个目标优于其他所有的解，一般称为p a r e t o 最优解( p a r e t oo p t i m a ls o l u t i o n s ) ， 非劣最优解或非支配最优解( n o n i n f e r i o rs o l u t i o n s 或n o n d o m i n a t e ds o l u t i o n s ) 。 法国经济学家v p a r e t o ( 1 8 4 8 1 9 2 3 ) 最早研究了经济学领域内的多目标优化问题， 一2 7 东北大学硕士学位论文第4 章改进的多目标人工免疫优化算法 并提出了p a r e t o 解集的概念【5 6 1 。 定义4 1 决策空间上的可行解集 集合d = xlx r “，蜀( x ) 0 ，红( x ) = o ，f 1 ，2 ，p ，= 1 ，2 ，q 称为式( 4 1 ) 在决策 空间上的可行解。 定义4 2 目标空间上的可行解集 集合f = ( 石，以，五) r lz = z ( x ) ，f - 1 ，2 ，k ，x d 称为式( 4 1 ) 在目标空间 上的可行解。 定义4 3p a r e t o 最优解 对于x + d ，若不存在觇d ，满足下列条件： n ( z ( x ) z ( x ) ) ( 4 2 ) t e l 其中，= 1 ，2 ，k ) ，k 为目标函数的个数。 且至少存在一个，i ，使： 一( x ) 正( x ) ( 4 3 ) 则称x 为p a r e t o 最优解( p a r e t oo p t i m a ls o l u t i o n ) 。