《数学建模遗传算法和粒子群算法》由会员分享，可在线阅读，更多相关《数学建模遗传算法和粒子群算法（34页珍藏版）》请在金锄头文库上搜索。
1、遗传算法遗传算法遗传算法（Genetic AlgorithmGA），是模拟达尔文的 遗传选择和自然淘汰的生物进化过程的计算模型，它是由美 国Michigan大学的J.Holland教授于1975年首先提出的遗 传算法作为一种新的全局优化搜索算法，以其简单通用、鲁 棒性强、适于并行处理及应用范围广等显著特点，奠定了它 作为21世纪关键智能计算之一的地位1.遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过 程它把问题的参数用基因代表，把问题的解用染色体代表 （在计算机里用二进制码表示），从而得到一个由具有不同 染色体的个体组成的群体这个群体在问题特定的环境里生 存竞争，适者有最
2、好的机会生存和产生后代后代随机化地 继承了父代的最好特征，并也在生存环境的控制支配下继续 这一过程群体的染色体都将逐渐适应环境，不断进化，最 后收敛到一族最适应环境的类似个体，即得到问题最优的解 值得注意的一点是，现在的遗传算法是受生物进化论学说 的启发提出的，这种学说对我们用计算机解决复杂问题很有 用，而它本身是否完全正确并不重要（目前生物界对此学说 尚有争议） 序号遗传遗传 学概念遗传遗传 算法概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码 中的元素5基因位某一基因在染色体中的位置元素在编码
3、中的位置6适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应 的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜 的个体， 淘汰劣质个体的操作保留或复制适应值 大的可行解，去掉 小的可行解9交叉一组染色体上对应 基因段的 交换根据交叉原则产 生的一组新解10交叉概率染色体对应 基因段交换的概 率（可能性大小）闭区间0,1上的一个值，一般为 0.650.9011变异染色体水平上基因变化编码 的某些元素被改变12变异概率染色体上基因变化的概率（ 可能性大小）开区间(0,1)内的一个值, 一般为 0.0010.0113进化、 适者生存个体进
4、行优胜 劣汰的进化， 一代又一代地优化目标函数取到最大值，最优的可行解2、遗传算法的具体步骤：第一步：选择编码策略，把参数集合（可行解集合）转换 染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉 、变异方法以及确定交叉概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用 于群体，形成下一代群体；第七步：判断群体性能是否满足某一指标、或者是否已完 成预定的迭代次数，不满足则返回第五步、或者修改遗传策 略再返回第六步产生初始群体是否满足终止条件
5、得到结果结束程序是否计算每个个体的适应值以概率选择遗传算子选择一个个体复制 到新群体选择两个个体进行交叉插入 到新群体选择一个个体进行变异插入 到新群体得到新群体（1）编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把到2 这个区间内的数用计算机语言表示出来编码时要注 意以下 三个原则：完备性：问题空间中所有点（潜在解）都能成为GA 编码空间中的点（染色体位串）的表现型；健全性：GA编码空间中的染色体位串必须对应问题 空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应（1）编码和产生初始群体通过采用二进制的形式来解决编码问题，将某个变量 值代表的个体表示为一个0，1二进制串当然
6、，串 长取决于求解的精度如果要设定求解精度到六位小 数，由于区间长度为3，则必须将闭区间-1,2分为 3*10(6)等分因为 所以编码的二进制串至少需要22位将一个二进制串（b21b20b19b1b0）转化为区间内 对应的实数值很简单，只需采取以下两步： 1）将一个二进制串（b21b20b19b1b0）代表的二 进制数化为10进制数：2） 对应的区间内的实数：例如，一个二进制串a= 表示实数0.637197二进制串， ，则分别表示区间的两 个端点值-1和2利用这种方法完成了遗传算法的第一步编码，这种二 进制编码的方法完全符合上述的编码的三个原则 首先我们来随机的产生一个个体数为4个的初始群体如
7、下： pop(1)= ， % a1 ， % a2 ， % a3 % a4 化成十进制的数分别为： pop(1)= 1.523032，0.574022 ，-0.697235 ，0.247238 接下来我们就要解决每个染色体个体的适应值问题了（2）定义适应函数和适应值由于给定的目标函数在内的值有正有负，所以必须通过建 立适应函数与目标函数的映射关系，保证映射后的适应值非 负，而且目标函数的优化方向应对应于适应值增大的方向， 也为以后计算各个体的入选概率打下基础对于本题中的最大化问题，定义适应函数，采用下述方法 ：式中既可以是特定的输入值，也可以是当前所有代或最近K代 中的最小值，这里为了便于计算，
8、将采用了一个特定的输入 值若取Fmin=-1，则当 时适应函数 ；当 时适应函数由上述所随机产生的初始群体，我们可以先计算出目标函 数值分别如下 f pop(1)= 1.226437 , 1.318543 , -1.380607 , 0.933350 然后通过适应函数计算出适应值分别如下 gpop(1)= 2.226437 , 2.318543 , 0 , 1.933350 （3）确定选择标准 这里用到了适应值的比例来作为选择的标准，得到的每个个 体的适应值比例叫作入选概率其计算公式如下： 对于给定的规模为n的群体pop= ，个体的适应值 为 ，则其入选概率为由上述给出的群体，计算出各个个体的
9、入选概率首先然后分别用四个个体的适应值去除以 得： P(a1)=2.226437 / 6.478330 = 0.343675 % a1 P(a2)=2.318543 / 6.478330 = 0.357892 % a2 P(a3)= 0 / 6.478330 = 0 % a3 P(a4)=1.933350 / 6.478330 = 0.298433 % a4（4）产生种群计算完了入选概率后，就将入选概率大的个体选入种 群，淘汰概率小的个体，并用入选概率最大的个体补入种 群，得到与原群体大小同样的种群 由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与 群体同样大小的种群得到newpop(1
10、)如下： newpop(1)= ， % a1 ， % a2 ， % a2 % a4（5）交叉 交叉也就是将一组染色体上对应基因段的交换得到新的染色 体，然后得到新的染色体组，组成新的群体我们把之前得到的newpop(1)的四个个体两两组成一对， 重复的不配对，进行交叉（可以在任一位进行交叉）通过交叉得到了四个新个体，得到新的群体jchpop (1)如下 ： jchpop(1)= ，1101011101001100011110 ，1000011001010001000010 ，1000011001010001000010 0110101001101110010101这里采用的是单点交叉的方法，当
11、然还有多点交叉的方法， 这里就不着重介绍了（6）变异 变异也就是通过一个小概率改变染色体位串上的某个基因 现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生 了变异，得到了新的群体pop(2)如下： pop(2)= ， ， ， 然后重复上述的选择、交叉、变异直到满足终止条件为止（7）终止条件遗传算法的终止条件有两类常见条件：（1）采用设定最 大（遗传）代数的方法，一般可设定为50代，此时就可能得 出最优解此种方法简单易行，但可能不是很精确（Matlab 程序参见附录1）；（2）根据个体的差异来判断，通过计算 种群中基因多样性测度，即所有基因位相似程度来进行控制 粒子群算法(par
12、ticle swarm optimization， PSO)由Kennedy和Eberhart在1995年提出，该算法模 拟鸟集群飞行觅食的行为，鸟之间通过集体的协作 使群体达到最优目的，是一种基于群智能的优化方 法。PSO的优势在于简单容易实现同时又有深刻的智 能背景，既适合科学研究，又特别适合工程应用， 并且没有许多参数需要调整。 1 PSO算法简介 粒子群算法粒子群算法James Kennedy received the Ph.D. degree from the University of North Carolina, Chapel Hill, in 1992. He is with
13、 the U.S. Department of Labor, Washington, DC. He is a Social Psychologist who has been working with the particle swarm algorithm since 1994. Russell C. Eberhart (M88 SM89F01) received the Ph.D. degree in electrical engineering from Kansas State University, Manhattan. He is the Chair and Professor o
14、f Electrical and Computer Engineering, Purdue School of Engineering and Technology, Indiana UniversityPurdue University Indianapolis (IUPUI),Indianapolis, IN. 2 PSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下：我们把系统中的成员称为具有适应性的主体 ，简称为主体。所谓具有适应性，就是指它能够 与环境以及其它主体进行交流，在这种交流的过 程中“学习”或“积累经验”，并且根据学到的 经验改变自身的结构和行为方式。整个系
15、统的演 变或进化，包括新层次的产生，分化和多样性的 出现，新的、聚合而成的、更大的主体的出现等 等，都是在这个基础上出现的。 CAS的四个基本特点：n首先，主体(Adaptive Agent)是主动的、活的实体；n其次，个体与环境(包括个体之间)的相互影响，相互 作用，是系统演变和进化的主要动力；n再次，这种方法不象许多其他的方法那样，把宏观和 微观截然分开，而是把它们有机地联系起来；n最后，这种建模方法还引进了随机因素的作用，使它 具有更强的描述和表达能力。 2 PSO产生背景之二:人工生命 人工生命“是来研究具有某些生命基本特征的 人工系统。人工生命包括两方面的内容： 研究如何利用计算技术
16、研究生物现象； 研究如何利用生物技术研究计算问题。现在我们讨论另一种生物系统：社会系统，更确切 地说，是由简单个体组成的群落与环境以及个体之间 的互动行为，也可称做“群智能“。3 基本PSO算法 粒子群优化算法源于1987年Reynolds对鸟群社会系 统的仿真研究。在鸟群中，一群鸟在空中飞行，每个鸟遵 守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，鸟群系统就出现非常逼真的 群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们 会分开绕行而过，随后又会重新形成群体。 Reynolds仅仅将
