遗传算法在多目标优化中的作用 调研报告

遗传算法在多目标优化中的作用调研报告

姓名:

学院:

班级:

学号:

完成时间:20 年月日

目录

1 .课题分析................................................................................................................................ 0

2 .检索策略................................................................................................................................ 0

2.1 检索工具的选择................................................................................................................................ ......... 0 2.2 检索词的选择................................................................................................................................ ............. 0 2.3 通用检索式................................................................................................................................ .. 0

3.检索步骤及检索结果 0

3.1 维普中文科技期刊数据库 0

3.2 中国国家知识产权局数据

库................................................................................................................... 2 3.3 美国工程索引 E NGINEERING V ILLAGE(EI)数据库....................................................................................... 4 3.4 ISI W EB OF

K NOWLEDGE(包含WEB OF SCIENCE AND

INSPEC) ............................................................................ 6 3.5 欧洲专利局数据库................................................................................................................................ (9)

4.检索体会................................................................................................................................ .................9 5 . 国内外研究概况...............................................................................................................................

10 参考文献................................................................................................................................ .. (3)

1.课题分析

多目标优化问题是近30 年来迅速发展起来的一门新兴学科,属于应用型基础课题, 有着重要和广泛的应用价值。多目标优化主要是研究多个数值目标在给定约束条件下的最优解的求取。随着理论研究的不断深入,多目标优化的应用领域也日益扩大,已经涉及到过程控制、航空航天、人工智能、计算科学、许多实际复杂系统的设计、建模和规划问题等诸多领域。求解多目标问题的传统算法存在许多局限性,并且存在关键致命问题。1975 年美国密歇根大学教授J.Holland 首次提出了遗传算法,该领域的研究便迅速增长。遗传算法是在计算机上模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程,进行搜索寻优的算法。近十几年来,国内外涌现出许多求解多目标问题的遗传算法及其改进形式,这些算法及其改进形式在解决多目标优化问题中得到成功应用,显示出强大的生命力。本课题的主要目的是通过应用所学的文献检索知识,检索国内外在多目标优化遗传算法的研究进展方面的文献。通过阅读理解这些文献,掌握该领域的最新研究情况;通过对各种遗传算法适用条件、应

用范围及优缺点的分析,以发现该领域研究切入点和今后发展方向。

2.检索策略

2.1 检索工具的选择

该课题涉及目标规划领域、进化算法领域,属于数学、计算科学。同时,该课题在众多工程领域中应用广泛。因此,以下数据库为必检数据库:

(1)中文数据库维普中文期刊数据库或万方数据资源系统中国国家知识产权局数据库 (2)外文数据库美国工程索引EI英国科学文摘网络版INSPEC 科学引文索引SCI欧洲专利数据库

2.2 检索词的选择

在检索词的选择上要注意同义词、近义词、不同拼写方式等。

(1)中文检索词

核心检索词:遗传算法、多目标优化

其他检索词:进化算法、多目标、多目标规划、多目标决策、优化、传统多目标

优化方法、多目标遗传算法

在研究课题文献检索初期,主要应用课题的核心词做适当的组配成为检索式,进行文献查找。对于本课题而言,最核心、最显著的检索词是“遗传算法和多目标优化”。因为多目标问题应用广泛,所以存在多目标决策、多目标规划、多目标优化等多个检索近义词,如果只检索“多目标优化”,可能会导致检索不到“多目标决策、多目标规划”, 然而这些领域却是多目标问题的重要应用领域。综上考虑,在检索过程中为提高查全率, 决定将初始检索词定为:“遗传算法和多目标”,即不考虑决策、规划、优化等词。另外, 对于本课题研究中诸如发展、研究、进展之类的词语太宽泛,故不将其设为检索词,这样也不会影响查

全率。在检索过程中应根据检索结果对检索词做灵活而适当的改变,在保证查全率的情况下保证查准率。

(2)英文检索词核心检索词:genetic algorithm(s)

GA,multi-objective optimization problem MOP 其他检索词: evolutionary computation EC, multiobjective,multi-objective optimization,

multi-objective decision making,optimization,traditional

multi-objective

optimization methods,multi-objective genetic algorithm

对于英文检索词,最值得注意的是截词符的使用,因为英语中一个词义有多种表达形式,尽可能的考虑某些词不同的表现形式,使用截词符可以最大限度的提高查全率。例如。对“优化”这个词,至少有“optimization”和“optimizing”等两种表达方式。所以我们选择“optimiz*”作为检索词。根据具体的检索情况,可以挑选其中的部分组配组成检索式,以达到本课题的研究目的。

