This summary report describes progress in the first year of work at Stanford University under the HPCCP grant #1-NAG-1558. This research is aimed at the development of improved methods for multidisciplinary design and optimization of large-scale aeronautical systems. The architecture involves new approaches to system decomposition, interdisciplinary communication, and methods of exploiting coarse-grained parallelism for analysis and optimization. The basic approach involves three major components:
1. System decomposition using compatibility constraints to simplify the analysis structure and take advantage of coarse-grained parallelism introduced by the decomposition
2. The use of computational differentiation to improve the efficiency of both intradisciplinary design and optimization of the system as a whole.
3. The introduction of collaborative optimization: a decomposition of the optimization process to permit parallel design and to simplify interdisciplinary communication requirements.
This research deals with development of the basic architecture and supporting computational tools, application to an example HSCT design problem to demonstrate scalability to complex three-dimensional configurations, and demonstration of parallelism on a system of distributed workstations.
Work in several areas was undertaken in the first year of this grant. Reference 1 constitutes a more comprehensive description of the methodology and initial accomplishments, but major results are summarized here.
Decomposition and Parallelization by Compatibility Constraints
An example aircraft synthesis program, PASS, has been decomposed into three parts using auxiliary variables and compatibility constraints. Sequential execution proved faster than for the original one-part version of PASS. The exploitation of contraction among the several dozen analysis routines is responsible for this surprising result and methods for further exploiting this structure are under development. As described in the original statement of work, an investigation of various forms for compatibility constraints was undertaken and reported in reference 1. Although a parallel implementation of the decomposed design problem was not anticipated until year 2, this was recently accomplished on a heterogeneous network of workstations. This work included development of a new version of an MDO executive program, GenIE, for use with the network of workstations. This software will aid in the implementation of network-based versions of other codes.
A Tool for Decomposition and Planning
The decomposition through compatibility constraints permits division of problems into convenient parts, based either on traditional disciplinary groups, other management considerations, or efficiency. The three-part aircraft design problem , discussed previously, was divided by hand, based on the known structure of analysis interconnections. In a larger problem, this manual approach is not feasible. Problems with "thick" connections between analyses may be difficult to decompose, requiring the introduction of hundreds or even thousands of new variables and constraints. Thus, planning an efficient decomposition is an optimization task in itself. The objective is to minimize the total solution time, by creating subtasks that can be conducted in parallel. The design variables represent the ordering of the analysis subroutines. The optimizer seeks to find the correct location for each subroutine in the analysis procedure. Conventional calculus-based optimizers are not effective in this domain, but a number of genetic algorithms have been developed for the solution of planning problems.
Genetic algorithms are designed to mimic evolutionary selection. A population of candidate designs is evaluated at each iteration, and the candidates compete to contribute to the production of new designs. Each individual is represented by a string, which is a coded listing of the values of the design variables. The entire string is analogous to a chromosome, with genes for the different features (or variables). When individuals are selected to be parents for offspring designs, their genetic strings are recombined in a crossover operation, so that the new designs have elements of two earlier designs. A mutation operation also allows modification of elements of the new individual so that it may include new features that were not present in either parent. Simple crossover operators are not appropriate for permutation problems, because they do not guarantee offspring that include exactly one copy of each design variable, and no duplicates. Several crossover schemes have been developed for use in planning problems. Six of these were compared by Starkweather who found that the best overall performance (on a travelling salesman problem and a warehouse/shipping scheduling problem) was achieved by position-based crossover, originally introduced by Syswerda. This scheme was adopted for the decomposition problem.
The genetic string for the decomposition problem is an integer vector of length n+m, where n is the number of analysis subroutines and m is the number of potential break points (allowing m+1 independent subtasks). Each population member is a permutation of the integers between 1 and n+m. For a task with 10 subroutines to be split into 3 subtasks, n=10 and m=2.
The tool has been used on a number of problems with very favorable results. Solutions to task scheduling problems that are equal to or better than DeMaid on all test problems have been produced. The system also "discovers" traditional disciplinary classifications when applied to the aircraft synthesis program, PASS.
In addition to careful planning of the decomposition, advanced tools for differentiation may exploit the special character of compatibility constraints to make problems involving large numbers of auxiliary variables tractable. Preliminary work on this approach has already been undertaken in a collaborative effort with Argonne National Laboratory and the current work includes further investigation of the application of automatic differentiation in decomposed systems for MDO.
Work during the initial proposal effort, and subsequent investigations in collaboration with Christian Bischof and Paul Hovland from Argonne National Laboratory, have identified several synergistic effects between the proposed architecture and computational differentiation. The quasi-procedural framework was modified to allow for the use of ADIFOR-generated derivative subroutines and the complete system was tested on the single and decomposed version of the aircraft sizing problem. The following advantages are especially important in this work:
Recent work suggests that much of the surprisingly large time savings associated with the use of ADIFOR in the aircraft design problem is associated with greatly reduced overhead in the database management aspects of this problem. The analyses were divided into very small components, with an associated large overhead burden. Subsequent computations using more time-consuming lifting surface analyses showed smaller advantages. This aspect of the results is of interest as AD has usually been applied to large monolithic codes and its potential advantages in larger scale MDO problems may yet to be recognized.
As described in the original research proposal, collaborative optimization is an approach to decomposition of the design problem. The method involves separating analyses into discrete groups which share many of the same variables. In aircraft design, for example, these may be the familiar disciplines of aerodynamics, structures, etc.. Each group of analyses receives a set of input and output target parameters. The analyses each use a local optimizer to minimize the difference between the target parameters and those calculated by the local analyses, while ensuring local constraint satisfaction. The target parameters are specified by a separate, system level optimizer with the objective function of minimizing one of the targets (i.e. range or DOC for an aircraft design problem). This scheme has several advantages, including minimizing the amount of information transferred between disciplines, removing large iteration loops between disciplines, and exploiting conventional disciplinary organizations.
In the first year of the program, the details of this method were to be investigated by application to simple problems. This was accomplished as planned, but in addition, more complex problems were solved, and a parallel version of the system, run on a network of workstations, was successfully demonstrated.
This scheme was first successfully implemented using Rosenbrock's Valley Function as a test case. Separating the function into two discrete analyses the Collaborative scheme successfully found the optimum. Wood's problem and a more complex version of Rosenbrock's were also successfully implemented with collaborative optimization. An aircraft design problem was created using simple analytical equations to represent the three disciplines of aerodynamics, structures, and performance. With range as the objective function, this problem was executed using collaborative optimization and converged to a result obtained using a conventional problem formulation.
Several different versions of the aircraft design problem were successfully run and the system was then adapted to run in a distributed computing environment. Each discipline was assigned to a single workstation and the coordination maintained by file sharing over a local network.
Finally, the compatibility constraint approach and collaborative optimization were applied to a launch vehicle design problem, described in reference 4. The method is also being used to study trajectory problems for aircraft and spacecraft using a collocation method.
1. Kroo,I., Altus, S., Braun, B., Gage, P., and Sobieski, I., "Multidisciplinary Optimization Methods for Aircraft Preliminary Design," AIAA 94-2543, Sept. 1994.
2. Kroo, I. Gage, P., Altus, S., Bischoff, C., Hovland, P., " New Approaches To Multidisciplinary Optimization," NASA Workshop on Distributed Computing for Aerosciences Applications, Oct. 1993.
3. Gage, P., Kroo, I., Sobieski, I., "A Variable Complexity Genetic Algorithm for Topological Design," AIAA 94-4413, Sept. 1994.
4. Braun, R.D., Powell, R.W.; Lepsch; R.; Stanley, D.; and Kroo, I., "Multidisciplinary Optimization Strategies for Launch Vehicle Design," AIAA 94-4341, Sept. , 1994.
In addition, papers more specific to the decomposition tool, the collaborative optimization results, and experience with automatic differentiation in the MDO environment, are in progress.
The planned work for the second year of the grant was described in the original proposal, although because of the more rapid progress in implementation of the methods during the first year, more emphasis will be placed on the parallel implementation of the collaborative architecture. Specifically, the following topics will be addressed:
Decomposition and Optimization
A new distributed version of the MDO executive, GenIE, is being developed using more advanced communications protocols. Interaction with PVM and MPI is being investigated and a system definition and test will be completed by the end of the second year of work. One prototype version of the system currently works, although very inefficiently, and this will be revised in the next few months.
We will investigate means for dealing with analysis expansion (large numbers of intermediate results that limit decomposition). The usual approach involves some form of curve fitting, and this will be studied in a sample problem, making use of the flexibility of the compatibility constraint formulation. One unconventional possibility involves the use of intermediate basis functions, the representation of a more complete design space using linear combinations of previous results.
Work on the decomposition and planning tool, AGenDA, continues, with refinement of the current objective functions and derivation of others which may be useful for more complex problems. Additional test cases from other programs and from the literature will be analyzed using this tool. An easy-to-use version of the code will be released to NASA, universities, and industry in consultation with the technical monitor.
In addition to the subsonic aircraft synthesis program, the method will be applied to other test problems including an HSCT design problem, for which most of the analysis code has been completed. Results of the decomposed optimization problem will be compared with those of the conventional, monolithic architecture.
The most recent version of ADIFOR will be integrated into the existing executive and will be applied to decomposed design problems. The improved handling of sparsity will be studied in the context of compatibility constraints and modifications to the AGenDA objective to reflect the lower cost of sparse Jacobians.
The use of optimization algorithms that take advantage of the system sparsity will also be explored further. A version of NPSOL, especially adapted for sparse systems has been obtained and installed. This will be used in conjunction with the sparse ADIFOR on two test problems with differing degrees of sparsity.
Convergence and Formulation Details
We plan to investigate convergence of the method more formally and compare this with other multi-level systems that have been described in the literature. In particular, two features of the formulation have been discovered that cause potential difficulties for conventional system-level optimization methods. First, the system Jacobian is singular at the optimum, posing possible problems for the SQP method. We have begun investigating the use of Tensor methods for system level coordination as these are more appropriate for such cases. We are also pursuing a problem formulation that is not singular, but retains many of the desirable features of the original approach. The second difficulty is associated with problems that involve local minima and active constraint set switching in the subproblems. For such cases, it has been found that switching of the active set can lead the subspace optimizer to suddenly move from one local minimum to another, creating difficulties for the system level optimization. A formulation using equality constraints and slack variables avoids this problem and is currently being tested on several problems.
The collaborative optimization system will be applied to additional problems in the second year of the work. These will include trajectory problems, more complex subsonic aircraft preliminary design problems, and HSCT applications.