一类二层多目标规划的混沌遗传优化算法及其应用.pdf

D0I:10.13374/1.issnl00I53.2006.07.019 第28卷第7期北京科技大学学报 Vol.28 No.7 2006年7月 Journal of University of Science and Technology Beijing Jul.2006 类二层多目标规划的混沌遗传优化算法及其应用郭兴众马健安微工程科技学院电气工程系，芜湖241000 摘要针对求解一类二层多目标规划问题，首先将其转化为等价的单目标规划问题，然后利用遗传算法优化的反演性和混沌优化方法的遍历性，并结合精确罚函数求解非线性约束优化问题，提出了求解此类问题的混沌遗传算法·该方法能够有效改善遗传算法的局部搜索能力和搜索精度，求解精度和可靠性较高·实际算例表明，算法是有效可行的关键词二层多目标规划：混沌遗传算法；优化分类号TP18 遗传算法(GA)是一种启发式蒙特卡洛反演方法，是基于自然选择和遗传学机理的迭代自适 1一类二层多目标规划问题应概率性搜索算法，其主要特点是群体搜索策略 1.1 问题的描述9] 和群体中个体之间的信息交换，搜索不依赖于梯考虑一类二层多目标规划问题(BLMOP): 度信息、它尤其适用于处理传统搜索方法难以解 minF(x,y) 决的复杂和非线性问题，在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用. st,G(xy)≤0 (1) 但对于大型复杂系统，尤其是非线性系统优化问 minf:(x,y:),i=l,…,p 题的求解，GA仍有许多缺陷，如无法保证收敛到 st,g(x,y)≤0，i=1,…,p 全局最优解，群体中最好的染色体的丢失，进化过式中，x=(x1,x2,…,xN)∈R,:=(yi,y2, 程的过早收敛等1) …,yi)T∈R",i=1,…,p,y∈R1XR"X…× 混沌是非线性系统独有的一种运动形式，混 R心，FR+N→R,fR+N→R,分别为上层沌运动具有遍历性、随机性、规律性等特点，能在多目标规划与下层第ⅱ个多目标规划的目标函一定范围内按其自身的规律不重复地遍历所有状数：GR+N→RO,g:R+N→R分别为上层多态，混沌优化是一种新型搜索算法，它直接采用目标规划与下层第i个多目标规划的约束函数，混沌变量在允许解空间进行搜索，具有对初值敏感、易于跳出局部最优解、搜索速度快和全局渐近收敛的特点，被广泛用于非线性优化领域5门. 对问题(1)的信息结构和决策机理有如下假利用遗传算法和混沌优化方法各自的优点，设：本文将遗传算法优化的反演性和混沌优化的遍历 1)对上层规划给定的x值，下层第个规划将性相结合，把混沌搜索机制嵌入遗传算法中，提出选择自己的决策变量y:值，使其向量目标函数f: 了解决一类二层多目标规划问题全局最优解的新最优，由于下层的多目标性，故对固定的x,一般方法一混沌遗传算法[23,78](CGA)·该算法可下层问题的解：(x)不是惟一的，而是一个有效以克服遗传算法存在的早熟收敛的缺点，解决引解（或非劣解）集，入混沌后遗传算法收敛慢的问题，能更有效地收 2)下层各规划之间是相互独立的，不进行任敛到最优解或近似最优解何信息交换收稿日期：2006-02-24修回日期：2006-04-18 3)上层决策者基于它自己的目标和偏好确基金项目：安徽省高校自然科学基金资助项目(N0.2003j041) 定其决策变量x的取值x,及与x相应的下层作者简介：郭兴众(1962一)，男，副教授，硕士各规划的y"(x)为问题(1)的最终解

