文档库 最新最全的文档下载
当前位置:文档库 › 遗传算法在微带天线优化中的应用

遗传算法在微带天线优化中的应用

遗传算法在微带天线优化中的应用
遗传算法在微带天线优化中的应用

遗传算法在微带天线优化中的应用

杨 帆,张雪霞

(清华大学电子工程系,北京100084)

摘 要: 本论文将遗传算法成功地应用到微带天线的优化中.论文中详细讨论微带天线采用遗传算法进行优化

的一些基本问题,如基因串的定义,遗传算法与矩量法的结合,适应度函数的设计以及控制参数的选择等.最后,论文成功地应用遗传算法,优化出宽带天线,带宽由初始5%展宽到1616%;并优化出双频工作天线,双频比为1∶1131,而且具有同向的线极化.

关键词: 遗传算法;微带天线;矩量法;宽带天线;双频天线中图分类号: T N821+191 文献标识码: A 文章编号: 037222112(2000)0920091205

The Application of Genetic Algorithms in Micro strip Antenna Optimization

Y ANG Fan ,ZH ANG Xue 2xia

(Dept.o f Electronic Engineering ,Tsinghua University ,Beijing 100084,China )

Abstract : G enetic alg orithms (G As )are success fully applied to the optimization of microstrip antenna design.This paper dis 2cusses s ome basic problems in this application thoroughly ,such as the definition of genetic series ,the combination of G As and method of m oment ,the design of fitness function and the selection of control https://www.wendangku.net/doc/6c3253759.html,ing G As ,a wide band microstrip antenna is de 2signed ,the bandwidth expands from 5%to 1616%.A dual frequency antenna is als o optimized.The ratio of these tw o frequencies is 1

∶1131and both frequencies have the same linear polarization.K ey words : genetic alg orithms ;microstrip antennas ;m oment of method ;broadband antenna ;dual frequency antenna

1 引言

遗传算法是一类借鉴生物界遗传机制进行随机搜索的优

化算法[1].作为一种新的全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理等显著特点吸引了许多研究者的注意.其主要特点是群体搜索策略和群体中个体之间的信息交换,其搜索不依赖于梯度信息.由于上述特点,遗传算法已经在组合优化

、图像处理、系统识别等众多领域得到成功的应用,而且其应用范围也越来越广.

微带天线近年来受到极大关注,发展迅速.与其他天线相比,它具有以下优点:体积小,重量轻,剖面低,容易与载体共形;电性能多样化,容易实现多种极化、多频工作等要求;平面结构,易于与馈线,匹配网络,固体器件等集成,降低成本.但它也具有一些缺点,如频带窄,损耗大,效率低等.设计合适形式的微带天线,使其克服缺点,发挥优势,是微带天线设计中的一个主要内容.

随着微带天线设计理论的不断发展,遗传算法也开始应用到微带天线的设计中来[2].通过遗传算法的优化设计,可以得到合适形状的微带天线,满足某些特定的性能要求.本论文中将遗传算法成功地应用到微带天线的优化中,讨论了遗传算法应用到微带天线的优化中的一些具体问题,如基因串的定义,适应度的设计以及控制参数的选择等;并利用遗传算

法,分别优化出了具有宽带特性和双频特性的微带天线,克服了微带天线窄带的缺点,实现了微带天线电性能的多样化.

2 微带天线设计中的遗传算法优化

本文中,主要讨论对微带天线形状的优化.其基本问题如下图所示:

图1 微带天线贴片初始形状及优化后的形状

微带天线贴片的初始形状是一个矩形.将矩形贴片划分

为若干个小的矩形单位贴片,如图1左侧.通过优化,保留其中的一些贴片,去除其中的一些贴片,图中,打“×”的贴片代表要去除的贴片,得到优化后的贴片形状如图1右侧.从物理意义上理解,去除这些贴片等效于在天线这个谐振腔中加入合适的电感,电容或匹配元件,从而实现要求的特性.

收稿日期:1999206208;修回日期:2000204220

 

第9期2000年9月

电 子 学 报

ACT A E LECTRONICA SINICA V ol.28 N o.9

Sep. 2000

 

遗传算法优化的基本流程如图2所示:

 图2 遗传算法的

基本流程

遗传算法是一种群体型操作,该操作以群体中的所有个体为对象.选择(selection )、交叉(cross over )和变异(mutation )是遗

传算法的三个主要操作算子,它们构成了所谓的遗传操作,使遗传算法具有了其它传统方法没有的特点.将遗传算法应用到微带天线的研究中,主要要解决的几个问题包括:基因串的定义,遗传算法与矩量法的结合,适应度函数的设计,控制参数的选择等等.下面就这些问题逐一进行讨论.

211 基因串的定义如前所述,在微带天线的优

化问题中,待优化的参数是天线的形状.而遗传算子操作的是二进制的基因串.因此必须将天线的形状映射为合适的基因串.从图1中可以看出,优化所得到的天线,实际是将原天线去掉某些矩形单元得到的.具体的过程就是,首先将天线的矩形贴片划分为若干个小矩形单元,如图3,是42(7×6)

个矩形单元.然后通过优化程序,确定哪些单元应该保留,那些单元应该去掉.最后得到优化后的天线.这个过程提示我们,可以将每一个矩形单元对应于基因串的每一位,实现从贴片形状到基因串的映射,即自然空间到遗传空间的转化.图3给出了一个这样转化,即编码的例子.

图3 微带天线形状的编码

从图中可以看出,将天线的形状转化为一个二进制的7×6的基因矩阵.当矩形单元要保留时,对应位上的代码定义

为1;反之,当矩形单元要去除时,对应位上的代码定义为0.然后将这个矩阵按行的顺序写成一串,就得到了一个基因串.这样,就将天线的形状转化为对应的基因串.而且,这种映射是一对一的,即给定一个天线的形状,必然可以写出唯一的一个基因串与其相对应;同样给出一个基因串,也必然可以画出唯一的一种天线形状对应于这个基因串.212 遗传算法与矩量法的结合这里采用基于全波分析的矩量法对微带天线进行分

[3]

.应用矩量法,可以对微带天线得到比较精确的分析结

