智能优化算法笔试考试试题

智能优化算法笔试考试试题智能优化算法笔试考试试题II一、写出遗传算法中的两种交叉运算方法，并分别举例说明。解：双亲双子法(两父代交叉位之后的全部基因互换)、变化交叉法(从不相同的基因开始选取交叉位，之后的方法同双亲双子法)、多交叉位法(间隔交换)、双亲单子法(2选1)、显性遗传法(按位或)、单亲遗传法(2-opt)等，例子见课本175-179<>二、什么是P问题，什么是NP问题？智能优化算法主要是针对什么问题而提出的？解：(1)P问题记问题的实例为I,实例规模为/(I)，算法人在求解1时的计算量〔基本计算总次数)为G(I).•若存在多项式函数g(x)和一个常数。使得对给定问题的所有实例1成立，记cxi)=o<g<qi)))「则称算法人为解决对应问题的多项式时间算法，P类问题指具有多项武时间算法的问题类NP问题若存在一个多项式函数g(X)和一亍验证算法几对一类判定问题的任何一个“是”的判定实例I都存在一个字符串S是1的“是“回答，其规模满足/(S)=0(外(1)几且算法。验证5为实例1白勺」是“答案的计算时间为0(g(/(I))),则称这个判定问题是非确定多项式的'简记为NPNP-C问题和NP-Hard问题•如果判定问题QeNP且AP中的任何一个问题都可在多朗岛內归约为Q,则称Q为NP完全(简记为NP-C).•若NP中的任何一个问题都可在多项式时间归约为判定问题Q,则称Q为NP难(简记为NP-hard).智能优化算法主要是针对组合优化问题而提出的。三、描述组合优化问题中的一个典型例子，并建立其数学模型。解：(1)旅行商问题(TravelingSalesmanProblemTSP)设有n个城市1.2.9nT城市f勻城市J间的距离为％一售货商要去这些城市推销货物，他希望从一城市出发后走遍所有的城市且旅途中每个城市只经过一次，最后回到起点.选择一条路经使得售货商所走路线总长唐最短，这就是旅行商问题引进决策变量切，若商人从城市，岀来后紧接着到城市八则旳-1.否则勺=。(/.;=1.2. ./)).那么TSP的数学模型可表示为*nnmin內£Xy=J=1*f旳二/=/£旳<|5|-1,S^(lt2..J}的非空真子筑Jjes,X(/e(0l}7/；j-E知其中|S|表示集合s中元素的亍数背包问题设有一个容量为動的背包n个容积分别为旳，价值分别为q_(；=12.,〃的物品，选择那些物品放入背包中以使装入的物品总价值最大，这就是背包问题一引入决策变量坨，若第；个物品被放入包中，则x;=b否则片=o(r-i_2—那么背包问题的数学模型为max刀c/x/*S.t.SWfXi<bi=l、x/e{0,1), /= ,n.并行机排序问题设有m台同型机器隔陋、….般冲n个相互独立的工件J丄…人现在要安排这些工灌U机器上进行加工，设每个工件只需在任一台机器上加工，工件d的如工时间为口(/=12■-n).如何安携这些工件的加工方案，以使机器完成所有工作的时间最少一这就是井行机排序问题一引入决策变量冷，若工件丿」在机器明上加工，则勺=1,否则駕=0.那么井行机排序问题的数学模型为mintm^•52^=h#=XN...m«7=1r>£j=h2：…冲;=i靭E{°1}： /=1,2.A-.nJ=1,2,-Tm.智能优化算法笔试考试试题智能优化算法笔试考试试题/4四、描述模拟退火算法中的接收准则。解：在一给定温度下，由一个状态变到另一个状态，每一个状态到达的次数服从一个概率分布，即基于Metropolis接受准则的过程，该过程达到平衡时停止。在状态s时，产生的状态s被接受的概率为：1 iff(S)”(Sj)W为iff(S)vfd这里，3讣心.五、 解释蚁群智能优化算法中信息素的一种更新方法。解：在t时刻「设专是目前为止的最好可行解「而$是当前t时刻的最好可行解•设f(s)和f(s「)是对应的目标函数值一如果f(sjvf(s"则S—匀在S的弧上増强信息素，而在其它弧上挥发信息素一评(jj评(jj)e=J(1-pt-i)坊(匸一1)+otherwise,$IIotherwise,1(1一一1),其中go<fr<1是挥发因子，且满足9=g9=gt=iPt<l- .z.八ln(t+1)六、 描述Hopfiled人工神经网络的函数逼近一连续函数的方法。解：假设f(x)是一个连续函数.我们希望训练一个NN去逼近函数fg对于一个固定神经元和网络结构的nn,网络权可作成一个向量w.设F(x.w)是由NN所得出的输出训练过程是寻找权向量W以最好地逼近函数f(x).设｛(*占；)卩二12N｝是训练数据集'我们希望选择权向量w使得F(x\w)对于愉入x；来说最接近要求的输出听.即，训练过程是找权向量w以极小化以下的误差函数1“Frr(w)=-J2||F(x*tw)-y；||2.z*=iStepl.构造函数逼近的能量函数，使得能量函数有好的稳定性，如 Err(w);Step2,由能量函数Err(w),根据-dZ「=-Err(*)求解出动力系统方程dtcy.( 孚二一A石+K呦乃41*Step3.用数值计算的方法求解动力系统方程的平衡点，用定理判断平衡点是否为稳定点或渐近稳定点，网络达到稳定状态即达到极小值。七、 用遗传算法解决实数编码求连续函数优化问题，写出一种变异的运算方法。解：连续的实数变量在一定精度下也可以采用二进制编码一对给定的区间[a.fe],设二进制编码的长为m则变量b—ab-a b-aX—a+3j I、32 …+3“2打与二进制码巧电…咼相对应.二进制码与实际变量