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

ll 一、写出遗传算法中的两种交叉运算方法，并分别举例说明。解：双亲双子法(两父代交叉位之后的全部基因互换)、变化交叉法(从不相同 的基因开始选取交叉位，之后的方法同双亲双子法)、多交叉位法(间隔交换)、 双亲单子法(2选1)、显性遗传法(按位或)、单亲遗传法(2-opt)等，例子见 课本 175-179。二、什么是P问题，什么是NP问题？智能优化算法主要是针对什么问题而提出 的？解：(1) P问题记问题的实例为I,实例规模为/(I),算法4在求解I时的计算量 (基本计算总次数)为G(I).若存在多项式函数g(x)和一个常数比使得G(I) ag(/(I)对给定问题的所有实例I成立，记Q(I) = O(g(/(I),则称算 法4为解决对应问题的多项式时间算法.P类问题指具有多项式时间算法的问题类(2) NP问题若存在一个多项式函数g(x)和一个验证算法A,对一类判定 问题的任何一个“是的判定实例I都存在一个字符串S是I 的“是”回答，其规模满足/(S) = O(g(/(I),且算法A验证S 为实例I的“是”答案的计算时间为。(/(1),则称这个判定 问题是非确定多项式的，简记为NP.(3) NP-C问题和NP-Hard问题如果判定问题Q eNP且NP中的任何一个问题都可在多嘉 间内归约为Q,则称Q为NP完全(简记为NP-C).a若NP中的任何一个问题都可在多项式时间归约为判定问题 Q,则称Q为NP难(简记为NP-hard).(4) 智能优化算法主要是针对组合优化问题而提出的。三、描述组合优化问题中的一个典型例子，并建立其数学模型。解：(1)旅行商问题(Traveling Salesman Problem，TSP)设有个城市12，城市/与城市J间的距离为山 一售 货商要去这些城市推销货物，他希望从一城市出发后走遍所有的 城市且旅途中每个城市只经过一次，最后回到起点.选择一条路 经使得售货商所走路线总长度最短，这就是旅行商问题.引进决策变量勺，若商人从城市/出来后紧接着到城市八 则 Xjj = 1,否则X厂0 (/J = 12)那么TSP的数学模型可 表示为1,J=L2,- - tn,Xij iJS|5|7 S为1,2,“的非空真子集,其中|S|表示集合S中元素的个数.(2)背包问题设有一个容量为b的背包，n个容积分别为僻，价值分别为 (/ = L2r-. ;/7)的物品，选择那些物品放入背包中以使装入的物 品总价值最大，这就是背包问题.引入决策变量X/,若第/个物品被放入包中，则X, - 1,否则 Xi = 0 (/ = 1： 2 ：Z7).那么背包问题的数学模型为max、s.t.(3)并行机排序问题昭吩e0nsb f (Sj)A (t)纣，这里，纣二 f(s )- f(s )ijexp(), iff (s) f (s )j j 1I ti j五、解释蚁群智能优化算法中信息素的一种更新方法。解：在t时刻，设S是目前为止的最好可行解，而5,是当前 t时刻的最好可行解.设和f(St)是对应的目标函 数值如果 f(st) f(5)r 则 去在5的弧上增强信息素，而在其它弧上挥发信息素.方法一：f (1 一 仇一1)可(t 一 1) +if (，J) g ?= lslI (1 一 Pai)可(t 一 1),Otherwise,其中g 0 1是挥发因子，且满足I .OO心-E = o-六、描述Hopfiled人工神经网络的函数逼近一连续函数的方法。解：假设f(x)是一个连续函数.我们希望训练一个NN去逼 近函数f(x).对于一个固定神经元和网络结构的NN,网络权可作成一 个向量w.设w)是由NN所得岀的输岀.训练过程是寻找权向量W以最好地逼近函数f(x).设 (x；y；)|/ = 12r/V是训练数据集.我们希望选择 权向量w使得F(xw)对于输入x；来说最接近要求的 输出即，训练过程是找权向量w以极小化以下的误 差函数Err(W) = -HF(w)-yz ；=1Step 1.构造函数逼近的能量函数，使得能量函数有好的稳定性，如Err(w)；dz dErr (w)，* 、Step 2.由能量函数Err(w)，根据-求解出动力系统方程atoyif譽一4乙+ 呵为+ ；Step 3.用数值计算的方法求解动力系统方程的平衡点，用定理判断平衡点是否为稳定点或 渐近稳定点，网络达到稳定状态即达到极小值。七、用遗传算法解决实数编码求连续函数优化问题，写出一种变异的运算方法。 解：连续的实数变量在一定精度下也可以采用二进制编码.对给定的区间彳纵设二进制编码的长为0则变量b a b ab aX =占 + al卜I卜 an 2n与二进制码32冇相对应.二进制码与实际变量的误 差为器.再用单点变异法或多点变异法即可完成实数码的变异方法。(随机选一个或几个变异位取反)八、为什么学“智能优化算法”？学习之后有什么感想？对本课程考核方法有什 么建议。答：最优化问题使人们在工程实践中，科学研究和经济管理等诸多领域中经常 遇到的问题。