Affordability Measurement and Prediction Techniques
 
Search and Optimization Methods
 
The ADEPT environment being developed by Decision Dynamics, Inc. contains a suite of inter-related simulation models designed to help people understand and manage a product’s entire life cycle from design, through production, and operation. Supporting these three models is a model which provides insights into the operation of an in-depth supplier-chain supporting an end product (e.g., weapons system) and a model used to explore the dynamics associated with managing the resources (labor, material, capital) used to design, build and maintain a product. The power and capability these models offer users is well beyond existing analytical or simulation tools. Although designed to be easy to use, ADEPT models can become increasingly complex as the level of detail is increased. Increasing the model resolution yields a proportional increase in the number of variables that will affect desired outcomes.
 
Using the ADEPT production module as an example, it is easy to see how the number of policy decisions under a user’s control can grow beyond the user’s capability to effectively manage the 'what-if?' analysis process. The production module allows users to separately define a manufacturing process and production run and the resources available for the production process. For example, a user can lay out a production sequence with several dozen key assemblies, each with a handful of tasks. The user can then specify a manufacturing production run of 100 aircraft. For this production example, the user may identify two manufacturing facilities, each with ten workstations and five labor trades. In this type of model setup, the user can explore tradeoffs in delivery dates, resource requirements and production costs measured in direct labor hours. In order to minimize even a single objective, total production costs for example, the user can modify production schedules, resources available, levels of concurrent production and management policies affecting overtime or over-manning to name a few. The model described may have decision points that number in the hundreds!
 
Traditional trial-and-error methods force users to make a series of changes to one or more parameters, run the model, note the results and repeat the process. Such techniques almost guarantee that the user will miss one or more sets of actions likely to provide a better result. Fortunately, search and optimization methods exist which can help automate the trial-and-error process.
 
These methods fundamentally change the way analysts work with advanced simulation models. Instead of spending time making hundreds of runs looking for an acceptable answer, the user can focus attention on defining the objectives for the system being modeled (lowest cost, shortest schedule) and on identifying the policies which can be realistically influenced in the real-world system. This information, in unison with appropriate search and optimization methods allows the simulation model to determine the appropriate values for the policies under user influence. ADEPT will let end-users know if their goals can be met, and if so, how to get there!
 
Search and Optimization Methods of Solution
 
A search of the literature on optimization methods has been conducted to ensure that the most appropriate optimization methodologies for use with SD models are selected and to understand the capabilities and limitations of the different methodologies. The following subsections provide a comparison of key optimization methods of solution (4:2). Two key terms need to be defined before the discussion:
 
  1. Variable or Parameter. Defined as “those independent features that distinguish the results from one another - they may be represented as binary, integer, otherwise discrete or real values (4:2).”
  2. Objective Function. “A rational decision between the real or imagined variants presupposes a value judgment, which requires a scale of values, a quantitative criterion of merit, according to which one solution can be classified as better, another as worse. This dependent variable is usually called an objective (function) because it depends upon the objective of the system – the goal to be attained with it (4:2).”
 
Experimental versus Mathematical. Experimental methods are applied to optimization problems when the functional relationship between variables and the objective function are not known. The experiments may be run on the real system, or on a model of the real system. Test strategies are established to vary parameters in a reproducible manner in order to determine the influence on the objective.
 
Mathematical optimization may be used when the relationship between the objective function and the parameters are known (at least approximately). Parameters are varied in order to achieve the desired objective.
 
Static versus Dynamic. The term static optimization means that the optimum is time invariant. Dynamic optimization supports the notion of an optimal condition determined by the existence of varying conditions in the system under consideration.
 
Parameter versus Functional. Parameter optimization is defined as having the objective function and independent variables exist as scalar quantities. Functional optimization seeks to optimize trajectories in specified function spaces. The independent variables may be functions of one or more parameters.
 
Analytic versus Numeric. An analytic optimization technique attempts to reach an optimum in a single procedure without relying on tests or trials. Optimization is typically accomplished by solving for a set of simultaneous equations that approximate the system being optimized. Numeric optimization uses a series of steps, using approximations as needed, to iterate to an answer.
 
Optimization Strategies
 
A number of optimization strategies have been developed to meet the needs of different problem domains. The following paragraphs examine some of the strategies that have been developed and identify the characteristics necessary for use with SD models.
 
