第七章单纯形优化法-PPT.pptx

第七章单纯形优化法发展简史发展简史1962年年,Spendley提出基本单纯形法提出基本单纯形法1965年年,Nelder等提出改进单纯形法等提出改进单纯形法之后之后,Routh提出加权形心法与控制加权形心法提出加权形心法与控制加权形心法7-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)可以根据等边三角形性质解得可以根据等边三角形性质解得:a2+pa2+qa2a1+pa1+qa1因素2因素1ABCDEo由由A、B、C三点构成得单纯形称为初始单纯形三点构成得单纯形称为初始单纯形首先在首先在A、B、C三点下分别试验三点下分别试验,得出三个响应值得出三个响应值,比较其比较其大小大小,找出最坏响应值得点称为坏点找出最坏响应值得点称为坏点此处设此处设A为坏点为坏点,去掉去掉A点并取点并取A得对称点得对称点D点作为新试验点点作为新试验点,比较比较B、C、D三点响应值得好坏三点响应值得好坏此处设此处设C为坏点为坏点,去点去点C点点,取其反点取其反点E,此时此时C、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个定点构成得个定点构成得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)其中其中新点计算新点计算新坐标点新坐标点2n留下点得坐标与留下点得坐标与/n 去掉点坐标去掉点坐标 (9-11)四、四、n,p,q取值对应表取值对应表由由(9-8)我们可以算出我们可以算出n取不同值得取不同值得p、q得取值得取值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取值对应表12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流五、小结五、小结用前面得例子用前面得例子,对两因素问题对两因素问题A、B、C构成初始单纯形构成初始单纯形,在在此三点上进行试验此三点上进行试验规则规则1:去掉最坏点去掉最坏点,用其对称反射点作新试点用其对称反射点作新试点例例A、B、C中中,A为最坏点为最坏点,去掉去掉A点并取点并取A得对称点得对称点D点作为新试点作为新试验点。验点。D留下各点之与留下各点之与去掉点去掉点BCA在在B、C、D三角形中继续使用规则三角形中继续使用规则1,如果如果C为坏点为坏点,去点去点C点点,取其取其反点反点E,此时此时C、D、E三点又构成新得单纯形。三点又构成新得单纯形。如果最坏点为如果最坏点为D那么对称点就会返回到与那么对称点就会返回到与A重合重合,此时改用规则此时改用规则2规则规则2:去掉次坏点去掉次坏点,用其对称反射点作新试点对称计算公式用其对称反射点作新试点对称计算公式与前面相同与前面相同经过反复使用后经过反复使用后,如果有一个点老就是保留下来如果有一个点老就是保留下来,必须使用规必须使用规则则3规则规则3:重复、停止与缩短步长重复、停止与缩短步长一般一个点劲一般一个点劲3次单纯形后仍未被淘汰次单纯形后仍未被淘汰,它可能就是一个很好它可能就是一个很好点点,也可能就是偶然性或试验误差导致得假象。也可能就是偶然性或试验误差导致得假象。此时需要重复试验此时需要重复试验:结果不好结果不好,淘汰淘汰;结果已很满意则停止试结果已很满意则停止试验验反之则以它为起点缩短步长反之则以它为起点缩短步长,继续试验继续试验六、特殊方法六、特殊方法前面介绍得单纯形就是正规得前面介绍得单纯形就是正规得,任意两点间得任意两点间得距离一样距离一样,实际上实际上,这个要求可以不要。尤其就是由这个要求可以不要。尤其就是由于各个因素所取得量纲不一样于各个因素所取得量纲不一样(例如一个因素就是例如一个因素就是温度温度(),(),另一个因素就是时间另一个因素就是时间(秒秒)。即使量纲一。即使量纲一样所取得单位也可以不一样。样所取得单位也可以不一样。(一一)直角单纯形法直角单纯形法我们考虑双因素模型我们考虑双因素模型,开始不从正三角形出发开始不从正三角形出发,而就是从一而就是从一个直角三角形出发个直角三角形出发,其顶点取值如下其顶点取值如下:=(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,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+pn)(二二)、双水平单纯形法、双水平单纯形法7-3 改进单纯形法改进单纯形法为了解决优化结果精度与优化速度得矛盾为了解决优化结果精度与优化速度得矛盾,可以采可以采用可变步长推移单纯形用可变步长推移单纯形,此即改进单纯形法此即改进单纯形法,既能加既能加快优化速度快优化速度,又能获得较好得优化精度。又能获得较好得优化精度。改进单纯形法就是改进单纯形法就是1965年年J、A、Nelder等提出来等提出来得得,它就是在基本单纯形法得基础上引入了反射、它就是在基本单纯形法得基础上引入了反射、扩大、收缩与整体收缩规则扩大、收缩与整体收缩规则,变固定步长为可变步变固定步长为可变步长长,较好地解决了优化速度与优化精度之间得矛盾较好地解决了优化速度与优化精度之间得矛盾,就是各种单纯形优化法中应用最广泛得一种单纯形就是各种单纯形优化法中应用最广泛得一种单纯形优化方法。优化方法。两因素单纯形得推移过程两因素单纯形得推移过程因素1因素2BACDEONA改进单纯形ND单纯形得整体收缩单纯形得整体收缩因素1因素2ABCCA在单纯形得推移过程中在单纯形得推移过程中,新实验点在空间得位置坐新实验点在空间得位置坐标按以下方法计算标按以下方法计算:讨论讨论:a1,此时此时(9-19)式变差基本单纯形中新点得计算公式式变差基本单纯形中新点得计算公式,此时此时新试验点为去掉点得等距离反射点新试验点为去掉点得等距离反射点,这时改进单纯形又变成这时改进单纯形又变成了基本单纯形了基本单纯形a1,按基本单纯形法按基本单纯形法(a1)计算出新点后计算出新点后,对新试验点做试对新试验点做试验得出新试验点得响应值。如果新点得响应值好验得出新试验点得响应值。如果新点得响应值好,说明我们说明我们搜索方向正确搜索方向正确,可以进一步沿可以进一步沿AD搜索。因此取搜索。因此取a1,称为扩大。称为扩大。如果扩大点如果扩大点E不如反射点不如反射点D好好,则则“扩大扩大”失败失败,仍采用仍采用D,由由反射点何留下点构成得单纯形反射点何留下点构成得单纯形BCD继续优化继续优化-1a0,按按(a1)计算出来得反射点计算出来得反射点D得响应值最坏得响应值最坏,此时采用此时采用-1a0(称为内收缩称为内收缩)计算新试验点计算新试验点,此时形成新得单纯形此时形成新得单纯形BNAC0a1,按基本单纯形法按基本单纯形法(a1)计算除反射点计算除反射点D响应值最坏。但响应值最坏。但比去掉点比去掉点A响应值好。此时采用响应值好。此时采用0a1,称为收缩称为收缩,新试点仍按新试点仍按(9-19)式计算式计算,此时形成新得单纯形此时形成新得单纯形BCND如果去掉点与其反射点连线如果去掉点与其反射点连线AD方向上所有点得响应值都比去方向上所有点得响应值都比去掉点掉点A坏坏,则不能沿此方向搜索。这时应以单纯形中最好点为初则不能沿此方向搜索。这时应以单纯形中最好点为初点点,到其它各点得一半为新点到其它各点得一半为新点,构成新得单纯形构成新得单纯形BAC进行优化。进行优化。此时步长减半此时步长减半,称为称为“整体收缩整体收缩”7-4 加权形心法加权形心法基本单纯形与改进单纯形都就是采用去掉点得反射基本单纯形与改进单纯形都就是采用去掉点得反射方向为新试验点得搜索方向方向为新试验点得搜索方向,这就意味着这就意味着,去掉点得去掉点得反射方向作为近似得优化方向反射方向作为近似得优化方向,就就是梯度变化最就就是梯度变化最大得方向大得方向实际上实际上,这个方向就是一个近似得梯度最大方向这个方向就是一个近似得梯度最大方向,这这样得搜索结果可能导致搜索次数得增加与搜索结果样得搜索结果可能导致搜索次数得增加与搜索结果精度得降低精度得降低为了解决这个问题为了解决这个问题,提出了加权形心法提出了加权形心法,加权形心法加权形心法利用加权形心代替单纯得反射形心利用加权形心代替单纯得反射形心,使新点得搜索使新点得搜索方向更接近实际得最优方向方向更接近实际得最优方向因素1因素2BCOEEO形心点O与加权形心点O如图如图,使使W、B、C三个顶点组成得一个二因素得优三个顶点组成得一个二因素得优化过程得一个单纯形化过程得一个单纯形,并知并知W点得响应最坏点得响应最坏,B得响得响应最好。应最好。如果搜索优化过程中函数不出现异常如果搜索优化过程中函数不出现异常,那么搜索最那么搜索最优点得方向明显应当更靠近优点得方向明显应当更靠近WB得方向得方向,而不就是而不就是靠近靠近WC得方向。因此可以通过加权得办法来使搜得方向。因此可以通过加权得办法来使搜索得方向由原来得索得方向由原来得WE(反射方向反射方向)变为变为WE方向方向(加加权方向权方向),),此时用加权形心点此时用加权形心点O 代替反射形心点代替反射形心点O7-5 单纯形优化得参数选择单纯形优化得参数选择在试验中在试验中,我们只研究优化条件我们只研究优化条件,可用基本单纯形法可用基本单纯形法时时,首先必须确定研究得因素首先必须确定研究得因素由于单纯形法不受因素得限制由于单纯形法不受因素得限制,考察得因素可以相考察得因素可以相对得多些对得多些因素确定后因素确定后,据分析仪器与试验要求据分析仪器与试验要求,规定因素变化规定因素变化得上下限得上下限,据上下限得范围确定步长得大小。据上下限得范围确定步长得大小。步长较大步长较大,优化速度加快优化速度加快,精度较差精度较差;步长太小试验步长太小试验次数增多次数增多,优化速度变慢优化速度变慢一、试验指标一、试验指标试验指标就是用于衡量与考核试验响应得各种数值试验指标就是用于衡量与考核试验响应得各种数值在分析测试中可将仪器响应值作为试验指标在分析测试中可将仪器响应值作为试验指标,但有时须转但有时须转换称其它得数量换称其它得数量,试验指标就是数量化得试验指标就是数量化得,以便直接比较以便直接比较结果得大小结果得大小二、初始单纯形得构成二、初始单纯形得构成本章第一节介绍得方法就是根据初始点与步长来计本章第一节介绍得方法就是根据初始点与步长来计算初始单纯形得各个顶点算初始单纯形得各个顶点,各因素得步长就是相同各因素得步长就是相同得得实际过程中实际过程中,各因素步长与单位并不相同各因素步长与单位并不相同,利用这种利用这种方法会变得很麻烦方法会变得很麻烦,在实际应用中问题较多在实际应用中问题较多我们介绍下述两个构成初始单纯形得方法我们介绍下述两个构成初始单纯形得方法(一一)long系数表法系数表法D、E、Long提出一种用系数表构成初始单纯形各顶点提出一种用系数表构成初始单纯形各顶点得方法得方法,可以解决试验设计中初始单纯形得构成问题可以解决试验设计中初始单纯形得构成问题使用时把表中得对应值乘上该因素得步长后使用时把表中得对应值乘上该因素得步长后,再加到初再加到初始点坐标上始点坐标上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.1580.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)顶点顶点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、0,1、0,1,0,1、0);步长为步长为0、5,1、0,1、5,2、0。要求计算初始单。要求计算初始单纯形得各顶点纯形得各顶点四因素均匀设表四因素均匀设表U5(54)顶点顶点1:(1、0+1 0、5,1、0+2 1、0,1、0+3 0、5,1、0+4 2、0)=(1、5,3、0,5、5,9、0)顶点顶点2:(1、0+2 0、5,1、0+4 1、0,1、0+1 0、5,1、0+32、0)=(2、0,5、0,2、5,7、0)顶点顶点3:(1、0+3 0、5,1、0+11、0,1、0+4 0、5,1、0+2 2、0)=(2、5,2、0,7、0,5、0)顶点顶点4:(1、0+4 0、5,1、0+3 1、0,1、0+2 0、5,1、0+1 2、0)=(3、0,4、0,4、0,3、0)顶点顶点5:(1、0+5 0、5,1、0+5 1、0,1、0+5 0、5,1、0+52、0)=(3、5、6、0,8、5、11、0)(三三)单纯形得收敛单纯形得收敛单纯形收敛得检验办法单纯形收敛得检验办法:在在n因素得单纯形中因素得单纯形中,如果有一个点经如果有一个点经n1次单纯形仍为被次单纯形仍为被淘汰淘汰,一般可以在此点收敛一般可以在此点收敛这种检验方法未考虑到试验误差得存在这种检验方法未考虑到试验误差得存在,按助理统计或实际按助理统计或实际工作要求单纯形收敛准则应为工作要求单纯形收敛准则应为:|R(B)-R()/R(B)|式中式中R(B)与与R()分别代表最好点分别代表最好点B与最坏点与最坏点 得响应值得响应值,为为试验误差或预给定得允许误差试验误差或预给定得允许误差应用举例应用举例