第七章单纯形优化法

1、第七章第七章 单纯形优化法单纯形优化法7-1 概述 单纯形法是一种优化设计方法单纯形法是一种优化设计方法 和正交试验相比的特点：和正交试验相比的特点：计算简便计算简便不受因素数的限制不受因素数的限制因素数的增加不会导致试验次数大量增加因素数的增加不会导致试验次数大量增加它属于非线性动态调优过程它属于非线性动态调优过程 发展简史发展简史1962年，年，spendley提出基本单纯形法提出基本单纯形法1965年，年，nelder等提出改进单纯形法等提出改进单纯形法之后，之后，routh提出加权形心法与控制加权形心法提出加权形心法与控制加权形心法7-2 基本单纯形基本单纯形 一、双因素基本单纯形法一

2、、双因素基本单纯形法如果我们有一个试验设计，只选有两个影响因如果我们有一个试验设计，只选有两个影响因素，即因素数为素，即因素数为2。分别取值。分别取值a1和和a2作为试验的初作为试验的初点。记为点。记为a(a1,a2)。对其余两个点分别设为。对其余两个点分别设为b和和c，再设三角形的边长为再设三角形的边长为a(步长步长)。那么。那么b、c点就可以点就可以计算出来计算出来 假设假设ab、 ac、bc间距均为间距均为 ，等边三角形可以算出，等边三角形可以算出b点为：点为： b=(a1+p, a2+q)根据对称性可知：根据对称性可知： c=(a1+q, a2+p)可以根据等边三角形性质解得：可以根据

3、等边三角形性质解得：312 2(91)312 2qapaa2+pa2+qa2a1+pa1+qa1因素2因素1abcdeo 由由a、b、c三点构成得单纯形称为初始单纯形三点构成得单纯形称为初始单纯形 首先在首先在a、b、c三点下分别试验，得出三个响应值，比较三点下分别试验，得出三个响应值，比较其大小，找出最坏响应值的点称为坏点其大小，找出最坏响应值的点称为坏点 此处设此处设a为坏点，去掉为坏点，去掉a点并取点并取a的对称点的对称点d点作为新试验点，点作为新试验点，比较比较b、c、d三点响应值的好坏三点响应值的好坏 此处设此处设c为坏点，去点为坏点，去点c点，取其反点点，取其反点e，此时，此时c、

4、d、e三三点又构成新的单纯形点又构成新的单纯形 重复以上结果，最终达到优化试验的目的重复以上结果，最终达到优化试验的目的 二、新试验点的计算方法二、新试验点的计算方法以初始单纯形以初始单纯形a、b、c为例，设为例，设a为坏点，为坏点，a应该去掉，求其反射点应该去掉，求其反射点d，此时，此时a(a1,a2)、b=(a1+p, a2+q)、c=(a1+q, a2+p)d=b+c-a=(a1+p+q,a2+p+q)e=b+d-c=(a1+2p,a2+2q) 即：即：新试验点新试验点留下各点之和留下各点之和去掉点去掉点(9-8) 三、多因素基本单纯形三、多因素基本单纯形 设有设有n个因素个因素n1个定

5、点构成的个定点构成的n维空间单纯形，维空间单纯形，设有一点设有一点a=(a1, a2, a3, an)，步长为，步长为a 则其余各点为：则其余各点为： b=(a1+p,a2+q,a3+q, an+q) c=(a1+q,a2+p,a3+q, an+q) (n)=(a1+q,a2+q, an-1+p, an+q) (n+1)=(a1+q,a2+q,a3+q, an+p) 其中其中112(98)112nnqannpan 新点计算新点计算新坐标点新坐标点2n留下点的坐标和留下点的坐标和/n 去掉点坐标去掉点坐标 (9-11) 四、四、n，p，q取值对应表取值对应表 由由(9-8) 我们可以算出我们可以

6、算出n取不同值的取不同值的p、q的取值的取值112(98)112nnqannpan n2345678pqn9101112131415pq0.966 0.943 0.926 0.911 0.901 0.892 0.883 0.259 0.236 0.219 0.204 0.194 0.185 0.176 0.878 0.872 0.865 0.861 0.855 0.854 0.848 0.171 0.165 0.158 0.154 0.148 0.147 0.141 n、q、p取值对应表 五、小结五、小结 用前面的例子，对两因素问题用前面的例子，对两因素问题a、b、c构成初始单纯形，构成初始单