Hill Climbing Strategies. Hill climbing strategies are applicable to static, non-discrete, non-stochastic, mostly unconstrained functions. The name, 'Hill Climbing', is given to this class of strategies because the functions approximate the intuitive way a sightless person might feel their way to the highest mountain peak that they are on. Hill climbing strategies are most frequently applied to engineering design problems.
 
Hill climbing strategies are useful when analytic methods are not suitable for a number of reasons. Analytic limitations include solutions which provide sub-optimal results (local minima or maxima or a saddle point) or when a system of simultaneous equations describing the system are not solvable.
 
Reviews of the numerous hill climbing strategies which exist are beyond the scope of this report. Interested readers should consult the references included at the end of this report.
 
Random Strategies. Random strategies include optimization methods that vary parameters according to probabilistic rather than deterministic rules. Such strategies are often used when deterministic strategies have limited success or lead to a sub-optimal result. Random search and optimization strategies benefit from being “blind” with respect to the problem domain. In other words, a random strategy does not need to know anything about the system being optimized. It works by varying parameters and comparing the results through an objective function.
 
Evolution Algorithms. Evolution algorithms are a subset of the random strategies. These algorithms mimic the behavior of the natural selection process where a population of parameter sets evolve according to rules of selection. Each member of the population receives a measure of fitness, which is then compared with other members of the population. A new population is generated by breeding the most fit members of the current population. Recombination and mutation are used to provide for a fuller exploration of the problem space being searched for an optimal value.
 
Techniques Appropriate for System Dynamics Models
 
SD models are classified as continuous, deterministic models. By continuous, it is meant that during the course of a simulation a fixed-size time step is used. For example, a SD model designed to run for 20 years with a monthly time step would iterate through the simulation 240 times. By deterministic, it is meant that no random functions are used to generate model behavior. Given a set of fixed parameters, a deterministic model will generate an identical result for every simulation.
 
In addition to these two properties, SD models are distinguished from other modeling methodologies in that the model structure is established independent of any data. The same model structure can be used to simulate a range of practices. For example, the task model structure used in the production module is equally applicable to a one-hour task using one person and to a 10,000-hour task using 50 people.
 
These three properties of SD models, continuous, deterministic and structural make them very amenable to the types of search and optimization algorithms which use parameter-based algorithms using a (relatively) large population size to search a solution space. Specifically, the search and optimization algorithms developed under the umbrella classification of evolutionary algorithms are suitable for use with SD models.
 
Based on the literature review of available search and optimization methods, the following attributes were deemed necessary for successful integration of optimization with SD models:
 
  1. SD models support mathematical optimization methods. The structure and functional relationships among parameters and specified objective functions can be intuited.
  2. The optimization method must support static and dynamic optimization. SD models support the notion of static and dynamic optima. Minimizing total cost is a representative static optimum, while maintaining a level-loaded labor force is representative of a dynamic optimum one might consider when working with a SD model.
  3. The optimization method can be parameter based, rather than function based. The parameters used for optimizing a SD model can always be represented as scalar values. SD model functions can be represented as a series of scalar values for optimization purposes.
  4. The optimization method should be numeric rather than analytic. The set of simultaneous, first order differential equations which comprise a SD model, combined with the n-dimensionality of the model structure employed by SNAP models, places them in the category of insolvable. Numeric methods do allow for reasonable approximations for solutions to the model equations.
  5. The optimization method must be “blind” to the model structure. The selected optimization technique must apply to a range of SD models (even beyond the five models included with SNAP). Techniques that are specific to a single model and to a single objective within a model are too inflexible to be considered for integration.
 
Based on the literature review of optimization characteristics and strategies, and given the requirements for use with SD models, two complimentary strategies have been identified as applicable to ADEPT: evolutionary strategies and genetic algorithms. The following section describes these two strategies.
 
Evolutionary Algorithms
 
