复合形优化算法在VC环境下的开发与实践.DOC

1、复合形优化算法在 VC 环境下的开发与实践摘要： 本文阐述了复合形法在 VC 环境下的设计和实现过程。通过将算法封装于一个单独的类（razor ）中，本文实现的 razor 复合形法优化类可以适用于有任意维数、有任意数量约束方程、自变量取值在有限范围内的优化问题，且具有交互界面良好，使用方便等特点。关键词：复合形法 优化算法 VC目 录1 绪论 .11.1 复合形法概述 .11.2 任务目标 .11.3 任务解决 的主要问题 .12 算法封装与使用方法 .13 复合形优化算法流程 .34 具体算法实现 .64.1 razor 类的结构设计 .64.2 razor 类的成员函数 .84.2.1

2、razor（结构函数） .84.2.2 razor（析构函数） .84.2.3 Add_g（绑定约束函数） .84.2.4 random_vertex（生成一个随机 顶点） .94.2.5 Is_fillin（检测顶点是否在可行域内） .94.2.6 optimize（优化总函数） .104.2.7 Init（交互设定及确定初始顶点（STEP 1） .114.2.8 construct_shape（随机产 生其它顶点，构成复形（ STEP 2,3）.124.2.9 get_queue（排队（STEP 4） .134.2.10 get_XC（计算中点 Xc（STEP 5）.134.2.11 ge

3、t_XR（计算反射点 XR（STEP 6）.144.2.12 compare（比较（STEP 7） .144.2.13 get_XE（计算延伸点 Xe（STEP 8）.154.2.14 zoom（缩小（STEP 9） .154.2.15 over（结束处理） .165 算例 .166 总结 .19参考文献 .1911 绪论1.1 复合形法概述 1复合形法是单纯形法的扩展，是适用于不等式约束的一种直接算法。它的基本思路是在设计空间的可行域内，构造具有 k 个顶点的多面体，按顶点函数值大小排队，找出函数值最小的最好点和函数值最大的最坏点，并计算出最坏点的反射点，一般反射点都优于最坏点，故以反射点代

4、替最坏点，构成新的复形，这样不断调整多面体的顶点，使多面体不断向最优点靠拢，最后搜索到最优点。1.2 任务目标本次作业的自选题为利用 VC 编制复合形算法的通用程序包，该程序包可以提供良好的交互界面且便于使用者设置与调用。1.3 任务解决的主要问题1复合形法程序封装实现的具体形式2约束函数与目标函数的引入方法3算法编写4结果存储方式5用户交互性2 算法封装与使用方法由于具体算法的编写结构与封装方式关系密切，故首先考虑算法的封装方法。优化算法程序的一大特点是需要用户定制约束方程和目标方程。最好的方式是令程序具有优秀的公式解算器，为用户提供良好的交互界面，从用户的表达式输入中生成优化过程中需要的各

5、个表达式，Matlab、ADAMS、AutoCAD 及许多专业软件都具有这样的功能。但是，本人不会编写这样的解算器，也不了解其解算过程。于是，本人决定提供一个类，让这个类完成所有的复合形法优化过程，用户在需要使用该算法时调用该类即可。唯一遗憾的是，用户必须会 Visual Studio 的基本操作，知道怎样使用“#include”来包含该类的头文件，知道怎样写出约束函数和目标函数。值得庆幸的是，本程序需要读入的函数形式简洁明了，不比直接输入表达式要难。本程序包的使用方法是：1 在 Visual Stidio 中新建或在已有 VC 工程（交互需要使用 win32 控制台程序形式）中包含本算法所在

6、的 h 和 cpp 文件2 在需要的地方添加#include ”razor.h”，同时确保工程中已包含了、这几个库3 编写一组函数作为约束函数，其格式为：double 函数名函数名 (double *x)double y;y = 表达式表达式2return y;其中，表达式为令 y 小于或等于 0 时状态。即，程序中，表达式令 y 小于或等于 0时，认定表达式中涉及的空间坐标满足约束条件。4 同样的方法和格式，编写一个函数作为目标函数。注意：程序中，优化方向为令表达式的值在实数域上最小的方向。5 添加如下语句以便随机数生成：srand(unsigned)time(NULL);6 在程序中创建一