2.3 通用检索式

a) 遗传算法*多目标*(进化算法+规划+决策+优化+传统) b) 遗传算法*多目标c) 遗传算法*(进化算法+规划+决策+优化+传统) d) 多目标*(进化算法+规划+决策+优化+传统)

e) 进化算法+规划+决策+优化+传统f) geneticalgorithm+genetic algorithm+GA g) evolutionarycomputation+ evolutionary computation+EC+optimization+optimizing

+traditional+decision making 这里,“*”表示逻辑“与”,“+”表示逻辑“或”。检索时可根据数据库和检索结果

作相应的调整。

3.检索步骤及检索结果

3.1 维普中文科技期刊数据库

检索式:(Title_C=遗传算法)*(Title_C=多目

标)*((Keyword_C=(传统多目

标)+Title_C=(传统多目标))) 由于检索条件限制过于严格,导致只有一篇文献被命中,结果如下:

1) 【题名】传统多目标优化方法和多目标遗传算法的比较综述【作者】马小姝、李宇龙、严浪【机构】马小姝(西安电子科技大学,计算机学院,陕西,西安,710071;天水师

范学院,物理与信息科学学院,甘肃,天水,741000), 李宇龙,严浪 (天

水电气传动研究所有限责任公司,甘肃,天水,741020) 【刊名】电气传动自动化,2010,32(3):48-50,53【ISNN 号】1005-7277【关键词】多目标优化;传统优化方法;遗传算法【中图分类号】TP18 【摘要】多目标优化是最优化领域的一个重要的研究方向。论述了多目标优化模型,

同时介绍了常用的几种传统优化方法和常用的几种多目标遗传算法,对改进后的遗传算法与传统优化方法求解效果进行了比较,认为要进一步研究求解多目标优化问题的更多高效算法,若能结合两者的优点,处理多目标问题的效果将越来越好。

为了能够更好的了解“遗传算法在多目标优化中的作用”,决定将检索式简化为: (Title_C=遗传算法)*(Title_C=多目标),找到约393 篇文献,选出两篇对课题研究进展有重要意义的文献摘录如下:2) 【题名】基于遗传算法的多目标优化方法

【作者】钱艳婷,王鹏涛【机构】天津理工大学计算机与通信工程学院,天津300384 【刊名】天津理工大学学

报,2010,26(3):20-22【ISNN 号】1673-095X【关键词】遗传算法;多目标优化;AHP(层次分析)方法【中图分类号】

TP301;U116 【摘要】文通过建立多目标问题模型,提出了运用改进的遗传算法求解多目标物流

网络问题.该算法借鉴AHP 方法的思想,采用将其与遗传算法混合的求解策略,并采用分阶段化的实数编码思想以及相应的遗传算子设计,对遗传算法进行适应性改进。

3) 【题名】基于遗传算法的锻模阻力墙结构多目标优化设计【作者】周杰1,张渝1,2,安治国1,李路1 【机构】1.重庆大学材料科学与工程学院重庆400044;2.重庆交通大学机电与汽

车工程学院重庆400074 【刊名】机械工程学

报,2010,46(14):85-90

【ISNN 号】0577-6686【关键词】阻力墙,模具寿命,Kriging 模型,遗传算法【中图分类号】TG315.2 【摘要】针对传统模锻工艺中飞边槽结构的不足,在综合常规飞边槽与楔形飞边槽

优点的基础上,提出锻模新型飞边结构形式——阻力墙。以减少模具磨损和降低成形载荷为目标,通过优化分析得到最佳阻力墙结构参数,为阻力墙的应用提供设计依据。应用拉丁超立方方法对阻力墙结构参数进行抽样, 对所得样本进行有限元模拟。将模拟结果作为响应,以阻力墙结构参数为变量,分别建立模具磨损和成形载荷的Kriging 模型。基于上述近似模型, 采用线性加权法将磨损Kriging 模型和载荷Kriging 模型转化为单目

标函数,利用遗传算法进行全局寻优,得到优化的阻力墙结构参数。采用该方法,充分利用Kriging 模型适合计算机仿真的优点,并利用遗传算法适合求解隐式函数优化问题的特点。以曲轴为例,验证了阻力墙的优化设计应用。

3.2 中国国家知识产权局数据库

检索式:(名称=遗传算法)and(摘要=多目标),有三条发明专利被命中。摘录其中两条如下,

4) 申请号:200810057374.1 申请日:2008.02.01 名称:基于遗

