基于遗传算法的多目标优化算法

2011年第9期SCIENCE&TECHNOLOGYINFORMATION

○科教前沿○科技信息

基于遗传算法的多目标优化算法

李焱1,2

(1.西安电子科技大学研究生院陕西西安710071;2.青海建筑职业技术学院网络管理中心青海西宁810012)

【摘要】本文先介绍了遗传算法的实现技术,又介绍了多目标优化问题的概念,然后使用遗传算法来求解多目标优化问题。文中使用了均匀设计方法来设计适应度函数,并设计了新的变异算子,算法结果是有效的。

【关键词】遗传算法;多目标优化;均匀设计

Multi-objectiveGeneticAlgorithm-basedOptimizationAlgorithm

LIYan1,2

(1.Graduateschool,XidianUniversity,Xi’anShannxi,710071,China;2.NetworkManagementCenter,QinghaiArchitectural

VocationalandTechnicalCollege,XiningQinghai,810012,China)

【Abstract】Thisarticlefirstdescribestheimplementationofgeneticalgorithmtechnology,butalsointroducestheconceptofmulti-objectiveoptimizationproblem,andthenusegeneticalgorithmtosolvemulti-objectiveoptimizationproblem.Thepaperusestheuniformdesignmethodtodesignthefitnessfunction,anddesignofanewmutationoperator,thealgorithmresultisvalid.

【Keywords】Geneticalgorithm;Multi-objectiveoptimization;Uniformdesign

0引言

考虑如下多目标问题:

现实生活中的很多决策问题都要考虑同时优化若干个目标,而这些目标之间往往是彼此冲突的,多目标优化算法就是要从所有可能的方案中找到最合理、最可靠的解决方案。本文提出了基于加权平均法和均匀设计方法的一种解决多目标优化算法。

minF(x)=(f1(x),f2(x),…,fM(x))

x∈Ω

其中x=(x1,x2,…,xN)是实N维向量,Ω是可行解空间,f1(x),f2

(x),…,fM(x)为M个目标函数,记为F(x)=(f1(x),…,fM(x))。

定义1:(Pareto最优解)对任意两个点x1,x2∈Ω,如果下列条件成立:

1遗传算法的基本实现技术

遗传算法从任意一个初始种群出发,通过选择、交叉和变异操作,产生了一群更适应环境的个体,使群体进化到搜索空间中越来越好的区域,这样一代一代地不断繁衍进化,最后收敛到一群最适应环境的个体,求得问题的最优解。遗传算法主要涉及以下几个因素:1.1遗传编码

在遗传算法中描述问题的可行解,即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。1.2初始群体的生成

一定数量的个体组成了群体(也称为种群),群体中个体的数目称为群体规模;在执行遗传操作之前,必须先构造一个由若干个解组成的初始群体。1.3适应度函数

度量个体适应度的函数称为适应度函数。适应度函数通常是根据目标函数确定的,用于区分群体中个体好坏的标准,是进行进化算法选择的依据。本文按按均匀设计构造适应度函数。1.4标准遗传算法的操作算子

标准遗传算法的操作算子一般都包括选择、交叉和变异三种基本形式。

1)选择算子

遗传算法中使用选择操作来对群体中的个体进行优胜劣汰,选择算子根据每个个体的适应度值大小来进行选择,适应度较高的个体被遗传到下一代群体中的概率较大。

2)交叉算子

交叉操作是遗传算法中最主要的遗传操作,交叉运算是遗传算法区别于其他进化算法的重要特征。交叉操作是在两个个体之间进行的,是产生新个体的主要方法。本文使用了算术交叉。

3)变异算子

变异是以较小的概率对个体编码串上的某个或某些位值进行改变,从而形成一个新的个体,而且保证了种群发展的稳定性。1.5控制参数选择

遗传算法中的控制参数选择非常重要,选择不同的参数会对算法的性能产生较大的影响。这些参数包括种群规模,编码长度,编码方式,交叉概率,变异概率,终止代数等,应针对具体问题或者具体阶段选取不同的值。

fi(x1)≤fi(x2),坌i∈{1,2,,M}fj(x1)≤fj(x2),埚j∈{1,2,,M}