果.但应用矩量法进行分析的一个缺点就是计算时间比较长.而导致时间长的主要原因在于Z 矩阵的填充要花费很长时间,因为Z 矩阵的每个元素都要通过多重积分得到.因此,在优化中,如果对不同形状的天线贴片均分别填充Z 矩阵,那

么整个优化的时间是不可想象的.尤其遗传算法是以群体为操作对象,假设群体大小为64,那么一代分析的时间就接近于一个天线分析时间的64倍,这是实际条件无法允许的.实际应用中,采用矢量三角形基函数[4],并用下面的“母矩阵”技术[5]

,节约了计算时间.

基因矩阵中的每一个元素对应的是天线贴片上的每一个矩形单元;而矩量法矩阵中每个元素对应的是一个矢量三角形基函数.两者并不一样,但是存在一定的联系.图4给出了两者之间的一个对应关系.图4中去掉了带阴影的矩形.带阴影的矩形包括了五条边,即边界的四条边和中间的一条斜边,设这些边的编号分别为n 1,n 2,n 3,n 4,n 5.当这个矩形被去掉以后,根据物理意义,这五条边上也就自然没有法向电流.因此,解矩量方程的时候,电流系数向量I 中这几条边对应的电流系数应该为零.所以,新的贴片形状所对应的矩量方程中的矩阵可以由原矩阵去掉这些行和列得到,如图4中去掉n

1,n 2,n 3,n 4,n 5这五行五列.即可以将原来完整贴片的Z 矩阵理解为“母矩阵”,其他形状贴片的天线的Z 矩阵都可以由它们简单地去掉某些行和列得到,不需要重新计算就可以得到现在形状下的Z 矩阵.这样可以大大地节省Z 矩阵的计算时间,提高优化效率.

图4 基因矩阵与矩量法中Z 矩阵的关系

213 适应度函数的设计

适应度设计是遗传算法优化中的一个十分关键的问题.适应度设计的好坏直接关系到收敛速度和准确度.通过对个体适应度的评估,可以判断是否优化出需要的解;如果没有,可以以每个个体的适应度为根据,进行选择算子等遗传操作.

实际应用中,常采用待优化的目标函数作为适应度评估函数.下面以宽频带微带天线的优化为例说明适应度的设计.我们的目标是设计出一个输入阻抗带宽超过10%的微带天线.转化为具体的参数指标,即优化出在频率范围215-219G H z 内反射系数S 11<-10dB 的微带天线.当在带内选取三个频率点f 1,f 2,f 3作为抽样点,以其反射系数作为适应度.可以得到下面的适应度评估函数:

F =

|S 11(f 1)|+|S 11(f 2)|+|S 11(f 3)|

3

(1)其中,F 表示某一形状的天线对应的适应度值(Fitness ),其大小等于在三个抽样点的S 11的平均值.这里,S 11取dB 为单位,而且要加上绝对值,因为下面进行选择算子操作时,适应度必须为非负数.

实际应用中,还必须注意如下几个问题:

29 电 子 学 报2000年

(1)抽样点数目的选择.式1中选择了三个点作为抽样点.由于反射系数的曲线是连续变化的,因此一般情况下,如果这三个频率点的反射系数均小于-10dB的时候,整个频带内的反射系数都会小于-10dB.但是也有反射系数曲线变化很剧烈的情况,这样就必须取多个抽样点.另外,频带范围较大,三个频点难以概括整个频带的变化特性时,也需要取多个频率点.一般来说,抽样频率点的数目取得越多,计算得到的精度也会越高.但是由于计算的频点增加,整体的计算时间也会增加.

(2)反射系数作为适应度的补充.由于反射系数转化为以dB为单位的时候,是做了一次对数计算的,在天线匹配得很好的情况下,即反射系数很小的时候,反射系数转化为dB时其绝对值就会很大.这样,即使其它两个频率处的反射系数转化为dB很小,整体的适应度也可能还是比较大,甚至还要大于三个点都匹配的情况.因此,必须要对反射系数作为适应度做一补充:

|S11|=|S11|,

20,

 

|S11|Φ20

|S11|>20

(2)

(3)频率带外的限制.在宽带优化设计中,主要考虑的是带内的反射系数小于-10dB,对于带外没有什么限制.但是,在其它优化目标下,还必须考虑带外的限制,这一点类似于滤波器的带外衰减的要求.比如,当我们考虑优化双频工作的天线时,除了在指定的频率处反射系数比较小外,还要求在其它频率处没有谐振现象,即反射系数比较大.假设要工作的双频为f1,f2,要限制的频率为f3,则适应度函数可以定义为:

F1=〈|S11(f1)|+|S11(f2)|〉/2(3)

F2=20-|S11(f3)|(4)式中,F1,F2分别对应为通带和阻带的适应度值.

214 微带天线遗传算法优化中控制参数的讨论

微带天线中采用遗传算法进行优化过程中,有一些控制参数.合适地选取这些控制参数,可以提高优化的效率,得到更好的优化结果.几个主要的优化参数为:贴片去除的概率,群体的规模,遗传世代,变异概率.

(1)贴片去除的概率.初始群体是在遗传空间里采用随机的方法生成.在生成微带天线的初始群体时,有一个重要问题就是:基因矩阵中应该有多少个是零,或者说,被去除的矩形单元的概率是多少.显然,这个概率不能太大.因为如果被去除的单元过多,就失去了微带天线的特点了.而如果这个概率太小,就达不到调整天线输入阻抗的目的.实际应用中,取这个概率为1/5.

(2)群体的规模.遗传算法是一种并行算法,它同时处理整个群体.群体的规模大,则可以包含更多的基因模式,群体的多样性丰富.从图4中看出,天线被分为42个矩形单元,天线形状共有242个不同选择.只有取的群体规模比较大,才有可能得到较好的全局特性,避免陷入局部的极值.但是群体的规模越大,计算的时间也就越长,相应的收敛速度也就越慢.实际计算中,采用了规模为16,32,64和128的不同群体.当群体规模为16的时候,优化过程很快能收敛,但是没有得到合适的优化结果,这是由于基因型太少的原因.采用规模为128的群体时,收敛十分慢.但是,当计算到第四代群体的时候,已经有合适的个体产生.由于规模太大,这种群体每一代的计算时间都十分长.综合考虑计算时间和优化结果,最后选取大小为64的群体.