传算法的企业过程模型多目标参数优化方法

5) 申名

化方法。在企业过程模型参数优化领域,大多数优化方法均使用对策权衡原理对各子目标组合成一个单目标来处理优化目标,在综合评价过程方面存在一定缺陷的问题。本发明主要针对源产品产生速率、各类资源的总数、各个活动的持续时间与所需资源的配置方案以及可供选择的资源调度策略等多类优化参数,综合评价运行时间、运行成本、最终产品产量、资源利用率、队列长度等多项指标。本发明采用多层次划分问题空间的方法来处理各类优化参数之间的组合约束关系,不仅增加了优化参数选择的灵活性,避免了优化时对无效参数组合方案的分析计算,而且有助于保持群体的多样性。

请号: 200910219163.8 申请日: 2009.11.26 称: 基于遗传算法的网络文本分割方法

公开(公告) 号:主分类号:分类号:申请(专利权)人: 北京航空

航天大学地址: 100083 北京市海淀区学院路37 号发明(设计)人: 王博;张莉国际申请:

CN101231720 公开(公告)日: 2008.07.30 G06Q10/00(2006.01)I 分案原申请号: G06Q10/00(2006.01)I;G06N3/12(2006.01)I

国际公布: 进入国家日期: 摘要:一种企业工程与信息技术领域的基于遗传算法的多目标企业过程模型参数优

公开(公告) 号: CN101710333A 公开(公告)日: 2010.05.19

主分类号: G06F17/30(2006.01)I 分案原申请号:分类号:

G06F17/30(2006.01)I;G06F17/27(2006.01)I;G06N3/12(2006.01)I 颁证日: 优先权:申请(专利权)人: 西北工业大学地址: 710072 陕西省西安市友谊西路127 号发明(设计)人: 蔡皖东;赵煜国际申请:国际公布: 进入国家日期:专利代理机构: 西北工业大学专利中心61204 代理人: 黄毅新摘要:本发明公开了一种基于遗传算法的网络文本分割方法,用于对网络短篇幅文

本的分割,所述方法利用Gibbs 采样方法估计语料库对应的潜在狄利克雷分配(Latent?Dirichlet?allocation,LDA)模型,并利用该模型推断目标文本的潜在话题信息,利用潜在话题信息表示文本;再采用并行遗传算法,将文本分割过程转化为多目标优化过程,利用深层次语义信息计算分割单元内凝聚性、分割单元间发散性以及适应度函数,进行文本分割过程的遗传迭代,依据多次迭代结果之间的相似度或迭代次数上限决定分割过程是否结束,得到文本分割全局最优解,提高了网络短篇幅文本分割准确率。

3.3 美国工程索引 Engineering Village(EI)数据库

检索式:((((genetic algorithm) WN TI) AND ((multi objective ) WN TI)) AND ((traditional multi objective optimization) WN KY))

共有44 篇文献被检索命中,根据文献研究所需,选择其中一篇国内,两篇国外学者写的文献摘录如下:6) [Title]Improved genetic algorithm of multi-objective structure fuzzy optimization

[Authors] Lai, Yinan1; Lai, Mingzhu1; You, Bindi1; Dimitrov, Todorov Georgi2 [Author affiliation] 1 Harbin University of Science and Technology, 150080, China

2 MTF, Technical University of Sofia, Bulgaria[Source] Proceedings - 5th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2008, v 1, p 306-310, 2008, Proceedings - 5th International

Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2008 [ISBN-13] 9780769533056

[Abstract] A kind of improved symmetry and a kind of improved asymmetry genetic algorithm were introduced to solve the general multi-objective optimization problem according to the different important degree of objective functions and constraint functions. It can search the optimum solution from many initial points at the same time. The example of helical gear was given to demonstrate these algorithms. By applying Matlab toolbox we obtained the optimal values of various multi-objective optimization fuzzy models. The results showed that the improved algorithm has fast convergence speed of the solution process and high accuracy, and can obtain the global optimum solution of the whole optimization problems comparing with the traditional

multi-objective optimization , and it also meets the security, economical efficiency and other requirements.

.7) [Title] Multi-objective optimization of an industrial penicillin V bioreactor train using non-dominated sorting

genetic algorithm [Authors] Fook, Choon Lee; Rangaiah,

Gade Pandu; Ray, Ajay Kumar[Author affiliation]

Department of Chemical and Biomolecular Engineering,

National University of Singapore, Engineering Drive 4,

Singapore 117576, Singapore[Source] Biotechnology and Bioengineering, v 98, n 3, p 586-598, October 15, 2007

