Skip to main content

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'