第九讲-复合形法

复合形法基本思想:在n维空间的可行域中选取k个设计点（）作为初始复合形的顶点，然后比较复合形各顶点目标函数值的大小，其中目标函数值最大的点为坏点，以坏点之外其余各点的中心（形心）为映射中心，寻找坏点的映射点，若映射点优于坏点，则替换它构成新的复合形，如此反复迭代，使复合形不断向最优点移动和收缩，直到满足精度为止。nkn211.初始复合形的产生初始复合形的k个顶点都必须在可行域内，对维数较低的优化问题可直接指定，对复杂问题，一般用随机方法产生：（1）确定一个可行点作为初始复合形的第一个顶点，可调用[0,1]区间内服从均匀分布的伪随机数来生成的分量：检验是否可行；若不可行，重新生成。1X1X1Xjir)(iijiijiabrax)2,1,1(nij（2）继续产生其它（k-1）个随机点；（3）将非可行点调入可行域构成初始复合形依次检验是否在可行域内，若前q个点都在可行域内，它们都可以作为初始复合形的顶点，第q+1个不在可行域内，按下面方法将调入可行域：1）计算前q个点的中心2）将点向方向推进，移到它们连线kXXX,,321qXqjjDXqX111qXDX的中点，即如果移到后的已经进入可行域，则将作为第q+1个顶点，否则按上式重新移动直到满足要求为止；3）继续检查后面的点，若不在可行域内，重复应用上述方法将其调入可行域，直至全部成为可行点，从而构成了可行域内的初始复合形。)(5.011DqDqXXXX1qX1qX复合形法的具体迭代步骤：（1）给定n，变量界限，k，精度要求（2）产生初始复合形，得k个顶点；（3）计算各顶点目标函数值，找出最坏点：最好点：转步骤（8）；iiba,,jX),2,1()(max{)(:kjXfXfXjHH),2,1()(min{)(:kjXfXfXjLL（4）计算除最坏点外的其余各顶点的中心（5）检查的可行性；若不在可行域内，说明可行域可能是一个非凸集，这里为了将移入可行域内，可在点和点为界的超立方体内，重新利用伪随机数产生k个新的顶点，这时，变量的上下限改为：若，则取否则相反，返回步骤（2）；)(111HjXkXkjjCCXCXCXCXLXCiLixxCiiLiixbxa（6）按计算映射点并检查它是否在可行域内，若在可行域内转（7），否则将映射系数减半，继续计算直至满足全部约束要求；（7）计算点的目标函数值，若则用替代最坏点，构成新的复合形。完成一次迭代，转（3），否则，转（6），若经过若干次减半值的计算并使得其值已缩小到给定的一个很小的正数，仍)(HCCRXXXXRXRXRX)()(HRXfXfRX5.0HX不能使映射点优于最坏点，说明该映射方向不利，将次坏点代替最坏点，然后转（4）（8）检查是否满足迭代终止条件若满足，则将最后复合形的最好点结束迭代，否则转（4），继续下一次迭代。2/112)]()([1kjLjXfXfk)()(,**XfXfXXLL