一类二层多目标规划的混沌遗传优化算法及其应用郭兴众马健安徽工程科技学院电气工程系芜湖241000 摘要针对求解一类二层多目标规划问题首先将其转化为等价的单目标规划问题然后利用遗传算法优化的反演性和混沌优化方法的遍历性并结合精确罚函数求解非线性约束优化问题提出了求解此类问题的混沌遗传算法．该方法能够有效改善遗传算法的局部搜索能力和搜索精度求解精度和可靠性较高．实际算例表明算法是有效可行的．关键词二层多目标规划；混沌遗传算法；优化分类号 TP18 收稿日期：20060224 修回日期：20060418 基金项目：安徽省高校自然科学基金资助项目（No．2003kj041）作者简介：郭兴众（1962—）男副教授硕士遗传算法（GA）是一种启发式蒙特卡洛反演方法是基于自然选择和遗传学机理的迭代自适应概率性搜索算法．其主要特点是群体搜索策略和群体中个体之间的信息交换搜索不依赖于梯度信息．它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题在组合优化、机器学习、自适应控制、多目标决策等领域中有许多应用．但对于大型复杂系统尤其是非线性系统优化问题的求解GA 仍有许多缺陷如无法保证收敛到全局最优解群体中最好的染色体的丢失进化过程的过早收敛等［14］．混沌是非线性系统独有的一种运动形式混沌运动具有遍历性、随机性、规律性等特点能在一定范围内按其自身的规律不重复地遍历所有状态．混沌优化是一种新型搜索算法它直接采用混沌变量在允许解空间进行搜索具有对初值敏感、易于跳出局部最优解、搜索速度快和全局渐近收敛的特点被广泛用于非线性优化领域［57］．利用遗传算法和混沌优化方法各自的优点本文将遗传算法优化的反演性和混沌优化的遍历性相结合把混沌搜索机制嵌入遗传算法中提出了解决一类二层多目标规划问题全局最优解的新方法———混沌遗传算法［2378］（CGA）．该算法可以克服遗传算法存在的早熟收敛的缺点解决引入混沌后遗传算法收敛慢的问题能更有效地收敛到最优解或近似最优解． 1 一类二层多目标规划问题 1∙1 问题的描述［9］考虑一类二层多目标规划问题（BLMOP）： min x F（ xy） s．t．G（ xy）≤0 min y f i（ xyi）i＝1…p s．t．gi（ xyi）≤0i＝1…p （1）式中x＝（ x1x2…x N） T ∈R Nyi ＝（ y i 1y i 2 …y i n i ） T∈R n ii＝1…py∈R n1×R n2×…× R n pF∶R n＋ N→R Mf i∶R n i＋ N→R mi分别为上层多目标规划与下层第 i 个多目标规划的目标函数；G∶R n＋ N→R Qgi∶R n i＋ N→R g i分别为上层多目标规划与下层第 i 个多目标规划的约束函数 n＝ ∑ p i＝1 ni．对问题（1）的信息结构和决策机理有如下假设： 1）对上层规划给定的 x 值下层第个规划将选择自己的决策变量 yi 值使其向量目标函数 f i 最优由于下层的多目标性故对固定的 x一般下层问题的解＾yi（ x ）不是惟一的而是一个有效解（或非劣解）集． 2）下层各规划之间是相互独立的不进行任何信息交换． 3）上层决策者基于它自己的目标和偏好确定其决策变量 x 的取值 x ∗及与 x ∗相应的下层各规划的 y ∗（ x ∗）为问题（1）的最终解．第28卷第7期 2006年 7月北京科技大学学报 Journal of University of Science and Technology Beijing Vol．28No．7 Jul．2006 DOI:10．13374／j．issn1001－053x．2006．07．019

