智能优化算法

1模拟退火算法模拟退火算法(SA)是一种启发式算法，它是受加热金属的退火过程所启发而提出的一种求解组合优化问题的一种逼近算法.在某个温度下，金属分子停留在能量小的状态的概率比停留在能量大的状态的概率要大.SA在求复杂优化问题最好解中已显示出其非常的有效性自Kirkpatrick于1983将Metropolis在1953年提出的模拟退火思想应用到组合优化问题以来，受到大家的普遍关注.算法(模拟退火算法)Step1.初始化可行解和温度.Step2.根据Boltzmann概率退火.Step3.重复第二步直到稳定状态.Step4.降温.Step5.重复第二步至第四步直到满足终止条件或直到给定的步数.Step6.输出最好的解作为最优解.初始化过程1.随机产生一个可行解S0.2.理论上，初始温度应保证平稳分布中每一状态的概率相等，即其中△fij=f(sj)-f(si)如可取t0=K△0(右下角),K为充分大的数而算法(初始温度算法)Step1.给定一个常数T;温度to;常数Xo(如0.9);Ro=0.Step2.在这个温度退火L步.记接受状态的个数为L'，计算Rk=L'/L.Step3.如果|Rk一X0|，停止.否则，如果R(k-1),RkX0，则k=k+l,to=to+T，返回step2;如果R(k-1),Rk=X0，则k=k+l,to=to一T，返回step2;如果R(k-1)=X0,Rk=X0，则k=k+l,to=to+T/2，返回step2;如果R(k-1)=X0,Rk=X0，则k=k+l,to=to一T/2，返回step2.退火退火过程就是在一给定温度下，由一个状态变到另一个状态，每一个状态到达的次数服从一个概率分布，即基于Metropolis接受准则的过程，该过程达到平稳时停止.在状态sj时，产生的状态sj被接受的概率为2降温：一种方法：另一种：其中M为温度下降的总次数.技术问题：解的表达形式和邻域结构:要求解的表达形式简洁明了易于操作;邻域中每个邻居都是可行解，解空间中任何两状态可达.对TSP问题，解S可表示为城市的一个排序.解的邻域可用不同的操作算子定义，如互换操作:即随机交换解码中两不同的字符位置逆序操作:即将解码中两不同的随机位置间的字符串逆序插入操作:即随机选择某个点插入到串中的不同随机位置如果邻域中有不是可行解的邻居，可用罚值法，将其视为可行解，目标值为一个充分大的数.但该法的缺陷是扩大了搜索区域，从而使计算时间增加.内循环终止准则:常用的有1.固定步数2.连续若干步的目标值变化较小3.由接受和拒绝的比率控制迭代步数外循环终止准则:常用的有1.设置终止温度的i-值(比较小的正数)2.设置循环总数3.连续若干步搜索到的最优解不再改进4.设置接受概率遗传算法遗传算法(GA)是一种解优化问题的随机搜索方法，它借助于生物进化中的自然选择和遗传(即适者生存)的规律.基本遗传算法算法(基本遗传算法)Step1.随机初始化pop_size个染色体.Step2.用交叉算法更新染色体.Step3.用变异算法更新染色体.Step4.计算所有染色体的目标值.Step5.根据目标值计算每个染色体的适应度.Step6.通过轮盘赌的方法选择染色体.Step7.重复第二至第六步直到终止条件满足.Step8.输出最好的染色体作为最优解.为利于遗传算法的计算，首先要对解进行编码，编码后的解称为染色体.对于约束优化问题，遗传算法是在染色体中进行操作，而把操作结果解码后去检验其可3行性.收敛性：模板理论设遗传算法中群体和种群的维数相等，为一个偶数维，且不随代数的变化而变化;适应函数直接选用目标函数;种群中的个体通过轮盘赌的方式选取，即第i个染色体被选中的概率为种群中的一对个体采用随机交叉的方式产生下一代;每一个基因有相同的变异概率.模板定理我们有如果则从概率意义来说，每代中具有H模板的染色体个数将随代数t的增加而增加.收敛定理若变异概率0pm1，交叉概率0=Pc=1，则基本遗传算法不收敛到全局最优解.如果改进基本遗传算法按交叉、变异、种群选取之后更新当前最优染色体(解)的进化循环过程，则收敛于全局最优.如果改进基本遗传算法按交叉、变异后就更新当前最优染色体之后进行种群选取的进化循环过程，则收敛于全局最优。算法实现：4编码和解码---初始化----评价函数----选择---交叉----变异编码与解码GA的关键问题之一是把解编码为染色体，也要能把染色体解码为解.常用的编码方法有1.常规码，即二进制码2.实数码3.根据问题确定的编码二进制码就是0一1编码.采用0一1码可以精确地表示整数.用0一1编码精确表示a到b所有整数，只需编码长度n初始化群体假设群体的规模为pop_size，随机产生pop_size个染色体作为初始群体.初始化的方法根据问题的不同而设计.如对于连续优化问题，可预估一个含有最优解的区域(如超平面).在这个区域中随机产生一个点，然后检验这个解的可行性.如是可行的，则接受为染色体;如不可行，则重新在那个区域中随机产生一个点直到是可行点为止.重复刚才的过程pop_size次得到pop_size个初始染色体.群体的规模1.群体的规模可以设定为个体编码长度数的一个线性倍数2.群体的规模可以是一个给定数3.群体的规模也可以是变化的.当连续多代没能改变解的性能，则可扩大群体的规模;若解的改进非常好，则可以减少群体的规模.评价函数评价函数Eval(V)是根据每个染色体V的适应函数fitness(V)而得到与其他染色体的比例关系，可用它决定该染色体被选为种群的概率.如选择过程5交叉运算1.常用方法一一双亲双子2.变化交叉位法3.多交叉位法4.双亲单子法5.显性遗传法6.单亲遗传法*对于根据问题确定的编码，交叉运算可用如下之方法1.随机选一个交叉位，父代交叉位前的基因分别继承给两个后代，两后代之后的基因分别按对方基因顺.序选取不重基因2.不变位法变异运算6蚁群优化算法AntColonyOptimizationAlgorithms(ACOA)是求解组合优化问题的一种启发式算法，它受蚂蚁的社会行为而启发.在ACOA，计算信息是靠赋予一群人工蚂蚁信息素而实现的.ACOA由orig。于1992年提出，在求解许多复杂优化问题中宣示出良好的鲁棒性和通用性.问题描述蚂蚁在寻找食物过程中，会在他们经过的地方留下信息素.这些物质能影响后来蚂蚁的行动，后到的蚂蚁选择有较多这些物质的路径的可能性比有较少这些物质的路径的可能性大得多.后到的蚂蚁留下的信息素会对原有的信息素进行加强.考虑极小化问题(s,f,偶米噶)，其中s是定义域，f是目标函数，而（偶米噶）约束集.组合优化问题(S,f,偶米噶)也可描述为一个有向图问题G=(C,L,T)，其中C为顶点集，L为连接顶点C的边集，而T是一个称为信息素（淘）的向量.基本蚁群算法算法(蚁群优化算法)Step1.初始化所有的信息素具有同样的量.Step2.根据信息素构造人工蚂蚁行动路线(解)Step3.重复第二步直至所有蚂蚁完成一次行动.Step4.根据当前最好解更新路径上的信息素.Step5.重复第二至第四步直至终止条件满足.Step6.输出最好解作为最优解.信息素更新在t时刻，设S^是目前为止的最好可行解，而St是当前t时刻的最好可行解.设f(s^)和f(st)是对应的目标函数值.如果，f(St)f(s^),则s^St，在s^的弧上增强信息素，而在其它弧上挥发信息素.信息素增强和挥发的方法一:7信息素增强和挥发的方法二(MAX-MIN方法):信息素增强和挥发的方法三:收敛性8神经网络James在1890年描述了神经网络的基本原理:大脑皮层每一点的活力是由其他点势能释放的综合效能产生的.这一势能同下面的因素有关:相关其他点的兴奋次数;兴奋的强度;与其他不相连的其他点所接受的能量.人工神经元人工神经元模拟生物神经元的行为对输入信号作权和运算Y=wo+w1X1+w2X2+…+wnXn其中X1,X2,……，Xn是输入，w0，wl，w2，……wn是权重，而y是输出.Sigmoid函数定义一个没记忆的非线性函数(fai)作为激励函数来改变输出值9激励函数的选取依赖于应用问题.如可用sigmoid函数它的导数为我们考虑一个单隐层的NN，其中输入层有n个神经元，输出层有m个神经元，而隐含层有p个神经元.那么在隐层神经元的输出为因此输出层神经元的输出为函数逼近假设，f(x)是一个连续函数.我们希望训练一个NN去逼近函数f(x).对于一个固定神经元和网络结构的NN，网络权可作成一个向量w.设F(x,w)是由NN所得出的输出训练过程是寻找权向量w以最好地逼近函数f(x).设是训练数据集.我们希望选择权向量w使得F(x*,w)对于输入x*i(小写)来说最接近要求的输出y*i.即，训练过程是找权向量w以极小化以下的误差函数神经元数的确定因为函数f从Rn(右上角)映入Rm，输入神经元的数目是n，而输出神经元的数目是m.因此主要问题是确定隐层神经元的数目.虽然连续函数可用在隐层具有无穷多神经元的NN任意逼近，但在实际应用中不可能用无穷多神经元的隐层.一方面，太少的隐层神经元会使NN缺乏一般能力.另一方面，太多的隐层神经元会增加训练NN的时间以及增加NN的反应时间.在实际应用中，可根据具体问题通过适当增加或减少神经元数目来确定隐层神经元数.10反向传播算法算法(反向传播算法)Step1.初始化权向量w，Step2.k--k+1.-------Step3.调整权重w.------Step4.计算误差Ek.-----Step5.如果kN，到第二步.------Step6.置E=E1+E2+…+EN.Step7.如果EEo，那么k=0,到第二步------Step8.结束.hopfield神经网络的计算步骤Step1.针对实际问题的组合优化问题构造能量函数，使得能量函数有好的稳定性，如满足定理条件;Step2.由能量函数，写出动力系统方程;Step3.用数值的方法求解动力系统方程的平衡点，用定理判断平衡点是否为稳定点或渐近稳定点.