Evolutionary Algorithms (EA’s) are an umbrella term for a class of search and optimization techniques that use models of evolutionary processes to evolve a solution to an optimum as specified by an objective function. EA’s share a basic algorithmic structure.
 
  1. Start with an initial generation (t = 0).
  2. Initialize a population of individuals (usually with random values) – each individual in the population maintains a representation of the parameters used in the optimization.
  3. Evaluate the fitness of each member of the population.
  4. Iterate until the desired fitness level is achieved, or the number of generations specified is reached. Iterate using the following steps:
    1. Increment the generation (t = t + 1).
    2. Select a sub-population for offspring production.
    3. Generate a new population by recombination of the selected members of the sub-population.
    4. Perturb the new population (mutate).
    5. Evaluate the fitness of each member of the population.
    6. Return to ‘D’.
 
Although EA’s share a basic algorithm, different EA’s vary in their implementation of elements found in the algorithm. Differences in methods used to define individuals in a population, selection methods for recombination, recombination techniques and mutation methods distinguish one type of EA from another. The next two sections explain how two EA’s, evolutionary strategies (ES) and genetic algorithms (GA) implement this basic algorithm.
 
Evolutionary Strategies
 
Evolutionary Strategies (ES’s) were developed in the mid-60’s by engineering students at the Technical University of Berlin to solve problems in the field of fluid mechanics. Given their origin, ES’s have historically been applied to engineering disciplines.
 
Despite their initial success with engineering problems, ES’s are adaptable to a broad range of problems because they need very little information about the problem to produce results. “ES’s are capable of solving high dimensional, multimodal, nonlinear problems subject to linear and/or nonlinear constraints. The objective function can also, for example, be the result of a simulation, it does not have to be given in a closed form (3).”
 
Basic ES Algorithm. ES’s can be implemented in a number of ways. Different implementations vary the population size, the selection process, recombination and mutations. The basic ES algorithm uses a single parent that is mutated to generate a single offspring. The basic algorithm is described in the following paragraphs.
 
Initializations:
          A single parent (P) is created where the parent is defined as a vector of n real valued numbers,
          where n represents the number of independent parameters.
 
                    P(x) = {x1, x2, … xn}
 
Mutations:
          An offspring (N) is generated by applying normally distributed mutations to each member
          variable:
 
                    N(x) = {x1 + z1, x2 + z2, … xn + zn}
 
          Where zi, is a random value generated uniquely for each xi. Rules used to generate zi are beyond
          the scope of this report. Interested readers should refer to references in the bibliography.
 
Selection:
          The parent, P, and the offspring, N, are compared for fitness based on the specified objective
          function. The one determined to be most fit is used to generate the next offspring.
 
Multi-Membered Evolutionary Strategies. The basic, two membered evolutionary strategy is capable of solving many optimization problems. In order to achieve a more accurate representation of evolutionary processes, however, the method has been extended to a population beyond two members. This refinement is referred to as a multi-membered evolutionary strategy. Multi-membered ES’s work as follows:
 
Initialization:
          A population of m individuals are defined. Each individual is defined having the same
          n parameters, each with potentially different initial values.
 
Variation:
          Each parent produces l/m offspring (on average), generating a new population of l individuals.
          Mutations are applied to each offspring so that they vary slightly from their parents. Each
          individual in the population l still includes n parameters.
 
Filtering:
          The m best of the l population are selected to become parents of the next generation. The
          selection of m parents is based on fitness as determined by the specified objective function.
 
Alternative Mutation Operations. Mutation operations beyond the one described in the basic algorithm may be applied to members of a population. Descriptions of these alternative operations are beyond the scope of this report. Interested readers should refer to texts listed in the bibliography for more information. The most common alternative methods require that the reader be familiar with basic probability theory and applied statistics in order to understand their operation.
 
Recombination. ES’s have also been developed to support the concept of recombination. Recombination is the process of swapping information among members of a population during the generation of a new population. The basic algorithms previously described assume an offspring is created with a single parent. Recombination requires two parents to generate new offspring. Recombination works as follows:
 
Given two parents, P1 and P2, with parameters 1 through n, two offspring will be created.
 

 

X1

X2

X3

Xn

P1

a

b

c

d

P2

e

f

g

h

 

 

 

 

 

N1

a

f

g

d

N2

e

b

c

h
 
For each parameter, 1 through n, a random selection is used to choose a value for each offspring. A number of selection methods are documented in the literature on ES’s. The simplest assumes a 50-50 probability of selection.
 
Recombination provides for variations in the population designed to prevent the optimization algorithm from becoming focused on a local optima.
 