[E-ISSN] 1097-0290[Abstract] Bulk of the penicillin

produced is used as raw material for semi-synthetic

penicillin (such as amoxicillin and ampicillin) and

semi-synthetic cephalosporins (such as cephalexin and

cefadroxil). In the present paper, an industrial penicillin V

bioreactor train is optimized for multiple objectives

simultaneously. An industrial train, comprising a bank of

identical bioreactors, is run semi-continuously in a

synchronous fashion. The fermentation taking place in a

bioreactor is modeled using a morphologically structured

mechanism. For multi-objective optimization for two and

three objectives, the elitist non-dominated sorting genetic

algorithm (NSGA-II) is chosen. Instead of a single optimum as in the traditional optimization, a wide range of optimal

design and operating conditions depicting trade-offs of key

performance indicators such as batch cycle time, yield, profit and penicillin concentration, is successfully obtained. The

effects of design and operating variables on the optimal

solutions are discussed in detail.

.8) [Title] Multi-objective optimization of wire-electro discharge machining process by Non-Dominated Sorting

Genetic Algorithm [Authors] Kuriakose, Shajan;

Shunmugam, M.S.[Author affiliation] Department of

Mechanical Engineering, Indian Institute of Technology

Madras, Chennai 600036, India[Source] Journal of

Materials Processing Technology, v 170, n 1-2, p 133-141,

Decem- ber 14, 2005 [ISSN] 09240136 [Abstract]

Wire-electro discharge machining (Wire-EDM or WEDM) is one of the important non-traditional machining processes,

which is used for machining of

difficult-to-machine materials and intricate profiles. Being a complex process, it is very difficult to determine optimal parameters for improving cutting performance. Cutting velocity

and surface finish are most important output parameters, which decide the cutting performance. There is no single optimal combination of cutting parameters, as their influences on the cutting velocity and the surface finish are quite the opposite. In the present work, a multiple regression model is used to represent relationship between input and output variables and a

multi-objective optimization method based on a Non-Dominated Sorting Genetic Algorithm (NSGA) is used to optimize Wire-EDM process. A non-dominated solution set has been obtained and reported.

3.4 ISI Web of Knowledge(包含 web of science and inspec)

检索式:标题=(genetic algorithm) AND 标题=(multi objective optimization) AND 主题=(traditional multi objective)

有20 篇文献被命中,现摘录其中重要两篇摘录如下:

9)Multi-objective optimization of wire-electro discharge machining process by Non-Domin-

ated Sorting Genetic Algorithm作者: Shunmugam, M.S.; Kuriakose, S.来源出版物: Journal of Materials Processing Technology 卷: 170 期: 1-2 页: 133-41 出版年: 14 December 2005摘要: Wire-electro discharge machining (Wire-EDM or WEDM) is one of the important

non-traditional machining processes, which is used for machining of difficult-to-machine materials and intricate profiles. Being a complex process, it is very difficult to determine optimal parameters for improving cutting performance. Cutting velocity and surface finish are most important output parameters, which decide the cutting performance. There is no single optimal combination of cutting parameters, as their influences on the cutting velocity and the surface finish are quite the opposite. In the

present work, a multiple regression model is used to represent relationship between input and output variables and a

multi-objective optimization method based on a Non-Dominated Sorting Genetic Algorithm (NSGA) is used to optimize Wire-EDM process. A non-dominated solution set has been obtained and reported.

10)Thermodynamic Pareto optimization of turbojet engines using multi-objective genetic algorithms

作者: Atashkari K, Nariman-Zadeh N, Pilechi A, Jamali A, Yao

X来源出版物: INTERNATIONAL JOURNAL OF THERMAL SCIENCES 卷: 44 期: 11

摘要:

页: 1061-1071 出版年: NOV 2005Multi-objective genetic algorithms (GAs) are used for Pareto approach

optimization of thermodynamic cycle of ideal turbojet engines. On this behalf, a new diversity preserving algorithm is proposed to enhance the performance of multi-objective evolutionary algorithms (MOEAs) in optimization problems with more than two objective functions. The important conflicting thermodynamic objectives that have been considered in this work are, namely, specific thrust (ST), thrust-specific fuel consumption (TSFC), propulsive efficiency (eta(rho)), and thermal efficiency (eta(t)). In this paper, different pairs of these objective functions have been selected for two-objective optimization processes. Moreover, these objectives have also been considered for a four-objective optimization problem using the new diversity preserving algorithm of this work. The comparison results demonstrate the superiority of the new algorithm in preserving the diversity of non-dominated individuals and the quality of Pareto fronts in both two-objective and 4-objective optimization processes. Further, it is shown that some interesting and important relationships among optimal