即向量(f1(x1),…,fM(x1))优于向量=(f1(x2),…,fM(x2)),则称x1

优于x2。

对于多目标问题,在优化过程中要考虑多个目标同时优化,使算法的搜索不断向Pareto最优解集移动,并且保持解在Pareto界面的均匀分布。本文采用基于均匀设计和加权和法求解多目标优化算法。

3

3.1

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

适应度函数

在目标空间中,将每个目标作为一个因素,因此有M个因素,构造D个适应度函数,需要D个权向量,因此每个因素取D个水平。根据表1[3]和公式Ui,j=(iσj-1modq)+1计算均匀阵列U(M,D),根据加权平均法计算ωi,j,得到适应度函数为:

fiti=ωi,1(f1(x)+ωi,2f2(x)+…+ωi,MfM(x),1≤i≤D

随机产生初始种群的算法

1)定义种群规模为pop;2)产生服从[0,1]N×n上均匀分布的随机向量r,i=1;3)i=li+rij(ui-li)(i=1~N,j=1~n);4)若i≤N,转2),否则停;5)将随机产生的个体存入种群Pt中。3.3交叉算子

在交叉运算之前必须先对群体中的个体进行配对。给定交叉概率Pc∈(0,1)。对种群Pt中每个个体依均匀分布产生[0,1]中一个随机数ri,(i=1~N),N为种群个数,当ri<Pc,将该个体选作交叉父代,随机选择两两交叉,用算术交叉将两个个体进行线性组合而产生出两个新的个体。

3.4变异算子

对个体xi以概率Pm进行变异,随机选择xi的某个分量xir∈[lr,ur],为分量xir的取值范围的左右边界值,随机生成范围[lr,ur]内的一个数xit,将它替换xi中的分量xir,(r≠t)。3.5选择算子

根据均匀设计产生D个适应度函数,用每个适应度函数来评价种群中的所有的个体,对每个个体选出[pop/D]或[pop/D]个最好值,共选出pop个个体,作为下一代种群。

3.2

4结论(下转第423页)

2多目标优化问题基本概念

454

科技信息○本刊重稿○

SCIENCE&TECHNOLOGYINFORMATION

2011年第9期

随时间变化呈单峰态特征,0:00~7:00浓度变化基本平稳,8:00~11:00迅速上升,12:00-15:00迅速下降,16:00-23:00缓慢下降。气象资料[17]统计结果显示,2009年4月23日前后银川市天气干燥,大风天气且伴有大的沙尘,无降雨,容易发生严重的空气污染。

污染物,月际变化呈较明显的“W”字型,污染状况最为严重。

2.42009年银川市SO2超标天集中在1月和2月,造成污染的原因可能是采暖期煤的燃烧,以及超标天气压升高,风速小,无降雨,不利于污染物扩散。PM10超标天集中在冬春两季,造成污染的原因可能是天气干燥,大风天气且伴有大的沙尘,无降雨。总的来说,银川市的空气污染状况可能与大尺度的天气现象相关。科

【参考文献】

[1]徐华英.我国空气污染状况及其对人体健康的影响[J].气候与环境研究,

图72009年1月16日SO2日小时平均浓度变化

图82009年4月23日PM10日小时平均浓度变化

2结论

本文通过对银川市2009年环境空气质量统计特征的分析,主要包括空间统计特征,季、月、日际变化特征和典型变化特征三个方面,得出以下结论:

2.12009年银川市空气污染质量总体状况良好,SO2、NO2和PM10的年均浓度值均未超过国家二级标准。四个季节三种污染物在整个市区的浓度分布表现为:冬春最严重,其次是春季和秋季,污染最轻的是夏季。三种污染物日均浓度在春冬季节变化较大,夏秋季节变化较小,较长的采暖期空气污染比较严重。

2.2银川市兴庆区、金凤区和西夏区三个行政区中西夏区的污染相对来说比较严重,可能与西夏区是重工业发展基地有关。兴庆区和金凤区污染物的年均浓度都没有超过国家二级标准,而西夏区也只有PM10超标。

