数学建模遗传算法和粒子群算法

1、遗传算法（遗传算法（Genetic AlgorithmGA），是模拟达尔文的），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国美国Michigan大学的大学的J.Holland教授于教授于1975年首先提出年首先提出的遗传算法作为一种新的全局优化搜索算法，以其简单的遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为奠定了它作为21世纪关键智能计算之一的地位世纪关键智能计算之一的地位1.遗传算法的基本原理遗传算法的

2、基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程它把问题的参数用基因代表，把问题的解用染色体代表程它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体这个群体在问题特定的环境里生染色体的个体组成的群体这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代后代随机化地存竞争，适者有最好的机会生存和产生后代后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续继承了父代的最好特征，并也在生存环

3、境的控制支配下继续这一过程群体的染色体都将逐渐适应环境，不断进化，最这一过程群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的后收敛到一族最适应环境的类似个体，即得到问题最优的解值得注意的一点是，现在的遗传算法是受生物进化论学解值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）说尚有争议） 序号序号遗传学概念遗传学概念遗传算法概念遗传算法

4、概念数学概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间0,1上的一个值，一般为0.650.9011

5、变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值, 一般为0.0010.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解2、遗传算法的具体步骤、遗传算法的具体步骤： 第一步：选择编码策略，把参数集合（可行解集合）转换第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间；染色体结构空间； 第二步：定义适应函数，便于计算适应值；第二步：定义适应函数，便于计算适应值； 第三步：确定遗传策略，包括选择群体大小，选择、交叉、第三步：确定遗传策略，包括选择群体大小，选择、交叉、变

6、异方法以及确定交叉概率、变异概率等遗传参数；变异方法以及确定交叉概率、变异概率等遗传参数； 第四步：随机产生初始化群体；第四步：随机产生初始化群体； 第五步：计算群体中的个体或染色体解码后的适应值；第五步：计算群体中的个体或染色体解码后的适应值； 第六步：按照遗传策略，运用选择、交叉和变异算子作用第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；于群体，形成下一代群体； 第七步：判断群体性能是否满足某一指标、或者是否已完第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策成预定的迭代次数，不满足则返回第五步、或者修改遗传

7、策略再返回第六步略再返回第六步产生初始群体是否满足终止条件得到结果结束程序是否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体2( )20.5,max( ) 1,2f xxxf xx 已知求，（1）编码和产生初始群体）编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把到首先第一步要确定编码的策略，也就是说如何把到2这个区间内的数用计算机语言表示出来编码时要注这个区间内的数用计算机语言表示出来编码时要注意以下意以下 三个原则：三个原则： 完备性：问题空间中所有点（潜在解）都能成为完备性：问题空间中

8、所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；编码空间中的点（染色体位串）的表现型； 健全性：健全性：GA编码空间中的染色体位串必须对应问题编码空间中的染色体位串必须对应问题空间中的某一潜在解；空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应非冗余性：染色体和潜在解必须一一对应（1）编码和产生初始群体）编码和产生初始群体通过采用二进制的形式来解决编码问题，将某个变量通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个值代表的个体表示为一个0，1二进制串当然，串二进制串当然，串长取决于求解的精度如果要设定求解精度到六位小长取决于求解的精度如果要设定求

9、解精度到六位小数，由于区间长度为数，由于区间长度为3，则必须将闭区间，则必须将闭区间-1,2分为分为3*10(6)等分因为等分因为 所以编码的二进制串至少需要所以编码的二进制串至少需要22位位21622209715223 1024194304 2( )20.5,max( ) 1,2f xxxf xx 已知求，将一个二进制串（将一个二进制串（b21b20b19b1b0）转化为区间内）转化为区间内对应的实数值很简单，只需采取以下两步：对应的实数值很简单，只需采取以下两步：1）将一个二进制串（）将一个二进制串（b21b20b19b1b0）代表的二）代表的二进制数化为进制数化为10进制数：进制数：2）

