你在这里

优选法阅读

主标签

优选法

  • 一个真实案例

某电子管厂从仓库中清出了积压多年的几百万米某种“废”金属丝。为了使得这些废金属丝能够重新被利用,科研人员经过研究发现,找出准确的退火温度是使该废金属丝复活的关键。 由经验知道,退火温度的范围为\([{1400^ \circ }C,{1600^ \circ }C]\),因此,试验范围为\([{1400^ \circ }C,{1600^ \circ }C]\)。如果不考虑其他次要因素,则该金属丝的质量指标\(f(t)\)是温度\(t\)的函数,其中\(t \in [1400,1600]\)。由于目标函数\(f(t)\)的具体表达式不知道,因此,该问题的关键在于能否通过次数尽量少的调温试验,求出满足一定精度条件下的最佳退火温度。

华罗庚先生70年代初期支援大西南三线建设期间的一个案例)

分析: 尽管目标函数\(f(t)\)的具体表达式不知道,但是根据经验可知:从退火温度的最低点1400\(^ \circ C\)开始,随着\(t\)的增大,质量指标\(f(t)\)的函数值随之增大;当达到最佳退火温度\({t_0}\)时,随着\(t\)的继续增大,一直到最高点1600\(^ \circ C\),质量指标\(f(t)\)的函数值随之减少。也就是说,\(f(t)\)是在试验区间内先增后减的单峰函数,其中只有唯一的一个最优点。

试验方法讨论:

  1. 等分法

通常的想法是:在试验区间[1400,1600]上均匀取点试验,就可以求得满足一定精度要求的最佳退火温度。例如,若要求精度达到\(\frac{1}{{20}}\),我们只要在

\({t_1} = 1410,{t_2} = 1420,{t_3} = 1430, \cdots ,{t_{19}} = 1590\)

各点进行试验,通过比较各点的试验结果,就能找到最佳试验点。例如,若发现\({t_9} = 1490\)是其中最好的点,就可以断定最佳退火温度必在区间(1480,1500)上。在生产实际中,就可以把1490\(^ \circ C\)作为最佳退火温度。

问题:每一次试验都需要较高的成本,而上述等分法均匀取点,试验时没有考虑已经获得的质量指标\(f(t)\)的信息,往往需要作大量试验才能获得较好的结果。因此等分法是一种浪费的方法。

需要找到一种更节约的方法。

  1. 优选法(0.618法-黄金分割法)

(受到蜂巢结构的启发)

具体步骤如下:

先在试验区间的0.618处做第一次试验,第一点的温度为:

`第一次点=(大-小)×0.618+小=(1600-1400)×0.618+1400=1520^{\circ}C`

第二次试验:在第一次点关于中心对称的点,即第二次的温度为

`第二次点=大-第一次点+小=1600-1520+1400=1480^{circ}C`    

比较上面的两次结果,如果1480\(^ \circ C\)点较好,去掉1520\(^ \circ C\)(称之为“坏点”)以上的温度。然后在[1400\(^ \circ C\),1520\(^ \circ C\)]中找出第二试验点1480\(^ \circ C\)的对称点,在该点做第三次试验,再比较两次试验结果,把“坏点”的外部去掉。如此反复试验,温度范围越来越少,最后找出一个合适的温度进行生产。

由于采取0.618法,大大减少试验次数,与等分法相比,在70年代环境下为国家节约资金约10万元。

0.618法算法描述:

设试验区间为\([a,b]\),0.618法要求第一个试验点安排在\({x_1} = (b - a) \times 0.618 + a\),第二个试验点安排在\({x_2} = a + b - {x_1}\)处,此时对比\({x_1},{x_2}\)的结果,裁去“坏点”外边的部分,留下的区间长度为\({L_2} = (b - a) \times 0.618\),精度为\({G_2} = (b - a) \times {0.618^2}\),且每个试验点\({x_n}\)可按照如下公式计算:

第n次试验后留下的区间的长度和精度分别为

\({L_n} = (b - a) \times {0.618^{n - 1}}\),\({G_n} = (b - a) \times {0.618^n}\)

与等分法的试验结果比较

 优选法试验次数

   2

5

9

17

19

效果

剩余区间长是原试验区间长的比率

0.618

0.146

0.021

0.004

0.0015

精       度

0.382

0.09

0.012

0.002

0.001

相当于等分法试验次数

3

11

84

400

1000

优选法的特点:充分利用已有信息

优选法的合理性 ?(为什么要采用0.618法?)

以区间[0,1]进行说明,设\({x_1},{x_2}\)是最初的两个试验点,并且\({x_1} > {x_2}\),在试验开始之前或者仅取其中一个点做试验不能确定哪一个点会更好一些,因此,丢掉\([0,{x_2}],[{x_1},1]\)都有可能,为了试验公平,要求它们一样长,即

           \({x_2} = 1 - {x_1}\)

故\({x_2}\)应是\({x_1}\)关于试验区间的对称点。

