II 一、写出遗传算法中的两种交叉运算方法，并分别举例说明。 解：双亲双子法（两父代交叉位之后的全部基因互换）、变化交叉法（从不相同 的基因开始选取交叉位，之后的方法同双亲双子法）、多交叉位法（间隔交换）、 双亲单子法（2选1）、显性遗传法（按位或）、单亲遗传法（2-opt）等，例子见 课本 175-179。
二、什么是P问题，什么是NP问题？智能优化算法主要是针对什么问题而提出 的？ 解：（1）P问题
记问题的实例为I,实例规模为/（I）,算法人在求解1时的计算量
〔基本计算总次数）为G（I）.
•若存在多项式函数g（x）和一个常数e使得
对给定问题的所有实例1成立，记cxi） = o（g（qi）））「则称算 法人为解决对应问题的多项式时间算法，
P类问题指具有多项武时间算法的问题类
（2） NP问题
若存在一个多项式函数g（x）和一亍验证算法几对一类判定 问题的任何一个“是”的判定实例I都存在一个字符串S是1 的“是“回答，其规模满足/（S） = 0（外（1｝几且算法A验证5 为实例1白勺」是“答案的计算时间为0（g（/（I）））r则称这个判定 问题是非确定多项式的’简记为NP
（3） NP-C问题和NP-Hard问题
•如果判定问题Q eNP且NP中的任何一个问题都可在多朗 间內归约为Qt则称Q为NP完全（简记为NP-C）.
•若NP中的任何一个问题都可在多项式时间归约为判定问题 Qr则称Q为NP难（简记为NP-hard）.
（4）智能优化算法主要是针对组合优化问题而提出的。
三、描述组合优化问题中的一个典型例子，并建立其数学模型。
解：（1）旅行商问题（Traveling Salesman Problem TSP）
设有n个城市1.2. ?n可发性聚苯乙烯T城市f勻城市J间的距离为dfj —售 货商要去这些城市推销货物，他希望从一城市出发后走遍所有的 城市且旅途中每个城市只经过一次，最后回到起点.选择一条路 经使得售货商所走路线总长唐最短，这就是旅行商问题
引进决策变量切，若商人从城市，岀来后紧接着到城市八 则 旳=1.否则勺=0 (/.； = 1.2. ./)).那么TSP的数学模型可
表示为
* n有机物除杂 n
min 內
J=1 J=1
D
£ Xy = 厶* ■ * $ 馮
J=1
* f 旳=h j = 1.2, - ,n,
i=l
E旳< |5| - 1, S为{lt2…』}的非空真子筑
Jjes
, Xij e {0:l}7 i；j — ・ E 知
其中|S|表示集合s中元素的亍数
(2)背包问题
设有一个容量为b的背包.n个容积分别为旳，价值分别为q- (；=1 2. . n)的物品，选择那些物品放入背包中以使装入的物
品总价值最大，这就是背包问题一
引入决策变量坨，若第；个物品被放入包中，则x； = b否则 片=0(『=1_2一那么背包问题的数学模型为
max 刀 cixi
j=i
n
* S.t. S WfXi < b
i=l
、 Xi e dna复制方向{0,1}, /= ,n.
(3)并行机排序问题
设有m台同型机器隔陋、….Mrnt n个相互独立的工件
」丄…几现在要安排这些工件到机器上进行加工，设每个工 件只需在任一台机器上加工，工件d的如工时间为口
(/ = 1 2 ■- n).如何安携这些工件的加工方案，以使机器完成
所有工作的时间最少一这就是井行机排序问题一
引入决策变量冷，若工件丿」在机器明上加工，则勺=1,否 则駕=0.那么井行机排序问题的数学模型为
min T
m
必52冷=h # = X N…m
« 7=1 n
r> £ j = h 2：…冲
;
=1
靭 E{°1}： / = 1,2.^- . nJ = 1,2, - Tm.
四、描述模拟退火算法中的接收准则。
腺苷蛋氨酸解：在一给定温度下，由一个状态变到另一个状态，每一个状态到达的次数服从 一个概率分布，即基于Metropolis接受准则的过程，该过程达到平衡时停止。在 状态s时，产生的状态s被接受的概率为： 1 if f(S)"(Sj)
W为iff(S)<fd这里，3讣心.
五、解释蚁智能优化算法中信息素的一种更新方法。
解：
在t时刻「设专是目前为止的最好可行解「而$是当前 t时刻的最好可行解.设f(s)和f(sr)是对应的目标函 数值一
如果 f(st) < f(s)t 则 S 一 匀
在S的弧上增强信息素，而在其它弧上挥发信息素一
方法一：
J (1— pt—i)坊(匸一1) + 评(jJ)e =
$ ||
I (1 一 一 1), otherwise,
其中g 0 < fr < 1是挥发因子，且满足
六、描述Hopfiled混沌模式人工神经网络的函数逼近一连续函数的方法。
解：
假设f(x)是一个连续函数.我们希望训练一个NN去逼 近函数fg
对于一个固定神经元和网络结构的NN,网络权可作成一
个向量w.设F(x.w)是由NN所得出的输出 训练过程是寻权向量W以最好地逼近函数f(x).设 ｛(*占；)卩=12….N｝是训练数据集’我们希望选择 权向量w使得F(x\w)对于愉入x；来说最接近要求的 输出听.即，训练过程是权向量w以极小化以下的误 差函数
1 “
Frr(w) = -液体表面张力J2||F(x*tw)-y；||2.
z *=i
Step 1.构造函数逼近的能量函数，使得能量函数有好的稳定性，如 Err(w);
Step 2.由能量函数 Err (w)，根据-dZi_ = - Err (w)求解出动力系统方程
dt cyi
｛
孚 =—A石+ K 呦乃41*
；
Step 3.用数值计算的方法求解动力系统方程的平衡点，用定理判断平衡点是否为稳定点或 渐近稳定点，网络达到稳定状态即达到极小值。
七、用遗传算法解决实数编码求连续函数优化问题，写出一种变异的运算方法。 解：
连续的实数变量在一定精度下也可以采用二进制编码一
对给定的区间[a.fe],设二进制编码的长为m则变量
b — a b - a b - a
X — a + 3j— 卜 32 * * * + 3“ 2打
与二进制码巧电…咼 相对应.二进制码与实际变量的误 差为
再用单点变异法或多点变异法即可完成实数码的变异方法。 (随机选一个或几个变异位取反)
八、为什么学 智能优化算法”？学习之后有什么感想？对本课程考核方法有什 么建议。
答：最优化问题使人们在工程实践中，科学研究和经济管理等诸多领域中经常 遇到的问题。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议