7、个 razor 对象，格式为：razor 对象名对象名 (维数维数 ,复合形顶点数复合形顶点数 );对象名任意，维数指优化问题中的自变量数目，顶点数为维数+1 至 2 倍维数任意。7 将约束函数分别与 razor 对象绑定，格式为：对象名对象名 .Add_g(函数名函数名 );8 将目标函数与 razor 对象绑定，格式为：body.targetFunc = 函数名函数名 ;9 运行优化程序对象名对象名 .optimize();10 启动调试或运行程序11 按照控制台窗口中的提示进行进一步操作具体示例请参考下面的图示。图 2.1 必要的头文件和命名空间设定图 2.2 定义一个约束函数（x0(y

8、)?(y):(x) /求较小值求较小值#define MAXIMUM(x,y) (x)(y)?(x):(y) /求较大值求较大值#define DELTA 0.0000001 /误差限误差限#define NUMLIMUP 10000 /最多求取次数最多求取次数 ,避免陷入死循环避免陷入死循环typedef struct g_node7double (*g)(double*); /函数指针，指向约束函数函数指针，指向约束函数g_node *next; g_node;class razorpublic:razor(int dimens,int num);razor(void);public:in

9、t dimension; /优化维数优化维数int vertex_num; /算法中使用的顶点数算法中使用的顶点数g_node *g_function; /约束函数链表约束函数链表double (*targetFunc)(double*); /目标函数指针目标函数指针double *x,*l,*h; /变量数组、自变量取值下、上限数组变量数组、自变量取值下、上限数组int g,b,s; /最好点最好点 g、最坏点、最坏点 b、次坏点、次坏点 s的顶点序的顶点序号号double *xc,*xr,*xe; /记录记录 Xc、 Xr、 Xedouble a; /算法中的算法中的 a值值public:

10、void Add_g(double (*p)(double*); /添加约束函数添加约束函数void optimize(); /优化主程序优化主程序void Init(); /初始化交互及顶点设置初始化交互及顶点设置int Is_fillin(double *x); /检查所选点是否在可行域内检查所选点是否在可行域内 ,是返回是返回void random_vertex(double *x); /生成随机顶点生成随机顶点 ,serial为顶点序号为顶点序号void construct_shape(); /step2、构成复形、构成复形double get_queue(); /step4排队排队i

11、nt get_XC(); /step5计算中点计算中点 Xc int get_XR(); /step6计算反射点计算反射点 Xr int compare(); /step7比较比较int get_XE(); /step8计算延伸点计算延伸点 Xe int zoom(); /step9缩小缩小int over(); /结束处理结束处理;采用结构体构成链表的目的是使算法可以容纳无穷多个约束函数，同时简化代码里的一些调用名称，该链表仅在 Add_g 和 Is_fillin 函数中创建和遍历。可以从代码中发现，x、l、h 等与维数有关的成员变量均采用了指针型。这样可以在确定优化问题的维数（dimens

12、ion）后再申请开辟优化计算所需要的空间，故算法适用于任意维数的优化问题。上列代码中最后几个注释为 step的，与第 3 章中的算法步骤序号严格对应，它们是复合形优化法的算法执行函数。84.2 razor 类的成员函数4.2.1 razor（结构函数）razor:razor(int dimens,int num)dimension = dimens;vertex_num = num;g_function = NULL;a = 1.3;x = new doubledimens*num;l = new doubledimens;h = new doubledimens;xc = new doubl

13、edimens;xr = new doubledimens;xe = new doubledimens;razor 对象在创建时必须由用户同时指定优化问题的维数和复合形法采用的顶点数。razor 对象创建的同时会申请开辟各成员变量所需的运算空间。4.2.2 razor（析构函数）razor:razor(void) /释放申请的各种空间释放申请的各种空间delete x;delete l;delete h;delete xc;delete xe;g_node *temp,*del;temp = g_function;del = temp;while(temp!=NULL)temp = temp-next;delete del;del = temp;优化结束后，如果删除 razor 对象，可以自动释放占用的空间。4.2.3 Add_g（绑定约束函数）void razor:Add_g(double (*p)(double*)g_node *node,*temp1,*temp2;temp1 = g_function;