2.3三种污染物中NO2全年浓度较低,未超过国家一级标准,污染较轻。SO2浓度变化具有明显的季节性,月际变化呈宽阔的“U”字型,与NO2相比污染状况较严重。PM10是2009年银川市空气污染最主要的

1999,4(1):56-60.

[2]G.Grivas,A.Chaloulakou,P.Kassomenos,AnoverviewofthePM10pollutionproblem,intheMetropolitanAreaofAthens,Greece[J].Assessmentofcontrollingfactorsandpotentialimpactoflongrangetransport,ScienceoftheTotalEnvironment2007(1):1-13.

[3]IndraniGupta,RakeshKumar,TrendsofparticulatematterinfourcitiesinIndia[J].AtmosphericEnvironment,2006(40):2552-2566.

[4]PLiu.AnalysisofdisebrakesquealusingtheeomPlexeigenvaluemethod[J].APPliedAeousties,2007,68(6):603-615.

[5]王斌.利用空气污染指数(API)分析我国空气污染的区域时空变化特征[D].青岛:中国海洋大学,2008:13-70.

[6]程涛.基于小波分析的上海市环境空气质量变化及与气象关系研究[D].上海:华东师范大学,2007:6-7.

[7]司瑶冰,宫春宁,郑有飞.呼和浩特市大气污染与天气气候的关系[J].气象科技,2005,33(2):173-177.

[8]刘彩霞,边玮瓅.天津市空气质量与气象因子相关分析[J].中国环境监测,2007,23(5):63-65.

[9]李国翠,连志鸾,郭卫红,等.石家庄市污染日特征及其天气背景分析[J].气象科技,2006,34(6):674-679.

[10]李国翠,王建国,连志鸾,等.2006年春季石家庄市沙尘天气与PM10污染[J].中国环境监测,2007,23(6):57-60.

[11]唐燕秋,陈佳,熊强,等.重庆市多年空气污染指数分析及大气污染控制对策[J].四川环境,2005,24(6):80-82.

[12]柴微涛,宋述军,宋学鸿.成都市城区空气污染指数的时间序列分析[J].成都理工大学学报:自然科学版,2007,34(4):485-488.

[13]陈灿.广州市2002~2003年空气污染指数分析[J].四川环境,2005,24(05):20-23.

[14]纪忠萍,罗秋红,罗森波,等.广州市空气污染的变化特征及预报[J].热带气象学报,2006,22(6):574-581.

[15]张凌,付朝阳,郑习健,等.广州市区大气污染特征与影响因子分析[J].生态环境,2007,16(2):305-308.

[16]GB3095-1996环境空气质量标准[S].

[17]实时气象资料[EB/OL].中国气象科学数据共享服务网http://cdc.cma.gov.cn.

作者简介:樊韬(1972—),男,工程师,主要从事固体危险废物管理及环境影响评价研究。

※宁夏科技攻关项目“宁夏灰霾天气形成机理、预报预测及防治对策研究”资助。

[责任编辑:汤静]

(上接第454页)本文提出的多目标遗传算法中,使用了均匀设计方法产生初始种群,种群分布范围宽广且均匀,通过加权平均法的适应度函数选择下一代种群,可获得较均匀的Pareto最优解。如何减少适应度评估时间是需要继续研究的问题。科

【参考文献】

[1]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999.[2]崔逊学.多目标进化算法及其应用.北京:国防工业出版社,2006.

[3]Yiu-WingLeung,WangYuping.MultiobjectiveProgrammingUsingUniformDesignandGeneticAlgorithm.IEEETransactionsonSystems.2000,(30):293-304[4]刘淳安,王宇平.基于新模型的多目标遗传算法.西安电子科技大学学报:自然科学版,2005,30(2):260-267.

[5]刘淳安,王宇平.基于一种新模型的多目标遗传算法及性能分析.控制理论与

应用,2006,23(3):425-428.

[6]刘淳安,王宇平.一种基于新的模型的多目标存档遗传算法.计算机工程与应用,2005:43-45.

[7]刘淳安,王宇平.基于新模型的动态多目标优化进化算法.计算机研究与发展,2008,45(4):603-611.

