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
、 ， ， 。 ， 勺 ， 。 了 、 。 ， 。 一 一 ， 。 了 厂 忍 二 一 二 ’ 。 二 ’ ， 。 ， 皿 。 一 。 ， 一 ， 爪 主 主 。 了 ， ， 〔 ， 。 ， 、
of MDOD and MDRP have not found the solutions at given error level,there- fore,it is considered as solving fault. Given in Fig.5 are the preformance curves for MDOD,MDCP MDRP and 15 12 MOHP MDCP MDGP 12 MORP 8 HOGP ·2 0 0.5 2 6 810 15 0 MORP Fraction of average time 0.0050.020.04 Fract ion of average time Fig.2 Algorithm preformance at e,=0.05 and Fig.3 Algorithm performance fraction of average time in 0.05 2te,=0.05 30 MDHP 25 20 10 10 15 Fraction of average time Fig.4 Algorithm performance at e,=0.001 with TEST-I MDHP with TEST-I testing at error level 0.001,and the general conclusions are about the same with above, Given in Fig,6 is the plot of number of problems solved versus the relative error of objective function.It will be seen from this diagram,the MDHP is an algorithm which hasn't been influenced by the computational accuracy,it is illustrated to be a better algorithm for the ability to find global optimum. The computative results as shown in Tablc I that be used combination of two algorithms,indicate that the package MOD on the whole have high robust- 345
， ， ‘ 户 ， 夕 巴 态爪 启沙 ， ‘ 州口尸 一 尸尸 月 一，了夕 厂 相日 幻 一 ‘ 一 产 一 曰 、厂料即 一 口。夕的任﹄山。 。已已山肠的山。 提 扩 ‘ 吕 气 「 一 户 「， · ￡ 了二 又 公 · 夕 峪。﹄。 逻 一 痔荞释 ‘ ， 日 · 公 “ 一 一 。 ， ， 五 ， ， 五 ， 五 ， ， ， 川 。 ，
Table 1 Computative results of some problems with combination of algorithm Computational results of Computational results of original algorithm succeded algorithm problem Values of f(x) No. et Valucs of f(x) (algorithm used in) (algorithm used in 9 -5.055100(MDRP) 2,0×10-2 -5.157810(MDCP) 0 16 -0.937150(MDCP) 8,1×10-2 -0.944750(MDHP) 0 26 2667.482(MDCP) 2.8×10-2 2595.754(MDOD) 0 27 317.0819(MDOD) 7.7×10-2 289,3374(MDCP) 0 400 minf￥归100（名-x1-x2)2 100 MDHP 8,t,-1006*;≤100i1,2 地约 100 80 Ai FUN MDCP 10.00011936 60 20.001641 50.0149% 40.1 279 40 51.0129 20 x*=f1.0,1.01 f(x)=0.0 0 Alternative number 102 5×10-21035×10- 10-4 400 1000 18002000 Relative error of FUN ob jective function Fig.5 Number of problems solved versus Fig.6 Convergent speed for different the computational accuracy quasi-discrete increment A ness of solving discrete variable problems. In addition,the package MOD were also found to solve with high effecti- veness on a wide variety of all continuous variable probloms after they are discretized,as an example of the mathmatical problem shown in Fig.7 If all continuous variables have been discretized with the same discrete interval,the diffrent quasi-discrele increment 4:will influence the convergent speed, 4 Examples of Application As the examples of using package MOD,let us consider the optimal desi- gn for TDC Type gear-cylinder of the conveger,there are three types and forty variations.The transimission sketch illustrated in Fig.7(a)is a two- stage in-and out-meshing gear drive.Now it is required to have the ma- ximum loading ability on each stage and to equalize them with each other,For example,when the cylinder in diameter 500mm and the input speed is 906r/min we have obtained the following optimum by the package MOD:m=3mm, 346
亡 动 。 五 呈 已 巴 一 。 一 。 。 。 。 一 。 一 ， 。 一 ， 一 一 一 。 一 。 。 。 ， 口， 曰口 卜 千律 一 ’ 、 、 苍界二 阳尺尸 ，，卜、 ‘ 二 一 、︵姚 兄幻 ︺欲‘﹄。忿州叫 瓦料粼 姗牡厂 万为 。 。 今 。 。 「 公 扭 压 勺 一 △ ， ， 五 ， 五 』 ， 一 」‘ ，，、 人 ， 一 ， ， 一 一 。 往 。 ，
m2=5mm,Z1=18,Z2=61,Z3=19,Z4=68,b1=52mm,b2=88mm,512=0.94, 534=0.48,axis distance 4=122.5mm.In this case the allowed loading ability is 19.7kW for the high speed stage and 19.6kW for the low speed stage.The error of the equal strength is 0.5%.As shown in Fig,7(b)there is only 7.5kW for tradational design. D=50mm =9061/mm i=12.56 Out meshes 30 Constraints of 3n2 cylinders 20 21,17n1,5 diameter 10 In meshes 0 110120130 T140 A/mm (a) (b) Fig.7 Gear drive of gear-cylinder of TDC a)Sketch of the drive b)Design point location of the optimal and tradational design 5 Conclusion A Summary of some results of our research in the discrete variable opti- mization have inducted above.It is noteworthy pointed out that the package MOD is generally a very effective way to solve the discrete variable problems. At present,the package MOD has been applied successfully to mechanical engi- neering,reliability engineering,city water engineering and economic develop- ment planning and other areas. References 1 Siddall J N.Optimal Engineering Design (Principles and Applications). Marcel Dekker,1982 2 Reklaitis G V.Engineering Optimzation (Methods and Application).Joh Wiley and Sons,New York,1983 3 Chen Lizhou,et al.Optimal Design for Mechanical Engineering.Sha- nghai Science and Technology Press (in China),1982 4 Chen Lizhou,et al,Mixed Discrete Variable Optimization for Enginee- ring Design (Priciles and Application).Mechanical Industry Press,1990 5 Chen Lizhou,J of CMES,1985,21(2):179 6 Chen Lizhou,et al.J of Beijing University of Iron and Steel Technolo- gy,1987,9(3):65 7 Chen Lizhou,et al.I of Beijing University of Iron and steel Techno- 1ogy,1987,9(4):73 347
， ， ， ， 二 ， 二 ， ， ， 考 ， 。 ， 古 ， ， 。 。 ， 月 二 口 取 士 三 〕 一 公 五 宜 宜 呈 五 。 ， ， ， 几 、 ， ， ， ， ， 。 。 。 ， ， 飞 又 。 ， ， ， ， ， ， ， 。 ， ， 口九︸