(3)遗传世代.遗传世代是指遗传的群体更新次数.一般来说,遗传的世代越多,得到的优化结果也就越好.一般的优化问题,优化终止有两种办法,一个是优化的结果收敛到某一优化值;另一个办法是优化结果已经达到了要求的指标从而结束优化过程.遗传世代是遗传算法中的一个控制优化次数,终止优化的参数.微带天线优化中,它主要受计算时间的限制.这个参数的设定一般与群体规模成反比.如当群体规模为16时,遗传世代选为32;而当群体规模为128时,遗传世代设为4.当然,遗传算法也可以同时采用另外两种优化终止的办法结束优化过程.

(4)变异概率.上一节中简单介绍了变异操作的实现方法.变异操作是遗传算法中一个十分微妙的操作.通过变异操作,可以产生原来群体中所不包含的基因模式,挖掘出群体的多样性,克服优化陷入局部解的危险,产生更好的优化结果.变异概率就是变异操作中的控制参数,变异概率如果取得太大,则选择操作和遗传操作的结果就会被破坏,失去了遗传算法的特点.如果变异概率取得过小,又难以产生新的基因模式.在计算中,设定变异概率为0102.对于大小为64,基因串长度为42的群体,所需要变异的位为54位.

3 微带天线的优化结果

利用遗传算法,对微带天线的形状进行了优化:针对微带天线窄带的缺点,设计了一幅宽带天线;同时设计了合适的微带天线形状,实现双频工作.图5给出了一个同轴微带天线的初始结构.

馈电点左侧均匀分成5×6个矩形片,右侧均匀分成2×6个矩形片,并将矩形片由左至右,由下而上进行统一编号.

图5 同轴馈电微带天线结构图

微带天线的参数为:

L=48mm,W=48mm,(x f,y f)=(36,24)mm

h0=412mm,εr0=1,h1=018mm,εr1=2165

311 宽频带微带天线

微带天线的一个很大缺点是其频带太窄.设计各种方法以展宽微带天线的频带,是微带天线研究中的一个热点问题.常用的方法是多谐振贴片的方法,即采用寄生的微带贴片,通过不同贴片的尺寸不同分别谐振于不同频率,来实现展宽频带的目的.近年来,通过设计合适的贴片形状来达到展宽频带

39

第 9 期杨 帆:遗传算法在微带天线优化中的应用

的文献也时有报道,比较突出的是U 形缝微带天线和平行双

槽微带天线.这里,采用第二种方法,即通过遗传算法对微带天线形状的优化功能,设计出合适的天线形式,实现宽带的要求.

优化目标:

在215~219G H z 频带内,反射系数小于-10dB .适应度函数:

F =

∑3

i =1

S i

/3

(6)

S i =|S 11(f i )|,20,

0,

 5Φ|S 11|Φ20|S 11|>20|S 11|<5

(7)

选取抽样点数目为3,频率分别为215,217和219G H z.这里,除了上限20dB 以外,当|S 11|小于5dB 时,设S 11=0,相当于对不匹配的形状加上一个惩罚项.

控制参数的选取:

贴片去除概率:p d =012;群体规模:N =64;遗传世代:8;变异概率

:0102.

经过优化,去除贴片(2,4,5,6,14,30,42),得到如图6所示的微带天线

:

图6 宽带微带天线形状

图7给出了天线反射系数曲线的实验值与理论值的对

比.从图中可以看到,微带天线的初始带宽为5%,而采用遗传算法优化后天线的带宽展宽为1616%.理论与实验结果符合得很好.312 双频工作微带天线

图7 宽带微带天线的反射系数.—?—?—初始形状天线的

S 11,———优化后天线的S 11(理论值),……优化后天线的S 11(实验值)

随着通信技术的发展,对天线的电性能也提出了许多应

用的要求.例如,在一幅天线上实现收发双工.区分收发最简

单的方法是频率区分的方法.让天线在收发的时候工作于不同频段,从而实现收发的分开.因此,设计合适的双频天线,是天线研究中的一个重要问题.微带天线的研究也遇到了这个问题,就是如何设计合适的形状,以使其工作于两个指定的频段.论文工作中,采用遗传算法优化,得到了一幅同时工作于219G H z 和318G H z 的微带天线.

优化目标:在219G H z 和318G H z 处,反射系数小于-10dB .

适应度函数:

F =

∑n

1

i =1

S i

n 1

+

∑n

2

i =1

(20-S i )

n 2

(8)

S i =|S 11(f i )|,20,

0,

 5Φ|S 11|Φ20|S 11|>20|S 11|<5

(9)

选取抽样点数目为5,通带频率为219G H z ,318G H z ;阻带

频率为217G H z 和313G H z 和4G H z .

控制参数的选取:

贴片去除概率:p d =012 群体规模:N =64遗传世代:5 变异概率:0102

经过优化,去除贴片(1,7,8,9,11,14,21,28,29,30,32,35,36,42),得到如图8所示的微带天线:

 图8 双频微带天线形状

图9给出了天线反射系数曲线的实验值与理论值的对比.从图中可以看到,初始形状的微带天线只有一个谐振频率,在2155G H z 处.经

过遗传算法优化后,天线实现了双频工作的目的.两个工作频率分别为219G H z 和318G H z ,双频比为1∶1131.图中看出,

理论和实验符合得很一致.

图9 双频微带天线的反射系数.—?—?—初始形状天线的

S 11,———优化后天线的S 11(实验值),……优化后天线的S 11(理论值)

图10给出了天线的极化曲线.从图中可以看出,在两个频率处极化方向一致,都是x 方向线极化.在实际应用中,有

49 电 子 学 报2000年

时需要同向的线极化.对于普通的同向线极化的双频工作,就必须同时激励起微带贴片下电磁场的一次模与三次模,但是这样双频比就很大,不可能达到如图9那么小的双频比(1∶1131).这也是这种形状双频天线的一个很好的特点

.

图10 双频天线的S 12曲线

4 结论