objective functions and decision variables involved in the thermodynamic cycle of turbojet engines. can be discovered consequently. Such important relationships as useful optimal design principles would not have been obtained without the use of a multi-objective optimization approach. It is also demonstrated that the results of four-objective optimization can include those of two-objective optimization and, therefore, provide more choices

for optimal design of thermodynamic cycle of ideal turbojet engines.

利用SCI 的分析功能,可以了解目前国内外有关机构、学者在这方面的研究进展。检索式:Title=(genetic algorithm) AND Title=(multi objective).由于在检索式中加入“traditional multi objective optimization”会使查全率严重下降,不利于对检索结果的分析,因此将检索式设为“Title=(genetic algorithm) AND Title=(multi objective)”。分析结果如图3.4.1 至图3.4.3 所示。

图3.4.1 根据“作者”排列记录

图3.4.2 根据“机构名称”排列记录

图3.4.3 根据“来源出版物”排列记录3.5 欧洲专利局数据库

检索式:keyword(s) in title=(genetic algorithm) and (multi objective).共有一条专利被命中,摘录如下:

11)ROUTING TREE SEARCHING METHOD USING

MULTI-OBJECTIVE GENETIC ALGORITHM AND CORRESPONDING SENSOR NETWORK

Publication number: KR20090103188 (A)Publication date:

2009-10-01Inventor(s): SHIN JI TAE [KR]; NAVRATI SAXENA [KR]; ABHISHEK ROY [KR] +

(SHIN, JI TAE, ; NAVRATI SAXENA, ; ABHISHEK

ROY)Applicant(s): UNIV SUNGKYUNKWAN FOUND [KR] + (SUNGKYUNKWAN

UNIVERSITY FOUNDATION FOR CORPORATE COLLABORATION) Classification:

- international: H04L12/28; H04L12/28- European:Application number: KR20080028614 20080327 Priority number(s):

KR20080028614 20080327 Abstract not available for KR 20090103188 (A)

4.检索体会

1)在文献信息检索过程中,要想得到令人满意的检索效果,关键是能够构造出全面描述、正确揭示信息需求的检索式。检索词是检索式的基本组成元素,如果选词不当就很容易造成漏检和误检,因此,能否选准、选全检索词直接影响到检索效果的优劣。选择检索词应先确定核心词,在确定其他的检索词,并充分考虑同义词、近义词,并采

用截词符、位置算符和逻辑组配制定多个检索式进行试检索,根据检索结果进行调整。检索式的复杂与否,取决于课题需要。描述简炼的课题,检索式可能会很复杂;名称冗长的课题,检索式反而可能会很简单。检索词是表达信息需求的基本元素,其选择恰当与否直接影响到检索效果。对于给定的检索课题,应首先深入分析课题内容,在提取核心词的基础上进行扩展,然后构造较为完善的检索策略和检索式,才能获得令人满意的检索效果。

2)检索时应从综述论文入手。先抽取核心的关键词,制定检索式进入数据库中检索,在所得的检索结果中浏览综述性文章,或检

索时直接指定综述类论文,可以帮助我们快速的了解课题背景。而且首先应从中文文献入手,这样更容易了解课题背景。本课题中我们从维普数据库中检索到了《基于遗传算法的多目标优化方法》等多篇文献,这帮助了我们很快了解课题,并且,从图书馆参考了《广义机械优化设计》第五章进化设计与优化和《机械优化设计》第六章第十一节遗传算法简述以及《多目标优化算法及在卫星星座设计中的应用》。

3)利用Web of Science的数据分析功能,对检索到的结果进行分析,可以发现在该领域中研究较多的机构和个人以及该领域的论文主要在哪个或哪些期刊上发表。例如, 本课题在Web of Science 通过检索式“Title=(genetic algorithm) AND Title=(multi objective)”检索到了429 篇文献,对429 篇检索到的文献分析结果如表4.1 所示。

4)检索词要做相应调整。由于本课题研究成果较多,发表的相关论文和申请的相关专利较多。所以在检索过程中,首先以“标题=(遗传算法)and(多目标)”为检索式, 如果检索结果数目过于庞大,则将检索式改为“(标题=(遗传算法)and(多目标)and(标题、关键词、摘要=(传统多目标优化))”。这样可以在保证查全率的前提下保证查准率,为课题研究节省了大量时间。

5)有必要阅读全文时必须阅读全文。虽然大多数文摘能够揭示文献的内容特征, 但也有相当一部分不能从文摘中获取所需的信息,所以在需要阅读全文时必须阅读全文。这样才能更准确的确定是否为密切相关文献。

