2022年改进遗传算法与粒子群优化算法及其对比分析 .pdf
《2022年改进遗传算法与粒子群优化算法及其对比分析 .pdf》由会员分享,可在线阅读,更多相关《2022年改进遗传算法与粒子群优化算法及其对比分析 .pdf(7页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、改进遗传算法与粒子群优化算法及其对比分析X任斌 , 丰镇平( 西安交通大学叶轮机械研究所, 710049, 西安 ) 摘要 进化算法作为一类新的优化搜索方法, 广泛应用于各种优化问题. 现对简单遗传算法进行了改进, 采用实值编码 ,并与模拟退火算法及基于适值排序和随机选择的方法相结合, 形成了改进遗传算法 . 同时还介绍了一种新的进化算法 ) 粒子群优化算法. 将这两种优化算法应用于函数优化, 并对优化结果进行了对比分析. 比较结果表明, 改进遗传算法和粒子群优化算法都可以在函数优化方面表现出较好的健壮性, 但在找寻最优解的效率上, 粒子群优化算法较好. 关键词 函数优化 , 改进遗传算法,
2、粒子群优化算法 中图分类号 O224; 文献标识码 A ; 文章编号 1672- 1292( 2002) 02- 0014- 070引言自然界经过数万年的演化, 存在的方式、 规律都是最优的. 所以 , 人们总是在找寻自然界的优化规律,发展形成所谓的进化算法, 并应用到各类优化问题, 如本文介绍的遗传算法以及近年兴起的粒子群优化算法就是借鉴自然界优化规律而产生的进化算法.遗传算法 ( Genetic Algorithm, 简称 GA) 是 20 世纪 70 年代由美国密歇根大学J. H. Holland 教授提出的 1, 它是一类基于自然选择和遗传学原理的有效寻优方法, 目前在很多方面都有成功
3、应用 1 4. 粒子群优化算法最初由Jim Kennedy 于 1995 年提出并成功地用于连续非线性函数的优化 5, 它是对鸟群觅食过程中的迁徙和聚集的模拟, 也可以说是对社会心理学的一种模拟. 粒子群优化算法对优化问题求解来说 , 最大特点就是收敛速度较快.工程优化应用的大多数问题,都需要先对其进行数学建模,即向数学问题转化, 然后对函数进行优化.工程优化所建立的数学函数, 往往是带有多种约束条件的复杂函数,而且大都是既不连续、 也不可微的隐函数 . 对于这些复杂函数来说, 用常规的数学方法很难或根本无法处理. 本文所涉及的这两种进化算法都能处理这类复杂函数的优化问题, 但由于算法的原理不
4、同, 在优化过程中所表现出来的特性和优点也会不同 . 为了了解两种算法的基本特点, 本文在对简单遗传算法改进的基础上, 通过一个较为典型的数学问题的优化, 对这两种进化算法的性态进行了对比分析, 以此来检验它们在工程优化中的有效性.1简单遗传算法及其改进研究遗传算法通过对参数的编码进行操作, 而不是对参数本身进行操作, 这使得它处理优化问题时, 既不要求函数连续, 更不要求可微 . 因此 , 这些函数既可以是数学解析式所表达的显函数, 也可以是映射矩阵甚至是神经网络等隐函数, 因而应用范围较广. 进一步 , 该方法通过目标函数来计算适配值,不需要其)14)第 2 卷第 2 期2002 年南京师
5、范大学学报( 工 程技术版 )JOURNAL OF NAN JING NORMAL UNI VERSIT Y( ENGINEERIN G AN D TECHNOL OGY)Vol. 2 No. 22002X收稿日期 :2002-09-111基金项目 :教育部高校骨干教师资助计划资助( GG - 807 -10698- 1016) 1作者简介 :任斌 , 1974-, 西安交通大学叶轮机械研究所博士研究生, 从事叶轮机械气动热力学优化研究1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
6、 1 页,共 7 页 - - - - - - - - - 它的推导和辅助信息,从而对问题的依赖较小.遗传算法是从许多初始点开始并行操作, 而不是从一个点开始 , 因而可以有效的防止搜索过程收敛于局部最优, 而且有较大的可能求得全部的最优解. 遗传算法具有并行计算的特点, 因而可通过大规模并行计算来提高计算速度. 上述特点使得遗传算法较适合复杂问题的优化 .图 1简单遗传算法( SGA) 计算流程图111简单遗传算法简单遗传算 法一般由编码机制、适应 值函数、 遗传算子、 控制参数等四个部分组成 1. 简单遗传算法由0 和 1 进行编码 , 0 和 1 称为基因 , 由基因组成二进制串, 二进制
7、串称为染色体 ( 或称之为个体) , 染色体与优化问题的解相对应,并通过编码和解码过程实现基因空间和解空间的转换.遗传算法中的优胜劣汰的评价标准是通过适应值函数来体现的, 通过适应值函数的好坏可以判断解的好坏, 从而判断染色体的优劣 . 对于优化问题, 适应值函数是目标函数. 遗传算法中的遗传算子(genetic operator) 主要有三种 : 交叉算子(crossover)、 变异算子(mutation) 、 选择算子(selection).交叉和变异算子就是在算法中采用何种交叉和变异策略,即采用单点或是多点交叉或变异. 选择算子也称复制算子(reproduction) , 它的作用在于
8、根据个体的优劣程度决定它在下一代是被复制还是被淘汰.一般来说 , 通过选择 , 适应值较高的个体有较大的复制机会; 而适应值较小的个体即低劣的个体在下一代中存在的几率也就较小. 简单遗传算法中的控 制参 数包 括, 染色体 的串 长 ( string ) 、 种群大 小(popsize)、 交叉概率 (pc) 、 变异概率 (pm) 、 最大遗传代数 ( maxgen)等.1. 2改进遗传算法本文在简单遗传算法的基础上, 通过采用实数编码机制, 并在遗传算子的改进等策略方面对简单遗传算法进行了改进.采用实数编码机制, 即直接在优化问题的解空间进行编码, 不但省去了基因空间与解空间之间的编码和解
9、码过程 , 而且可以提高解的精度及减少优化过程的计算量. 相应地 , 本文优化的二元函数采用如下的交叉和变异算子.交叉算子 : A*=A+ ( B-A) *X;B*=B+ ( A-B)* ( 1-X)变异算子 : A*=A* ( 1-X* ( 1-gen/maxgen) * * 2) ;B*=B*( 1-X*(1 -gen/ maxgen) * * 2).以上算子中 , X 为 0,1 之间的随机数 , gen、 maxgen 分别为进化的当前代数和最大代数. 以此实现从上代染色体 ( A, B) 到下代染色体 ( A*, B*) 的进化 .在对选择算子的改进方面, 本文采用如下的选择方法产生
10、下代种群.1 将杂交和变异产生的新染色体和父代所有染色体组合成新的被选种群;o 对被选种群按升序排列;? 删去所有重复的染色体;? 在被选种群中按顺序挑选两个染色体, 计算其概率min 1, exp( -$f / Tk) 当概率大于random0, 1 时, 接受前一染色体进入新种群, 否则 , 接受后一染色体进入新种群, 按照这种选择, 直到选择pop)15)任斌 ,等: 改进遗传算法与粒子群优化算法及其对比分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 7 页 -
11、 - - - - - - - - size个染色体组成新的种群.改进后的遗传算法, 由于采用了实数编码,避免了编码和解码的过程, 有利于提高计算效率.又由于采用了合并种群的排序、 剔除重复染色体以及在这个基础上的模拟退火原理的概率接受机制选择下代染色体 6, 这样 , 就可以以一定的概率接受较差解, 即适应值较差的染色体. 遗传算法在原理上是一种概率搜索方法 , 所以, 只要所给的种群足够大, 遗传代数足够多, 原则上它是可以找到最优值的, 但这必须以牺牲时间为代价;而且 ,遗传算法作为一种优化算法, 虽然其健壮性较好, 但遇到多峰函数的时候,有时候也难免收敛到局部最优值, 而不是全局最优值.
12、 存在这两种问题的原因, 往往是在选择的过程中,发生了有价值的染色体信息的丢失. 所以 , 以一定的概率接受较差解,就保证了种群的多样性,也保存了有价值的染色体信息,从而可以使搜索最优解的时间缩短且可以防止遗传算法收敛到局部最优解, 同时也增强了其健壮性.2粒子群优化算法粒子群优化算法是对鸟群觅食过程中的迁徙和群集的模拟 5, 7, 8. 鸟群在觅食时, 在它们找到有食物的地方之前的迁徙过程中, 既有分散又有群集的特点. 所谓鸟语花香,鸟也有鸟的语言, 它们总是通过自己一套独有的方式在无时无刻地相互传递着信息,其实 , 这种个体之间信息的交换在群居的生物群体中都存在 , 如蜜峰、蚂蚁 , 也包
13、括人类 . 对于鸟群来说,在它们找到食源之前的从一地到另一地的迁徙过程中, 总是有那么一只鸟对食物的嗅觉较好, 即对食源的大致方面具有较好的洞察力, 从而 , 这只鸟就拥有食源的较好信息. 由于在找寻食源的途中, 它们又在无时无刻地相互传递信息, 特别是这种较好的信息.所以 , 在这种/ 好消息 0的指引下 , 最终导致了鸟群/ 一窝蜂 0的奔向食源, 达到了在食源的群集. JimKennedy 从这种自然现象中受到启发,提出了粒子群优化算法.解群相当于一个鸟群, 一地到另一地的迁徙相当于解群的进化,/ 好消息 0相当于解群每代进化中的最优解, 食源相当于全局最优解.粒子群优化算法的数学抽象和
14、实现步骤如下:设定有 N 个解的解群 Xi d , i I 1, N , d I 1, M , d 为每个解的维数, 即每个解可以是个解向量.然后 ,对每个解定义一个速度矢量Vi, 该速度矢量相当于$Xi, 该速度矢量在第一代中与解群一样,是随机初始生成的. 对于进化的第k 代来说 , 对于每一个解向量来说,通过如下关系式生成下代解向量.Xi( k+ 1) =Xi( k) +Vi( k).( 1)其次 , 定义 pbest( personal best)和 gbest(global best) 分别代表个体k-1 代和 k 代的较好值和k 代解群中的最好值, 即 Xpbest, i和 Xgbe
15、st,i. 而 Xpbe st, i-Xi和 Xgbest, i-Xi分别表示每代个体解向量位置和个体最优位置及每代中最优个体位置的距离. 这种距离在速度矢量中体现. 如下式 :Vi( k + 1) =Vi( k) +G ( Xpbest, i-Xi)( 2)Vi( k + 1) =Vi( k) +G ( Xgbest, i-Xi)( 3)综合 ( 2) 式和( 3) 式可得到速度矢量的迭代变化:Vi( k + 1) =XVi( k) + C1G( Xpbest, i-Xi) + C2G ( Xgbest, i-Xi)( 4)这样 , 新解可以这样产生:Xi( k+ 1) =Xi( k) +V
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年改进遗传算法与粒子群优化算法及其对比分析 2022 改进 遗传 算法 粒子 优化 及其 对比 分析
限制150内