论文成功地在微带天线的设计中引入了遗传算法进行优

化,讨论了优化中的一些基本问题,如基因串的定义,遗传算法与矩量法的结合,适应度函数的设计以及控制参数的选择等.论文中还采用遗传算法,优化出不同形状的微带天线,分别具有宽带和双频的特点.宽带天线的设计克服了以往微带天线窄带的缺点,将天线带宽从5%扩展到1616%.双频天线的双频比为1∶1131,而且是同向的线极化.这两个例子充分说明了遗传算法在微带天线优化中的有效性.参考文献:

[1] 陈国良,等.遗传算法及其应用[M].北京:人民邮电出版社,

1996.

[2] J.M ichael Johns on ,Y ahya

Rahmat 2Samii.G enetic alg orithms in engi 2

neering electromagnetics [J ].IEEE AP M agazine ,1997,39(4):7-21.

[3] E.H.Newman ,P.Tulyathan.Analysis of microstrip antennas using m o 2

ment methods [J ].IEEE T rans.AP ,1981,29:47-53.

[4] S.M.Rao ,D.R.W ilton ,A.W.G liss on.E lectromagnetic scattering by

surfaces of arbitrary shape [J ].IEEE T rans.AP ,1982,30:409-418.

[5] J.M.Johns on ,Y.Rahmat 2Samii.G enetic alg orithms and method of M o 2

ments (G A/M oM ):A novel integration for antenna design [J ].IEEE AP 2s Digest ,1997:1664-1667.

作者简介:

杨 帆 分别于1997年,1999年获清华大学电子工程系学士、硕士学位.现在美国加州大学洛杉矶分校攻读博士学位.目前研究方向包

括:微带天线、光子带隙结构在天线中的应用以及电磁场数值解法.

张雪霞 清华大学电子工程系教授,中国电.1958年毕业于清华大学无线电电子学系,1959年-1961年为前苏联莫斯科动力学院访问学者.长期从事天线、微波技术、波导理论等方面的教学和科研工作.

(上接第107页)

[4] J.M.S ong ,W.C.Chew.Multilevel fast multipole alg orithm for s olving

combined field integral equation of electromagnetic scattering ,mi 2crowave and optical technology letters [C].10,1,September 1995:14-19.

[5] C.C.Lu ,W.C.Chew.A multilevel alg orithm for s olving boundary 2val 2

ue scattering [J ].M icro.Opt.T ech.Lett.July 1994,7(10):466-470.

[6] J.M.S ong ,C.C.Lu ,W.C.Chew ,et al.Introduction to fast Illinois

s olver code (FISC )[A].IEEE Proceedings of ′97Inter.Sym p.on An 2tennas and Propagation ,1997:48-51.

[7] R.L.W agner ,W.C.Chew.A ray 2propagation fast multipole alg orithm

[J ].M icrowave and Opt.T ech.Lett.,July 1994,7(10):435-438.

[8] J.S ong ,et al.Multilevel fast mutipole alg orithm for electromagnetic

scattering by large com plex objects [J ].IEEE T rans.Antennas and Propag.,1998,145(10):1488-1498.

[9] J.S ong ,et al.Fast illinois s olver code (FISC )[J ].IEEE Antennas and

Propag.M agazine ,June 1998,40(3):27-34.

[10] 胡俊,聂在平,姚海英,王浩刚,王军.多层快速多极子方法中的

树型算法[J ].电波科学学报,1999,14(增刊):99-102.

[11] 胡俊,聂在平,姚海英,王浩刚.用于复杂目标三维矢量散射的

一种高效数值方法[J ].电子学报,1999,27(6):104-109.

[12] 聂在平.面向实际工程应用的电磁场数值方法进展[J ].电波科

学学报,1999,14(增刊):155-158.

[13] 聂在平,胡俊.三维矢量电磁散射高效数值分析中新的迭代算

法[J ].电波科学学报,1999,14(增刊):99-102.

[14] Hu Jun ,Nie Z aiping.S olving electromagnetic scattering from tw o 2di 2

mensional cavity by FM M with com plexifying k technique [J ].M i 2crowave Optical T ech.Lett.,1999,3.

[15] A.Brandt.Multilevel com putations of integral trans forms and particle

interactions with oscillatory kernels [J ].C om put.Phys.C ommun ,1991,65:24-38.

[16] Vikram Jandhyala ,Balasubramaniam Shanker ,Eric M ichielssen ,W.C.

Chew.A combined steepest descent 2fast multipole alg orithm for the analysis of three 2dimensional scattering by rough surfaces [A ].1997Inter.IEEE Antennas and Propagat sym posium :2308-2311.

[17] W.C.Chew.W aves and Fields in Inhom ogeneous M edia [M].Van

N ostrand Reinhold ,New y ork.

5

9第 9 期杨 帆:遗传算法在微带天线优化中的应用

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作(选择、交叉、变异); 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题; 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图,上下两根黑条分别代表上电极和下电极,一般下电极接地,上电极接输入信号,电极之间是介质(如空气,陶瓷等)。微带电极的结构参数如图所示,W 、t 分别是上电极的宽度和厚度,D 是上下电极间距。当微波信号在微带线中传输时,由于趋肤效应,微带线中的电流集中在电极的表面,会产生较大的欧姆损耗。根据微带传输线理论,高频工作状态下(假定信号频率1GHz ),电极的欧姆损耗可以写成(简单起见,不考虑电极厚度造成电极宽度的增加): 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率, ρ为电阻率。可见电极的结构参数影响着电极损耗,通过合理设计这些参数可以使电极的欧姆损耗做到最小,这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个:W 、D 、t ,它们组成决策向量[W, D ,t ] T ,待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述: ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

遗传算法优化相关MATLAB算法实现