[8]魏静萱,王宇平.基于新模型的多目标Memetic算法及收敛分析.控制理论与应用,2008,25(3):389-392.

作者简介:李焱(1975—),女,青海西宁人,高级讲师,在读硕士研究生,研究方向为进化算法。

[责任编辑:张慧]

423


相关范文

  1. Matlab遗传算法工具箱的应用

    ^工●砷化聩件技m0.I.Automation2005年第24卷第6期Softwwe1khnjque2005.VbI.24.No.6文章蚺号l10D6一],76(2D05)06一0115一02 Matlab遗传算法工具箱的应用 曾日波 (江西财经大学电子学院,江西南昌330013) 摘要:Matla ...

  2. 多目标优化的求解方法与发展

    多目标优化的求解方法与发展 耿玉磊 张翔 (福建农林大学机电工程学院,福州金山 350002) 摘要:本文首先介绍了传统多目标优化求解方法和改进:对遗传算法,模糊优化,神经网络等算法在多目标优化中的应用做了介绍:最后介绍了满意度. 关键词:多目标优化 遗传算法 神经网络 1前言 多目标优化(Mult ...

  3. 遗传算法在自动控制领域的应用

    遗传算法在自动控制领域的应用 信息与控制学院 10自动化2班 宋晓莉 [1**********] 一.引言 随着现代控制理论和计算机技术的持续快速发展,控制工程师面临着越来越严峻的挑战:选择适合的控制器结构然后优化其参数以满足特定实际应用的性能要求.实际上,控制系统的建模和设计都是在具有噪声情况下的 ...

  4. 传统多目标优化方法和多目标遗传算法的比较综述

    2010年第32卷第3期第48页 电气传动自动化 ELECTRlCDRIVE V01.32,No.3 AUT()MATIoN2010.32(3):48-50 传统多目标优化方法和多目标遗传算法的比较综述 马小妹L2,李宇龙3,严浪3 (1.西安电子科技大学计算机学院.陕西西安710071:2.天水师 ...

  5. 物流系统模型和算法研究

    物流系统模型和算法研究 [摘要]:物流是企业的"第三利润源",是国民经济发展的动脉和基础产业.加强信息技术在物流系统中的应用,可以有效地降低物流费用.物流系统的模型和算法是计算机科学和物流科学当前研究的热点.物流费用主要包括物流中心的选址费用.物流配送费用和库存费用.本文以降低物 ...

  6. 基于遗传算法的装配线平衡_宋华明

    第20卷第1期(总第109期) 系 统 工 程 Vol.20,No.1 2002年1月 SystemsEngineering Jan.,2002 文章编号:1001-4098(2002)01-0087-05 基于遗传算法的装配线平衡 宋华明,韩玉启 (南京理工大学经济管理学院,江苏南京 210094 ...

  7. 基于混合遗传算法的宽带阶梯阻抗变换器的优化设计

    基于混合遗传算法的宽带阶梯阻抗变换器的优 化设计* 马国田 梁昌洪 摘要 提出了一种将标准遗传算法和确定性方法相结合的混合遗传算法,并应用该方法对相对带宽为100%的宽带阶梯阻抗变换器进行优化设计,克服了标准遗传算法效率太低及确定性方法易收敛于局部极小点的缺点.分别对负载阻抗为纯实数和复数的两种情况 ...

  8. 路径规划的智能控制

    (综述报告) 考 核 科 目 :机电系统智能控制 学生所在院(系):机电学院 学生所在学科 :机学生姓名 学号 : 学生类别 :工考 核 结 果 械制学 造 阅卷人 智能控制在机器人领域的应用 遗传算法在移动机器人路径规划上的研究 摘要:近些年来机器人技术飞速发展,对机器人运动的控制要求越来越高,机 ...

  9. 基于改进的粒子群遗传算法的DNA编码序列优化

    第33卷 第2期2010年2月 计 算 机 学 报 CHINESEJOURNALOFCOMPUTERS Vol.33No.2 Feb.2010 基于改进的粒子群遗传算法的DNA编码序列优化 崔光照 1),2) 李小广 张勋才 1)2) 1)1),2) 王延峰 1),2) 李翠玲 1) (郑州轻工业学 ...