群体智能算法求函数极值.doc-资料库

zhiwen11-9246765-4744302543442380877.doc.pdf-第1页.png

第1页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第2页.png

第2页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第3页.png

第3页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第4页.png

第4页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第5页.png

第5页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第6页.png

第6页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第7页.png

第7页 / 共23页

zhiwen11-9246765-4744302543442380877.doc.pdf-第8页.png

第8页 / 共23页

河孕育文明，海凝聚智慧水资源系统优化方法大作业 ——群体智能算法学院专业班级学号姓名指导老师 1

河孕育文明，海凝聚智慧目录一、题目简介.............................................................................................3 1.1 题目.................................................................................................3 1.2 测试函数.........................................................................................3 二、粒子群算法简介.................................................................................5 2.1 粒子群算法起源.............................................................................5 2.2 粒子群算法的基本原理.................................................................5 2.3 粒子群算法的基本步骤................................................................6 三、遗传算法简介.....................................................................................7 3.1 遗传算法起源.................................................................................7 3.2 遗传算法的基本原理.....................................................................7 3.3 遗传算法的基本步骤.....................................................................8 四、结果分析.............................................................................................9 4.1 f1:Sphere Model function 函数................................................... 9 4.2 f2:Goldstein-Price function 函数.............................................. 10 4.3 f3:Schwefel function 函数.........................................................11 4.4 f9:多个全局最优点函数........................................................... 12 4.5 总体分析....................................................................................13 五、附录................................................................................................... 15 1 .Genetic Algorithm program............................................................ 15 2 POS program....................................................................................20 2