遗传算法 1、案例背景 遗传算法(Genetic Algorithm,GA)是一种进化算法,其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体。 在遗传算法中,染色体对应的是数据或数组,通常是由一维的串结构数据来表示,串上各个位置对应基因的取值。基因组成的串就是染色体,或者叫基因型个体( Individuals) 。一定数量的个体组成了群体(Population)。群体中个体的数目称为群体大小(Population Size),也叫群体规模。而各个个体对环境的适应程度叫做适应度( Fitness) 。 2、遗传算法中常用函数 1)创建种群函数—crtbp 2)适应度计算函数—ranking 3)选择函数—select 4)交叉算子函数—recombin 5)变异算子函数—mut 6)选择函数—reins 7)实用函数—bs2rv 8)实用函数—rep 3、主程序: 1. 简单一元函数优化: clc clear all close all %% 画出函数图 figure(1); hold on; lb=1;ub=2; %函数自变量范围【1,2】 ezplot('sin(10*pi*X)/X',[lb,ub]); %画出函数曲线 xlabel('自变量/X') ylabel('函数值/Y') %% 定义遗传算法参数 NIND=40; %个体数目 MAXGEN=20; %最大遗传代数 PRECI=20; %变量的二进制位数 GGAP=0.95; %代沟 px=0.7; %交叉概率 pm=0.01; %变异概率

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm—GA),是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是由美国Michigan大学的J.Holland教授于1975年首先提出的.遗传算法作为一种新的全局优化搜索算法,以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点,奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论,然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算.1.遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生存竞争,适者有最好的机会生存和产生后代.后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解.值得注意的一点是,现在的遗传算法是受生物进化论学说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法;故而在这个算法中要用到各种进化和遗传学的概念. 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系.这些概念如下: 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度, 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体, 淘汰劣质个体的操作保留或复制适应值大的可行解,去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率(可能性大小)闭区间[0,1]上的一个值,一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

用遗传算法解决0-1背包问题概述

实现遗传算法的0-1背包问题 求解及其改进 姓名: 学号: 班级: 提交日期:2012年6月27日

实现遗传算法的0-1背包问题求解 摘要:研究了遗传算法解决0-1背包问题中的几个问题: 1)对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性 2)对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法 3)对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4)一种最优解只向更好进化方法的尝试。 通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算,表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。 关键词:遗传算法;背包问题;优化 1.基本实现原理: 一、问题描述 0-1背包问题属于组合优化问题的一个例子,求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择合适的物品装入背包,使得背包中装入的物品的总价值最大。注意的一点是,背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或者不装入背包,即只能将物品i装入背包一次。称此类问题为0/1背包问题。 其数学模型为: 0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法(Genetic Algorithms)则是一种适合于在大量的可行解中搜索最优(或次优)解的有效算法。 二、遗传算法特点介绍: 遗传算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激增,发展起来的一种崭新的全局优化算法,它借用了生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。 基本遗传算法求解步骤: Step 1 参数设置:在论域空间U上定义一个适应度函数f(x),给定种群规模N,交叉率P c 和变异率P m,代数T; Step 2 初始种群:随机产生U中的N个染色体s1, s2, …, s N,组成初始种群S={s1, s2, …, s N},置代数计数器t=1; Step 3计算适应度:S中每个染色体的适应度f() ; Step 4 判断:若终止条件满足,则取S中适应度最大的染色体作为所求结果,算法结束。Step 5 选择-复制:按选择概率P(x i)所决定的选中机会,每次从S中随机选定1个染色体并将其复制,共做N次,然后将复制所得的N个染色体组成群体S1; Step 6 交叉:按交叉率P c所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体S2; Step 7 变异:按变异率P m所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体S3; Step 8 更新:将群体S3作为新一代种群,即用S3代替S,t=t+1,转步3;

遗传算法求解背包问题

遗传算法求解背包问题 信管专业李鹏 201101002044 一、遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。 二、背包问题描述 背包问题是一个典型的组合优化问题,在计算理论中属于NP完全问题,主要应用于管理中的资源分配,资金预算,投资决策、装载问题的建模。传统“0/1”背包问题可以描述为:把具有一定体积和价值的n件不同种类物品放到一个有限容量的背包里,使得背包中物品的价值总量最大。 三、数学模型 背包问题可以描述如下:假设有n个物体,其重量用表示,价值用表示,背包的最大容量为b。这里和b都大于0。问题是要求背包所装的物体的总价值最大。背包问题的数学模型描述如下: (1) (2) (3) 约束条件(3)中表示物体i被选入背包,反之,表示物体i没有被选入背包。约束条件(2)表示背包的容量约束。

四、使用遗传算法解决“0-1背包问题”的思路:0-1背包的解可以编码为一串0-1字符串(0:不取,1:取);首先,随机产生M个0-1字符串,然后评价这些0-1字符串作为0-1背包问题的解的优劣;然后,随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串,而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。 五、程序整体流程 (1)读取存取包的限种、商品的重要和价值的TXT文件; (2)初始化种群; (3)计算群体上每个个体的适应度值(Fitness) ; (4)评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi),适应度表示了该个体的性能好坏; (5)依照Pc选择个体进行交叉操作; (6)仿照Pm对繁殖个体进行变异操作 (7)没有满足某种停止条件,则转第3步,否则进入8 ; (8)输出种群中适应度值最优的个体。 六、代码 function Main() %定义全局变量 global VariableNum POPSIZE MaxGens PXOVER PMutation VariableNum=3 %变量个数 POPSIZE=50 %种群大小 MaxGens=1000 %种群代数 PXOVER=0.8 %交叉概率 PMutation=0.2 %变异概率 %读取数据文件

4遗传算法与函数优化

第四章遗传算法与函数优化 4.1 研究函数优化的必要性: 首先,对很多实际问题进行数学建模后,可将其抽象为一个数值函数的优化问题。由于问题种类的繁多,影响因素的复杂,这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外,大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次,如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多,影响因素复杂,若对各种情况都加以考虑进行试算,其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识,它们便于不同应用领域中的研究人员能够进行相互理解和相互交流,并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数,通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时,必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性,以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括: ●连续函数或离散函数; ●凹函数或凸函数; ●二次函数或非二次函数; ●低维函数或高维函数; ●确定性函数或随机性函数; ●单峰值函数或多峰值函数,等等。 下面是一些在评价遗传算法性能时经常用到的测试函数: (1)De Jong函数F1: 这是一个简单的平方和函数,只有一个极小点f1(0, 0, 0)=0。