10、 对应的区间内的实数：对应的区间内的实数：例如，一个二进制串例如，一个二进制串a=表示实数表示实数0.637197 二进制串二进制串，则分别表示区间的两个，则分别表示区间的两个端点值端点值-1和和22121 20 191 02100()(2 )iiib b bbbbx222( 1)121xx 222=(1000101110110101000111) =22889673122889670.63719721xx 利用这种方法完成了遗传算法的第一步利用这种方法完成了遗传算法的第一步编码，这种二编码，这种二进制编码的方法完全符合上述的编码的三个原则进制编码的方法完全符合上述的编码的三个原则首先我们来随

11、机的产生一个个体数为首先我们来随机的产生一个个体数为4个的初始群体如下：个的初始群体如下：pop(1)=， % a1， % a2， % a3 % a4化成十进制的数分别为：化成十进制的数分别为：pop(1)= 1.523032，0.574022 ，-0.697235 ，0.247238 接下来我们就要解决每个染色体个体的适应值问题了接下来我们就要解决每个染色体个体的适应值问题了 （2）定义适应函数和适应值）定义适应函数和适应值 由于给定的目标函数在内的值有正有负，所以必须通过建由于给定的目标函数在内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非立适应函数与目标

12、函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础也为以后计算各个体的入选概率打下基础 对于本题中的最大化问题，定义适应函数，采用下述方法：对于本题中的最大化问题，定义适应函数，采用下述方法：式中既可以是特定的输入值，也可以是当前所有代或最近式中既可以是特定的输入值，也可以是当前所有代或最近K代代中的最小值，这里为了便于计算，将采用了一个特定的输入中的最小值，这里为了便于计算，将采用了一个特定的输入值值minmin( ), ( )0( )0,f xFf xFg x若其他

13、 若取若取Fmin=-1，则当，则当 时适应函数时适应函数 ；当；当时适应函数时适应函数 由上述所随机产生的初始群体，我们可以先计算出目标函由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下数值分别如下f pop(1)= 1.226437 , 1.318543 , -1.380607 , 0.933350 然后通过适应函数计算出适应值分别如下然后通过适应函数计算出适应值分别如下gpop(1)= 2.226437 , 2.318543 , 0 , 1.933350 ( )1f x ( )2g x ( )1.1f x ( )0.g x （3）确定选择标准）确定选择标准这里用到了适应值的

14、比例来作为选择的标准，得到的每个个这里用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率其计算公式如下：体的适应值比例叫作入选概率其计算公式如下：对于给定的规模为对于给定的规模为n的群体的群体pop= ，个体的适应值，个体的适应值为为 ，则其入选概率为，则其入选概率为 由上述给出的群体，计算出各个个体的入选概率首先由上述给出的群体，计算出各个个体的入选概率首先然后分别用四个个体的适应值去除以然后分别用四个个体的适应值去除以 得：得：P(a1)=2.226437 / 6.478330 = 0.343675 % a1P(a2)=2.318543 / 6.478330 = 0

15、.357892 % a2P(a3)= 0 / 6.478330 = 0 % a3P(a4)=1.933350 / 6.478330 = 0.298433 % a4123,naa aa1( )( ),1,2,3,( )isiniig aP aing a41()6.478330iig a41()6.478330iig a( )ig a （4）产生种群）产生种群 计算完了入选概率后，就将入选概率大的个体选入种计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群群，得到与原群体大

16、小同样的种群由初始群体的入选概率我们淘汰掉由初始群体的入选概率我们淘汰掉a3，再加入，再加入a2补足成与补足成与群体同样大小的种群得到群体同样大小的种群得到newpop(1)如下：如下：newpop(1)=， % a1， % a2， % a2 % a4 （5）交叉）交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体体，然后得到新的染色体组，组成新的群体 我们把之前得到的我们把之前得到的newpop(1)的四个个体两两组成一对，的四个个体两两组成一对，重复的不配对，进行交叉（可以在任一位进行交叉）重复

17、的不配对，进行交叉（可以在任一位进行交叉） 通过交叉得到了四个新个体，得到新的群体通过交叉得到了四个新个体，得到新的群体jchpop (1)如如下：下：jchpop(1)=，1101011101001100011110，1000011001010001000010，1000011001010001000010 0110101001101110010101 这里采用的是单点交叉的方法，当然还有多点交叉的方法，这里采用的是单点交叉的方法，当然还有多点交叉的方法，这里就不着重介绍了这里就不着重介绍了 （6）变异）变异变异也就是通过一个小概率改变染色体位串上的某个基变异也就是通过一个小概率改变染色体位

