您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 第1章优化算法基本理论
智能优化算法第一章优化算法基本理论第二章神经网络基本理论第三章遗传算法基本理论第四章蚁群算法基本理论第五章蜂群算法基本理论第六章粒子群算法基本理论第七章鱼群算法基本理论第八章其他群智能优化算法课程结构及学时安排1.1优化的概念与方法1.1.1优化的概念1.1.2优化的一般数学模型1.1.3优化的分类1.1.4优化问题的求解方法1.1.5常用的无约束优化方法1.2智能优化的概念及分类1.2.1智能优化的概念1.2.2智能优化的分类1.3群体智能的概念及分类1.3.1群体智能的概念1.3.2群体智能的分类1.3.3群体智能的特点1.3.2群体智能算法的一般流程第1章优化算法基本理论1.1优化的概念及方法1.1.1优化的概念优化、最优化均是一个术语,是指关于求解一个问题的“最优”解的计算科学的一个分支,也就是从各种可能方案中选取一个最好的,以达到最优目标。从数学意义上说,最优化方法是一种求极值的方法,即在一组约束为等式或不等式的条件下,使系统的目标函数达到极值,即最大值或最小值。从经济意义上说,是在一定的人力、物力和财力资源条件下,使经济效果达到最大(如产值、利润),或者在完成规定的生产或经济任务下,使投入的人力、物力和财力等资源为最少。1.1优化的概念及方法优化技术是一种以数学为基础、用于求解各种工程问题优化解的应用技术。1.1.2优化的一般数学模型数学模型s.t.式中,,即为n维矢量,也称为决策变量;、和均为的函数,称为目标函数,称为等式约束函数,称为不等式约束函数;s.t.为英文subjectto的缩写,表示“受限制于”。对于求目标函数极大值的问题,可以转化为求极小值。1.1优化的概念及方法xminfmihi,,2,10x,pjgj,,2,10x,nTnxxxR,,,x21xxfxihxfxxihxjgxjg几个定义♣可行解:又称为可行点或容许解,是指满足约束条件的。♣可行域:又称为容许集,是指全体可行解构成的集合,即若和为连续函数,则D是闭集。♣最优解:一般分为整体最优解(总体最优解)、严格整体最优解、局部最优解、严格局部最优解。♣整体最优解:若,对于一切恒有,则称为最优问题的整体最优解。1.1优化的概念及方法xnjipjgmihDRx,,2,1,0x,,2,1,0xxxihxjgDxDxxxffx1.1优化的概念及方法♣严格整体最优解:若,对于一切和恒有,则称为最优问题的严格整体最优解。♣局部最优解:若,存在的某邻域(),使得对于一切,恒有,则称为最优问题的局部整体最优解。♣严格局部最优解:若,存在的某邻域(),使得对于一切,恒有,则称为最优问题的严格局部整体最优解。♣最优值:最优解对应的目标函数值称为最优值。DxDxxxffxxxDxxxeN0,xxxxeNxxeNDxxffxDxxxeN0,xxxxeNxxeNDxxffxxxf♣范数:在n维线性空间中,定义实函数,使其满足以下三个条件:①对于任意,有,当且仅当,;②对于任意及实数,有;③对于任意,有。则称函数为上的向量范数。♣p-范数:对于任意,,定义p-范数为1.1优化的概念及方法nRxDxDx0x0x0xaxxaaDy,xyxyxxnRnTnxxxR,,,x21p1pnipipx/11x♣∞-范数:♣2-范数:,通常记作整体最优解与局部最优解的关系整体最优解一定是局部最优解,而局部最优解不一定是整体最优解。1.1优化的概念及方法inix1maxx2/1122xniix21.1.3优化的分类根据约束条件分类♣无约束最优化问题:没有约束条件限制的最优化问题。♣约束最优化问题:有约束条件的最优化问题。约束最优化问题又可分为♣等式约束最优化问题:♣不等式约束最优化问题:♣混合约束最优化问题:既有等式约束,又有不等式约束最优化问题。即1.1优化的概念及方法mihi,,2,10xpjgj,,2,10xmihi,,2,10xpjgj,,2,10x1.1优化的概念及方法根据决策变量取值的状态分类♣连续最优化问题:决策变量取值是连续的优化问题。♣离散最优化问题:决策变量取值是离散的优化问题。根据决策变量取值的性质分类♣确定性最优化问题:每个决策变量取值是确定的。♣随机性最优化问题:某些决策变量取值是不确定的,但知道决策变量取某值而服从一定的概率分布。按照目标函数和约束函数的劳累性分类♣线性最优化问题:目标函数和所有约束条件中的函数都是决策变量的线性函数,即、和均为的线性函数。xfxihxjgx1.1优化的概念及方法♣非线性最优化问题:目标函数或约束条件中至少有一个是决策变量的非线性函数,即、和中至少有一个是的非线性函数。按照最优化解是否变化分类♣静态最优化问题:最优化问题的解不随时间而变。♣动态最优化问题:最优化问题的解随时间而变化。按照目标函数的个数分类♣单目标最优化问题:最优化问题中只有一个目标函数。♣多目标最优化问题:最优化问题中含有多个目标函数。xfxihxjgx1.1.4优化问题的求解方法一般思路最优化问题的一般求解方法是迭代算法。首先给定一个初始可行点(即初始值),然后从此点出发,依次产生一个可行点列,记作,使得某个恰好是问题的一个最优解,或者说该点列收敛到问题的一个最优解。一般步骤包括:①给定初始点,即令;②确定处的下降方向,使得点沿方向移动时函数值有所下降;③确定步长,令使得;1.1优化的概念及方法D0x,x,,x,x21kkxkxxkx0x0kkpkpkxxf0kkkkkpxx1kkffxx11.1优化的概念及方法④若满足某种终止准则,则停止迭代,以为近似最优解。否则令转①。影响算法收敛的条件♣如果某算法构造出的点列能够在有限步之内得到最优化问题的最优解,或者说点列有极限点,且其极限点就是最优解,则称算法是收敛的。算法收敛的影响因素较多,包括初始点的选取、下降方向的确定、迭代步长的选择以及目标函数自身的影响。除要求收敛外,一般还要求收敛速度要快。♣收敛:设序列,对于,存在正整数N,当时,有,则称收敛于。1kkkxxkx1xk1xkx0kxNkxxkkxx1.1优化的概念及方法♣线性收敛:设序列收敛于,且若,则称序列为线性收敛,为收敛比;若,则称序列为超线性收敛;若,则称序列为次线性收敛。♣p阶收敛:设序列收敛于,若对于某个实数,有则称序列为p阶收敛,一般情况下,称为二阶收敛。kxxkx10kx2pkxxxxxxlim1kkkkx011ppkkkxxxxlim1kx1.1优化的概念及方法常用的终止准则♣(,预先给定)或;♣,;♣;♣上述三种终止准则的组合。0kkxx1kkkxxx1kkffxx1kkkfffxxx1kkfgx1.1.5常用的无约束优化方法常用的无约束最优化方法包括最速下降法和牛顿法等。最速下降法最速下降法又称为梯度法、梯度下降法,是1847年由著名数学家Cauchy推导而出。根据泰勒公式得由此可见,当时,,符合迭代要求。1.1优化的概念及方法kkTkkkkkTkkkkkkkfffffpgxpxxpxx1kkkTkkkkTkkkkffpgpgxx10pgkTkkkffxx1由于,为和的夹角。故当时,取得极小值,下降最快。一般取,得到即负梯度方向使目标函数下降最快,称为最速下降法。牛顿(Newton)法牛顿(Newton)法最初由艾萨克·牛顿(IsaacNewton,1643年1月4日~1727年3月31日)在《流数法》(MethodofFluxions)首次提出(1671年完成,在牛顿死后的1736年公开发表),同时约瑟夫·拉弗森(JosephRaphson,1648年~1715年)也曾于1690年在AnalysisAequationum中提出此方法。故有时称为牛顿-拉弗森法。1.1优化的概念及方法cospgpgkkkTkkgkp180kTkpgkfxkkgpkkkkkkkfxxgxx1kfx设二阶连续可导,对在处进行泰勒展开,得设为的近似最优解,得到即得到牛顿迭代公式为1.1优化的概念及方法xfxfkxkkTkkTkkkkTkkTkkGfffffxxxx!21xxgxxxxxx!21xxxxx2kkkpxx1xf0x1kfkkkfxxGgx0xxGgx11kkkkkf0pGgkkkkkkgGp1kkkkkkgGxpxx11最速下降法的应用以最小均方算法(简称LMS)为例。如图1-1为一横向滤波器图中,为输入矢量,为抽头系数矢量。1.1优化的概念及方法图1-1横向滤波器结构图TLkkkyyy11Y,,,TL,,,WY~10TLiiikwyx设为系统的期望响应信号,为滤波器实际输出相对于的误差,即按照最小均方误差准则(简称MMSE),定义滤波器的输出与期望响应之间的均方误差(简称MSE)为代价函数,即定义为滤波器输入序列的自相关矩阵,是一个L×L阶方阵;为互相关矩阵。于是,上式可表示为1.1优化的概念及方法WYYWWY2WY222TTTkkTkkEdEdEdEeEJTEYYRTkdEYPRWWPW22TTkdEJkdkdkekx~WY~Tkkkkdxde根据最小均方误差准则,使上式对W的梯度(即偏导)为零,即则可得到的最佳值应满足方程式中,称为横向滤波器的维纳解,即最佳滤波器系数矢量。由于均方误差函数(即代价函数)是滤波器系数的二次方程,故形成了一个多维的超抛物曲面,好象一个碗状曲面且只有唯一的碗底最小点,通常称为滤波器的误差性能曲面。当给定初始值时,均方误差就位于误差性能曲面上的某一点,系数的自适应调节使得均方误差超碗底的最小点方向移动,最终到达碗底的最小点,实现了最佳维纳滤波。1.1优化的概念及方法0P2RW2WJJWWPRW1W在自适应算法中,人们提出了不少梯度估计的方法,其中最著名、应用最广的是B.Widrow提出的LMS算法。其算法的核心思想是用平方误差代替均方误差,即代价函数变为根据最陡下降法得到LMS自适应均衡算法公式为式中,为步长因子。1.1优化的概念及方法2keJWYTkkdeY2W2kkeeJY2k1.2智能优化的概念及方法1.2智能优化的概念及方法1.2.1智能优化的概念人工智能(ArtificialIntelligent,简称AI)是在计算机科学、控制论、信息论、哲学、语言学等多种学科研究基础上发展起来的一门综合性交叉学科。即人工智能就是用人工的方法在机器(计算机)上实现的智能,或者说是人们使机器具有类似于人的智能。智能优化算法(intelligentoptimizationalgorithms)是以模拟物质变化过程或模拟生命体而设计的搜索方式为基
本文标题:第1章优化算法基本理论
链接地址:https://www.777doc.com/doc-2153999 .html