最优化理论课件

最优化理论——三大经典算法三大经典算法NO.1遗传算法NO.2模拟退火法NO.3神经网络算法遗传算法GeneticAlgorithm1

遗传算法是一类借鉴生物界的进化规律（优胜劣汰，适者生存）演化而来的随机化搜索方法。广泛应用于函数优化和组合优化领域。1.函数优化：许多被构造出的各种复杂形式的测试函数“连续函数或离散函数，凹函数或凸函数，单峰函数或多峰函数等”，非线性多模型多目标的优化问题遗传算法可以方便得到较好的结果。2.组合优化：随着问题规模的增大，组合优化问题的搜索空间也增大，有时枚举法很难求出最优解，人们意识到应该把精力主要放在寻求满意解上，遗传算法是最佳工具之一。生物学术语说明染色体染色体又可以叫做基因型个体，一定数量的个体组成了群体，群体中个体的数量叫做群体大小基因基因是串中的元素，基因用于表示个体的特征。eg：有一个串S=1011，则其中的1,0,1,1分别称为基因，它们的值称为等位基因基因地点（位置）表示一个与基因在串中的位置称为基因位置（基因位），基因位置在串中由左向右计算。eg：在串S=1011中，0的基因位置是3特征值在用串表示整数时，基因的特征值与二进制的权一致。eg：在S=1011中基因位置3中的1特征值是2，基因位置1中的1特征值是8.适应度各个个体对环境的适应程度叫做适应度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数是计算个体在群体中被使用的概率。简单说来就是：繁殖过程，会发生基因交叉，基因突变，适应度低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。1常用的选择策略是“比例选择”，也就是个体被选中的概率与其适应度函数值成正比。选择2交叉前：00000|011100000000|1000011100|000001111110|00101交叉后：00000|000001111110|1000011100|011100000000|00101交叉3变异前：000001110000000010000变异后：000001110000100010000变异遗传算法的三个最基本操作选择轮盘赌算法/**按设定的概率，随机选中一个个体*P[i]表示第i个个体被选中的概率*/intRWS(){m=0;r=Random(0,1);//r为0至1的随机数for(i=1;i<=N;i++){/*产生的随机数在m~m+P[i]间则认为选中了i*因此i被选中的概率是P[i]*/m=m+P[i];if(r<=m)returni;}}基本遗传算法伪代码/**Pc：交叉发生的概率*Pm：变异发生的概率*M：种群规模*G：终止进化的代数*Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程*/初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Popdo{计算种群Pop中每一个体的适应度F(i)。初始化空种群newPopdo{根据适应度以比例选择算法从种群Pop中选出2个个体if(random(0,1)<Pc){对2个个体按交叉概率Pc执行交叉操作}if(random(0,1)<Pm){对2个个体按变异概率Pm执行变异操作}将2个新个体加入种群newPop中}until(M个子代被创建)用newPop取代Pop}until(任何染色体得分超过Tf，或繁殖代数超过G)模拟退火法SimulateAnnealArithmetic21爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法2模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。模拟退火法爬山算法与模拟退火法

冶金学中，退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。其中k是一个常数，exp表示自然指数，且dE<0。温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0，因此dE/kT<0，所以P(dE)的函数取值范围是(0,1)。关于爬山算法与模拟退火，有一个有趣的比喻：爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

算法描述

若J(Y(i+1))>=J(Y(i))(即移动后得到更优解)，则总是接受该移动若J(Y(i+1))<J(Y(i))(即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）/**J(y)：在状态y时的评价函数值*Y(i)：表示当前状态*Y(i+1)：表示新的状态*r：用于控制降温的快慢*T：系统的温度，系统初始应该要处于一个高温的状态*T_min：温度的下限，若温度T达到T_min，则停止搜索*/while(T>T_min){dE=J(Y(i+1))-J(Y(i));if(dE>=0)//表达移动后得到更优解，则总是接受移动Y(i+1)=Y(i);//接受从Y(i)到Y(i+1)的移动else{//函数exp(dE/T)的取值范围是(0,1)，dE/T越大，则exp(dE/T)也if(exp(dE/T)>random(0,1))Y(i+1)=Y(i);//接受从Y(i)到Y(i+1)的移动}T=r*T;//降温退火，0<r<1。r越大，降温越慢；r越小，降温越快/**若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值*/i++;}神经网络算法artificialneuralnetworks3

思维学中，人类的大脑的思维分为：逻辑思维、直观思维、和灵感思维三种基本方式。而神经网络就是利用其算法特点来模拟人脑思维的第二种方式，它是一个非线性动力学系统，其特点就是信息分布式存储和并行协同处理，虽然单个神经元的结构及其简单，功能有限，但是如果大量的神经元构成的网络系统所能实现的行为确实及其丰富多彩的。神经元也和其他类型的细胞一样，包括有细胞膜、细胞质和细胞核。但是神经细胞的形态比较特殊，具有许多突起，因此又分为细胞体、，它只有一个。轴突和树突三部分。细胞体内有细胞核，突起的作用是传递信息。树突是作为引入输入信号的突起，而轴突是作为输出端的突起树突是细胞体的延伸部分，它由细胞体发出后逐渐变细，全长各部位都可与其他神经元的轴突末梢相互联系，形成所谓“突触”。在突触处两神经元并未连通，它只是发生信息传递功能的结合部，联系界面之间间隙约为（15～50)×10米。突触可分为兴奋性与抑制性两种类型，它相应于神经元之间耦合的极性。每个神经元的突触数目正常，最高可达10个。各神经元之间的连接强度和极性有所不同，并且都可调整、基于这一特性，人脑具有存储信息的功能。利用大量神经元相互联接组成人工神经网络可显示出人的大脑的某些特征。人类神经网络抽象模拟神经网络算法原理Microsoft神经网络使用最多的是由三层神经元组成的“多层感知器”网络，分别为：输入层、可选隐含层和输出层。输入层：输入神经元定义数据挖掘模型所有的输入属性值以及概率。隐含层：隐藏神经元接受来自输入神经元的输入，并向输出神经元提供输出。隐藏层是向各种输入概率分配权重的位置。权重说明某一特定宿儒对于隐藏神经元的相关性或重要性。输入所分配的权重越大，则输入值也就越重要。而这个过程可以描述为学习的过程。权重可为负值，表示输入抑制而不是促进某一特定结果。输出层：输出神经元代表数据挖掘模型的可预测属性值。输入层特点：如果输入层如果为离散值，那么输入神经元通常代表输入属性的单个状态。如果输入数据包含Null值，则缺失的值也包括在内。具有两个以上状态的离散输入属性值会生成一个输入神经元，如果存在NUll值，会自动再重新的生成一个输入的神经元，用以处理Null值，一个连续的输入属性将生成两个输入神经元：一个用于缺失的状态、一个用以连续属性自身的值。输入神经元可向一个多多个神经元提供输入。隐含层特点:隐含神经元接受来自输入神经元的输入，并向输出神经元提供输出。存在激活函数供其使用改变阀值。输出层特点：输出神经如果对于离散输入属性，输出神经元通常代表可预测可预测属性的单个预测状态，其中包括缺失的Null值。数据从输入经过中间隐含层到输出，整个过程是一个从前向后的传播数据和信息的过程，后面一层节点上的数据值从与它相连接的前面节点传来，之后把数据加权之后经过一定的函数运算得到新的值，继续传播到下一层节点。这个过程就是一个前向传播过程。而当节点输出发生错误时，也就是和预期不同，神经网络就要自动“学习”，后一层节点对前一层节点一个“信任”程度（其实改变的就是连接件的权重），采取降低权重的方式来惩罚，如果节点输出现错误，那就要查看这个错误的受那些输入节点的影响，降低导致出错的节点连接的权重，惩罚这些节点，同时提高那些做出正确建议节点的连接的权重。对那些受到惩罚的节点而说，也用同样的方法来惩罚它前面的节点，直到输入节点而止。这种称为：回馈。而我们学习的过程就是重复上面的介绍的流程，通过前向传播得到输入值，用回馈法进行学习。当把训练集中的所有数据运行过一遍之后，则称为一个训练周期。训练后得到神经网络模型，包含了训练集中相应值和受预测值影响变化的规律。在每个神经元中的隐含层中都有着复杂的函数，并且这些都非线性函数，并且类似生物学神经网络的基本传输特征，这些函数称之为：激活函数，即：输入值发生细微的变化有时候会产生较大的输出变化。如果挖掘模型包含一个或多个仅用于预测的属性，算法将创建一个代表所有这些属性的单一网络，如果挖掘模型包含一个或多个同时用于输入和预测的属性，则该算法提供程序将为其中每个属性构建一个网络。对于具有离散值的输入属性和可预测属性，每个输入或输出神经元各自表示单个状态。对于具有连续值的输入属性和可预测属性，每个输入或输出神经元分别表示该属性值的范围和分布。算法提供程序通过接受之前保留的定性数据集也就是事例集合并将维持数据中的每个事例的实际已知值与网络的预测进行比较。即通过一个“批学习”的过程来迭代计算的整个网络，并且改变的输入权重。该算法处理了整个事例集合之后，将检查每个神经元的预测值和实际值。该算法将计算错误程度（如果错误），并且调整与神经输入关联的权重，并通过一个“回传”的过程从输出神经元返回到输出神经元。然后，该算法对整个事例集合重复该过程。经过以上的层层沉淀我们的算法就算从一个不懂的“婴儿”逐渐成长成“成人”，而这个结果就是我们那它来发掘和预测的工具。符号说明x（p）：输入层的输入矢量；y（p）：输入层输入为x（p）时输出层的实际输出量；t（p）：目标输出矢量；n：输入层神经元个数；m：隐层神经元个数；r：输出层神经元个数；W：隐层与输入层间的权矩阵；V：输出层与隐层间的权矩阵。（1）随机给定隐层和输入层间神经元的初始权值wij。（2）由给定的样本输入xi（p）计算出隐层的实际输出aj（p）。为方便起见将图1网络中的阀值写入连接权中去，令：隐层阀值θj=wnj，x（n）=－1，则：aj（p）=f（■