论文部分内容阅读
摘要:本文对遗传算法的基本特点、步骤和流程和基于MATLAB的遗传算法优化工具箱进行了介绍,结合多目标函数问题的优化实例,说明了遗传算法是一种具有良好的全局寻优性能的优化方法。
关键词:遗传算法;MATLAB;多目标函数优化
中图分类号:TP311文献标志码:B文章编号:1671-7953(2009)01-0049-03
Multi-objective Optimization Based on MATLAB
Genetic Algorithm Optimization Toolbox
ZHANG Peijun1,Li Xiaoxia1,JI Zhiqiang2
(1.Hebei University of Engineering,Handan 056038,China;
2.Chuang’an Digital Technology Co. Ltd. Handan 056002,China)
Abstract:The paper introduces genetic algorithm (GA) and genetic algorithm optimization toolbox and analyses the optimization toolbox function. The function optimization problem of multi-objective has been given to demonstrate that genetic algorithm is a better global optimization method.
Key words:genetic algorithm;MATLAB;Multi-objective optimization
1遗传算法简介
遗传算法由JohnHolland教授于1975年率先提出,是基于达尔文的自然选择原理,用来模拟生物遗传过程中的物竞天择、优胜劣汰,依据自然界不断进化发展的过程来实现优化,弱者子代较少将被淘汰,从而使群体在若干代进化后“素质”得以提高,这些子代中“素质”最好的,即问题的最优解得以生存,是一种随机搜索优化算法。遗传算法以其搜索空间大这一优点在众多工程应用中为解决多变量、多目标、多峰值等约束的优化问题发挥了作用。
1.1遗传算法具有以下特点:
1)遗传算法不是直接处理优化问题变量本身的实际值,而是以优化变量的编码为运算对象。
2)遗传算法是从优化问题解的编码组开始搜索的,而不是从单个解开始搜索的。
3)遗传算法不要求目标函数连续,更不要求目标函数可微。
4)遗传算法使用的选择、交叉、变异这三个算子都是随机操作,而不是确定规则。
1.2遗传算法步骤
采用有限体积法离散控制方程和湍流模式。对于压力方程采用标准的离散格式进行离散,对于动量方程、湍流方程、雷诺应力方程,均采用二阶迎风格式进行离散,压力速度耦合迭代采用Simplec算法。
标准遗传算法的主要步骤可描述如下。
1)随机产生一组初始个体构成初始种群,并评价每一个个体的适配值。
2)判断算法收敛准则是否满足。若满足则输出搜索结果;否则执行以下步骤。
3)根据适配值大小以一定方式执行复制操作。
4)按交叉概率pc执行交叉操作。
5)按变异概率pm执行变异操作。
6)返回步骤(2)。
1.3流程
2基于MATLAB遗传工具箱的多目标优化
2.1MATLAB遗传工具箱主要参数含义
x最终值到达的点@fitnessfcn适应度函数句柄(即适应度函数的文件名,通常是.m文件)
fval适应度函数的最终值(即运行中最好的结果)
nvars适应度函数的独立变量个数
reason算法停止的原因(可选项)
output包含关于算法在每一代性能的结构体(可选项)
population最后种群(即最后一代染色体)(可选项)
options一个包含遗传算法选项参数的结构(可选项),如果不传递选项参数,则GA使用其本身的缺省选项值。该参数结构体包含种群规模,默认值为[20],最大代数,默认值为[20],选择概率默认值为[0.5],交叉概率,默认值为[0.8],变异概率,默认值为[0.2]。也可通过gaoptimset函数改变其默认值,达到使用者需要的值[1]。
2.2多目标函数优化简介
在实际的优化设计过程当中,对某一问题的优化仅仅有一个指标是不能完全表达的,必须考虑多种目标。如同大家去商场,对商品总是要求物美价廉,这当中就包含了多目标优化的思想在其中。所以,解决含多目标和多约束的最优值的问题称之为多目标优化(Multi-objectiveOptimization)问题。
2.2.1多目标函数优化的数学模型[2]
min[f1(X),f2(X),…,fp(X)]T(p≥2,X∈Rn)
约束条件为
gi(X)≤0(i=1,2,…m)hj=0(j=1,2,…1)
2.2.2多目标函数优化问题的遗传算法[3]
若对于2.2.1中数学模型,x1∈X,并且不存在比x1更优越的解x,则称x1是多目标最优化模型的Pareto最优解。求解Pareto最优解常用的方法有:
1)权重系数变换法
对一个多目标优化问题,给其每个子目标函数pi(x)(i=1,2,…,k),赋予权重λi(i=1,2,…,k),其中λi为pi(x)相应的在多目标优化问题中的重要程度,则各个子目标函数pi(x)的线性加权和表示为:
max(min)u=∑ki=1λi*pi(x)
将u作为多目标优化问题的评价函数,此时多目标优化问题就转化为单目标优化问题,因此可利用单目标优化的遗传算法求解多目标优化问题。
2)并列选择法
其基本思想是:先将群体中的全部个体按照子目标函数的数目均等地划分为一些子群体,对每个子群体分配一个子目标函数,各个子目标函数在相应的子群体中独立地进行选择运算,各自选择出一些适应度高的个体组成一个新的子群体,然后再将所有这些新生成的子群体合并成一个完整的群体,在这个群体中进行交叉和变异运算,从而生成下一代的完整群体,如此不断地进行“分割——并列选择——合并”操作,最终可求出多目标优化问题的Pareto最优解。
3)排列选择法
这种方法是基于Pareto最优个体,对群体中的各个个体进行排序,依据这个排列次序来进行进化过程中的选择运算,从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体中。
4)共享函数法
利用小生境遗传算法的技术来求解多目标最优化问题,将共享函数的概念引入到求解多目标最优化问题的遗传算法中。
5)混合法
其基本思想是选择算子的主体使用并列选择法,然后通过引入保留最佳个体和共享函数的思想来弥补只使用并列选择法的不足之处。
3多目标函数优化实例
已知
minf1=x21/5+x22/5minf2=x1(2-x2)+10s.t.1≤x1≤4,1≤x2≤2
其中f1和f2的权重系数都为0.5,种群数目为100,最大遗传代数为100,变量个数为2,变量的二进制位数为20位。
经过遗传算法优化后,第一目标函数的最优解及性能跟踪,如图2;第二目标函数的最优解及性能跟踪,如图3所示;两目标函数和的最优解及性能跟踪,如图4;第一目标函数值和第二目标函数值,如图5所示[4]。
图2经过100次迭代后第一目标函数的最优解及性能跟踪
图3经过100次迭代后第二目标函数的最优解及性能跟踪
图4经过100次迭代后两目标函数和的最优解及性能跟踪踪
图5经过100次迭代后种群的第一目标函数值和第二目标函数值
利用MATLAB的强大数学计算能力和遗传工具箱,能够有效的对多目标函数进行优化,可以减少我们计算和编程的工作量。
参考文献
[1]杜东,马震,孙晓明.MATLAB遗传算法工具箱(GAOT)在水资源优化计算中的应用[M].水利科技与经济,13(2),2007:73-76
[2]罗中华.最优化方法及其在机械行业中的应用[M].北京:电子工业出版社,2008
[3]雷英杰,张善文,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:30-33,150-176.
[4]刘万林,张新燕,晁勤,MATLAB环境下遗传算法优化工具箱的应用[M].新疆大学学报(自然科学版),22(3):357-360.
关键词:遗传算法;MATLAB;多目标函数优化
中图分类号:TP311文献标志码:B文章编号:1671-7953(2009)01-0049-03
Multi-objective Optimization Based on MATLAB
Genetic Algorithm Optimization Toolbox
ZHANG Peijun1,Li Xiaoxia1,JI Zhiqiang2
(1.Hebei University of Engineering,Handan 056038,China;
2.Chuang’an Digital Technology Co. Ltd. Handan 056002,China)
Abstract:The paper introduces genetic algorithm (GA) and genetic algorithm optimization toolbox and analyses the optimization toolbox function. The function optimization problem of multi-objective has been given to demonstrate that genetic algorithm is a better global optimization method.
Key words:genetic algorithm;MATLAB;Multi-objective optimization
1遗传算法简介
遗传算法由JohnHolland教授于1975年率先提出,是基于达尔文的自然选择原理,用来模拟生物遗传过程中的物竞天择、优胜劣汰,依据自然界不断进化发展的过程来实现优化,弱者子代较少将被淘汰,从而使群体在若干代进化后“素质”得以提高,这些子代中“素质”最好的,即问题的最优解得以生存,是一种随机搜索优化算法。遗传算法以其搜索空间大这一优点在众多工程应用中为解决多变量、多目标、多峰值等约束的优化问题发挥了作用。
1.1遗传算法具有以下特点:
1)遗传算法不是直接处理优化问题变量本身的实际值,而是以优化变量的编码为运算对象。
2)遗传算法是从优化问题解的编码组开始搜索的,而不是从单个解开始搜索的。
3)遗传算法不要求目标函数连续,更不要求目标函数可微。
4)遗传算法使用的选择、交叉、变异这三个算子都是随机操作,而不是确定规则。
1.2遗传算法步骤
采用有限体积法离散控制方程和湍流模式。对于压力方程采用标准的离散格式进行离散,对于动量方程、湍流方程、雷诺应力方程,均采用二阶迎风格式进行离散,压力速度耦合迭代采用Simplec算法。
标准遗传算法的主要步骤可描述如下。
1)随机产生一组初始个体构成初始种群,并评价每一个个体的适配值。
2)判断算法收敛准则是否满足。若满足则输出搜索结果;否则执行以下步骤。
3)根据适配值大小以一定方式执行复制操作。
4)按交叉概率pc执行交叉操作。
5)按变异概率pm执行变异操作。
6)返回步骤(2)。
1.3流程
2基于MATLAB遗传工具箱的多目标优化
2.1MATLAB遗传工具箱主要参数含义
x最终值到达的点@fitnessfcn适应度函数句柄(即适应度函数的文件名,通常是.m文件)
fval适应度函数的最终值(即运行中最好的结果)
nvars适应度函数的独立变量个数
reason算法停止的原因(可选项)
output包含关于算法在每一代性能的结构体(可选项)
population最后种群(即最后一代染色体)(可选项)
options一个包含遗传算法选项参数的结构(可选项),如果不传递选项参数,则GA使用其本身的缺省选项值。该参数结构体包含种群规模,默认值为[20],最大代数,默认值为[20],选择概率默认值为[0.5],交叉概率,默认值为[0.8],变异概率,默认值为[0.2]。也可通过gaoptimset函数改变其默认值,达到使用者需要的值[1]。
2.2多目标函数优化简介
在实际的优化设计过程当中,对某一问题的优化仅仅有一个指标是不能完全表达的,必须考虑多种目标。如同大家去商场,对商品总是要求物美价廉,这当中就包含了多目标优化的思想在其中。所以,解决含多目标和多约束的最优值的问题称之为多目标优化(Multi-objectiveOptimization)问题。
2.2.1多目标函数优化的数学模型[2]
min[f1(X),f2(X),…,fp(X)]T(p≥2,X∈Rn)
约束条件为
gi(X)≤0(i=1,2,…m)hj=0(j=1,2,…1)
2.2.2多目标函数优化问题的遗传算法[3]
若对于2.2.1中数学模型,x1∈X,并且不存在比x1更优越的解x,则称x1是多目标最优化模型的Pareto最优解。求解Pareto最优解常用的方法有:
1)权重系数变换法
对一个多目标优化问题,给其每个子目标函数pi(x)(i=1,2,…,k),赋予权重λi(i=1,2,…,k),其中λi为pi(x)相应的在多目标优化问题中的重要程度,则各个子目标函数pi(x)的线性加权和表示为:
max(min)u=∑ki=1λi*pi(x)
将u作为多目标优化问题的评价函数,此时多目标优化问题就转化为单目标优化问题,因此可利用单目标优化的遗传算法求解多目标优化问题。
2)并列选择法
其基本思想是:先将群体中的全部个体按照子目标函数的数目均等地划分为一些子群体,对每个子群体分配一个子目标函数,各个子目标函数在相应的子群体中独立地进行选择运算,各自选择出一些适应度高的个体组成一个新的子群体,然后再将所有这些新生成的子群体合并成一个完整的群体,在这个群体中进行交叉和变异运算,从而生成下一代的完整群体,如此不断地进行“分割——并列选择——合并”操作,最终可求出多目标优化问题的Pareto最优解。
3)排列选择法
这种方法是基于Pareto最优个体,对群体中的各个个体进行排序,依据这个排列次序来进行进化过程中的选择运算,从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体中。
4)共享函数法
利用小生境遗传算法的技术来求解多目标最优化问题,将共享函数的概念引入到求解多目标最优化问题的遗传算法中。
5)混合法
其基本思想是选择算子的主体使用并列选择法,然后通过引入保留最佳个体和共享函数的思想来弥补只使用并列选择法的不足之处。
3多目标函数优化实例
已知
minf1=x21/5+x22/5minf2=x1(2-x2)+10s.t.1≤x1≤4,1≤x2≤2
其中f1和f2的权重系数都为0.5,种群数目为100,最大遗传代数为100,变量个数为2,变量的二进制位数为20位。
经过遗传算法优化后,第一目标函数的最优解及性能跟踪,如图2;第二目标函数的最优解及性能跟踪,如图3所示;两目标函数和的最优解及性能跟踪,如图4;第一目标函数值和第二目标函数值,如图5所示[4]。
图2经过100次迭代后第一目标函数的最优解及性能跟踪
图3经过100次迭代后第二目标函数的最优解及性能跟踪
图4经过100次迭代后两目标函数和的最优解及性能跟踪踪
图5经过100次迭代后种群的第一目标函数值和第二目标函数值
利用MATLAB的强大数学计算能力和遗传工具箱,能够有效的对多目标函数进行优化,可以减少我们计算和编程的工作量。
参考文献
[1]杜东,马震,孙晓明.MATLAB遗传算法工具箱(GAOT)在水资源优化计算中的应用[M].水利科技与经济,13(2),2007:73-76
[2]罗中华.最优化方法及其在机械行业中的应用[M].北京:电子工业出版社,2008
[3]雷英杰,张善文,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:30-33,150-176.
[4]刘万林,张新燕,晁勤,MATLAB环境下遗传算法优化工具箱的应用[M].新疆大学学报(自然科学版),22(3):357-360.