为了有利于试验的继续进行,经过取舍后,保留的一点(即新范围内所含的已试点)在新范围内仍应处于相应的位置。即,若丢掉\([{x_1},1]\)留下\([0,{x_1}]\),则\({x_2}\)在新区间\([0,{x_1}]\)中的位置应与\({x_1}\)在区间[0,1]中的位置相同,即其比值相同,故

\(\frac{{{x_1}}}{1} = \frac{{{x_2}}}{{{x_1}}}\)

由上述两个方程得到

             \(x_1^2 + {x_1} - 1 = 0\)

解得正根

                    \({x_1} = \frac{{\sqrt 5  - 1}}{2} \approx 0.618\)

若丢掉\([0,{x_2}]\),同样可得\({x_1} = \frac{{\sqrt 5  - 1}}{2} \approx 0.618\)。

称\(k = \frac{{\sqrt 5  - 1}}{2}\)为黄金分割比。

黄金分割法的适用范围:目标为在某个范围[a,b]内变化的一个变量\(x\)的单峰函数\(y = f(x)\),并且不知道函数\(y = f(x)\)的表达式。

黄金分割法的数学理论支撑:设函数\(y = f(x)\)是区间\([a,b]\)上的单峰函数,\({x_2} < {x_1}\)为试验区间\([a,b]\)上的两点,\({x^ * }\)是最优点,则

  1. 若\(f({x_1})\)优于\(f({x_2})\),则\({x^ * } \in ({x_2},b)\);
  2. 若\(f({x_1})\)劣于\(f({x_2})\),则\({x^ * } \in (a,{x_1})\)

分数法的产生

  1. 斐波那契数列

兔子问题:如果有一对成兔每月生一对幼兔,幼兔经过两

个月变成成兔,并开始繁殖,若不发生任何死亡,问年初一对幼兔一年后能繁殖成多少对兔子?

设\({u_n}\)表示第\(n\)个月底大兔子的对数,那么依题意得:

\(\left\{ {\begin{array}{*{20}{c}}{{u_1} = {u_2} = 1}\\{{u_{n + 1}} = {u_n} + {u_{n - 1}}}\end{array},n = 1,2, \cdots } \right.\)

性质:

\({u_n} = \frac{1}{{\sqrt 5 }}[{(\frac{{1 + \sqrt 5 }}{2})^n} - {(\frac{{\sqrt 5  - 1}}{2})^n}]\)

\(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n}}}{{{u_{n + 1}}}} = \frac{{\sqrt 5  - 1}}{2}\)为黄金分割数

利用上述的分数\(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n}}}{{{u_{n + 1}}}} = \frac{{\sqrt 5  - 1}}{2}\)的性质,设计如下分数法:

利用比值\(\frac{{{u_n}}}{{{u_{n + 1}}}}\)得到一个分数数列

\(\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{{13}},\frac{{13}}{{21}},\frac{{21}}{{34}}, \cdots ,\frac{{{u_{n + 1}}}}{{{u_{n + 2}}}}, \cdots \)

它的分子与分母都是斐波那契数。

假若知道试验次数,如需作5次试验,则选取第5 个分数

\({F_5} = \frac{8}{{13}}\)。做法如下:将试验区间\([a,b]\)分成13等份,在第8个分点安排第一次试验,在8的对称点5处安排第二次试验,比较8和5两处的优劣,如8好,则去掉\([a,5]\)段(否则去掉\([8,b]\)段,剩下的区间为\([a,8]\)),剩下的区间为\([5,b]\);第二次及其后续试验原理与0.618法完全相同。

统筹法及其思想

一项工程由若干到工序来完成,每道工序都需要一定的工期,各道工序之间存在一定的前后衔接关系,那么,工程进度如何管理使总的工期时间最少?

国际上称之为计划评审法或关键轨道法,中国被华罗庚先生称之为统筹法。

一个例子:造某栋房子的工序、工期和工序衔接关系如表所示

工序代号

工序名称

工期(天)

紧前工序

A

了解设计要求

3

B

地基建设

5

A

C

建造主体结构

12

B

D

排设管道

5

C

E

埋置电缆线

3

C

F

安装空调设备

7

E

G

建隔离墙

9

D,F

H

外墙装饰

15

C

I

内强装饰

7

G

J

地面装饰

3

I

K

环境美化

4

H

表中的“紧前工序”是指紧接着的前道工序,B的紧前工序为A是指在工序A完成后才能实施工序B;工序A的紧前工序为“无”是指不依赖于其它工序是否完成。

问:怎样安排才能使工程以最快的时间完工?

分析:如果一道工序接着一道工序做完,时间为73天。画出施工过程图,知其中有些工序可以同时进行。如:工序C完成后,工序D和工序E,以及工序D和工序F之间无依赖关系,如果他们同时施工,那么在工序F完成时,工序D也已经完成,从而缩短5天工期。

关键轨道法本质上就是如何利用时间的可重叠性实现并行施工。重叠时间最多者即位最优算法。