Vol.28 No.7 郭兴众等：一类二层多目标规划的混沌遗传优化算法及其应用 .697. 1.2问题的等价简化6，] 为求全局最优解，在引入混沌遗传算法 2混沌遗传优化算法 (CGA)之前，先将二层多目标规划问题转化为等 2.1混沌遗传优化方法求解问题的基本思路价的一般多目标规划问题，进而将其化为单目标本文求解问题的思路是利用混沌优化策略引最优化问题导种群进化，将混沌状态引入到优化变量中，并把定理设问题(1)中f,g:均为y:的连续可混沌运动的遍历范围放大到优化变量的取值范微凸函数，则对任意固定的x,该问题与以下的多围；把得到的混沌变量进行编码，根据适者生存的目标决策问题等价：原则，对其进行遗传算子操作：然后给各个混沌变 miF(x.y) 量附加一混沌小扰动，通过逐代不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优 s.t. G(x,y)0 解 7y时(x,y)十7yg:(xy)=0 2.2混沌机制与编码方式 g:(xy)=0 考虑Logistic混沌映射，即： g月+1=a(1-月)，月∈[0,1]，k=1,2,… 9(x,y)≤0 (9) 含4=1 其中，a为吸引子，当a=4时，Logistic映射为满映射，系统处于完全混沌状态，式(9)产生的序列 :≥0,1≥0 1}为混沌变量，利用混沌变量对初值的敏感 =1,,p 性，赋n个微小差异的初值，得到n个混沌变量， (2) 并将它们作为遗传种群引入遗传算法，即：设问题(2)的可行域为2，并令Z⊥(x,y, 月.k+1=cx,k(1-月.k), 入，：，=1，，p),则问题(2)可简单表示为： x:=c十d3.k+1,i=1,2,…,n (10) F(Z)=(F1(Z,…,FM(Z)(3) 式中，k为种群序号，n为种群规模，初值不能取利用线性加权和法将其转化为单目标规划问题：为不动点0,0.25,0.5,0.75,1.c,d:为变换常哭ghF(Z)=goF(Z) (4) 数，变换后的混沌变量的变化范围为相应的优化 0=(,…,ωM) (5) 变量的取值范围，其中，0为权系数，且编码的实质是在问题的解空间与算法的搜索会9=10 空间之间建立一个映射，为获得更好的性能，本 (6) 文个体编码采用实数编码方式，这种方式下，每问题(4)~(6)的最优解就是原问题(2)的有效解个个体用一个n维的实向量来表示，具有直观、或弱有效解快捷的优点，容易提高解的精度对于有约束优化问题： 2.3混沌遗传算法的基本步骤 minf(x) Step1初始化控制参数.设定种群规模 st.g(x)≤0，j=1,2,…,me M,交叉概率P。,变异概率Pm,最大进化代数 (7) hj(x)=0,j=1,2,…,mb gm,m,遗传搜索粒度0，遗传搜索代数T,最佳适 x=(x1,x2,…,xn) 应度连续保持代数h,混沌迭代次数k,混沌扰动概率P,混沌扰动量△r,混沌吸引子α. 采用1精确罚函数法，将问题(7)转化为以罚函 Step2按式(10)生成初始种群.以式(8)作数为目标函数的无约束最优化问题：为适应度函数，计算各个个体的适应度值F:置 min F(x)= p=1,t=0. fx+4mx(0,g(x)+214(x] Step3对当前种群进行交叉、变异操作.交叉的方法是对每个个体X,根据[0,1]区间的随 (8) 机数r与交叉概率P。的关系，若r<P。则个体其中为罚因子， X参加交叉操作，选出参加交叉的一组个体后

1∙2 问题的等价简化［69］为求全局最优解在引入混沌遗传算法（CGA）之前先将二层多目标规划问题转化为等价的一般多目标规划问题进而将其化为单目标最优化问题．定理设问题（1）中 f igi 均为 yi 的连续可微凸函数则对任意固定的 x该问题与以下的多目标决策问题等价： min xyλμ F（ xy） s．t． G（ xy）≤0 λ T i ∇yif i（ xyi）＋μ T i ∇yigi（ xyi）＝0 μ T i gi（ xyi）＝0 gi（ xyi）≤0 ∑ mi j＝0 λj i＝1 μi≥0λi≥0 i＝1…p （2）设问题（2）的可行域为 Ω并令 Z≜（ xy λiμii＝1…p）则问题（2）可简单表示为： min Z∈Ω F（ Z）＝min Z∈Ω （F1（ Z）…FM（ Z））（3）利用线性加权和法将其转化为单目标规划问题： min Z∈Ω hF（ Z）＝min Z∈Ω ωF（ Z）（4） ω＝（ω1…ωM）（5）其中ω为权系数且 ∑ M j＝1 ωj＝1ωj≥0 （6）问题（4）～（6）的最优解就是原问题（2）的有效解或弱有效解．对于有约束优化问题： min f （ x） s．t．gi（ x）≤0j＝12…me hj（ x）＝0j＝12…mb x＝（ x1x2…x n）（7）采用 l1 精确罚函数法将问题（7）转化为以罚函数为目标函数的无约束最优化问题： minF（ x）＝ f （ x）＋α ∑ me i max（0gi（ x））＋ ∑ mb j ｜hj（ x）｜（8）其中 α为罚因子． 2 混沌遗传优化算法 2∙1 混沌遗传优化方法求解问题的基本思路本文求解问题的思路是利用混沌优化策略引导种群进化将混沌状态引入到优化变量中并把混沌运动的遍历范围放大到优化变量的取值范围；把得到的混沌变量进行编码根据适者生存的原则对其进行遗传算子操作；然后给各个混沌变量附加一混沌小扰动通过逐代不断进化最后收敛到一个最适合环境的个体上求得问题的最优解． 2∙2 混沌机制与编码方式考虑 Logistic 混沌映射即： g∶βk＋1＝αβk（1—βk）βk∈［01］k＝12… （9）其中α为吸引子当 α＝4时Logistic 映射为满映射系统处于完全混沌状态．式（9）产生的序列｛βk｝为混沌变量．利用混沌变量对初值的敏感性赋 n 个微小差异的初值得到 n 个混沌变量并将它们作为遗传种群引入遗传算法即： βik＋1＝αxik（1—βik） xi＝ci＋ dβi ik＋1i＝12…n （10）式中k 为种群序号n 为种群规模初值不能取为不动点00∙250∙50∙751．cidi 为变换常数变换后的混沌变量的变化范围为相应的优化变量的取值范围．编码的实质是在问题的解空间与算法的搜索空间之间建立一个映射．为获得更好的性能本文个体编码采用实数编码方式．这种方式下每个个体用一个 n 维的实向量来表示具有直观、快捷的优点容易提高解的精度． 2∙3 混沌遗传算法的基本步骤 Step1 初始化控制参数．设定种群规模 M交叉概率 Pc变异概率 Pm最大进化代数 gnm遗传搜索粒度 θ遗传搜索代数 T最佳适应度连续保持代数 h混沌迭代次数 k混沌扰动概率 Pr混沌扰动量Δr混沌吸引子 α． Step2 按式（10）生成初始种群．以式（8）作为适应度函数计算各个个体的适应度值 Fi；置 p＝1t＝0． Step3 对当前种群进行交叉、变异操作．交叉的方法是对每个个体 X根据［01］区间的随机数 r 与交叉概率 Pc 的关系若 r＜ Pc 则个体 X 参加交叉操作．选出参加交叉的一组个体后 Vol．28No．7 郭兴众等：一类二层多目标规划的混沌遗传优化算法及其应用 ·697·

.698 北京科技大学学报 2006年第7期随机进行配对，为了保持群体的多样性，采用正 25, 交叉算子，由两个父辈交叉操作产生一组个体，从 mi3x,2(y-10) 新个体和两个父辈中选择最优的进入下一代 st.-x十y≤0,0≤x≤15 群体。 4入(x+2y-30)十2y+1-h2=0 以变异概率P按适当的变异方式对选中的 1y=0,2(y-15)=0,0≤y≤15 个体变异，实数编码方式下，变异操作对个体X 入1十λ2=1，λ1≥0，λ2≥0,1≥0，h2≥0 的每个分量作用一个随机偏差量，即 (13) xi=x:十6，i=1,2,…,n (11) 用线性加权和法将问题(13)转化为单目标问题：置p=p十1，t=t十1，如果t<T转Step3,否则 i吧(x2+(0-103) 转Step4. st.一x十y≤0,0≤x≤15 Step4对经过T次遗传搜索后得到的第T 4入(x+2y一30)十2y+H1一2=0 代种群X(T)={x1,x2,…,xm}中适应度较高的 41y=0,(y-15)=0,0≤y≤15 部分个体进行混沌扰动.选取满足个体适应度大入十λ2=1，入1≥0，λ2≥0,1≥0，h2≥0 于种群平均适应度的个体进行混沌扰动，混沌扰 (14) 动的幅度控制参数随着迭代次数增加而变小.混进而由式(8)将式(14)化为以下无约束优化问题：沌扰动的方法是，对于选出要进行混沌扰动的个 minF(x,y,,入2，h1,2)= 体的每一个分量，根据[0,1]区间的随机数r与 (x2+(y-10)3)十a[max(0,-x+y)十混沌扰动概率P的关系，若r<P,则该分量需 max(0,x-15)+max(0,-x+15)+ 要进行混沌扰动操作，设x:对应取值范围是 max(0,y-15)+max(0,-y+15)+ [ai,b:],那么x:演变为 |4入(x十2y-30)十y十h1-凸|+ x:=a:十a(b:-a)月+1(1-B+1). |+2-1] (15) 其中，月+1是Logistic映射，混沌吸引子a=4,B 基于本文提出的混沌遗传优化算法，取O≤x =十△r二a为混沌初始值，△：为一微小随机 ≤15,0≤y≤15,0≤入≤1,0≤λ2≤1,0≤H1≤ biai 量，取值为0到△r的随机数 20,0≤凸2≤20，种群规模M=30,杂交概率P.= Step5对混沌扰动后的变量进行迭代计 0.8,变异概率Pm=0.02,遗传搜索粒度0=100，算.若经过扰动后得到的个体X:适应度小于混遗传搜索代数T=50,混沌迭代次数k=1000,混沌扰动前的个体X:的适应度，即F(X)< 沌扰动概率P=0.1,混沌扰动量△r=0.05,最 F(X:),那么用X:代替X,否则保留原个体X:· 佳适应度保持代数h=10,最大进化代数gm,m= 200.利用MATLAB编程求解，计算结果为：x= 置t=0,转Step3. 4.7953,y=4.9832,=0.0768,2=0.9231, Step6检查结束条件.如果进化代数p= H1=0,2=0,最小值hmim=48.1632. g,m,或者连续进化h代后，个体最优值F= minF保持不变，则寻优过程结束， 4结论 3 算例给出了用混沌遗传算法求解一类二层多目标规划问题的方法，该方法将两层问题转化为单层以求解二层多目标规划问题为例：问题，利用遗传算法和混沌优化方法各自优点，克 m8,-10 服了传统遗传算法进行问题求解存在的早熟收敛 st.一x十y≤0,0≤x≤15 的缺点，对提高问题解的质量和效率有较好的效 min(x+2y-30)2,(x+0.5y2) 果，算例计算结果表明，该方法能实现规划问题的全局优化，有效地收敛到最优解或近似最优解， st.0≤y≤15 对处理此类规划问题是可行的， (12) 根据定理1将问题(12)化为等价的单级多目标规参考文献划问题： [1]Rendrs J.FlasseS P.Hybrid methods using genetic algorithms

随机进行配对．为了保持群体的多样性采用正交叉算子由两个父辈交叉操作产生一组个体从新个体和两个父辈中选择最优的进入下一代群体．以变异概率 Pm 按适当的变异方式对选中的个体变异．实数编码方式下变异操作对个体 X 的每个分量作用一个随机偏差量即 xi＝ xi＋δi＝12…n （11）置 p＝ p＋1t＝t＋1如果 t＜ T 转 Step3否则转 Step4． Step4 对经过 T 次遗传搜索后得到的第 T 代种群 X （ T）＝｛x1x2…xm｝中适应度较高的部分个体进行混沌扰动．选取满足个体适应度大于种群平均适应度的个体进行混沌扰动．混沌扰动的幅度控制参数随着迭代次数增加而变小．混沌扰动的方法是对于选出要进行混沌扰动的个体的每一个分量根据［01］区间的随机数 r 与混沌扰动概率 Pr 的关系若 r＜ Pr则该分量需要进行混沌扰动操作．设 xi 对应取值范围是［ aibi］那么 xi 演变为 xi＝ ai＋α（ bi— ai）βk＋1（1—βk＋1）．其中βk＋1是 Logistic 映射混沌吸引子 α＝4β0 ＝ xi＋Δri— ai bi— ai 为混沌初始值Δri 为一微小随机量取值为0到Δr 的随机数． Step5 对混沌扰动后的变量进行迭代计算．若经过扰动后得到的个体 X′i 适应度小于混沌扰动前的个体 Xi 的适应度即 F （ X′i ）＜ F（ Xi）那么用 X′i 代替 Xi否则保留原个体 Xi．置 t＝0转 Step3． Step6 检查结束条件．如果进化代数 p＝ gnm或者连续进化 h 代后个体最优值 F ∗ ＝ minF 保持不变则寻优过程结束． 3 算例以求解二层多目标规划问题为例： min x 5 3 x 2 5 2 （ y—10） 2 s．t．— x＋y≤00≤ x≤15 min y （（ x＋2y—30） 2（ x＋0∙5y 2）） s．t． 0≤y≤15 （12）根据定理1将问题（12）化为等价的单级多目标规划问题： min xyλμ 5 3 x 2 5 2 （ y—10） 2 s．t．— x＋y≤00≤ x≤15 4λ1（ x＋2y—30）＋λ2y＋μ1—μ2＝0 μ1y＝0μ2（ y—15）＝00≤y≤15 λ1＋λ2＝1λ1≥0λ2≥0μ1≥0μ2≥0 （13）用线性加权和法将问题（13）转化为单目标问题： min xyλμ （ x 2＋（ y—10） 2） s．t．— x＋y≤00≤ x≤15 4λ1（ x＋2y—30）＋λ2y＋μ1—μ2＝0 μ1y＝0μ2（ y—15）＝00≤y≤15 λ1＋λ2＝1λ1≥0λ2≥0μ1≥0μ2≥0 （14）进而由式（8）将式（14）化为以下无约束优化问题： minF（ xyλ1λ2μ1μ2）＝（ x 2＋（ y—10） 2）＋α［max（0— x＋y）＋ max（0x—15）＋max（0— x＋15）＋ max（0y—15）＋max（0—y＋15）＋｜4λ1（ x＋2y—30）＋λ2y＋μ1—μ2｜＋｜λ1＋λ2—1｜］（15）基于本文提出的混沌遗传优化算法取0≤ x ≤150≤ y≤150≤λ1≤10≤λ2≤10≤μ1≤ 200≤μ2≤20种群规模 M＝30杂交概率 Pc＝ 0∙8变异概率 Pm＝0∙02遗传搜索粒度 θ＝100 遗传搜索代数 T＝50混沌迭代次数 k＝1000混沌扰动概率 Pr＝0∙1混沌扰动量Δr＝0∙05最佳适应度保持代数 h＝10最大进化代数 gnm＝ 200．利用 MATLAB 编程求解计算结果为：x＝ 4∙7953y＝4∙9832λ1＝0∙0768λ2＝0∙9231 μ1＝0μ2＝0最小值 hmin＝48∙1632． 4 结论给出了用混沌遗传算法求解一类二层多目标规划问题的方法．该方法将两层问题转化为单层问题利用遗传算法和混沌优化方法各自优点克服了传统遗传算法进行问题求解存在的早熟收敛的缺点对提高问题解的质量和效率有较好的效果．算例计算结果表明该方法能实现规划问题的全局优化有效地收敛到最优解或近似最优解对处理此类规划问题是可行的．参考文献［1］ Rendrs JFlasse S P．Hybrid methods using genetic algorithms ·698· 北京科技大学学报 2006年第7期