7、纯形，在此三点上进行试验在此三点上进行试验 规则规则1：去掉最坏点，用其对称反射点作新试点：去掉最坏点，用其对称反射点作新试点 例例a、b、c中，中，a为最坏点，去掉为最坏点，去掉a点并取点并取a的对称点的对称点d点作为新点作为新试验点。试验点。 d留下各点之和留下各点之和去掉点去掉点bca 在在b、c、d三角形中继续使用规则三角形中继续使用规则1，如果，如果c为坏点，去点为坏点，去点c点，点，取其反点取其反点e，此时，此时c、d、e三点又构成新的单纯形。三点又构成新的单纯形。 如果最坏点为如果最坏点为d那么对称点就会返回到与那么对称点就会返回到与a重合，此时改用规则重合，此时改用规则2 规则

8、规则2：去掉次坏点，用其对称反射点作新试点对称计算公：去掉次坏点，用其对称反射点作新试点对称计算公式与前面相同式与前面相同经过反复使用后，如果有一个点老是保留下来，必须使用经过反复使用后，如果有一个点老是保留下来，必须使用规则规则3 规则规则3：重复、停止和缩短步长：重复、停止和缩短步长一般一个点劲一般一个点劲3次单纯形后仍未被淘汰，它可能是一个很好次单纯形后仍未被淘汰，它可能是一个很好点，也可能是偶然性或试验误差导致的假象。点，也可能是偶然性或试验误差导致的假象。此时需要重复试验：结果不好，淘汰；结果已很满意则停此时需要重复试验：结果不好，淘汰；结果已很满意则停止试验止试验反之则以它为起点缩

9、短步长，继续试验反之则以它为起点缩短步长，继续试验 六、特殊方法六、特殊方法前面介绍的单纯形是正规的，任意两点间的距前面介绍的单纯形是正规的，任意两点间的距离一样，实际上，这个要求可以不要。尤其是由离一样，实际上，这个要求可以不要。尤其是由于各个因素所取的量纲不一样（例如一个因素是于各个因素所取的量纲不一样（例如一个因素是温度（温度（），另一个因素是时间（秒）。即使量），另一个因素是时间（秒）。即使量纲一样所取的单位也可以不一样。纲一样所取的单位也可以不一样。 （一）直角单纯形法（一）直角单纯形法我们考虑双因素模型，开始不从正三角形出发，而是从一我们考虑双因素模型，开始不从正三角形出发，而是从

10、一个直角三角形出发，其顶点取值如下：个直角三角形出发，其顶点取值如下： =(a1,a2) =(a1+p1,a2) =(a1,a2+p2)用图表示如下用图表示如下a2+p2a2a1+2p1a1+p1a1因素2因素1同样比较三个顶点响应值的结果，若同样比较三个顶点响应值的结果，若最坏，则新点最坏，则新点就用对称公式就用对称公式 = =+ +- -=(a=(a1 1+p+p1 1,a,a2 2+p+p2 2) )在得到在得到点后，再用点后，再用、三点试验，比较其结果，三点试验，比较其结果，若若最坏，则取其对称点最坏，则取其对称点做新试验点做新试验点 =+ +- -=(a=(a1 1+2p+2p1 1

11、,a,a2 2) )、构成一个新单纯形，比较其结果，若构成一个新单纯形，比较其结果，若最坏，最坏，则用规则则用规则2去掉次坏点，若次坏点为去掉次坏点，若次坏点为，则新点，则新点 =+ +-=(a=(a1 1+2p+2p1 1,a,a2 2-p-p2 2) )如此等等，有时还会使用规则如此等等，有时还会使用规则3 3，直至结果满意为止。，直至结果满意为止。一般在任意一般在任意n个因素时个因素时 =(a1, a2, a3, an) =(a1+p1,a2,a3, an) =(a1,a2+p2,a3, an) (n)=(a1,a2, an-1+pn-1, an) (n+1)=(a1,a2,a3, an

12、+pn) （二）、双水平单纯形法（二）、双水平单纯形法7-3 改进单纯形法改进单纯形法 为了解决优化结果精度和优化速度的矛盾，可以为了解决优化结果精度和优化速度的矛盾，可以采用可变步长推移单纯形，此即改进单纯形法，采用可变步长推移单纯形，此即改进单纯形法，既能加快优化速度，又能获得较好的优化精度。既能加快优化速度，又能获得较好的优化精度。 改进单纯形法是改进单纯形法是1965年年janelder等提出来的，等提出来的，它是在基本单纯形法的基础上引入了它是在基本单纯形法的基础上引入了反射反射、扩大扩大、收缩收缩与与整体收缩整体收缩规则，变固定步长为规则，变固定步长为可变步长可变步长，较好地解决了

