多目标优化的进化优化算法

科技信息O科教前沿0SCIENCE & TECHNOLOGY INFORMATION2008年第23 期多目标优化的进化优化算法Evolutionary Algorithms for Multi- -objective Optimization张一倩12(1.山东大学计算机学院山东济南250014;2.济 南职业学院计算机系山东济南250103).[摘要]进化优化算法具有全局优化能力, 可以一次性求解多个非劣解。近年来,此类方法已经成为求解多目标优化问题一个重要的研究方向。本文分析了进化优化算法的关键步朦,介绍了几种代表性的多目标进化优化算法,并指出了值得进一步研究的相关问题。[关键词]多目标优化;进化优化算法;非劣解1.概述表示。根据向量元素的不同可以分为实数编码、十进制编码和二进制传统的单目标优化理论和算法经过几十年的发展和完善,在实践编码等。 编码的本质是将现实问题的解空间与编码空间相对应起来。中逐渐获得了广泛应用。但很多实际问题往往涉及多个目标和约束，前者 与生物体的表现型相对应，如组织器官的生理形态和生物的习不同目标之间难以进行客观公平的比较，且各目标密切关联、相互制性等;后者则对应于生物体的基因型.即底层的基因编码。理想的编码约甚至彼此矛盾。因此对于此类单目标优化模型难以解决的问题，有方案 是保证可行解与编码--对应。 一个解对应多种编码,将导致编必要建立多目标优化模型予以全面考虑。码空间的重叠,降低优化计算的效率。而多种解对应于一个编码,则会多目标优化问题最显著的特点之--是其最优解通常不是唯-的，使编码的解释陷人混乱和低效，是衢要尽可能避免的情况。而是一个集合。 该集合中的每个元素称为非劣解或pareto解"。非劣解进化策略足对现有个体的编码进行修改，从而得到新个体的操的含义是:不存在比其中至少一个目标更好而其它目标不劣的解,也作。 常见的进化策略包括交叉、变异。交叉操作模拟了生物界中普遍存就是不可能使该解的部分目标优化而其它目标不至变劣。因此在理论在的有性繁殖。 由于在有性繁殖中双亲的遗传基因发生了分割和交研究中,通常希望算法能够在非劣解集中找到尽可能多的.分布均匀换 ,通过基因信息的交换可以实现新的基因组合,极大的丰富了基因解。的多样性。传统的加权求和法可以将多个目标进行折算,但得到的非劣解数变异操作模拟了遗传变异,包括基因突变、染色体突变和苇因重量有限，且对权重值的确定有较大主观性。组三种分子水平的突变。适当的变异叮以给生物体带来有利的调整，进化优化算法是一-类求解优化问题的有效方法.在单目标优化问并能够随 着环境的变化面变化。题中得到了迅速的发展。随着进化优化算法的深入研究,提出了多种选择策略包括个体评价和个体选择两部分。个体评价即对群体中多目标进化优化算法，,具有-次性求取多个非劣解的能力。本文对具的每个个体的优劣 进行评价。在单目标优化问题中,个体的评价比较有代表性的算法进行了介绍和比较,并提出了多目标进化优化算法研简单,一 般采用目标函数即可。而多目标优化问题沙及到多个不同的究中需要深人思芍的问题。目标,各非劣解的评价和比较难以直接实现，是研究重点之一。个体选2.基于加权求和方法的算法择是优胜劣汰的环节，但选择压力过大会造成过早收敛到局部最优利用加权求和法网可以将多个目标折算为单一目标进行优化,而解,选择压力过小,又 会影响收敛速度和优化效率。且可以证明，转化后得到的最优解是原多目标优化问题的一个非劣3.2代表性的多目标进化优化算法解。但此类方法的结果取决于各目标权重的选取,而权重的选取带有3.2.1基于加权求和方法的进化优化算法很大的主观性。目标较多时,根据经验确定各目标权重的难度较大。此第一个多目标进化优化算法是由SchafferJD于1985年提出的外由于各目标的单位、量纲不同,难以公平比较,更加大了确定权重的基于向盐评 估的遗传算法(Vector Evluated Genetie Algorithm,VEGA),其特点是:在选择过程中,对各个目标分别加以考虑,即将全文献[3]建立隶属度函数对各个目标进行评价,将不同量纲的多个部个体平均划分为多个子群， 每个子群只针对某-一个目标进行优化，目标转换为对该目标的满意度，以便于各目标的比较;根据各目标两因此从本质上说,VEGA仍然是一种加权求和的方法。两之间的相对重要性构建判断矩阵.采用判断矩阵法确定各目标的权另外一种基于加权求和的优化算法是由Hajela和Lin于1992年重值。这在- -定程度上解决了目标比较和权重确定两个问题,但仍只提出的基于权重的遗传算法(Weighing-based Genetie Agorithm),其特能得到一个非劣解,而不是整个非劣解集,只适用于特定问题的求解。点是务 目标的权重值不是固定不变的，而是作为个体编码的一部分。3.多目标进化优化算法在评价个体优劣时,每个个体均按照不同权重进行计算,因此可以实模拟生物进化过程的进化优化算法是一类通用的优化问题求解现权重和解 的共同进化,其优化效率和结果要好于VEGA。思路。此类算法在单目标优化问题中能够以逃离局部最优解，具有全3.2.2 MOGA局寻优能力,对目标函数没有连续可导等要求,并具有并行性好等优在Fonsea和Fleming于1993年提出的多目标遗传算法(Muli-点。适用于求解传统数学优化算法难以处理的非线性、离散变量和强obijetive Genetie Algorithmn, MOGA)中,采用了基于排序数的评价方法约束条件的优化模型，经过几十年的发展，获得了丰硕的理论成果和(评价值等于 排序数加1)。所谓排序数,即在当前群体中,绝对优于某广泛应用。一个体的其他个体的数量。如图1所示,5个非劣解的评价值为1,而一随着进化算法研究的深人， 将进化计算的思想应用于求解多目标最差解 的评价值为10。优化问题，提出了VECA .NPCA.NSCA ,SPEA等算法以及改进算法。这些多目标进化优化算法的实现和性能各异,但都具有一次性求取非劣解集的能力。3.1进化优化算法的关键技术进化计算的特点是以群体优化搜索,代替了传统算法的单- -个体中国煤化工的优化.通过群体内信息的交互机制，可以更有效的提高计算效率,并有利于摆脱局部最优解陷阱。这一特点对于求解多目标优化问题,无MYHCNMHG疑是极为有利的特点。一般来说,进化类算法的设计和具体实现主要包括以下三个步骤:编码方案进化策略、选择策略。所谓编码方案.即如何将问题的解以一个向量或一组数字的形式圈1 MOGA 的评价方寨(下转第27页).科技信息O科教前沿OSCENCE & TECHNOLOGY INFORMATION2008年第23期贮藏。为了解决人工种子萌发率和成苗率低的问题,薛建平等以半夏活性成分 相关酶类,并进行分子克隆和基因调控的相关研究。此外,还试管小块茎为材料，用3%梅藻酸钠和2%壳聚糖为种皮基质，添加要 注重组织培养物的产品开发。如丁家宜教授以人参愈伤组织为原料CAs、多菌灵.CuCl2和NiCI等物质制成了复合型人工种皮,可获95%开 发出了一系列畅销的化妆品,就是我国药用植物组织培养开发产晶的萌发率和90%的成苗事，大大提高了人工种子的萌发率和成苗事，方 面的成功之作。利用半夏组培物可以进行生物制药及植物杀虫剂等为半夏人工种子的规模化生产和大田应用提供技术支持。但人工种子的研究 ,开发出新的产品,有产品的支持的半夏组织培养,其工业化步经过常温或低温贮藏不同时间后,是否影响其萌发率和成苗率等问题伐也将 大大加快。还有待进一步研究。4.3建立和完善半夏的快速繁殖体系3.半夏细胞培养的研究利用半夏的组织培养进行快速繁殖，可以采取一次性成苗的方近年来.利用细胞培养技术生产天然产物的研究十分活跃,并越法。 但若为了满足市场需求,进行大量的生产和种质保存,则最好建立来越受到人们的关注。尤其是半夏细胞培养条件的模索和细胞生长规半夏的 无性系快速繁殖体系。但必须以市场需求为导向,在合理进行律等基础性研究较为活跃，关于细胞培养过程中次生代谢产物的研可行性分析的基础 上再着手建立。建立快繁体系的基本方法是以外植究反应器的研制等方面开展的相对较少。贾永芳等用半夏幼嫩叶片体诱导 出愈伤组织,通过继代,建立能够不断传代的半夏愈伤组织体培养诱导出愈伤组织,然后进行悬浮振荡培养,经3~4欢继代培养得系 ,再对愈伤组织进行扩大培养,形成大量的试管苗。稳定的半夏快速到分散性好的细胞悬浮系。将细胞悬浮液过健得到的小细胞团接种于繁殖系统,繁殖系数高,1 个1cm直径的半夏块茎理论上可繁殖1x10MS附加NAA.2mg/L和BA1.Omg/L分化培养基上,40d可分化出小植个以上的试管苗。 从愈伤组织到可移裁的试管苗需50d左右,从而可株。范美华等研究得出半夏细胞的生长曲线星“S”型,细胞的最佳收获及时 高效的为生产上提供大量优质种苗。但是,在愈伤组织长期继代时间为21d,培养基的最佳组合为:20g/L葡萄糖+100mg/L肌醇+培养过程中 ,会造成遗传变异,影响试管苗的品质。因此,在建立快速1.8mmo/LCaCL 2H20+0.06mml/LFeSO. 7H;0。此外,还发现光照有利繁殖体 系的同时,要不断的完善相关技术环节:从外植体的选择、培养于半夏细胞的生长并且蛋白质含量与酶活性呈正相关性,MDA含量条件 、最佳植物生长调节剂的配比到炼苗移栽都需要在实践中总绪经和细胞的生长、分化呈负相关性。验,不断改进,以达到高效、经济的目的。丹4.结语和展望植物组织培养作为一项重要的生物技术存在无限的潜力和应用[参考文献] .价值。半夏的组织和细胞培养研究工作已取得成功,并获得了不少成(1]中国医学科学院药物研究所等编,中药志(M.第二版,北京:人民卫生出版社，果,但也还有不少向题需要深人研究。4.1 研究半夏组织培养和植株再生过程中的生理及结构上的变化[2]冉悬雄名贵中药材绿色栽培技术[M.北京:科学技术文献出版社20024.经研究发现,组织培养的半夏块茎中各成分的总含量要高于野生[3]任家惠,陈克润,徐琼芳.三叶半夏试管苗器官的诱导U.植物生理学通报，块茎。但其具体的生理生化方面的原因还不清楚。郭余龙等用HPLC1983.4:44.[4]万美亮,陈宏康，詹亚华,等.半夏组织培养与快迷繁殖研克[J.中国中药杂志，法比较分析了组织培养块基和野生块茎的成分,也发现了前者各成分9.909:592 -531.的总含量高于后者,二者的主成分构成也相似,但半夏培养物又觖乏[5]张腾国半 夏组织培养快繁技术研究，，甘肃农业.科19911:15-17.某些野生块茎中的特有成分，遣成该种影响的生理变化也尚未明白。[6]张苏锋谢索霞,半夏组织培 养快速繁殖的研究[D.信阳师范学院学报1998,11半夏组织培养过程中,植株再生途径有两种:一是从愈伤组织形成:外()86-89.植体上诱导愈伤组织的形成再转至分化培养基,发育成完整植株:二[7]武宗信，解红蛾,赫建平,等半夏快速繁殖研兖J.山西大学学报(自然科学版),是从非愈伤组织形成:外植体上诱导形成球状体,再发育成完整植株，205,283)315-317.未经脱分化面完成了再分化。造成这两种途径,除了有外源教素的影[8)何美民，划刚，路铁刚，等，半夏基尖培养及块蒸的品质改 良U植物学报。94.61)39 44.响外,其内部又有哪些生理和结构变化等都有待进一步探讨。[9]张小斌,赵月梅.商格半夏的组织塘养研兖[.商格师范专科学校学报[D4.2深化半夏细胞培养及工业化生产的研究半夏组织培养的培养基筛选植物生长调节剂的季加量,氨源及205.1914:40-43.培养条件等基本技术已经比较成熟。更深层次的研究工作应着重于半作者简介:顾明率,女19728出生,汉族。中药学本科,全国执业药师。主攻夏组织培养的工业化:如适合半夏培养的反应器的研制.细胞生长规方向:中药基定学。律的探讨.细胞在反应器中的生长动力学考察、诱导子的使用等。同时,还要开展对半夏块茎中总生物贼麻黄贼.半夏蛋白等次生代谢机[责任编辑:张艳芳]制的研究。通过对次生代谢机理的研究,可以深入分析调控半夏块茎(上接第32页)3.2.3 NSCA的非劣解作为精英保留在一一个附属外部种群;外部种群也参与所有的NSCA(Nondominated Sorting Genetic Algorithm)算法是基于对多目遗传操作 ;对外部种群不断的进行更新,并采用聚类的方法保持非劣标解群体进行逐层分类的方法。每代选种配对之前先按解个体的非劣解 的数量不超过规定值。性进行排序,并引进基于决策空间的共享函数,优点是优化目标个数4.结束语任选,非劣最优解分布均匀,允许存在多个不同等效解;缺点是计算效进化优化算法是- -类模拟生物进化过程的优化方法,具有全局寻事较低,未采用精英保留策略(itisn),共享参数需要预先确定。随后，优的能力。 利用进化优化算法求解多目标优化问题，可以一次求取非Deb与Pratap等通过引进快速非劣性排序和新的多样性保护方法,提劣解 集中多个非劣解的能力,是多目标优化问题研究的热点。出了第二代NSCA,简称NSCAII,在- -定程度 上克服了NSGA的缺点。多目标优化问题的进化优化算法中待研兖的问题还很多,特别是3.2.4 NPGA非劣最优解的质量评估.选种配对机制和选择机制等,是目前新算法1994年Horm,Napliotisi 和Goldberg等人于提出了小生境Pareto的研究重点。风遣传算法(Niched Pareto Genetic Algorihm,NPGA)。NPGA将共享函数的概念引人到多目标进化优化算法中,采用基于锦标赛方法的选择机[参考文献]制。该算法的非劣解选择是基于小生境,即一部分种群而非全体。其优[1]谢涛 .陈火吁名日标设化与冰管问样的油化暂块.计算机学报,003.26(8),点是能很快找到一些好的非劣最优解城,并能维持一个较长的种群更9-103中国煤化工新期。这就要求算法需要对小生境的规模和数量加以限制,以保证解[2]朝毓达1990的多样性,使最优解能够尽可能均匀的分散到整个非劣解集中。YHCN M H G电压优化控制.电力系统3.2.5 SPEAZitaler与Thiele提出了一种采用精英保留策略的强度Pareto进[4]王正志，薄诗进化计算.长沙:国防科技大学出版社,000.0化算去(Srengh Pareto Evoluionary Algorithm ,SPEA)。该算法将每代2