智能计算考试

优化技术：以数学为基础，解决各种工程问题优化解。用途：系统控制、人工智能、模式识别、生产调度；传统优化方法：待解决的问题是连续性问题，以微积分为基础，规模较小；理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等，排队论、库存论、对策论、决策论等；传统的评价方法：算法收敛性、收敛速度;现代优化方法：待解决的问题离散性、不确定性、大规模；有启发式算法、追求满意、实用性强；现在的评价方法：算法复杂性。最优化问题及其分类：函数优化问题：令S为Rn上的有界子集，f：S->R为n维实值函数，所谓函数f在S域上全局最小化就是寻求点Xmin€S使得f(Xmin)在S域上全局最小。组合优化问题：令Q={s1，s2，…，％}为所有状态构成的解的空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，，使得对于所有的Si€Q，C(S*)=minC(S「 ’启发式算法：一个基于直观或经验构造的算法，在可接受的花费下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。它是以一种技术、不能保证所得解的最优性。优点：1.模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；2.复杂问题无法求得最优算法或最优算法太复杂；简单易行，直观，程序简单。缺点：不能保证最优、不稳定、依赖于实际问题和设计者的经验。分类：简单直观的算法、数学规划算法、现代优化算法。评价算法优劣的指标：算法的复杂性、解的偏离程度、算法的稳健性。评价算法优劣的手段：最坏情况分析、概率分析、计算模拟分析。NP类问题：算法的时间复杂性：算法对时间的需要量(加、减、乘、除、比较、读、写等操作的总次数)。算法的空间复杂性：算法对空间的需要量(存储空间的大小，二进制位数)。问题的时间复杂性：所有算法中时间复杂性最小的算法时间复杂性。问题的空间复杂性：所有算法中空间复杂性最小的算法空间复杂性。定义：若一个问题的每个实例只有“是”或“否”两种回答，则称该问题为判定问题。若存在一个多项式g(x)和一个验证算法H，对一类判定问题A的任何一个“是”的判定实例I都存在一个字符串S是I的“是”回答，满足其输入长度d(S)不超过g(d(I))(其中d(I)为I的输入长度)，且验证算法验证S为I的“是”回答的计算时间不超过g(d(I))，则称判定问题A为非多项式确定问题，简称NP问题。模拟退火算法：模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-AE/(kT)，其中E为温度T时的内能，AE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解 i和控制参数初值t开始，对当前解重复“产生新解9计算目标函数差9接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表 (CoolingSchedule)控制，包括控制参数的初值t及其衰减因子&、每个t值时的迭代次数L和停止条件S。给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。1)从可行解空间中任选一初始状态x0，计算其目标函数值f(x0)，并选择初始控制温度T0和马尔可夫链的长度；2)在可行解空间中产生一个随机扰动，用状态产生函数产生一个新状态x0，计算其目标函数值f(x1)；3)根据状态接受函数判断是否接受：如果f(x1)<f(x0)，则接受新状态x1为当前状态，否则按Metropolis准则判决是否接受x1，若接受，则令当前状态等于x1，若不接受，则令当前状态等于x0；4)跟据某个收敛准则，判断抽样过程是否终止，是则转5,否则转2；5)按照某个温度冷却方案降低控制温度T；6)根据某个收敛准则，判断退火过程是否终止，是则转7,否则转2；7)当前解作为最优解输出Metropolis准则(1953)——以概率接受新状态：若在温度T，当前状态if新状态j。若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态优点：质量高、初值鲁棒性强、简单通用，容易实现。缺点：由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。改进的模拟退火算法：改进的可行方案：(1)设计合适的状态产生函数；(2)设计高效的退火历程；(3)避免状态的迂回搜索；(4)采用并行搜索结构；(5)避免陷入局部极小，改进对温度的控制方式；(6)选择合适的初始状态；(7)设计合适的算法终止准则。改进的方式：(1)增加升温或重升温过程，避免陷入局部极小；(2)增加记忆功能(记忆“Bestsofar”状态)；(3)增加补充搜索过程(以最优结果为初始解)(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；(5)结合其它搜索机制的算法；(6)上述各方法的综合。改进的退火过程：(1)给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s(0)=s，i=p=0；(2)令t=ti，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*'和当前状态s’(k)，令当前状态s(i)=s'(k)；(3)判断C(s*)<C(s*’)？若是，则令p=p+1；否则，令s*=s*'，p=0；(4)退温ti+1=update(ti)，令i=i+1；(5)判断p>m2?若是，则转第(6)步；否则，返回第(2)步；(6)以最优解s*作为最终解输出，停止算法。改进的抽样过程：(1)令k=0时的初始当前状态为s'(0)=s(i)，q=0；(2)由状态s通过状态产生函数产生新状态s'，计算增量△C'=C(s')-C(s)；(3)若巡'<0，则接受s'作为当前解，并判断C(s*')>C(s')?若是，则令s*'=s'，q=0；否则，令q=q+1。若△C'〉0，则以概率exp(-△C'/t)接受s'作为下一当前状态；(4)令k=k+1，判断q>m1?若是，则转第(5)步；否则，返回第(2)步；(5)将当前最优解s*'和当前状态s'(k)返回改进退火过程。遗传算法:mm孑■［寻mm孑■［寻遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。初始化:选择一个群体，问题的最优解将通过这些初始假设解进化而求出。选择:根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。交叉:对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。变异:根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。全局最优收敛:当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。神经网络：它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。优越性：具有自学习功能、具有联想存储功能、具有高速寻找优化解的能力。应用领域：模式识别、信号处理、知识工程、专家系统、优化组合、机器人控制。学习(训练)：有监督的学习：已知一组正确的输入输出结果的条件下，神经网络依据这些数据，调整并确定权值；无监督的学习：只有输入数据，没有正确的输出结果情况下，确定权值。M-P模型:y=M-P模型:y=f(z-8)=其中，sgn(x)=sgn(Uwx—8)i=1J1,x>0、0,x<0Hebb算法：当两个神经元同时处于激发状态时被加强，否则被减弱；数学表达式表示：Wij(t+1)=Wij(t)+aVi(t)Vj(t)；如果两个神经元同时兴奋(即同时被激活)，则它们之间的突触连接加强 '■■-aJ为学习速率，Vi,Vj为神经元i和j的输出感知器的学习规则：输入矢量X,输出矢量Y,目标矢量为O的感知器网络，其学习规则为：如果第i个神经元的输出是正确的，即有：yi=oi，那么与第i个神经元联接的权值wij和偏差值bi保持不变；如果第i个神经元的输出是0,但期望输出为1,即有yi=0,而oi=1,此时权值修正算法为：新的权值wij为旧的权值wij加上输入矢量xj；类似的，新的偏差bi为旧偏差bi加上它的输入1；如果第i个神经元的输出为1，但期望输出为0，即有yi=1，而oi=0，此时权值修正算法为：新的权值wij等于旧的权值wij减去输入矢量xj；类似的，新的偏差bi为旧偏差bi减去1。训练的步骤：1)对于所要解决的问题，确定输入矢量X，目标矢量0,并由此确定各矢量的维数以及确定网络结构大小的神经元数目：r,s和q；2)参数初始化：a)赋给权矢量w在(-1,1)的随机非零初始值；b)给出最大训练循环次数max_epoch；3)网络表达式：根据输入矢量X以及最新权矢量W,计算网络输出矢量X；4)检查：检查输出矢量X与目标矢量O是否相同，如果是，或已达最大循环次数，训练结束，否则转入5)；5)学习：根据(3-1)式感知器的学习规则调整权矢量，并返回3)。自适应的结构:步骤：1)表达：计算训练的输出矢量A=W*P+B，以及与期望输出之间的误差E=T—A；2)检查：将网络输出误差的平方和与期望误差相比较，如果其值小于期望误差，或训练已达到事先设定的最大训练次数，则停止训练；否则继续；3)学习：采用W—H学习规则计算新的权值和偏差，并返回到1)BP算法：弱点：训练速度非常慢、局部极小点的逃离问题、算法不一定收敛。缺点：广泛的适应性和有效性。训练步骤：初始化：用小的随机数初始化每一层的权值W和偏差B,保证网络不被大的加权输入饱和。期望误差最小值error_goal最大循环次数max_epoch修正权值的学习速率1r,一般情况下k=0.0l,0.7；变量表达：计算网络各层输出矢量A1和A2以及网络误差E。A1=tansig(W1*P,B1)、A2=purelin(W2*A1,B2)、E=T-A；权值修正：计算各层反传的误差变化D2和D1并计算各层权值的修正值以及新权值。D2=deltalin(A2,E)、D1=deltatan(A1,D2,W2)、[dlWl,dBl]=learnbp(P,D1,lr)、[dW2,dB2]=1earnbp(A1,D2,1r)、W1=W1十dW1；B1=B1十dBl、W2=W2十dW2；B2=B2十dB2；计算权值修正后误差平方和SSE=sumsqr(T-purelin(W2*tansig(W1*P,B1),B2))；检查：SSE是否小于err_goal。若是，训练结束；否则继续。蚁群算法：蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。粒子群算法：Initial:将群族做初始化，以随机的方式求出每一Particle之