13、优化速度与优化精度之间的矛盾，较好地解决了优化速度与优化精度之间的矛盾，是各种单纯形优化法中应用最广泛的一种单纯形是各种单纯形优化法中应用最广泛的一种单纯形优化方法。优化方法。 两因素单纯形的推移过程两因素单纯形的推移过程因素1因素2bacdeona改进单纯形nd 单纯形的整体收缩单纯形的整体收缩因素1因素2abcca 在单纯形的推移过程中，新实验点在空间的位置在单纯形的推移过程中，新实验点在空间的位置坐标按以下方法计算：坐标按以下方法计算：(919)0naa留下各点的坐标和新试点的坐标(1+a)去掉点的坐标式中 是大于 的系数 讨论：讨论：a1，此时，此时(9-19)式变差基本单纯形中新点的

14、计算公式，此式变差基本单纯形中新点的计算公式，此时新试验点为去掉点的等距离反射点，这时改进单纯形又时新试验点为去掉点的等距离反射点，这时改进单纯形又变成了基本单纯形变成了基本单纯形a1，按基本单纯形法（，按基本单纯形法（a1）计算出新点后，对新试验点）计算出新点后，对新试验点做试验得出新试验点的响应值。如果新点的响应值好，说做试验得出新试验点的响应值。如果新点的响应值好，说明我们搜索方向正确，可以进一步沿明我们搜索方向正确，可以进一步沿ad搜索。因此取搜索。因此取a1，称为称为扩大扩大。如果扩大点。如果扩大点e不如反射点不如反射点d好，则好，则“扩大扩大”失败，失败，仍采用仍采用d，由反射点何

15、留下点构成的单纯形，由反射点何留下点构成的单纯形bcd继续优化继续优化 -1a0，按（，按（a1）计算出来的反射点）计算出来的反射点d的响应值最坏，此时的响应值最坏，此时采用采用-1a0（称为（称为内收缩内收缩）计算新试验点，此时形成新的单纯）计算新试验点，此时形成新的单纯形形bnac 0a1，按基本单纯形法（，按基本单纯形法（a1）计算除反射点）计算除反射点d响应值最坏。响应值最坏。但比去掉点但比去掉点a响应值好。此时采用响应值好。此时采用0a1，称为，称为收缩收缩，新试点，新试点仍按仍按(9-19)式计算，此时形成新的单纯形式计算，此时形成新的单纯形bcnd 如果去掉点与其反射点连线如果去

16、掉点与其反射点连线ad方向上所有点的响应值都比去方向上所有点的响应值都比去掉点掉点a坏，则不能沿此方向搜索。这时应以单纯形中最好点为坏，则不能沿此方向搜索。这时应以单纯形中最好点为初点，到其它各点的一半为新点，构成新的单纯形初点，到其它各点的一半为新点，构成新的单纯形bac进行进行优化。此时步长减半，称为优化。此时步长减半，称为“整体收缩整体收缩”7-4 加权形心法加权形心法 基本单纯形和改进单纯形都是采用去掉点的反射基本单纯形和改进单纯形都是采用去掉点的反射方向为新试验点的搜索方向，这就意味着，去掉方向为新试验点的搜索方向，这就意味着，去掉点的反射方向作为近似的优化方向，就是梯度变点的反射方

17、向作为近似的优化方向，就是梯度变化最大的方向化最大的方向 实际上，这个方向是一个近似的梯度最大方向，实际上，这个方向是一个近似的梯度最大方向，这样的搜索结果可能导致搜索次数的增加和搜索这样的搜索结果可能导致搜索次数的增加和搜索结果精度的降低结果精度的降低 为了解决这个问题，提出了加权形心法，加权形为了解决这个问题，提出了加权形心法，加权形心法利用加权形心代替单纯的反射形心，使新点心法利用加权形心代替单纯的反射形心，使新点的搜索方向更接近实际的最优方向的搜索方向更接近实际的最优方向因素1因素2bcoeeo形心点o和加权形心点o 如图，使如图，使w、b、c三个顶点组成的一个二因素的三个顶点组成的一

18、个二因素的优化过程的一个单纯形，并知优化过程的一个单纯形，并知w点的响应最坏点的响应最坏，b的响应最好的响应最好。 如果搜索优化过程中函数不出现异常，那么搜索如果搜索优化过程中函数不出现异常，那么搜索最优点的方向明显应当更靠近最优点的方向明显应当更靠近wb的方向，而不是的方向，而不是靠近靠近wc的方向。因此可以通过加权的办法来使搜的方向。因此可以通过加权的办法来使搜索的方向由原来的索的方向由原来的we（反射方向）（反射方向）变为变为we方向方向（加权方向）（加权方向），此时用加权形心点，此时用加权形心点o 代替反射形代替反射形心点心点o3131 ()( )(920) ()( )i()i( )i