18、串上的某个基因现把刚得到的因现把刚得到的jchpop(1)中第中第3个个体中的第个个体中的第9位改变，就位改变，就产生了变异，得到了新的群体产生了变异，得到了新的群体pop(2)如下：如下：pop(2)= ， 然后重复上述的选择、交叉、变异直到满足终止条件为止然后重复上述的选择、交叉、变异直到满足终止条件为止 （7）终止条件）终止条件 遗传算法的终止条件有两类常见条件：（遗传算法的终止条件有两类常见条件：（1）采用设定最）采用设定最大（遗传）代数的方法，一般可设定为大（遗传）代数的方法，一般可设定为50代，此时就可能得代，此时就可能得出最优解此种方法简单易行，但可能不是很精确（出最优解此种方法

19、简单易行，但可能不是很精确（Matlab程序参见附录程序参见附录1）；（）；（2）根据个体的差异来判断，通过计算）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控种群中基因多样性测度，即所有基因位相似程度来进行控制制 粒子群算法粒子群算法(particle swarm optimization(particle swarm optimization，PSO)PSO)由由KennedyKennedy和和EberhartEberhart在在19951995年提出，该算法模年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作拟鸟集群飞行觅食的行为，鸟之间通过集

20、体的协作使群体达到最优目的，是一种基于群智能的优化方使群体达到最优目的，是一种基于群智能的优化方法。法。 PSOPSO的优势在于简单容易实现同时又有深刻的智的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。并且没有许多参数需要调整。 1 PSO算法简介 James Kennedy received the Ph.D. degree from the University of North Carolina, Chapel Hill, in 1992. He is with the U.S. D

21、epartment of Labor, Washington, DC. He is a Social Psychologist who has been working with the particle swarm algorithm since 1994. Russell C. Eberhart (M88SM89F01) received the Ph.D. degree in electrical engineering from Kansas State University, Manhattan. He is the Chair and Professor of Electrical

22、 and Computer Engineering, Purdue School of Engineering and Technology, Indiana UniversityPurdue University Indianapolis (IUPUI),Indianapolis, IN. 2 PSO产生背景之一：复杂适应系统产生背景之一：复杂适应系统 CAS CAS理论的最基本的思想可以概述如下理论的最基本的思想可以概述如下： 我们把系统中的成员称为具有适应性的主体，我们把系统中的成员称为具有适应性的主体，简称为主体。所谓具有适应性，就是指它能够与简称为主体。所谓具有适应性，就是指它能够与

23、环境以及其它主体进行环境以及其它主体进行交流交流，在这种交流的过程，在这种交流的过程中中“学习学习”或或“积累经验积累经验”，并且根据学到的经，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。都是在这个基础上出现的。 CASCAS的四个基本特点：的四个基本特点：n首先，主体首先，主体(Adaptive Agent)(Adaptive Agent)是主

24、动的、活的实体；是主动的、活的实体； n其次，个体与环境其次，个体与环境( (包括个体之间包括个体之间) )的相互影响，相互的相互影响，相互作用，是系统演变和进化的主要动力；作用，是系统演变和进化的主要动力；n再次，这种方法不象许多其他的方法那样，把宏观和再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；微观截然分开，而是把它们有机地联系起来；n最后，这种建模方法还引进了随机因素的作用，使它最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。具有更强的描述和表达能力。 2 PSO产生背景之二产生背景之二:人工生命人工生命 人工生命人工生命

25、“是来研究具有某些生命基本特征的是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：人工系统。人工生命包括两方面的内容： 研究如何利用计算技术研究生物现象；研究如何利用计算技术研究生物现象； 研究如何利用生物技术研究计算问题。研究如何利用生物技术研究计算问题。 现在我们讨论另一种生物系统：社会系统，更确切现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做的互动行为，也可称做 群智能群智能 。 3 基本基本PSO算法算法 粒子群优化算法源于粒子群优化算法源于19871987年年

