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
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