河孕育文明，海凝聚智慧一、题目简介 1.1 题目试用群体智能算法（任选 2 种）编程求解以下给定的试验函数极值。要求（1）群体智能算法包括：遗传算法、粒子群算法、蚁群算法等；（2）写出算法的起源、基本算法的原理、算法的基本步骤；（3）用 VB 或 VC 或 Fortran 编程求解、并附源程序；（4）对结果进行分析比较；（5）可以对方法进行改进。（至少选用 3 个测试函数进行测试） 1.2 测试函数在给出的 10 个函数里面，我选取了较为简单的 f1、f2、f3、f9 四个函数作为本次粒子群算法和遗传算法的测试函数。（1）f1:Sphere Model functio f 1 l  i 1  2 , x i x i  ]12.5,12.5[ 这里，l 为函数的维数。该函数是凸函数，有唯一的全局最小值 f )0(1  0 2 f （2）f2：Goldstein-Price function 函数 2 3 14 x x    1 2 2 12 48 x x   1 2 (1[ )1 x x   2 1 2( 30[ )3 x x    1 2 ],2,2[ x x   2 1 19( 14 x   1 32 18( x   1 ]2,2[ 2 2 2 6 xx 21 36   xx 21 3 )] x 2 27 x  2 2 )] 该函数有若干个极小值点，全局最小值为: f )1,0(2  3 （3）f3：Schwefel function f 3 l   i 1  x i  ( Sin x i ,) x i [  ]500,500 这里，l 为函数的维数。该函数的全局最小值为: 9687 , ; 9829 l  .420 .418  ) * ( xf 3 * x i i  ,2,1 l ，该函数的全局最优点在搜索空间的边缘，并与次最优解相距甚远，搜索算法极易收敛到错误的方向。 3

河孕育文明，海凝聚智慧（4）f9：多个全局最优点函数 f 9  4(  1.2 x 2  1 3 4 x 2 ) x  xy  4( 2 4 y 2 ) y ,  10  x  ,10  10  y  10 9f 有 6 个局部极小点, 全局极小点为（- 0.0898，0.7126）和(0.0898，-0.7126)，最小值为 –1.031628。此次水资源系统优化方法大作业，我将选用基本遗传算法和粒子群算法两种群体智能算法，简要介绍两种算法的起源、基本原理和基本步骤；用 4 个测试函数进行测试，对 4 个测试函数逐一进行分析，并用 matlab 作图进行辅助分析，并有一个总体的结果比较分析，得出两种算法在求解函数极值这方面的优缺点。附录附上粒子群算法和遗传算法的代码。由于本人能力有限，对遗传算法理解的不到位，虽然在编程过程中也请教了很多学长学姐，但是在报告中仍然存在很多不足之处，也未能想出更好的方法对遗传算法和粒子群算法存在的问题进行改进，希望王老师见谅，也十分感谢王老师在这次作业中给予我们的指导以及对我们无知的包容。 4

河孕育文明，海凝聚智慧二、粒子群算法简介 2.1 粒子群算法起源粒子群算法(Particle Swarm Optimization,PSO)是一种基于种群搜索策略的自适应随机优化算法,它是在 1995 年由 Eberhart 博士和 Kennedy 博士共同提出的,源于对鸟群捕食行为的模仿,通过群体中个体之间的协作和信息共享来寻找最优解。它是继 GA 和 ACO 之后的又一新的基于种群搜索策略的群智能优化算法,现已发展成为进化计算的一个重要分支。PSO 算法的主要来源思想可以描述为在鸟群的飞行过程中,每只鸟在开始时处于随机位置,各自朝着不同的方向飞行,但是随着飞行时间的推移,在开始处于随机位置下的鸟会通过相互的跟踪学习逐渐聚集在一个小群落内,并且以同样旳速度飞向同一个方向,这样最终整个鸟群都会聚集在同一个位置一一即食物所在的位置。粒子群算法因其概念简单、参数较少、实现容易等特点,自提出以来就受到国内外研究者的高度重视并被广泛应用于许多领域。 2.2 粒子群算法的基本原理 PSO 算法是一种新颖的群智能优化算法,其思想来源是对鸟群觅食行为的模仿。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集,其行为不可预测,但其整体总保持一致性,个体与个体之间也保持着最适宜的距离。通过对类似生物群体行为的研究,发现生物群体中存在着一种社会信息共享机制,它为群体的进化提供了一种优势,这也就是 PSO 算法形成的基础。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解． PSO 算法中,每个优化问题的解都是搜索空间中的一个粒子,所有的粒子都有一个由被优化的函数决定的适应度值,每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。该算法初始化为一群随机粒子(随机解),把优化问题的每一个解视为一个粒子，粒子就相当于鸟群中的鸟儿。用适应度函数来衡量每个粒子解的优越程度，即与最佳解的接近程度。然后随机给定各粒子的初始速度，让它们在解空间中以一定的速度飞行，在计算过程中这个速度会根据其本身的飞行经验和其他粒子的飞行经验来动态调整，经过不断寻找，这些粒子会在全空间内达到发现最优解的 5

河孕育文明，海凝聚智慧目的。每个粒子在解空间的搜索过程中同时向两个点接近，第一个点被称为全局极值，是整个粒子群在历代搜索过程中所找到的最优解，另一个点则被称为个体极值，是每个粒子在历代搜索过程中自身所找到的最优解。通过一段时间的迭代搜索后，一个全局最佳的粒子解就会产生。 2.3 粒子群算法的基本步骤 Step1:初始化一群微粒(群体规模为 m)，给定各参数的初始值,在指定的优化范围内初始化种群中每个粒子的速度和位置;初始化加速因子 Ci、C 和惯性权重参数； Step2:评价每个微粒的适应度； Step3:对每个微粒，将其适应值与其经过的最好位置 pbest 作比较，如果较好，则将其作为当前的最好位置 pbest; Step4:对每个微粒，将其适应值与其经过的最好位置 gbest 作比较，如果较好，则将其作为当前的最好位置 gbest; Step5:根据速度更新公式和位置更新公式调整微粒速度和位置； Step6：未达到结束条件则转 Step2。具体流程图如下： 6

河孕育文明，海凝聚智慧三、遗传算法简介 3.1 遗传算法起源遗传算法（Genetic Algorithm，简称 GA）最早由美国密歇根大学的 Holland 教授提出，起源于上世纪 60 年代对自然和人工自适应系统的研究。遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。上世纪 70 年代，De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，上世纪 80 年代由 Goldberg 进行归纳总结，形成了遗传算法的基本框架。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。 3.2 遗传算法的基本原理遗传算法的基本内容如下：个体和种群。个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。适应度与适应度函数。适应度(fitness)就是借鉴生物个体对环境的适应程度 ,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数（fitness function）就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。染色体与基因。染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如个体上 9，染色体的表示形式是 1001，0 和 1 是染色体上的基因。遗传操作。也称为遗传算子，就是关于染色体的运算。遗传算法中有三种遗传操作：选择-复制，交叉和变异。遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点 7

河孕育文明，海凝聚智慧集。这样一代代的不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素是：参数编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。 3.3 遗传算法的基本步骤 (1)随机产生初始种群 X(0)={X1(0),X2(0),……，Xµ(0)} 作为父代种群，令 k=0 (2)计算种群 X(k)中每一个个体的适应值，并对个体进行编码； (3)从种群 X(k)中选择µ/2 对个体进入交配池； (4)对交配池中的每个个体进行交叉，产生两个新个体； (5)对每个新个体依变异概率 Pm 进行变异，并把变异后的个体作为下一代种群 X(k+1)的个体，令 k=k+1 (6)判断是否满足收敛准则，若满足，则计算结束；否则转(2)。（遗传算法基本流程图） 8

资料库

群体智能算法求函数极值.doc

相关推荐

课程资源

热门标签

最新资料