26、ReynoldsReynolds对鸟群社会系对鸟群社会系统的仿真研究。在鸟群中，一群鸟在空中飞行，每个鸟遵统的仿真研究。在鸟群中，一群鸟在空中飞行，每个鸟遵守以下三条规则：守以下三条规则： 1 1）避免与相邻的鸟发生碰撞冲突；）避免与相邻的鸟发生碰撞冲突； 2 2）尽量与自己周围的鸟在速度上保持协调和一致；）尽量与自己周围的鸟在速度上保持协调和一致； 3 3）尽量试图向自己所认为的群体中靠近。）尽量试图向自己所认为的群体中靠近。 仅通过使用这三条规则，鸟群系统就出现非常逼真的仅通过使用这三条规则，鸟群系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们群体聚集行为，鸟成群地在

27、空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。会分开绕行而过，随后又会重新形成群体。 ReynoldsReynolds仅仅将其作为仅仅将其作为CASCAS的一个实例作仿真的一个实例作仿真研究，而并未将它用于优化计算中。研究，而并未将它用于优化计算中。 KennedyKennedy和和EberhartEberhart在中加入了一个特定点，在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真寻找食源的现

28、象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。间寻优中。 PSOPSO中，每个优化问题的解都是搜索空间中的一中，每个优化问题的解都是搜索空间中的一只鸟。称之为只鸟。称之为“粒子粒子”。所有的粒子都有一个由被优。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索优粒子在解空间中搜索. . PSO PSO 初始化为一群随机粒子。然后通过迭代找到最

29、初始化为一群随机粒子。然后通过迭代找到最优解。在每一次叠代中，粒子通过跟踪两个优解。在每一次叠代中，粒子通过跟踪两个 极值极值 来来更新自己。第一个就是粒子本身所找到的最优解。这更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值个解叫做个体极值pBestpBest. . 另一个极值是整个种群目前另一个极值是整个种群目前找到的最优解。这个极值是全局极值找到的最优解。这个极值是全局极值gBestgBest。 PSOPSO算法数学表示如下：算法数学表示如下： 设搜索空间为设搜索空间为D D维，总粒子数为维，总粒子数为n n。第。第i i个粒子位个粒子位置表示为向量置表示为向量X Xi i

30、= =( ( x xi1i1, x, xi2i2, x, xiDiD ) )；第；第i i个粒子个粒子 “飞行飞行”历史中的过去最优位置为历史中的过去最优位置为P Pi i= =( ( p pi1i1,p,pi2i2,p,piDiD ) )，其中第，其中第g g个粒子的过去最优位个粒子的过去最优位置置P Pg g为所有为所有P Pi i ( ( i=1, ,n i=1, ,n) )中的最优；第中的最优；第i i个粒子的个粒子的位置变化率（速度）为向量位置变化率（速度）为向量V Vi i= =( (v vi1i1, v, vi2i2, v, viDiD) )。每个粒子的位置按如下公式进行变化（每

31、个粒子的位置按如下公式进行变化（“飞行飞行”）：）：(1)( )(1)11idididxtxtvtindD（1）（2）其中，其中，C C1,C21,C2为正常数，称为加速因子；为正常数，称为加速因子；randrand( )( )为为00，11之间的随机数；之间的随机数；w w称惯性因子，称惯性因子，w w较大适于对解较大适于对解空间进行大范围探查，空间进行大范围探查，w w较小适于进行小范围开挖。较小适于进行小范围开挖。第第d d（1 1ddD D）维的位置变化范围为）维的位置变化范围为-XMAXd , -XMAXd , XMAXdXMAXd，速度变化范围为，速度变化范围为-VMAXd , VMAXd-VMAXd , VMAXd，迭代中，迭代中若位置和速度超过边界范围则取边界值。若位置和速度超过边界范围则取边界值。 12(1)( )( )( )( )( )( )( )ididididg didvtwvtcra n dptxtcra n dptxt 粒子群初始位置和速度随机产生，然后按公粒子群初始位置和速度随机产生，然后按公式式(1)(2)(1)(2)进行迭代，直至找到满意的解。目前，进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群常用的粒子群算法将全体粒子群(Global)(Glob