Advantages. The ES’s capacity for solving high dimensional, multimodal, nonlinear problems makes them ideally suited for use with a SD model. ES support for objective functions created from simulation results is also a definite advantage. Using a two-membered strategy minimizes the number of simulation runs required to reach a solution.
 
Disadvantages. ES’s require a fair degree of knowledge of probability and statistics. Two-membered strategies may not be acceptable for use with SD models. Multi-membered strategies require a high number of simulation runs to complete an optimization.
 
Genetic Algorithms
 
John Holland and his colleagues at the University of Michigan developed Genetic Algorithms (GA’s). The goals for development were twofold: to abstract and explain the adaptive processes of natural selection and to design software that implemented the natural selection processes.
 
GA’s differ from ES’s and other search and optimization methods in that they work with a coding of the parameter set not the parameters themselves. Aside from this, GA’s and ES’s are strikingly similar. GA’s and EA’s both perform a search using a population of points, both use objective functions and both use probabilistic transition rules for population generation, recombination and mutation.
 
Basic Algorithm
 
Initialization:
          A population of individuals is randomly generated. Each independent parameter, xi, is coded into
          a (typically) binary string representation. For example, given a parameter, x1, with a possible
          value of 25 to 75, the parameter could be randomly set for each member of the population with a
          value between: 0011001 and 1001011. Each parameter is similarly coded, creating a continuous
          binary string.
 
Selection:
          Members of each population are selected for reproduction based on their fitness, as defined by
          the specified objective function. There are two basic selection mechanisms: fitness-proportionate
          and tournament selection. Fitness-proportionate selection uses probability to determine who is
          selected for breeding.
 
          Tournament selection randomly selects members of the population to compete for the privilege of
          reproducing. This approach more closely mirrors the natural selection process where members of
          a species struggle for the right to breed.
 
Reproduction:
          Once two members of the population are selected for reproduction, a probabilistic method is
          used to determine a crossover point where the binary strings for each member are integrated.
          For example, given the two members of the population, P1 and P2, a crossover point is
          randomly chosen to occur between the 4th and 5th bit. The selection and crossover process
          generates offspring N1 and N2.
 
          P1: 0111|001100111 N1: 0111010110101
          P2: 1010|010110101 N2: 1010001100111
 
          In this manner a new population is created and the algorithm is applied again.
 
Mutation:
          EA’s also support the concept of mutation – the random change in bits in an individual’s genetic
          composition. Mutation is also applied in a probabilistic manner, with the chances of occurrence
          being very low (typically 1-3% probability).
 
Advantages. Like ES’s, GA’s are capable of solving high dimensional, multimodal, nonlinear problems. GA’s support for objective functions resulting from a simulation is also an advantage.
 
Disadvantages. The primary disadvantage of a GA over ES or other techniques is that parameters must be coded into a binary representation. While not a problem for integer valued parameters, this mechanism limits the range of real values which may be searched. Advanced GA’s do support work with real values, but perhaps not as well as EAs which were designed from the start for use with real numbers.
 
 
 
Bibliography
 
1. Ficek, Rhonda. Independent Study of Genetic Algorithms. Technical Report
          NDSU-CS-TR-90-51. North Dakota State University, 1990.
 
2. Goldberg, David E. Genetic Algorithms in Search, Optimization & Machine
          Learning. Reading, MA: Addison-Wesley Publishing Company, Inc., 1989.
 
3. Heitkoetter, Joerg and Beasley, David, eds. (1997) “The Hitch-Hiker’s Guide to Evolutionary
          Computation: A List of Frequently Asked Questions (FAQ)”, USENET: comp.ai.genetic.
          Available via anonymous FTP from rtfm.mit.edu:/pub/usenet/news.answers/ai-faq/genetic/ About
          110 pages.
 
4. Schwefel, Hans-Paul. Evolution and Optimum Seeking. New York: John Wiley & Sons, Inc., 1995.
 
5. “Dakota Iterator Toolkit.” Available from sass577.endo.sandia.gov/1434/sd_optim_dakota.
          Albuquerque, NM: Sandia National Laboratories, 1997.
 
6. “Evolutionary Algorithms: Genetic Algorithms, Evolutionary Programming and Genetic
          Programming”. Available from Global Optimization Survey – Main Page,
          www.cs.sandia.gov/opt/survey/. Albuquerque, NM: Sandia National Laboratories, 1997.