# Full text of "Bell-Curve Genetic Algorithm for Mixed Continuous and Discrete Optimization Problems"

## See other formats

^(£^330 Al AA 2002-1 675 Bell-Curve Genetic Algorithm for Mixed Continuous and Discrete Optimization Problems Rex K. Kincaid College of William and Mary, Williamsburg, VA 23187-8795 Michelle Griffith College of William and Mary, Williamsburg, VA 23187-8795 Ruth Sykes College of William and Mary Williamsburg, VA 23187-8795 Jaroslaw Sobieszczanski-Sobieski NASA Langley Research Center, M/S 240, Hampton, VA 23681, AIAA member 43rd AIAA Structures, Structural Dynamics and Materials April 22-25, 2002/Denver, CO For permission to copy or republish, contact the American Institute of Aeronautics and Astronautics 1801 Alexander Bell Drive, Suite 500, Reston, VA 20191-4344 Bell-Curve Genetic Algorithm for Mixed Continuous and Discrete Optimization Problems R('x K. Kincaid* College of William and Mary, WiUiamshurg ., VA 23187-8795 Michelle Griffith* College of William and Mary, William.'iburg, VA 23187-8795 Ruth Sykes^^ College of William and Mary, Wilhamshurg. VA 23187-8795 Jaroslaw Sobieszczanski-Sobieski^ NASA Langley Research. Center, M/S 240, Hampton. VA 23681, AIAA member 1. Introduction. This paper is the next installment in a series (Sobieszczanski-Sobieski et ai. 1998, Kincaid et al. 2000, '200 la, b and I'jassman and Sobieszczanski- Sobieski 2000) that has introduced a variant of the Genetic Algorithm in which the reproduction mecha- nism was modified to base it on the Gaussian prol)- abijity distribution, the bell curve. The bell-curve based (BOB) heuristic procedure, first presented in Sobieszczanski-Sobieski, Laba, and Kincaid (1998), is similar in spirit to Evolutionary Search strategies (ESs) and Evolutionary Programming methods (EPs) but has fewer parameters to adjust. In Sobieszczanski- Sobieski et a). (1998) BC'B was tested on a structural design optimization problem. The f|uality of solutions generated were verified by comparing BCB solutions to ones generated by a standard nonlinear program- ming technique. No attempt was made to analyze the sensitivity of the BOB parameters. Kincaid, Weber and Sobieszczanski-Sobieski (2000) provide a prelim- inary investigation into Bf'B parameter selection as well as document improvements in the performance of BCB. Gomputationa! results for continuous, dis- crete and mixed continuous and discrete design o]V timization problems with constraints is reported. Fur- ther experiments with B(!fi for purely discrete op- ' Department of Mathematics, 1 he first and second authors gratefully acknowledge the support of of NASA-Langley Re- search Center-N AG- 1-2077 t Department of Computer Science 'Department of (Computer Science S Senior Research Scientist Copyright (?) 2002 by the American Institute of Aeronautics and Astronautics. Inc. Xo copyright is asserted in the I'nited Stales under Title 17, I.S. Code. The I'.-S. Government has a royalty- free license to exercise all rights under the copyright claimed herein for Governmental Purposes. All other rights are reserved by the copyright owner. timization problems is provided in Kincaid, Weber and Sobieszczanski-Sobieski (2001a). Plassman and Sobieszczanski-Sobieski (2000) implement and test a parallel version of BCB for continuous optimization problems. I'he new^ contribution to be presented in this install- ment is an extension to applications that encompass a mix of continuous and quasi-discrete, as well as truly-discrete applications. The extension combines a definition of the distance between the parent designs in the space that comprises discrete and continuous variables with application to optimization of statically indeterminate structures in which the order of design variables, e.g. the type of the cross-section, is essen- tial. As expected, the algorithm that accommodates the order information produces better results. In addi- tion, we provide a comparison allowing sampling from the tails of a discrete normal distribution versus a stan- dard mutation scheme. .Adding sampling from the tails brings the continuous and discrete versions of BCB into agreement. Moreover, given the same computing resources, we show that sampling from the tails of the discrete normal leads to higher quality solutions than the standard genetic algorithm mutation approach. 2. Background Information. To illustrate the connection between FK-B, ESs and EPs we define our mutation, recombination, and se- lection mechanisms in ES and EP terms. X new- gen- eration in our approach is selected exactly the same as a (// + /;)-E]S. The recombination mechanism is similar to the extension of the intermediate recom- bination if the weights are required to sum to unity. Consider the line through two jj-dimensional parent vectors Pi and Pi selected for mating as in Figure 1. Figure I depicts a design space simplified to three 1 OF 9 Amrbican Instithtf, op a rron.mitks and AsTRONAUTir;s Papeb 2002-167.^1 dimensions (three design variables). First, determine tlie weighted mean M of these two vectors where the weights are given l)y the fitness of each parent. Next, sample from a normal distribution N(0, cr„,). The re- sulting point B = M + \P2-P]\* A'(0, (Tm) is the child, prior to mutation. Note that in the extended version of the intermediate recombination method when the weights sum to one the unmutated child can lie any- where on the line segment between the two parents. In our approach, rather than picking weights arbitrarily, the selection is governed by a normal distribution and the fitness weighted average of the parents. Moreover, B is not restricted to lie on the line segment PxP-i- Mutation ensues by first generating a radius r for an n— 1 dimensional hypersphere. The radius is a realiza- tion from a A'(0,iTr). Typically [(Tj. >> (t„,). Finally the mutated child C is .selected by sampling uniformly on the surface of the n — 1 dimensional hypersphere. Since the child can lie anywhere on the surface the ef- fect is similar to the rotated angle portion of an ES or EF (in n — 1 rather than ii dimensions). However, we do not allow the hypersphere to be stretched (or shrunk) along any of its axes as is the case for an ES and EF with non-identical (T,. We call our procedure a Bell-Curve Based evolutionary optimization algorithm (BCB). Figure 1 is a 3-dimensional view of BCB. In the case of constraints (or simple bounds) we make two adjustments to BCB. If the point B vio- lates a constraint then we select another candidate for B until we obtain a feasible one. That is, we sample from .'V(0,(T„) until B = M + \Pi - A| ♦ A'(0,<t„,) is feasible. If the child C that is produced is infeasible, we translate the components of C to the closest con- straint. For example, if all variables are to lie within [1, 10] and if C = (0.8,2.0, 11.9), the child would be- come (1.0,2.0,10.0). In addition to the general description of BCB above there are several specific details of note. Instead of a roulette wheel selection scheme for selecting parents we implement Baker's (1987) stochastic universal sam- pling. In doing so we eliminate the natural bias, noted by Baker (1987), in roulette wheel selection. Although BCB's performance may be improved if knowledge of the underlying feasible region's topology is included in the selection of the initial population, here we gener- ate the initial population randomly (uniformly). There are four parameters that mu.st be chosen to optimize a continuous unconstrained function: population size, number of generations, <t„, , and cr^. Kincaid et al. (2001b) provide an investigation into B( 'B parameter .selection. We make use of their observations in this manuscript. First, scaling with respect to the design variables is critical. BCB skews the search space towards design variables of small dimension during recombination. Hence, the search space should be scaled so that all design variables are of similar magnitude. Two normal distributions drive BCB - A' (0,(Tm) and A'(0, cr^). .As we seek to sample along the line through the two par- ents, P, and P2, we form B = M-|-|/\-P, |* A'(0,rr„,). (Jomputational experience in Kincaid et al. (2001b) showed that cr„i should have a value near 1.0. In- tuitively this makes sense since N{Q,a^) serves to inflate or deflate the value of the distance between the parents. Next, to inutate B we sample uniformly on the surface of an n — 1 dimensional hypersphere with radius sampled from our second normal distribution, A'(0, ar). Here, the value of ar is expected to be larger than 1.0 to allow for the possibility of hyperspheres of larger radii. Unfortunately there is no problem spe- cific data from which we can pick a baseline value for the radius of this hypersphere. A''(0,fTr) must repre- sent both the unknown radius baseline as well as its normal deviation. As expected, Kincaid et al. (2001b) found that a,, should be much larger than (T„,. lie- low is an outline of the B( -B procedure for continuous optimization problems. Fig. 1 . BCB Geometrical Construct in 3D Space Initialize BCB by choosing a population size, /<, a max- imum number of generations, nuni-gens, (t^ and fTr„. Scale the search space so that all design variables are of similar magnitude. Randomly generate /( individuals. Hepeat iium-ytns times Repeat // times 2 OF 9 American Institute of Aeronautics and Astronautics Paper 2002-1675 Select, two parents, I\ and P^. from the current population using Baker's stochastic universal sampling. Calculate M the fitness weighted mean of the parents. Generate B ^ M + \F2 - Pi\* jV(0, tr^,), the child prior to mutation. (If ll violates a constraint sample from A'(0, <T,n) until a feasible B is found.) Generate C the mutated child. Sample from N({),fTr) to determine r, the radius of a hypersphere centered at B. Sample uniformly on the surface of this hypershere. The resulting point is C. (If (' is infeasible we translate the violated components of C to lie on the boundary of the violated constraint.) End Repeat Keep best /( of parents and children as parents of next generation End Repeat BCB was originally designed to find high quality so- lutions to continuous optimization problems. In order to solve mixed continuous and discrete variable opti- mization BCB must also be able to optimize purely discrete problems as well. Our first experiment in this regard was to simply round continuous BCB solutions to the nearest discrete value (see Kincaid et al. 2000) for a ^-member hub design problem. This approach is known to work fairly well for quasi-discrete vari- ables, that is, the variables have a continuous physical interpretation but may be implemented only by choos- ing from a discrete set of options. The thickness of commercially available sheet metal is an example. In contrast, the variables maybe truly discrete. Choosing between propellers or jet engines in an aircraft design optimization problem is an example. The rounding approach is totally inapplicable for tr>ily discrete vari- ables. C^onsecjuently, in the truly discrete setting there is no obvious analog to a line segment connecting par- ents. Defining an underlying geometry via a lattice is possible but our approach is to define an artificial neighborhood structure. The notion of a neighborhood we use rests on a def- inition of distance l)etween objects in a finite set. This idea is not new. In particular, Kelly et al. (1994) use a similar measure in their diversification strategies in tabu search. To the best of our know^ledge there is no reference to this in the evolutionary strategy lit- erature. To be generic, consider an example of three objects, each possessing three attributes. Figure 2h provides such an example in which the attributes are letters chosen from a list of six letters (Figure 2a). Initially we assume that the order of the attributes in the object does not matter. We will remove this as- sumption later. Now, consider object d and ask the question: •'How many letters must be changed to make ii identical to a?". By inspection, the answer is three. The answer to the same question for - is two. Finally to change 7 to li we need change only one letter. Ob- viously, the above questions may be reversed without changing the answers. That is, the transformation of a to 7 also requires two letter changes. We now place o, J, and -;. on a numerical axis (Figure 2c). Choosing a arbitrarily as a reference at 0, then the locations of 7 and /?are 2 and '.) respectively. That is, each of these objects is placed at the number of attribute changes required to transform it to the reference object (o in this case). a) A B C D E F b) a= AB^ p = ! DCF y= TcAF c) a 7 I Figure 2. Distance between members of a discrete set A definition of a distance betw-een objects that are identified by attributes chosen from a finite set emerges from the example in Figure 2. • 'Fhe distance between two objects characterized by discrete attributes drawn from the same set is equal to the number of attributes that must be changed in one object so that it is identical to the second object in terms of its attributes. 'I'he distance defined above might also be interpreted as the dissimilarity between two objects. In this inter- pretation, the null distance corresponds to a complete similarity (identical attributes). The maximum dis- tance, the total number of attributes in the object (three in Figure 2), signifies a complete dissimilarity (no attributes in common). Note that the proper- ties of the similarity and dissimilarity are mutually complimentary their measures add to the number of attributes. Now^ consider the case when the order of attributes in the object does matter. To illustrate the conse- quence, consider a transformation of -;■ to q. In addi- tion to replacing the letters C and F with B and t respectively, one needs to change the position of T in 7 from position 2 to position 1. Counting the two letter re]>lacements and the position exchange results in - to a distance of I?. In addition to constructing the sin- gle transformations, such as 7 into o, we also want to 3 OF 9 Amrrican Institutb of Aeronautics and Astronautics Paper 2002-1675 sample among all the objects at a prescribed distance f l>etween the two objects. Kincaid et al. (2000) ex- perimented with discrete problems in which the order of the attributes does NOT matter. In Section 4 we will provide computational experience for problems in which the attribtite order does matter. The tacit assumption in the previous examples is that the ntimber of attribute positions in each object are the same. .Although this need not be the case in general, it will be true for the problems we .study here. Given the aforementioned distance definition we can now formally describe a discrete version of BCB. VVe describe the case when the positions of the attributes do matter since that is easier to explain. The symbols Pi, P2, and C (two parents and the resulting child) correspond to t>, /i, and 7 respectively in the previous discussion. Let k denote the number of attribute posi- tions in Py and P-i, let n denote the number of possible attribute values (11 > k)^ and let r denote the number of attributes that are dissimilar between Pj and Pi- • Step 1. Place Pi and P2 on a numerical axis rang- ing from to the number of dissimilar components between Pi and P^. Without loss of generality, let Pi serve as the reference point at on this numer- ical axis. • Step 2. Create a truncated discrete normal dis- tribution on the axis described in step 1. The distribution is centered on a point M whose lo- cation may be at the midpoint between Pi and P2 or it may be shifted toward the fittest parent. The distribution is truncated at Pi and P^- The parameter <t„j must be chosen by the user. • Step 3. Let t denote the .sample value chosen from the distribution in .step 2. Place the child i? at a distance < from Pi on the numerical axis between Pi and Pi. • Step 4. Reorder the attributes of P] and P2 so that the k — r attributes in common appear in the last k — r attribute positions. Assign the re- maining r attributes of Pi and P2 randomly to the first r attribute positions respectively within Pi and P2. Label these reordered parents Pi and Pi- Construct a child B of P] and P2 as follows. First, set B — P2. Then re-assign the attributes contained in the first r — t positions of Pi to the first r — t attribute positions of B. • Step 5. Construct the final child C from B by randomly mutating B. That is, with a small prob- ability of occurrence, p, randomly (uniformly) re- place any attribute of B with any of the allowed attribute values. In addition to experiments in which the attribute order does matter we will also explore the utility of the truncated normal. In order to make the discrete version of BCB closer in spirit to the continuous one it would be nice to replace Step 5 above with sampling in the tails of the discrete normal distribution. Lastly, we describe how these two algorithms in- teract when we solve mixed continuous and discrete optimization problems, we treat the discrete and con- tinuous variables as a single collection of decision vari- ables. Suppose that our design structure has b beams, and that there are t possible beam types. Further sup- pose that the cross-section of each beam type can be described by ri continuous variables. Then our sohi- tion is a vector x that is a concatenation of h vectors of the form .■riu ■ .,xin;r2u ■ r2n;- .■,riu...,Xtr, with one such vector for each beam. Here, Xij repre- sents the jih cros.s-section decision variable of the /th beam type. Thus, a solution will describe not just b beams, but h*i beams. A second vector ((/i, 1/2, . . . , .i/h) indicates the chosen set of beam types, where ?/,■ is in the integral range of [1,/]. Hence, the value of yi in- dicates which beam type we have chosen for beam /. Given two parents of the form described above, con- tinuous BCB recombines the Fs and discrete BCB recombines the j/"s- For further information on other possible ways to solve mixed continuous and discrete optimization problems the interested reader is referred to Kincaid et al. (2001a). 3. Refinements to Discrete BCB In this section we test certain features of discrete BCB. First we examine the two choices for M de- •scribed in Step 2 of the algorithm. That is, should M be the the midpoint between Pi and P2 or should it be shifted toward the fittest parent. Second, we compare the performance of discrete BCB as described above to a new version of discrete BCB in which Step .5 is re- placed by allowing sampling to occur in the tails of the discrete normal distribution defined in Step 2. That is, the discrete normal distribution defined in Step 2 is no longer truncated. In addition we will limit our at- tention to problems in which the attribute order does NOT matter. The test cases for these experiments is a constrained mixed continuous and discrete weighted shape selec- tion optimization problem. We wish to select F) shapes from a list of three (circle, triangle, and square) or more geometrical shapes. The five positions are num- bered in order 1 through .5. The goal is to choose 5 shapes (possibly with repeats) and the dimensions of those five chasen shapes to minimize the total weighted sum of the perimeters. Each chosen shape's perimeter is weighted by its position in the list: the first shape in the list is weighted by 5, the second by 4, the third 4 OF 9 American iNSTmiTF; op Arronaiitics and AsTRONAtrTics Paper 2002-1675 by 3, and so on. The contimions variable is the radius (r) for the circle, the length of a side (s) for the square and the length of the base (b) for a right isosceles tri- angle. The constraints are as follows. The total area must be greater than 100 units and each continuous variable has a lower bound of 1 .0 and an upper bound of 10.0. The optimal set of shapes is 4 triangles and 1 circle with an objective value of 8"2.(). The circle has the smallest perimeter to area ratio (2/r) and is cho- ,sen for position 5 with r just large enough so that 100 - (sum of the 4 triangles area) is satisfied. Small tri- angles are chosen for the remaining 4 shapes since its perimeter to area ratio is largest. In an attempt to un- derstand how BCB scales with respect to the number of discrete variables we solve the position dependent shape problem with the addition of regular polygons with 5, f), f<, and 10 sides. Table 1. Using fitness: 15 reps, 20,000 solutions, 0.04 mutation the .5 cases. # Shapes Mean Best Obj Min Best Obj Max- Best Obj Freq Opt Shapes 3 85.9 82.9 89.1 5/15 4 87.4 82.9 94.3 2/15 5 89.7 8.5.3 95. .'i 0/15 (i 91.2 85.1 97.1 0/15 7 91.0 85.2 97. (i 0/15 Table 2. Using midpoint: 15 reps, 20,000 solutions, 0.04 mutation # Shapes Mean Best Obj Min Best Obj Max Best Obj Vreq Opt Shapes 3 85.7 82.9 89.4 6/15 4 8C.1 82.9 90.4 .5/15 r, 89.1 83.7 93.2 1/15 fi 93.0 85.7 98.1 0/15 i 90.8 83.9 96.7 0/15 In the above experiment the fitness weighted mean in Step 2 of the algorithm does not perform quite as well as simply using the midpoint of I\ and P^- The midpoint approach has the min and mean best ob- jective values in 4 of the -5 cases and identifies more optimal shapes (12) than the fitness approach (7). Even so the appeal of making use of parent fitness has led us to continue with its use. One reason for doing so is to make the continuous and discrete implementa- tions of BCB as similar as possible. 'Jhe next set of experiments seeks to compare the truncated discrete normal with mutation versus a dis- crete normal distribution in Step '1 of the algorithm. The table below summarizes these experiments for the discrete normal distribution which can be compared against the results in Tables 1 and '2. Here we see that the use of tails for the discrete normal is beneficial. 26 optimal shapes are found with the tails and only 12 with the mutation approach. In addition, the mean best objective value for the tails approach wins in 4 of Table 3. Discrete Normal with tails; 15 reps, 20,000 solutions # Shapes Mean Best Obj Min Best Obj Max Best Obj Freq Opt Shapes 3 84.0 82.9 88.4 13/15 t 85.6 82.9 90.6 7/15 r 89.0 82.9 99.9 5/15 (i 91.3 86.0 99.9 0/15 ^ 91.8 82.9 99.6 1/15 4. Hub Design Problem Our standard test problem in Sobieszczanski- Sobieski et al. (1998), Kincaid et al. (2000) and Kincaid (2001) has been a minimum weight (volume) design of a huh structure also found in Balling and Sobieszczanski-Sobieski (1994). Each member of the hub structure is an I-beam rigidly attached to the hub and to the wall, forming a two-dimensional, wheel- wilh-spokes pattern whose two-beam version is illus- trated in Figure :?. The structure load has three com- ponents, horizontal and vertical concentrated forces, and a concentrated moment, all acting on the hub in the plane of the structure. Various loading cases (henceforth called '"loads'") are formed from the above load components, lliree loading cases are applied to a fi-beam structure, and two loading ca.se are used in case of a 20-beam structure to reduce the computing elapsed time. The beam cross-sectional dimensions are the design variables, and the constraint functions re- flect the material allowable stress as well as overall and local buckling. The top and bottom flanges of the I-beam are not necessarily of the same dimensions. Hence, the cross-section of each I-beam requires six design variables. Figure :? illustrates a 2-meml)er hub problem. Additional details may be found in Padula et al.(1996). The utility of the hub structure as a test case stems from its ability to be enlarged by adding as many members as desired without increasing the dimensionality of the load-deflection equations. These remain .] by :? equations for a 2-dimensional hub struc- ture regardless of the number of members. While analytically simple, the hub structure design space is complex because the stress, displacement and buck- ling constraints are rich in nonlinearities and couplings among the design variables. Our goal is to extend this problem so that, in addition to choosing the dimen- sions of the beams so as to minimize the volume of the hub frame, we would also select (among a finite list) the beam type. As a first step in this direction we consider '.\ beam cross-section types I, circular, and triangular. In all ca.ses the overall length of the beam is held constant amongst the cross-section types. The I-beam has 6 design variables; the circular beam has 2 design vari- 5 OF 9 Amebtcan iNSTrrnTR OF Arronaiitics and Astronautics Paprr 2002-1675 ables; and the triangular beam has 3 design variables. Our first experiment is with a 6 l)eam 3 load hub de- sign problem. Each beam has the same nominal length of 120.0 and the following BCB parameters values: B2 !T2 T3 ESt 7.:.:.::::..:::7.:.::j::jj.:..:.. <«—«—** j *~ -■»,* it B1 iTI Figure 3. 2-member hub description population size : 20 number of generations : 1250 replications : 50 PENALTY 1 : 2000.0 PENALTY2 : 4000.0 fitness-related mean for discrete normal number of swaps As a benchmark we force mixed BCB to choose all I-beams and obtain the following results: Order NOT Important Order Important min vol 576.62 554.51 mean vol 687.81 681.02 s.d. vol 63.63 126.33 The case in which the order of matching elements in the parents matters leads to slightly better results. This trend has been borne out in all of computational experience although the order is important approach seems to require more generations to converge. We ex- pect this is due to the larger neighborhood of feasible solutions when order counts. With the penalties shown above, the maximum con- straint violations occurred as follows: Order NOT Important Order Important mean max. violation -0.00039 -0.0085 s.d. max. violation 0.0027 0.0596 The following table lists the results when mixed BCB is allowed to choose one of three possible shapes (I- beam: 1 , circle:2, or triangle:3) for each of the six beams when the order does not matter in computing the dis- tance between discrete components. Table 4: Frequencies of designs chosen (order does not matter) Min Mean Std Dev Design # Best Vol Best Vol Best Vol 1,1,1,2,2,2 456.90 456.90 - 1,1,2,1,2,2 711.10 711.10 - 1,2,1,3,2,2 448.84 448.83 - 1,2,2,2,1,2 404.51 404.51 - 1,2,2 2 2,2 383.29 383.29 0.001 1,3,2,2,2,2 429.78 429.78 - 1,3.2,2,3,2 464.50 464.50 - 2,1,1,2,2,2 416.85 416.85 - •; 1 ') •) •> 462.20 462.20 - 2,1,2,2,2,3 592.75 592.75 - 2,1,2,3,2,2 447.83 447.83 - 2,1,3,2,2,1 477.77 477.77 - 2 2 2 12 2 417.72 417.72 - ■> •> ■> 1 3 ■> 464.91 464.91 - ■> ■> •) 1 1 461.79 461.79 - •> •> •> •> 1 •:> 383.20 383.20 - 2,2,2,2 2,1 471.11 471.11 - 2,2 2,2,2,2 361.91 .365.98 10.51 •> •> •> ■> •> x 426.61 426.61 - 2,2,2,2,3,2 401.99 422.61 20.62 •; •; •> :? •; i 533.66 533.66 - 2 2 2 3 2 2 416.74 447.42 30.68 ■) ■> '] ■> ■> ■> 401.51 401.51 0.002 2,3,2,2,2,2 424.75 426.89 2.14 2,3,2,2,2,3 576.26 576.26 - 2,3,3,2,2,3 541.52 541.52 - 2,3,3,3,2,2 502.52 502.52 - 3,1,2,2,2,2 489.31 489.31 - 3,1,3,3,2,2 541.69 541.69 - ■X ■> ■> •> 1 ■> 429.18 429.18 - 3 2 2 2 2 2 7 401.49 401.49 1.65 3,3,2,2,2,2 1 527.12 527.12 - Best Designs: 2,2,2,2,2,2 with a minimum volume of 361.91 3,2,2,2,2,2 with a minimum volume of 401.49 One of these two designs was selected 30'/. of the time The folloW'ing table lists the results when mixed BCB is allowed to choose one of three possible shapes (I- beam: 1 , circle:2, or triangle:3) for each of the six beams when the attribute order does matter in computing the distance between discrete components. 6 OF 9 American Tnstiti'tf, op Aeronautics and Astronautics Paper 2002-1675 Table 5: Frequencies of designs chosen (order does matter) following results are obtained when mixed BOB is al lowed onlv to choose I-beams: Design 1,2,2,1,2,2 1 2 2 2,2 2 2,2,1,2,1,2 •'•'•' 1 1 1 2 2 2,1,2 2 2 2 2 2 12 2,2,2,2,1,;^ 2,2,2,2,2,2 2 2,2,2,2,:? 2,2,2,^,2,1 2 2 2,:5 2,2 2,2,3,2,2,1 2,2,3,3,2,2 2,3,1,3,2,2 2,3,2.1,2,2 2,3,2,2,2,2 2,3,2,2,3,2 3,1,2,2,2,2 3), 2, 2, 2, 2, 2 ., ., ., ., ■:[ ., # 1 3 1 1 3 •_) 2 22 1 1 3 1 I 1 1 1 1 Min Best Vol 421.07 383.19 404.90 479.39 399.77 38f).97 434.42 361.91 412.54 .527.49 407.82 451.82 441.57 517.07 538.54 485.36 410.65 444.29 476.33 423.71 441.13 Mean Best Vol 421.07 383.44 404.90 479.39 477.93 436.16 488.10 362.00 412.54 527.49 427.82 451.82 441.57 517.07 538.54 485.36 410.65 444.29 476.33 423.71 441.13 Std Dev Best Vol 0.21 61.39 49.19 53.67 0.15 14.48 Best Designs: 2,2,2,2,2,2 with a minimum volume of 361.91 1,2,2,2,2,2 with a minimum volume of 383.19 2,2,2,1,2,2 with a minimum volume of 386.97 2,2,2,1,2,2 with a minimum volume of 399.77 One of these four designs was chosen 60*/, of the time. With the same penalties as l)efore, the maximiim con- straint violations occurred as follows: Order NOT Important Order Important mean max violation -0.076 -0.0619 s.d. max violation 0.0849 0.06 The above tables indicate the trends we have seen in variety of problem instances. The "order does matter" approach results in fewer, higher cpiality solutions and the distribution of final solutions is tighter (smaller variance) wnth a higher cpiality mean. Next, we consider a 20 beam 2 load hub design problem. Again all 20 beams are of the same nomi- nal length. The same BOB parameters were used as in the previous experiment except that Penalty 1 was increased to 10,000 and Penalty 2 was increased to 20,000. With these penalties, the program had a con- dition added that the maximum constraint violation must be less than 0.02. .\gain, as a l)enchmark, the Order NOT Important Order Important min. vol. 17089.629 17112.098 mean vol. 18984.661 17869.609 s.d. vol. 2051.516 1285.047 The use of the "order does matter'' definition of dis- crete distance yields results that are only slightly bet- ter with respect to the mean but are significantly better with regard to the variance in the results. The following table list.s the result.s when mixed BOB is allow^ed to choose one of three possible shapes (I- beam:!, circle:2, or triangle:3) for each of the six beams. Order NOT Important Order Important min. vol. 12865.855 13394.102 shapes 2,2,1,3,2,2,1,3,2.2. 2.3,2,1,1,2,2,2,2,1 2,2,2,2,2,2,1,3,2,1, 2,2,2,3,3,2,2,2,2,2 mean vol. 16140.339 14278.798 s.d. vol. 1694.326 1070.669 Here we can see a significant improvement w ith the use of the "order does matter'" discrete distance definition. Next we increase the number of choices for the beam type (the only discrete variable) from 3 to 6. The shape choices for each beam are 1:1, 2:circle, 3:triangle, 4:rectangle, 5:1", or 6:C. This problem w^as run with all 6 beams having the same nominal length and the following BOB parameters: population size : 20 number of generations : 1250 replications : 50 PENALTY 1 : 2000.0 PENALTY2 : 4000.0 fitness-related mean for discrete normal number of swaps The experiment was first run for the case when "order does NOT matter'" and, of the 50 replications, only the following solutions were repeated: Design # Min Best Vol Mean Best Vol Std Dev Best Vol 1,2,2,2,2,2 2,2,2,2,6,2 2 2 383.22 456.4 1 383.34 467.58 0.12 11.17 The range of values for all the solutions was 361.91 (2.2,2,2,2,2) to 977.27 (5,6,4,5,2,1) w^ith an average value of 533.11 and standard deviation of 1 19.91. The same experiment was repeated for the case when order does matter and, of the 50 replications, only the follow'ing solutions were repeated: 7 OF 9 Amrrican Insttti'tf, of Aeronai'ttcs and Astronautics Paprr 2002-1675 Min Mean Std Dev Design # Best Vol Best Vol Best Vol •; •> 1 •> •> ■> 2 383.20 383.32 0.12 •; ■) •> ■> •> ■> 6 361.91 376.94 33.22 •) •> •> •> 5 •> 2 395.20 415.09 19.89 ■} •) 5 •) -7 9 2 395.20 449.81 54.61 The range of vahies for all the solutions was 361.91 (2,2,2,2,2,2) to 1322.02 (5,2,6,2,2,2) with an average value of 526.35 and standard deviation of 148.02. If the single outlier value of 1322.02 is discarded, the maximum value is 701.03 (1,2,2,2,3,5) and the average value over the 50 replications is 507.85 with a standard deviation of 85.75. In this manner we have a tighter range of values then with the "order does not matter'" definition of distance. Next we consider the 20 beam 2 load problem and u.se the same BC'B parameters as in our previous 20 beam 2 load case except that 6 shape choices (1:1, 2:circle, 3:triangle, 4:rectangle, 5:1", or 6:C). are now available. This yielded the following results over 20 replications: Order NOT Important Order Important min. vol. 14949.145 143.59.097 shapes 2,4,4,2,2,6,1,2,2,2, 6,2,2,3,2,3,4,6,4,5 4,2,4,,5, 1,1, 4,2,2,4, 2,3,3,2,5,4,3,2,2,6 mean vol. 16827.441 15803.128 max. vol. 19001.340 177.34.045 shapes 1,3,4,6,4,6,5,6,2,6, 5,2,2,5,4,4,2,2,1,1 4,.5,4, 5,4, 1,2,1,2,6, 2,2,1,2,2,1,5,2,6,1 s.d. vol. 1233.146 901.371 The use of the "order does matter'' definition for dis- crete distance yields results that are both slightly better with respect to the mean and less spread out (smaller standard deviation) over the multiple runs. 5. Concluding Remarks in this manuscript we have examined an extension of BCB that encompa.sses a mix of continuous and quasi-discrete, as well as truly-discrete applications. We began by testing two refinements to the discrete version of BCB. The testing of midpoint versus fitness (Tables 1 and 2) proved inconclusive. The testing of discrete normal tails versus standard mutation showed was conclusive and demonstrated that the discrete nor- mal tails are better. Next, we implemented these re- finements in a combined continuous and discrete BCB and compared the performance of two discrete distance on the hub problem. Here we found when "order does matter'' it pays to take it into account. The computational experiments we have performed lead naturally to additional questions. Will the per- formance of mixed B( 'B be improved if BCB is linked with pattern search? Pattern search is a derivative free local search procedure that has been shown to perform well on a variety of nonlinear optimization problems (see Lewis et al. 2000 for details). Previous work (Kincaid et al. 2001b) has shown that BCB coupled with local search procedures works well for the contin- uous version of BCB. The reasoning is that BCB does a good job of identifying valleys of intere.st but takes too long getting to the bottom. Will the same be true in the mixed continuous and discrete ca.se? Our work here focused on a small scale structural op- timization problem for testing the performance of dis- crete BCB. It is natural to wonder if discrete BC'B will stand up against other competitors-tabu search, sim- ulated annealing, and traditional genetic algorithms. A potential scalable problem venue to test this conjec- ture is the the NK-landscape model. The NK model is due to Kauffman (1989) and is a random energy model similar to a spin glass. It is designed to be tune- able. That is, as K increases the landscape becomes more rugged. When A' = I) a highly correlated land- scape with a single peak results. At the other extreme, when A' = A' — 1 (where N is the number of decision variables) a completely uncorrelated landscape results with very many peaks. 6. References Baker, .I.E. (1987). Balancing Diversity and Con- vergence in Genetic Search. Dissertation, (\)mputer Science Dept. Vanderbilt University, Nashville, TN. Balling, R..I. and J. Sobieszczanski-Sobieski, "An Al- gorithm for Solving the System-Level Problem in Mul- tilevel Optimization," ICASE Report No. 94-96 and NASA Contractor Report 195015, December 1994. Kauffman, S.A. (1989) "Adaptation on Rugged Fit- ness Landscapes," in D.L. Stein (ed.) Lectures in the Sciences of Complexity, Addison Wesley, Vol. 1, pp. 527-618. Kelly, J. P., M. Laguna, and F. Glover (1994) "A Study on Diversification Strategies for the Quadratic Assign- ment Problem," ('omputers and Operations Research, Vol. 22, No.8, pp. 8«5-893. Kincaid, R.K., Weber, M. and Sobieszczanski- Sobieski, .1. (2000) "Performance of a Bell-( 'urve Based Evolutionary Optimization Algorithm," Proceedings of the ./7s< .47.4.4 Structures, Structural Dynamics, and Materials Conference, Atlanta, GA, AIAA 2000- 1388. Kincaid, R.K., Weber, M. and Sobieszczanski- Sobieski, .). (2001a) "A Bell-Curve Based Algorithm for Mixed Continuous and Discrete Structural Opti- mization," Proceedings of the ^2nd AIAA Structures, Structural Dynamics, and Materials Conference, Seat- 8 OP 9 Amrbican Institiitp, of Arronamtics and Astronautics Paper 2002-1675 tie, WA, AIAA 2001-1550. Kincaid, 1{.K., Weber, M. and Sobieszczanski- Sobieski, .1., "An Atypical (// + /() Evolutionary Al- gorithm,'" submitted for publication in 2001b. Lewis, R.M., I'orczon, V. and Trosset, M. (2000). Di- rect Search Methods: Then and Now. To appear: ./. of Computational arid Applied Mathematics. Padula, S.L., Alexandrov, N. and Green, L.L. (199<i). MDO lest Suite at NASA Langley Research Center. In: Proceedings of the 6th AlAA/NASA/ISSMO Sym- posium on Multidisciplinary Analysis and Optimiza- tion, (pp. .110-420). Bellvue, WA. (See http://fmad- www.larc.nasa.gov/mdob/) Plassman, .1. and Sobieszczanski-Sobieski, .1. (2000). Parallel Scalability of Bell-Curve Based Optimization. Working Paper. KASA-Langley Research Center. Hampton, VA 2:ifi81. Sobieszczanski-Sobieski, .1., Laba, K. and Kincaid, R.K. (199M) Bell-Curve Based Evolutionary Opti- mization Algorithm. In: Proceedings of the 7th AIAA/VSAF /.XASA/ISS.MO Symposium on Multi- disciplinary Analysis and Optimization, (pp. 208.'!- 2096) St. Louis, MO., AIAA Paper 98-4971. 9 OF 9 American Institute of Aeronaitttcs and Astronautics Paper 2002-167'