(2)De Jong 函数F2: 这是一个二维函数,它具有一个全局极小点f 2(1,1) = 0。该函数虽然是单峰值的函数,但它却是病态的,难以进行全局极小化。 (3)De Jong 函数F3: 这是一个不连续函数,对于]0.5,12.5[--∈i x 区域内的每一个点,它都取全局极小值 30),,,,(543213-=x x x x x f 。

matlab、lingo程序代码3-背包问题(遗传算法)复习过程

背包问题---遗传算法解决 function Population1=GA_copy(Population,p,w0,w) %复制算子 %Population为种群 n=length(Population(:,1)); fvalue=zeros(1,n); for i=1:n fvalue(i)=GA_beibao_fitnessvalue(Population(i,:),p,w0,w); end fval=fvalue/sum(fvalue); F(1)=0; for j=1:n F(j+1)=0; for k=1:j F(j+1)=F(j+1)+fval(k); end end for i=1:n test=rand; for j=1:n if((test>=F(j))&&(test

POP(j,z)=Population(i,z); end POP(j,l+1)=i; p(j)=randint(1,1,[1 l-1]); j=j+1; end end k0=j-1; k=floor(k0/2); if k>=1 for m=1:k for t=p(2*m-1)+1:l s=POP(2*m-1,t); POP(2*m-1,t)=POP(2*m,t); POP(2*m,t)=s; end end for m=1:k0 for i=1:l Population1(POP(m,l+1),i)=POP(m,i); end end end function fitnessvalue=GA_fitnessvalue(x,p,w0,w) %使用惩罚法计算适应度值 %x为染色体 %p为背包问题中每个被选物体的价值 %w0为背包问题中背包总容积 %w为背包问题中每个被选物品的容积 l=length(x); for i=1:l a(i)=p(i).*x(i); end f=sum(a); b=min(w0,abs(sum(w)-w0)); for i=1:l wx(i)=w(i).*x(i); end if abs(sum(wx)-w0)>b*0.99 p=0.99;

遗传算法与组合优化.

第四章 遗传算法与组合优化 4.1 背包问题(knapsack problem ) 4.1.1 问题描述 0/1背包问题:给出几个尺寸为S 1,S 2,…,S n 的物体和容量为C 的背包,此处S 1,S 2,…,S n 和C 都是正整数;要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式: 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题:输入由C 和两个向量C =(S 1,S 2,…,S n )和P =(P 1,P 2,…,P n )组成。设X 为一整数集合,即X =1,2,3,…,n ,T 为X 的子集,则问题就是找出满足约束条件∑∈≤T i i C X ,而使∑∈T i i P 获得最大的子集T ,即求S i 和P i 的下标子集。 在应用问题中,设S 的元素是n 项经营活动各自所需的资源消耗,C 是所能提供的资源总量,P 的元素是人们从每项经营活动中得到的利润或收益,则背包问题就是在资源有限的条件下,追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下: 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题,其计算复杂度为O (2n ),若允许物件可以部分地装入背包,即允许X ,可取从0.00到1.00闭区间上的实数,则背包问题就简化为极简单的P 类问题,此时计算复杂度为O (n )。

4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模),T i (1≤i ≤n )=1表示该物件装入背包,T i =0表示不装入背包。基于背包问题有近似求解知识,以及考虑到遗传算法的特点(适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题),通常将P i ,S i 按P i /S i 值的大小依次排列,即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下,背包问题的目标函数和约束条件可表示如下。 目标函数:∑==n i i i P T T J 1 )( 约束条件:C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法,我们可构造背包问题的适应度函数f (T )如下式: f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数,惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值,β为合适的惩罚系数。 4.2 货郎担问题(Traveling Salesman Problem ——TSP ) 在遗传其法研究中,TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此,主要有以下几个方面的原因: (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全(NP-complete )问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此,快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准,而遗传算法 就其本质来说,主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究,对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。

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

遗传算法在多目标优化的应用:公式,讨论,概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法(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)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解,所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到

遗传算法求解0-1背包问题(JAVA)

遗传算法求解0-1背包问题 一、问题描述 给定n种物品和容量为C的背包。物品i的重量是wi,其价值为vi。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 二、知识表示 1、状态表示 (1)个体或染色体:问题的一个解,表示为n个比特的字符串,比特值为0表示不选该物品,比特值为1表示选择该物品。 (2)基因:染色体的每一个比特。 (3)种群:解的集合。 (4)适应度:衡量个体优劣的函数值。 2、控制参数 (1)种群规模:解的个数。 (2)最大遗传的代数 (3)交叉率:参加交叉运算的染色体个数占全体染色体的比例,取值范围一般为0.4~0.99。(4)变异率:发生变异的基因位数所占全体染色体的基因总位数的比例,取值范围一般为0.0001~0.1。 3、算法描述 (1)在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T; (2)随机产生U中的N个个体s1, s2, …, sN,组成初始种群S={s1, s2, …, sN},置代数计数器t=1; (3)计算S中每个个体的适应度f() ; (4)若终止条件满足,则取S中适应度最大的个体作为所求结果,算法结束。 (5)按选择概率P(xi)所决定的选中机会,每次从S中随机选定1个个体并将其染色体复制,共做N次,然后将复制所得的N个染色体组成群体S1; (6)按交叉率Pc所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体S2; (7)按变异率P m所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体S3; (8)将群体S3作为新一代种群,即用S3代替S,t = t+1,转步3。 三、算法实现 1、主要的数据结构 染色体:用一维数组表示,数组中下标为i的元素表示第(i+1)个物品的选中状态,元素值为1,表示物品被选中,元素值为0表示物品不被选中。 种群:用二维数组表示,每一行表示一个染色体。 具有最大价值的染色体:由于每一个染色体经过选择、交叉、变异后都可能发生变化,所以对于产生的新的总群,需要记录每个物品的选中状态。同时保存该状态下物品的最大价值,如果新的总群能够产生更优的值,则替换具有最大价值的染色体。

遗传算法多目标函数优化

多目标遗传算法优化 铣削正交试验结果 说明: 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)];

人工智能之遗传算法求解01背包问题实验报告

人工智能之遗传算法求解0/1背包问题实验报告 Pb03000982 王皓棉 一、问题描述: 背包问题是著名的NP完备类困难问题, 在网络资源分配中有着广泛的应用,已经有很多人运用了各种不同的传统优化算法来解决这一问题,这些方法在求解较大规模的背包问题时,都存在着计算量大,迭代时间长的弱点。而将遗传算法应用到背包问题的求解,则克服了传统优化方法的缺点,遗传算法是借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制。 遗传算法(GA)是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法,由美国J.Holland教授提出,其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息。因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛应用于组合优化,机器学习,自适应控制,规划设计和人工生命领域。 GA是一种群体型操作,该操作以群体中的所有个体为对象。选择,交叉和变异是遗传算法的三个主要算子,他们构成了遗传算法的主要操作,使遗传算法具有了其它传统方法所没有的特性。遗传算法中包含了如下五个基本要素:1 .参数编码,2.初始群体的设置,3.适应度函数的设计, 4.遗传操作设计,5.控制参数设定,这个五个要素构成可遗传算法的核心内容。 遗传算法的搜索能力是由选择算子和交叉算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力.而遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释。 二、实验目的: 通过本实验,可以深入理解遗传算法,以及遗传算法对解决NP问题的作用。 三、算法设计: 1、确定种群规模M、惩罚系数 、杂交概率c p、变异概率m P、染色体长度n及最大 max. 进化代数gen x=1表 2、采用二进制n维解矢量X作为解空间参数的遗传编码,串T的长度等于n, i x=0表示不装入背包。例如X={0,1,0,1,0,0,1}表示第2,4,7示该物件装入背包, i 这三个物件被选入包中。

遗传算法解决01背包问题

遗传算法解决01背包问题2015 ~2016 学年第二学期 学生姓名 专业 学号 2016年 6 月

目录 一:问题描述 (3) 二:遗传算法原理及特点 (3) 三:背包问题的遗传算法求解 (3) 1.文字描述 (3) 2.遗传算法中的抽象概念在背包问题的具体化 (3) 3.算法求解的基本步骤 (4) 四:算法实现 (4) 1.数据结构 (4) 2.部分代码 (5) 五:结论 (8) 六:参考文献 (8)

一、问题描述 0-1背包问题属于组合优化问题的一个例子,求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。 01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。问应如何选择合适的物品装入背包,使得背包中装入的物品的总价值最大。注意的一点是,背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时,对每种物品i只有两种选择:即装入背包或者不装入背包,不能讲物品i装入背包多次,也不能只装入部分的物品,称此类问题为0/1背包问题。 二、遗传算法原理及特点 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法有着鲜明的优点:(1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因而具有良好的并行性.(2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因而适用于任何规模,高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性.(3)遗传算法择优机制是一种“软”选择,加上良好的并行性,使它具有良好的全局优化性和稳健性.(4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码),目标函数解释为编码化个体(可行解)的适应值,因而具有良好的可操作性与简单性. 三、背包问题的遗传算法求解 1、文字描述 0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。在物品不是很多的时候用这些算法来处理背包问题效率上还是可以接受的,一旦物品过多(如50件物品)这些算法的效率就大打折扣了,因此采用一些智能的启发式搜索算法来处理就显得很有必要,遗传算法(Genetic Algorithms)则是一种适合于在大量的可行解中搜索最优(或次优)解的有效算法。 2、遗传算法中的抽象概念在背包问题的具体化 (1)基因:0或1,代表相应的商品选还是不选。 (2)染色体:本实验中固定有50个商品,所以染色体就是50个基因序列,也就是40个0、1串,代表了一种往包里装商品的组合。一个染色体例:0111101101011011110101110101010101011110。 (3)群体:一定数量的基因个体组成了群体(population),群体中个体的数量叫做群体大小。本实验的背包问题中,种群大小为100,代表100个往包里装商品的组合。 (4)适应度:各个个体对环境的适应程度叫做适应度。本实验的背包问题中,每染色体个体的适应度为选入包中的商品的价值和。

TSP问题的遗传算法求解 优化设计小论文

TSP问题的遗传算法求解 摘要:遗传算法是模拟生物进化过程的一种新的全局优化搜索算法,本文简单介绍了遗传算法,并应用标准遗传算法对旅行包问题进行求解。 关键词:遗传算法、旅行包问题 一、旅行包问题描述: 旅行商问题,即TSP问题(Traveling Saleman Problem)是数学领域的一个著名问题,也称作货郎担问题,简单描述为:一个旅行商需要拜访n个城市(1,2,…,n),他必须选择所走的路径,每个城市只能拜访一次,最后回到原来出发的城市,使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题,对于国际象棋棋盘中的64个方格,走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=(V,E),其中V是顶点集,E是边集,设D=(d ij)是有顶点i和顶点j之间的距离所组成的距离矩阵,旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1,v2,v3,...,vn}的一个访问顺序为T=(t1,t2,t3,…,ti,…,tn),其中ti∈V(i=1,2,3,…,n),且记tn+1= t1,则旅行商问题的数学模型为:min L=Σd(t(i),t(i+1)) (i=1,…,n) 旅行商问题是一个典型组合优化的问题,是一个NP难问题,其可能的路径数为(n-1)!,随着城市数目的增加,路径数急剧增加,对与小规模的旅行商问题,可以采取穷举法得到最优路径,但对于大型旅行商问题,则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用,在交通方面,如何规划合理高效的道路交通,以减少拥堵;在物流方面,更好的规划物流,减少运营成本;在互联网中,如何设置节点,更好的让信息流动。许多实际工程问题属于大规模TSP,Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP,Bland于1989年提出X-ray衍射问题对应于14000城市TSP,Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP,以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。

遗传算法的优化计算

function Val=de_code(x) % 全局变量声明 global S P_train T_train P_test T_test mint maxt global p t r s s1 s2 % 数据提取 x=x(:,1:S); [m,n]=find(x==1); p_train=zeros(size(n,2),size(T_train,2)); p_test=zeros(size(n,2),size(T_test,2)); for i=1:length(n) p_train(i,:)=P_train(n(i),:); p_test(i,:)=P_test(n(i),:); end t_train=T_train; p=p_train; t=t_train; % 遗传算法优化BP网络权值和阈值 r=size(p,1); s2=size(t,1); s=r*s1+s1*s2+s1+s2; aa=ones(s,1)*[-1,1]; popu=20; % 种群规模 initPpp=initializega(popu,aa,'gabpEval'); % 初始化种群 gen=100; % 遗传代数 % 调用GAOT工具箱,其中目标函数定义为gabpEval x=ga(aa,'gabpEval',[],initPpp,[1e-6 1 0],'maxGenTerm',gen,... 'normGeomSelect',0.09,'arithXover',2,'nonUnifMutation',[2 gen 3]); % 创建BP网络 net=newff(minmax(p_train),[s1,1],{'tansig','purelin'},'trainlm'); % 将优化得到的权值和阈值赋值给BP网络 [W1,B1,W2,B2]=gadecod(x); net.IW{1,1}=W1; net.LW{2,1}=W2; net.b{1}=B1; net.b{2}=B2; % 设置训练参数 net.trainParam.epochs=1000; net.trainParam.show=10; net.trainParam.goal=0.1; net.trainParam.lr=0.1; net.trainParam.showwindow=0;

遗传算法的0-1背包问题(c语言)

基于遗传算法的0-1背包问题的求解 摘要: 一、前言 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点,这不仅在于其内在的复杂性有着重要的理论价值,同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是,往往由于问题的计算量远远超出了计算机在有效时间内的计算能力,使问题的求解变为异常的困难。尤其对于NP 完全问题,如何求解其最优解或是近似最优解便成为科学的焦点之一。 遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型,作为一种新的全局优化搜索算法,它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点,奠定了作为21世纪关键智能计算的地位。 背包问题是一个典型的组合优化问题,在计算理论中属于NP-完全问题, 其 计算复杂度为 )2(O n ,传统上采用动态规划来求解。设w[i]是经营活动 i 所需要的资源消耗,M 是所能提供的资源总量,p[i]是人们经营活动i 得到的利润或收益,则背包问题就是在资源有限的条件下, 追求总的最大收益的资源有效分配问题。 二、问题描述 背包问题( Knapsack Problem)的一般提法是:已知n 个物品的重量(weight )及其价值(或收益profit )分别为0>i w 和0>i p ,背包的容量(contain )假设设为0>i c ,如何选择哪些物品装入背包可以使得在背包的容量约束限制之内 所装物品的价值最大? 该问题的模型可以表示为下述0/1整数规划模型: 目标函数:∑==n i i i n x c x x x f 1 21),,(max Λ ????? =∈≤∑=) ,2,1(}1,0{t .s 1n i x p x w i n i i i i Λ (*)

基于遗传算法的库位优化问题

Logistics Sci-Tech 2010.5 收稿日期:2010-02-07 作者简介:周兴建(1979-),男,湖北黄冈人,武汉科技学院经济管理学院,讲师,武汉理工大学交通学院博士研究生,研究方向:物流价值链、物流系统规划;刘元奇(1988-),男,甘肃天水人,武汉科技学院经济管理学院;李泉(1989-),男,湖北 武汉人,武汉科技学院经济管理学院。 文章编号:1002-3100(2010)05-0038-03 物流科技2010年第5期Logistics Sci-Tech No.5,2010 摘 要:应用遗传算法对邯运集团仓库库位进行优化。在充分考虑邯运集团仓库所存放的货物种类、货物数量、出入库频 率等因素的基础上进行库位预分区规划,建立了二次指派问题的数学模型。利用遗传算法对其求解,结合MATLAB 进行编程计算并得出最优划分方案。 关键词:遗传算法;预分区规划;库位优化中图分类号:F253.4 文献标识码:A Abstract:The paper optimize the storage position in warehouse of Hanyun Group based on genetic algorithm.With thinking of the factors such as goods categories,quantities and frequencies of I/O,etc,firstly,the storage district is planned.Then the model of quadratic assignment problems is build,and genetic algorithm is utilized to resolve the problem.The software MATLAB is used to program and figure out the best alternatives. Key words:genetic algorithm;district planning;storage position optimization 1 库位优化的提出 邯郸交通运输集团有限公司(简称“邯运集团”)是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购(天信运业及天昊、天诚、天恒等)、快递服务(飞马快运)、汽贸业务(天诚汽贸)及仓储配送(河北快运)等。其中,邯运集团的仓储配送业务由河北快运经营,现有仓库面积总共40000㎡,主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送,其中以医药为主。邯运集团库存货物主要涉及两个方面:一个是大宗的供应商货物,如医药,化工产品等;另一方面主要是大规模的小件快递货物,如日用百货等[1]。经分析,邯运集团在仓储运作方面存在如下问题: (1)存储货物繁多而分拣速度低下。仓库每天到货近400箱,有近200多种规格,缺乏一套行之有效的仓储管理系统。(2)货架高度不当而货位分配混乱。现在采用的货架高度在2米以上,而且将整箱货物直接码垛在货架上,不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子,增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的,分拣和搬运速度较慢。 (3)拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成,出库效率低,出错率难以控制。 (4)存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势,现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。 当前邯运集团的货位分配主要采用物理地址编码的方式,很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率,还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时,结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素,对仓库货位进行规划,以提高仓储效率。 2库位预分区规划 在进行仓库货位规划时,作如下假设: (1)货物的存放种类已知; (2)货物每种类的单位时间内存放的数量己知; (3) 每一种货物的存取频率已知。 在仓库货位优化中一个重要的环节即预分区。所谓预分区,是指没有存放货物时的分区,分区时只考虑仓储作业人员的速基于遗传算法的库位优化问题 Optimization of Storage Position in Warehouse Based on Genetic Algorithm 周兴建1,2,刘元奇1,李泉1 ZHOU Xing-jian 1,2,LIU Yuan-qi 1,LI Quan 1 (1.武汉科技学院经济管理学院,湖北武汉430073;2.武汉理工大学交通学院,湖北武汉430063) (1.College of Economics &Management,Wuhan University of Science &Engineering,Wuhan 430073,China; 2.School of Transportation,Wuhan University of Technology,Wuhan 430063,China) !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 38

相关文档
相关文档 最新文档