最优化理论与方法2009年试题

1. 图1 所示的(a)和(b)分别为两种基本状态空间搜索，请指出它们分别是什么搜索方式？这两种搜索方式都属于什么搜索方法？它们是否具有启发性搜索的特点？(2分

)

(a) (b) 图1 两种基本状态空间搜索

2. 简单介绍一下A*算法，并试用A*算法寻找图2中给出一个8数码问题从起始布局s到最终布局g的最优移动步骤。以离家将牌数Misplaced(n)为启发函数，用A*算法构造搜索图。每移动一步时的价值是相等的。(6分

)

(a)起始布局s (b)目标布局g

图2 起始布局和目标布局

3. 已知霍普费尔德网络的基本结构如图3所示。设双极硬限器为：

(1)

这里取Ti＝0。

在同步进行时，网络中所有神经元的更新同时进行，也就是

(2)

0 0.3 1

其中初始值I0 0.7 ；S0 1 ；权系数为：W 1

2

。 0

试用霍氏神经网进行更新迭代过程计算，要求迭代2步以上。(4分

)

图3 神经网络的基本结构

4.二分图最优化问题定义为：给定n（n为偶数）个节点，任意两节点相互连线，由此连成一个线图；对于此线图，用分割线将所有节点分为二等份，从而获得一个二分图，要求该分割线跨越这两组之间的连线最少。如图4的线图中，给出了两种不同的分割方式，分割1有10条跨越连线，分割2有2条跨越连线（此为最小值）。

图4 二分图示例

问题：(1) 写出连接矩阵W表示图4所示的连接方式；（提示：注意写出矩阵W元素wij的定义）(2) 写出求解该二分图问题求解的Hopfield网络能量函数。（提示：注意写出节点i处神经元vi的定义）(6分)

5. 简述Metropolis准则，并用该准则说明为什么模拟退火算法能够越过局部极小值达到全局最小值。（3分）

6. 试用二进制遗传算法求解下述约束整数优化问题：

min f (x)＝x1＋x2＋x3

s.t. 7 x1 15 3 x2 6 5 x3 10

取初始群体个体数为3，即初始群体为vi =( x 1i, x 2i, x 3i), i=1,2,3。根据选择操作分别在满足约束条件下随机选取，设它们是：v 1=(11, 5, 10)、v 2=(8, 6, 9)与v 3=(13, 4, 7)。选择适应度函数为fi =80 f (xi)。请通过进行交叉，变异，选择遗传操作来求解上述的优化问题，进行两轮以上的遗传操作。并完成表1所示的数据表，注意：表格按表1的形式画在大题纸上，行可以增加到10行左右。(9分)

表1 当前群体各个体的数据表

7. 已知系统方程为

1 x x2 2 x， xu 2

边界条件为

xt 0

0 2

，xt 2 ，

0 1

求使性能泛函

J

12

20

udt

2

为极小值的最优控制函数u t 与最优轨迹x t 。(10分)

8. 在下列网络图中，数字代表连接两节点的有向弧弧长，试用函数空间迭代法求

（1）各点到t的最短路线。(5分) （2）t到各点的最短路线。(5分)

图5 两种基本状态空间搜索