D0I:10.13374/i.issm1001053x.1992.03.026 第14卷第3期 北京科技大学学报 Vol.14 No.3 1992年5月 Journal of University of Science and Technology Beijing May 1992 A Mixed-Discrete Variable Optimization Software Package MOD for Engineering Design Chen Lizhou"(陈立周) ABSTRACT:The algorithm principles,features of the software package MOD and comparative study of the algorithim are presented.At the end of the algo- rithm perfermance curves and the evalutive results,and the design examples for mechanical engineering are given. KEY WORDS:mixed-discrete,engineering design,CAD In engineering optimal design and planning,both objective and constrained functions are usually calculable functions which include some or all of discrete or interger design variables.In the past,a traditional way of solving this kind of problems is to treat the variables as continuous and to solve by the nonli- near programming algorithms,and after the obtained optimum yet we still have to need to find the discrete or integer values nearest them.Though this is a straightforward and easy approach,but it is well known that this proce- dure can't often find the discrete optimum or feasible discrete optimum. Because of this reasons,the discrete optimization has received much atten- tion and a lot of algorithms have been published in the literatures of latest years,Although these were developed with respect to solving a particular pro- blem and with difficulty to consider it as general algorithm applied to design problims,but their discrete optimization strategy ideas will have somewhat wor- thwhile to be developped further with new discrete variable optimization 1 General Principles of Algorithm The nonlinear discrete optimization is expressed mathematically as follows 1991-11-05收稿 ·机城工程系(Department of Mechanical Engincering) 340
第 卷给 期 北 京 科 技 大 学 学 报 了 。 材。 。 纽 ， 年 月 了 一 二 陈立 周 ， 。 ‘ ， 妞 ， 。 一 ， 叮 ， ， 。 ， 五 一 〕 ， 五 。 了 ， ， 血 功 ， 五 五 。 且 ， 沮 ，，， 了 一 一 收稿 机城工程系 DOI ：10．13374／j ．issn1001－053x．1992．03．026
minf(x)x=(xP,xc)∈Rn s.t.9,(x)≤0j=1,m xxi=1,n here f(x)and g;(x)(j=1,m)are permitted to be linear or nonlinear functions of x.=(x,x2.,)ER is a subset of discrete variables (the integer variablcs are considered as a special case of discrete ones)x=(, x.)ER is a subset of continuous variables.However,according to the fact that either of Ror Rc is empty,or both are not empty,there is an all-conti- nuous,an all-discrete,or a mixed discrete optimization problems,respectively. From the point of view of engincering design,variables that are inherently continuous wilk be allowed to discretize arbitrarily into k,value,so the discrete intervals are: e:=(x'-x)/(k,-1)j=p+1,n (2) where e.is called quasi-discrete increment,its values are determined by the requirement of engineering design,and so the problems (1)could be considered as an all-discrete problems. The discrete space is defined as a set of all discrete values,i.e. RD={xi}xs∈R (3) and so the feasible design region is defincd as D={xg,(x)≤0V,∈RPCR"} (4) The difference between two neighbouring discrete values with any variable axis direction is defined as the increment,i.e. PI..-increment f=x1-i j=1,k,i=1,n (5) Minus-increment4=x- general☑il卡l☑l,but for quasi-discrete increment=ldl=et, Assuming that x ERCR",the set =(i i=1,p1 (6) j=p+1,n) is defined as the unit neighborhood of the discrete point x,and then the set NC(x)=xUN(x)ne i=1,n) (7) is defined as the coordinate neighborhood of the discrete point x. The discrete optimum x'of problem (1)have to enclose this condition that could be formulated by the following active constraints: 341
二 ， 二 亡 任 ’ 一 。 ， 劣 簇 ， ，， 、 二 ，簇 犷 ， ， 气 主 二 夕 ， ， 左 劣 ，， ， ， … ， ， 任 ， ， ， 尸 ， … 〔 、 · ， ， ， 一 ， 一 ， ， 。 ， 舟 ‘ ， 口户尹 。 。 于 ‘ 一 二 于 八掩 ‘ 一 ， 。 ‘ 一 ， ， 一 ， 一 二 ‘ ， 。 、 任 “ 】夕， 簇 ，任 ” ， 。 ‘ 一 」 ‘ ， 一 劣 ‘ ， ， ， ， ” 一 了 二 劣 ‘ ，一 一 劣 ‘ ， 」李 午 」了 ， 一 亡 专 」下 ‘ 。 任 二 ’ ， “ ， 劣 」下， ‘ ， ‘ 」 一 ￡ ， 劣 一 劣 君 了 ， ， 月 二 ， 二 二 自 ， 川 劣 ’
9,(x)+c,=0j∈I(x") (8) where the I(x)is called the active constraint set of the discrete optimum,it is determined according to following conditions Suppose the ci=-g;(x) if the c;=c,,Then jel(x) here c,is constrained violated evaluation of g,(x),it can be calculated by the following formulas: ,=8(-）△x,(A) (9) g={1sg(-8,）ax,(合）>0，vi} (10) As above illustration the discrete optimum of problems (1)may be defined as follows:Supposing the xEDCR,for all xEUN(x),if there exists f(x) f(x),then x is a constrained discrete local optimum,and that for all x NC(x),if there exists f(x)<f(x),then x is a false constrained discrete local optimum.In a lot of papers at present,authors only discussed the solving methods for the false local optimum,as a consequence,those can not be consi- dered as complete algorithms. If the x is a discrete local optsmum,consider a convergence condition of discrete search,then a set of T T=W∩S=Φ (11) must be an empty one.Where the set of Wand S are W={△x|Axt Vf(x)≤0} (12) S={△xl△x'Vg,(x)≤C,j∈I(x·)} (13) here,Ax,=141,0,47}(i=1,n),v f(x)and vg;(x)are the quasi-gradi- ents of the objective and constrained functions at x. On the basis of above illustrated concepts,any of the complete algorithm for discrete optimization must consist of two strategies,that is the step by step searching in discrete space and the finding out better point in the unit neighbor- hood.And that a multi-function composited algorithm is superiorer to a single one in either the ability or the reliabibity of the obtained optimum in engine- ering design.Based on this,we have developped the five general constrained nonlinear discrete optimization algorithms,namely,the direct search method MDOD,combined complex method MDCP,the random search method MDRP, 342
劣 ’ ， “ 了任 ， 、 、 劣 ， ， 〔 〕 叫 一 劣 五 二 任 劣 ’ ， 、 ’ ， 石 ， 二 系 · 一 姜 。 二 ‘ 会 · 一 釜 △一 瓮 ” ， ‘ 二 〔 二 ， 〔 ， ， 义 。 ， 。 二 任 ， ， 二 ， ， ， ， ， ， ， 牙 自 必 。 平 户、 ‘ 牙 占 了 △二 △二 二 ‘ 廷 ， 毛 ， 任 ‘ ，，白 ， △ ‘ 落 ， ， 」丁 ， ， 二 ’ ， · 一 劣 。 ， ， 。 一 且 。 ， 、 ， ， ， ， ，
the heuristic combination method MDHP,and the geometric programming method MDGP. 2 An Introduction to the Software Package MOD The MOD software system consist of above five algorithms and two sets of test problems (TEST-I and TEST-I),as illustrated in Fig,1. M1OD 4 Algorithm choice Data file Model 5-1 TEST-II CONST FUNCT 00 Output fale Fig.1 Software system of the package MOD The package MOD has following featuses: (1)The input and output data for the various algorithms have been made integrated,namely,problem may b:carricd out by any algorithm in MOD, (2)User would be allowed to use the long or short output.The long ou- tput,i.e.detailed design information is provided to the designer to check the design model. (3)There are time indecator and iternative curve (shown on screen)of optimum computation。 (4)Different algorithm may be combined to be used,namely,the results that have been got from one algorithm may be considered as the input starting points of the other algorithms. The problem (1)is a mixed discrete variable nonlinear programming pro- blem,it can b:solved with MDOD,MDCP,MDRP and MDHP.Algorithm MDGP is only applied to solve the mixed discrete variable geometric progra- mming problem expressed as the following form minx。,1 st.g(x)=P,(x)-Q,(x)<1j=1,m+1 (14) 0≤xx,xij=1,n+1 where P (x)and Q(x)are generlized posynomial function. When this package is used,the desigu variables are required to be arranged in the following order:at first of the discrete variables arc the unequal inte- 343
人 ， 人 。 一 一 几 。 、万 ， 广 一 下 以 川川少少口口 〕 尸 · 幽 口口 目 五 ， ， 。 ， 。 。 。 斑 扭 往 。 ， ， 五 。 ， ， ， 。 。 。 ， 劣 ， 二 一 二 二 ， ， 劣 镇 ‘ 戈劣 ， ， 戈 ， ， ，
rvals,and then are the equal intevals,and at the end are continuous. 3 A Comparative Study of Algorithms in MOD In order to cnsure the quality of the software syslem,it was tested to take in whole of the package MOD based on the preliminaty test of every algori- thm. The problems used in the testing are thirty five classical ones which were selccted so as to include a wide range in various open literatures.These pro- blems are inclusive of the variable number from 2 to 48 and constraints number from 1 to 58 and five classical geometric programming problems.All are the integer,discrete or mixcd variables except for two all continuous variable pro- blems.These problems were made up of two sets:TEST-I and TEST-I. The information obtained during the examining collection data consists of objective and constrained function values and their evaluated numbers,and the solving time for each algorithm on one problem.In addition the relative error in the objective function is defined by following criterion =f()() or er=If(x)] (15) f(x·)川 Where the f(x)is the value of the objective function at a found optimal point on one problem for each algorithm,The f(x)is discrete optimum of reference that is obtained by above two algorithms. The number and time of solved problems of each algorithm are the two main characteristics,but both must be considered at the same time in order to produce a valid indication of the performance.On the basis of this,the cri- terion used in the comparison is the solved number under a reasonable amount of time and relative error accuracy.Here the reasonable amount of time means a series of specified limits on fraction of the average sofution time for all of the algorithms on each problem. This plot at relative error level of 0.05 and relating to the front fiften problems in TEST-I is presented in Fig.3 and Fig.4.This plot,the so-called algorithm preformance cuves,may be thought of as a utility graph for algori- thm quality comparison. Thus a good algorithm has to have a steep rise and attain a high maximum value on the vertical axis,We can quite easily pick out the superior algori- thm from this curve,the MDOD has the best characteristic following it are the MDCP,MDHP and MDGP,and then is MDRP,But worth mentioned that No.14 and No.15 problems include the posynomial function and the superior re- ference optimum is found by means of MDGP,but solving them by making use 344
、 ， ， 。 ， 勺 ， 。 了 、 。 ， 。 一 一 ， 。 了 厂 忍 二 一 二 ’ 。 二 ’ ， 。 ， 皿 。 一 。 ， 一 ， 爪 主 主 。 了 ， ， 〔 ， 。 ， 、