19、iiiiiir prpor prpr pr加权形心点其中为第 点的坐标为的 点的响应值。为最坏点的响应值。11()11()n ()( )(921) ()( ) niiiiniiir prpor proo同样对于 因素的加权形心点计算如下：然后将代替改进单纯形法中的形心点，即成为加权形心法。7-5 单纯形优化的参数选择单纯形优化的参数选择 在试验中，我们只研究优化条件，可用基本单纯在试验中，我们只研究优化条件，可用基本单纯形法时，首先必须确定研究的因素形法时，首先必须确定研究的因素 由于单纯形法不受因素的限制，考察的因素可以由于单纯形法不受因素的限制，考察的因素可以相对的多些相对的多些 因素确定

20、后，据分析仪器和试验要求，规定因素因素确定后，据分析仪器和试验要求，规定因素变化的上下限，据上下限的范围确定步长的大小。变化的上下限，据上下限的范围确定步长的大小。 步长较大，优化速度加快，精度较差；步长太小步长较大，优化速度加快，精度较差；步长太小试验次数增多，优化速度变慢试验次数增多，优化速度变慢 一、试验指标一、试验指标 试验指标是用于衡量和考核试验响应的各种数值试验指标是用于衡量和考核试验响应的各种数值 在分析测试中可将仪器响应值作为试验指标，但有时须在分析测试中可将仪器响应值作为试验指标，但有时须转换称其它的数量，试验指标是数量化的，以便直接比转换称其它的数量，试验指标是数量化的，以

21、便直接比较结果的大小较结果的大小 二、初始单纯形的构成二、初始单纯形的构成 本章第一节介绍的方法是根据本章第一节介绍的方法是根据初始点初始点和和步长步长来计来计算初始单纯形的各个顶点，各因素的步长是相同算初始单纯形的各个顶点，各因素的步长是相同的的 实际过程中，各因素步长和单位并不相同，利用实际过程中，各因素步长和单位并不相同，利用这种方法会变得很麻烦，在实际应用中问题较多这种方法会变得很麻烦，在实际应用中问题较多 我们介绍下述两个构成初始单纯形的方法我们介绍下述两个构成初始单纯形的方法 （一）（一）long系数表法系数表法 d.e.long提出一种用系数表构成初始单纯形各顶点的提出一种用系数

22、表构成初始单纯形各顶点的方法，可以解决试验设计中初始单纯形的构成问题方法，可以解决试验设计中初始单纯形的构成问题 使用时把表中的对应值乘上该因素的步长后，再加到使用时把表中的对应值乘上该因素的步长后，再加到初始点坐标上初始点坐标上1234567891010a b c d e f g h i j01.000.500.500.500.500.500.500.500.500.50000.8660.2890.2890.2890.2890.2890.2890.2890.2890000.8170.2040.1580.2040.2040.2040.2040.20400000.7910.1580.1580.1

23、580.1580.1580.158000000.7750.1290.1290.1290.1290.1290000000.7640.1090.1090.1090.10900000000.7560.0940.0940.094000000000.7500.0830.0830000000000.7450.07500000000000.742因素顶点long系数表 例：有一个二因素的设计过程，其初始点为例：有一个二因素的设计过程，其初始点为(10.0,2.0)；步长为；步长为1.0和和0.5，据，据long系数表来计系数表来计算其余两个顶点的坐标算其余两个顶点的坐标 顶点顶点1： （10.0,2.0）

24、顶点顶点2： （10.0+1.001.0，1.0+00.5） =（11.0,2.0） 顶点顶点3： （10.0+0.51.0，2.0+0.8660.5） =（10.5，2.433） （二）均匀设计表法（二）均匀设计表法 利用利用long系数表法所构成的初始单纯形各顶点在空间系数表法所构成的初始单纯形各顶点在空间的分布是不均匀的，因此进行的是不均匀优化的分布是不均匀的，因此进行的是不均匀优化 均匀设计表改变了这个缺点，使各顶点在空间均匀分均匀设计表改变了这个缺点，使各顶点在空间均匀分布，这样进行的优化就是布，这样进行的优化就是整体的均匀优化整体的均匀优化 据所选因素的因素数，确定一个比较合适的均匀表，据所选因素的因素数，确定一个比较合适的均匀表，使用时把表中的对应数值乘以响应因素的步长，加到使用时把表中的对应数值乘以响应因素的步长，加到初始点坐标上即可初始点坐标上即可 例：我们有一个四因素的优化过程，因此可以选例：我们有一个四因素的优化过程，因此可以选用四因素的均匀设计表。设初点为用四因素的均匀设计表。设初点为(1