智能优化算法的部分精华笔试试题

1、一、什么是P问题，什么是NP问题？智能优化算法主要是针对什么问题而提出 的？解：1P问题记间题的实例为1.实例规模为/（I）,算法在求解1时的计算量（基本计算总次数）为C卜若存在多项式函数莒彼）和一个常数e使得顷） 0,xD.典型的组合优化问题有旅行商问题，背包问题，并行排序问题等，二、描述组合优化问题中的一个典型例子，并建立其数学模型。解：1旅行商问题Traveling Salesman Problem, TSP设有计个城市城市i与城市j间的距离为一售 货商要去这些城市推销货物，他希望从一城市出发后走遍所有的 城市且旅途中每个城市只经过一次，最后回到起点.选择一条路 经使得售货商所走路线总长

2、度最短，这就是旅行商问题 引进决策变量勺.，若商人从城市i出来后紧接着到城市土 则 有=L否则听=0 (i.j = L2一.少那么TSP的数学模型可 表示为rn nmin 由裕f=ij=ins.t. = Lj=iJ n丈冷=It J = L2,Mt=lE Xij |S| - 1, 5为L 2，日的非空真子集, ues、 珂 e0,1,/J 手，其中|S|表示集合S中元素的个数2背包问题设有一个容量为b的背包，口个容积分别为蛔，价值分别为c； (12. n)的物品，选择那些物品放入背包中以使装入的物 品总价值最大这就是背包问题引入决策变量志，若第i个物品被放入包中，则芯=1,否则 用=。=1.2

3、一皿 那么背包问题的数学模型为max QXr s,t. 52 Ml ； t淘,y = 1,2, . m,地 6 (04, i = L2,nj = 1,2, 齐.三、描述模拟退火算法中的接收准则。步骤：1、初始化可行解和温度；2,根据Boltzmann概念退火；3,重复第二步 直到稳定状态；4,降温；5,重复第二步至第四步直到满足终止条件或直到给定 步数。6,输出最好的解作为最优解。退火接收准则：在一给定温度下，由一个状态变到另一个状态，每一个状态到达 的次数服从一个概率分布，即基于Metropolis接受准则的过程，该过程到达平衡时停止。在状态七时，产生的状态Sj被接受的概率为：A (t) J

4、盾 即 2 气这里 g = f (s )- f (s ).lJexp(-), iff (s) f (sjj j 降温：A 种方法为tk+1 = d(tk)另一种方法为其中 d(tk) = atkM-ktk= M 场其中M为温度下降的总次数.四、写出遗传算法中的两种交叉运算方法，并分别举例说明。步骤：1、随机初始化pop size个染色体；2、用交叉算法更新染色体；3、用变 异算法更新染色体；4,计算所有染色体的目标值；5,根据目标值计算每个染色 体的适应度；6,通过轮盘赌的方法选择染色体。7、重复第二至第六步直到终止 条件满足；8、输出最好的染色体作为最优解。评价函数：Eval（V）是根据每个

5、染色体V的适应函数fitness（V）而得到与其他染色体 的比例关系，可用它来决定该染色体被选为种群的概率如:M）=轮盘赌选择过程：算法（轮盘赌的选择过程）Step 1.计算所有染色体匕的累积概率qif如=0. % = Ev/Vj） .，=1. 2.pop size,j=iStep 2.在（O.qpops屁中产生一个随机数r.Step 3.若 r 为，则选择染色体*Step 4,重复第二至第三步pop size次以获得pop size个染色体.交叉运算方法：双亲双子法两父代交叉位之后的全部基因互换、变化交叉法 从不相同的基因开始选取交叉位，之后的方法同双亲双子法、多交叉位法间 隔交换、双亲单子

6、法2选1、显性遗传法按位或、单亲遗传法2-opt 等。双亲双子交叉方法例子：父代是以交叉概率Pc在种群中选取的.实现的方法从种群/ = 1到种群pop size逐个地 如下操作：从0.1中随机产生如r Pc,则染色体 峪被选为父代.记父代为峪,巧巧,，将他们配成对:（峪M），04崂）,（*崂）,对于实数码，可按以下方法实现交叉运算：随机产生一 个数ce (0.1),由父代峪,峻产生子代X. 丫X = cM + (l _ c)My =(i c).g + c 巧变异运算：单点、多点变异法；2-opt法；对实数码，可如下进行变异操作.设，为选为变异 的染色体，取肋0适当大，随机选个变异方向 d,如V

7、 + Md不可行，置肋为0到肋间的随 机数直到可行为止；若该过程在规定的代数还不能 找到可行解，则置M = 0.由，变异产生的后代为X=V + M-d.用遗传算法解决实数编码求连续函数优化问题，写出一种变异的运算方法。解：连续的实数变量在一定精度下也可以采用二进制编码.对给定的区间何ML设二进制编码的长为m则变量b 3 b 3b _ ax = m + 日 i - F 边 bF L x与二进制词a词 寻相对应一二进制码与实际变量的误差为穿再用单点变异法或多点变异法即可完成实数码的变异方法。随机选一个或 几个变异位取反五、解释蚁群智能优化算法中信息素的一种更新方法。步骤：1、初始化所有的信息素具有

8、同样的量；2、根据信息素构造人工蚂蚁行为 路线解；3、重复第二步直到所有人工蚂蚁完成一次行动；4、根据当前最好 解更新路径上的信息素；5、重复第二步至第四步直到终止条件满足；6、输出最 好解作为最优解。信息素的一种更新方法：在t时刻，设是目前为止的最好可行解，而殳是当前t时刻的最好可行解,设f(s)和f(S.)是对应的目标函数直如果f(st) f(s)t则会一成在s的孤上增强信息素，而在其它弧上挥发信息素.方法一：(1 - 1) + if (，J) G 5 11(I pr_i)Ty(t - 1),otherwise,其中p” 0 1是挥发因子，且满足心-器时)，事=皿方法二：max(l - p

9、)Tjj(t 1) + Tmin(t - 1) if (M) e3 max(l -1), rmfn(t - 1),otherwise,其中p,0 p 1是挥发因子而rmin(t - 1)为一个实 数.方法三:gx(l p)9(r 1)十如(), 丁村 n, if(3 侦，)=max(l - p)珂(r 一 1),而n, otherwise,其中p, 0 p 1是挥发因子，Em是一个参数，而 g(S), 0 g(5) X是一个函数满足f(s) g(5) g(s)如可取 施= 1/(胴 l + i)人工蚂蚁路线的构造：在第t步构造了序列用= 以如下概率选择下一个顶点q_ 矽+可如果9) e 4佝

10、_ %I 0,其它蚂蚊转移概率P，,更一般的规则为Pij =痉尚，如果J go, 如果jr其中T是从/可以到达的节点集合，A(f-1) = W _ 1) I (；j) e A取决于三部分因素， 第一部分为信息素邛(t - 1)和预见度响U _ 1)；第二部 分为每个蚂蚁自身的历史信息；第三部分为问题的约束 条件常见的蚁群路由表由下式求得(a . t如果i丁再瑞1)或(t-i)其中，心为残留信息的相对重要程度，3为预见值的 相对重要程度一六、描述Hopfiled人工神经网络的函数逼近一连续函数的方法。解：假设代)是一个连续函数 我们希望训练一个NN去逼 近函数f(x).对于一个固定神经元和网络结

11、构的NK.网络权可作成一 个向量w设F(x,w)是由NN所得出的输出 训练过程是寻找权向量w以最好地逼近函数f(x),设 (xLy；)|，=是训练数据集.我们希望选择权向量w使得F(xw)对于输入x；来说最接近要求的 输出y；.即，训练过程是找权向量w以极小化以下的误 差函数1 N&r(w) = 5El|F(x；.w) y；|2 1=1Step 1.构造函数逼近的能量函数，使得能量函数有好的稳定性，如Err(w);Step 2.由能量函数Err(w)，根据-冬=*(初 求解出动力系统方程 dtdyif 岑 +I用=机耳)、f = 1.2.m；Step 3.用数值计算的方法求解动力系统方程的平衡点，用定理判断平衡点是否 为稳定点或渐近稳定点，网络到达稳定状态即到达极小值。Hop