5.国内外研究概况

1975 年美国密歇根大学教授J.Holland 首次提出了遗传算法。这种算法起源于20 世纪60 年代对自然和人工自适应系统的研究。第一个把遗传算法用于函数优化的是

记录排列字段排列第一位排列第二位作者IEEE GUPTA, SK 机构名称INDIAN INST TECHNOL FIRAT UNIV

来源出版物LECTURE NOTES IN

COMPUTER SCIENCE

IEEE CONGRESS ON

EVOLUTIONARY

COMPUTATION

Hollstien,1971 年他在论文《计算机控制系统中的人工遗传自适应方法》中主要讨论了了对于二变量函数的优化问题。其中,对于优势基因控制、交叉和变异以及各种编码技术进行了深入的研究。遗传算法兴盛于20 世纪80 年代。遗传算法在单目标优化问题中已得到了成熟的发展和应用。遗传算法属于一门新兴的学科——进化计算。进化计算主要研究如何仿照生物进化自然选择过程中所表现出来的优化规律和方法,进行优化计算、预测和数字寻优的。

多目标最优化是最优化的一个重要分支。它主要研究在某种意义下多个数值目标的同时最优化问题,吸引了不少学者的关注。在现实生活中,多目标问题几乎在各行各业中都存在,如:柔性作业车间调度决策,输电塔阻尼器布置,机组短期负荷环境/经济调度,由于多目标寻优问题的复杂性,往往用传统优化理论和方法难以解决。越来越多的研究学者将具有全局性概率优化搜索能力的遗传算法运用于这一领域中,先后有学者提出了向量值评估遗传算法(VEGA),多目标遗传算法(MOGA),非支配排

序遗传算法(NSGA),带精英策略的非支配排序遗传算法(NSGA—II),小生境Pareto 遗传算法(NPGA).

同传统数学规划相比,遗传算法具有以下特点:

1)遗传算法是多点同时搜索,通过个体间的相互协调,具有可能避开局部解的功能;

2)遗传算法直接利用从目标函数转化成的适应函数,而不采用导数等信息,所以适用于不连续评价函数的求解问题;

3)遗传算法采用编码方法而不是参数本身; 4)遗传算法是以概率原则指导搜索,而不是确定性的转化原则; 5)遗传算法符合多目标优化问题不止存在一个解的特点。蓝艇等人总结出以下对MOGA 的改进方法:1)向量评估遗传算法.Schaffer 在向量评估遗传算法(VEGA)中主要对遗传算法中的

选择算子作了改进.在进化过程中,子种群的产生是根据每个目标函数分别进行选择. 2)非劣排序遗传算法.非劣排序遗传算法(NSGA)的基本思想是用分级选择方法来突出好的优秀个体子种群的稳定.Deb 等人后来对NSGA 方法进行了改进(称为

NSGA-II).在NSGA-II 中使用了精英选择策略,以及拥挤距离.

3)小生境Pareto 遗传算法.小生境Pareto 遗传算法(NPGA)将传统遗传算法的选择

算子改进为基于Pareto 优劣的比武选择策略.不像传统的遗传算法只比较两个个体,而是多个个体参与竞争.当两个参与竞争者都是非劣或者劣时,比武的结果应根据目标域内的适应值共享来决定.

以上的改进在近几年受到国内外学者的重视,但是也有很多研究学者提出新的改进措施并加以应用。比如Li Chen 等人提出了一种大进化多目标遗传算法(MMGA),将Marin 和Sole 提出的大进化算法(MA)与应用于多目标的遗传算法结合,用以解决多目

标水库系统的规则曲线优化问题。又如,2003 年Kasat 和Guptarl 订提出NSGA-II —JG,将一种新的JG 操作算子结合常用的NSGA-II 操作算子,它按一定的概率在染色体串中选取两

个位置,用一种新的,同样大小的,随机的遗传二进制串来取代

这两个位置间的部分。

根据查找的文献可知,钱艳婷,王鹏涛通过建立多目标问题模型,提出了运用改进的遗传算法求解多目标物流网络问题.该算法

借鉴AHP 方法的思想,采用将其与遗传算法混合的求解策略,

并采用分阶段化的实数编码思想以及相应的遗传算子设计,对

