Design problems can be classified into two types based on the problem specification and expected results. Preliminary or conceptual design deals with structuring a design problem and reducing it to a form suitable for detailed design. Configuration design is an example of a preliminary design problem and as such, has to cope with uncertain and missing information as well as system complexity brought on by the large number of components and their possible interactions. Its ill-structured nature leads to a lack of rigorous and/or effective design methods for attacking this problem. Artificial intelligence techniques typically cast such ill-structured problems as search problems in a large state space of possible solutions. Since genetic algorithms were designed to effectively search large, poorly-understood spaces, we use them as the search method of choice for this research.
When considering configuration design as a search problem, the number of possible solutions is usually too large for exhaustive search. Knowledge-based systems rely on expert or experiential knowledge to narrow the search space to a manageable size. Examples of such systems can be found in [Tong and Sriram, 1992]. This approach works well in areas where such knowledge is encodable, but there are two disadvantages: 1) it is often difficult to extract and encode relevant design knowledge and 2) knowledge applicable in one domain may not be applicable in another domain.
Optimization techniques work well for well-understood problems [Radford and Gero, 1988]. However, many problems are not well-understood and may not meet the preconditions necessary for the application of mathematical techniques. In addition, the problem size may be so large that the time taken to find a solution is not practical.
Genetic algorithms (GAs) are stochastic, parallel search algorithms based on the mechanics of natural selection, the process of evolution [Holland, 1975]. GAs were designed to efficiently search large, non-linear, poorly-understood search spaces where expert knowledge is scarce or difficult to encode and where traditional optimization techniques fail. They are flexible (not brittle) and robust, exhibiting the adaptiveness and graceful degradation of biological systems. As such, GAs appear well suited for searching the large, poorly-understood spaces that arise in design problems.
We seek to combine some of the speed and accuracy of knowledge based systems with the robustness and flexibility of genetic algorithm search by incorporating domain knowledge in a genetic algorithm
We chose the structural design and optimization of trusses as the application domain for three reasons. First, truss design involves the determination of the topology and geometry of a truss system as well as the properties of the truss members. Second, the structure of a truss only consists of axially loaded truss members with the major property of truss members being their cross sectional areas. Thus, truss design has the essential characteristics of a complex system while being simple enough to allow an understanding of both the interactions of different design elements and the effectiveness of the methodology. We use a genetic algorithm augmented with engineering heuristics to design the topology, geometry, and member properties of trusses while minimizing the weight and maintaining feasibility. The third and last reason was that we could use a finite element analysis program to provide the feedback required by the GA.
The next section provides a brief introduction to search in design problems and the use of domain knowledge. Section 3 describes genetic algorithms and truss design. Section 5 describes our representation, encoding of domain knowledge, and the effect of genetic operators on candidate designs. Initial results reported in Section 6 suggest that genetic algorithms can be used in system configuration problems to provide feasible and useful designs. The last section discusses the results and suggests questions for future research.