遗传算法进行适应性改进。周杰,张渝,安治国等人针对传统模锻工艺中飞边槽结构的不足,在综合常规飞边槽与楔形飞边槽

优点的基础上,提出锻模新型飞边结构形式——阻力墙。以减少模具磨损和降低成形载荷为目标,通过优化分析得到最佳阻力

墙结构参数,为阻力墙的应用提供设计依据。应用拉丁超立方方法对阻力墙结构参数进行抽样, 对所得样本进行有限元模拟。将模拟结果作为响应,以阻力墙结构参数为变量,分别建立模具磨损和成形载荷的Kriging 模型。基于上述近似模型,采用线性加权法将磨损Kriging 模型和载荷Kriging 模型转化为单目标

函数,利用遗传算法进行全局寻优,得到优化的阻力墙结构参数。采用该方法,充分利用Kriging 模型适合计算机仿真的优点,

并利用遗传算法适合求解隐式函数优化问题的特点。以曲轴为例,验证了阻力墙的优化设计应用。

遗传算法目前存在的问题有:1)其具体的操作方法(淘汰、增值、交叉和突然变异等)无一般的模式,需要根据实际求解问题,凭

经验和试算进行编程;2)大多数参数需要人为的确定。

多目标遗传算法是近几年逐渐火热的话题,在发展过程中注意

到以下问题:非劣解接近pareto 最优解曲面(前沿)的判断依据

还没有比较适用的研究结果,很多国内外文献上的研究结果都

只是表明通过比较曲线,用肉眼观察非劣解的分布均匀程度以

及接近pareto 曲面的距离来判断改进算法的优劣,并且大部分

的改进算法也只是停留在仿真阶段,而没有应用到具体的工业

过程。

参考文献

[1] 李莉,潘丰. 基于遗传算法的多目标进化算法综述[J]. 2007 中国控制与决策学术年会论文集.363-366

[2] 钱艳婷,王鹏涛. 基于遗传算法的多目标优化方法[J]. 天津理工大学学报,2010,26 (3),20-22

[3] 沈大旺,张慧. 遗传算法综述[J]. 黑龙江科技信

息,2009, ,(28),100,74[4] 马小姝,李宇龙,严浪. 传统多目标优化方法和多目标遗传算法的比较综述[J]. 电

气传动自动化,2010,32(3):48-53[5] 王安麟,刘广军,江涛.

广义机械优化设计[M]. 武汉,华中科技大学出版社,2008.11

[6] 孙靖民,梁迎春. 机械优化设计[M]. 北京,机械工业出版社,2006,12[7] 吉久明,孙济庆,曾媛等. 文献检索与知识发现指南[M]. 上海,华东理工大学出版

社,2010,01

遗传算法在多目标优化的应用：公式,讨论,概述总括

遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（niche formation method）在此也有适当的延伸,并提供了群落大小界定的理论根据。适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。 1.简介 求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解，仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。 本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法(Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集， 简化了多目标问题的优化求解步骤。 多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣，这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点，我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最 后对非劣解集的逼近。 考虑一个n维的多目标规划问题，且均为目标函数最大化， 其劣解可以定义为： f i (x * )≤f i (x t ) i=1，2，??，n (1) 且式(1)至少对一个i取“＜”。即至少劣于一个可行解的x必为劣解。 对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解，并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算，可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。 个体的适应度计算方法确定后，为保证能得到非劣解集，算法设计中必须处理好以下问题：(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到

多目标遗传算法代码

. % function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance

遗传算法在多目标优化中的作用 调研报告

遗传算法在多目标优化中的作用调研报告 姓名: 学院: 班级: 学号: 完成时间:20 年月日 目录 1 .课题分析................................................................................................................................ 0 2 .检索策略................................................................................................................................ 0 2.1 检索工具的选择................................................................................................................................ ......... 0 2.2 检索词的选择................................................................................................................................ ............. 0 2.3 通用检索式................................................................................................................................ .. 0 3.检索步骤及检索结果 0 3.1 维普中文科技期刊数据库 0 3.2 中国国家知识产权局数据

遗传算法多目标函数优化

多目标遗传算法优化 铣削正交试验结果 说明： 1.建立切削力和表面粗糙度模型 如： 3.190.08360.8250.5640.45410c e p z F v f a a -=（1） a R =此模型你们来拟合（上面有实验数据，剩下的两个方程已经是我帮你们拟合好的了）（2） R a =10?0.92146v c 0.14365f z 0.16065a e 0.047691a p 0.38457 10002/c z p e Q v f a a D π=-????（3） 变量约束范围：401000.020.080.25 1.0210c z e p v f a a ≤≤??≤≤??≤≤? ?≤≤? 公式（1）和（2）值越小越好，公式（3）值越大越好。π=3.14 D=8 2.请将多目标优化操作过程录像（同时考虑三个方程，优化出最优的自变量数值），方便我后续进行修改；将能保存的所有图片及源文件发给我；将最优解多组发给我，类似于下图（黄色部分为达到的要求）

遗传算法的结果:

程序如下: clear; clc; % 遗传算法直接求解多目标优化 D=8; % Function handle to the fitness function F=@(X)[10^(3.19)*(X(1).^(-0.0836)).*(X(2).^0.825).*(X(3).^0.564).*(X(4).^0. 454)]; Ra=@(X)[10^(-0.92146)*(X(1).^0.14365).*(X(2).^0.16065).*(X(3).^0.047691).*( X(4).^0.38457)]; Q=@(X)[-1000*2*X(1).*X(2).*X(3).*X(4)/(pi*D)];

遗传算法程序代码--多目标优化--函数最值问题

函数最值问题：F=X2+Y2-Z2, clear clc %%初始化 pc=0.9; %交叉概率 pm=0.05; %变异概率 popsize=500; chromlength1=21; chromlength2=23; chromlength3=20; chromlength=chromlength1+chromlength2+chromlength3; pop=initpop(popsize,chromlength);% 产生初始种群 for i=1:500 [objvalue]=calobjvalue(pop); %计算目标函数值 [fitvalue]=calfitvalue(objvalue);%计算个体适应度 [newpop]=selection(pop,fitvalue);%选择 [newpop1]=crossover(newpop,pc) ; %交叉 [newpop2]=mutation(newpop1,pm) ;%变异 [newobjvalue]=newcalobjvalue(newpop2); %计算最新代目标函数值 [newfitvalue]=newcalfitvalue(newobjvalue); % 计算新种群适应度值[bestindividual,bestfit]=best(newpop2,newfitvalue); %求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit); %储存最优个体适应值 pop5=bestindividual; %储存最优个体 n(i)=i; %记录最优代位置 %解码 x1(i)=0+decodechrom(pop5,1,21)*2/(pow2(21)-1); x2(i)=decodechrom(pop5,22,23)*6/(pow2(23)-1)-1; x3(i)=decodechrom(pop5,45,20)*1/(pow2(20)-1); pop=newpop2; end %%绘图 figure(1)%最优点变化趋势图 i=1:500; plot(y(i),'-b*') xlabel('迭代次数'); ylabel('最优个体适应值'); title('最优点变化趋势'); legend('最优点');

多目标遗传算法代码

% function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance % corresponding to their position in the front they belong. 真是牛X了。 chromosome = non_domination_sort_mod(chromosome,pro); %% Start the evolution process

多目标规划遗传算法

%遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen

多变量多目标的遗传算法程序

这是我在解决电梯动力学参数写的简单遗传算法（程序带目标函数值、适应度值计算，但是我的适应度函数因为目标函数的计算很特殊，一起放在了程序外面计算,在此不提供）。 头文件： // CMVSOGA.h : main header file for the CMVSOGA.cpp // 本来想使用链表里面套链表的，程序调试比较麻烦，改为种群用链表表示 //染色体固定为16的方法。 #if !defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767_ _INCLUDED_) #define AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED _ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "Afxtempl.h" #define variablenum 16 class CMVSOGA { public: CMVSOGA(); void selectionoperator(); void crossoveroperator(); void mutationoperator(); void initialpopulation(int, int ,double ,double,double *,double *); //种群初始化 void generatenextpopulation(); //生成下一代种群 void evaluatepopulation(); //评价个体，求最佳个体 void calculateobjectvalue(); //计算目标函数值 void calculatefitnessvalue(); //计算适应度函数值 void findbestandworstindividual(); //寻找最佳个体和最差个体 void performevolution(); void GetResult(double *); void GetPopData(double **); void SetValueData(double *); void maxandexpectation(); private: struct individual { double chromosome[variablenum]; //染色体编码长度应该为变量的个数 double value; double fitness; //适应度 };

多目标遗传算法中文【精品毕业设计】(完整版)

一种在复杂网络中发现社区的多目标遗传算法 Clara Pizzuti 摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。 关键词：复杂网络，多目标聚类，多目标进化算法 1、简介 复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。 复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。 多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。 因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。 在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。 本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。 多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级