Position Paper: AID'98 Evolutionary Design Workshop


Where's the Knowledge?
A Position Paper

It's clear from existing design-oriented work that GA's have a role in:

However, while it's possible that an expert could induce new knowledge from the design examples that a GA produced (e.g., common features of high performance designs), it's hard to imagine anyone learning about designing from using a GA. The GA approach is very algorithmic. At best one can view it as some kind of heuristic search.

So what connection is there between GAs and design? In particular, where's the design knowledge?

Some of the knowledge in the system is in the encoding used for each member of the population. The properties and features chosen for this representation affect the possible answers that can be reached, both due to what can actually be represented and to how crossovers can occur.

If constraints are used to prune `impossible' objects (e.g., rules or designs) before their fitness is evaluated, then knowledge resides there too.

But clearly the bulk of the knowledge -- the design knowledge -- is encoded in the method used to evaluate fitness. This is both a strength and a weakness.

The strength is that there is essentially a single place to locate design knowledge in a GA system, and, as long as a fitness is generated, its form and organization isn't of much importance.

The weakness is that building an effective fitness function is very hard, it's almost all the work, and it's probably the most important activity.

Building a fitness function is hard because, in general, evaluating a design is difficult, and it depends on many factors. There has to be some way of weighting these different factors so they can be combined, and these may reflect context sensitive tradeoffs between these factors.

A design has not only to meet the requirements given, but also to satisfy constraints, such as those concerning physical laws, or concerning professional standards/codes. Preferences based on experience should also be included, as well as practical issues such as resource availability or life-cycle costs. Goals such as `low cost' and `high strength' must be factored in too. This leads to a consideration of tradeoffs between all of these ingredients.

In order to generate good designs at all, all of these aspects have to be included. In essence, to use a GA approach to generate complete designs with any richness requires a sophisticated knowledge-based evaluation system embedded in the fitness function.

However, if all of this complex knowledge is compressed to a fitness value, it is essentially wasted. First, for example, a single value can't express the tradeoffs made, so there's no possibility of using that for any kind of guidance. Second, in an ``agenda based'' system for example, an entry might be made on the agenda with a value expressing its importance for further processing. However, that importance value can be calculated in a context dependent way from pieces of information attached to the entry. They provide an inspectable `rationale' for the value.

One possible approach to making use of all the knowledge we've discussed is to construct a `hybrid', a knowledge-based design system with GA features. For example, Campbell et al [1998] describe a such a system that does conceptual design.

Another possible improvement is to carry some rationale information along with the design representations. This has potential for inspection by the ``user'' of the GA-based system, and would help ``convince designers of the fact that an unpredictable, unexplainable, stochastic method is of use to them'' [Bentley 1998]. Accumulated rationale may be able to play a part in evaluation of fitness -- possibly with the involvement of the user (i.e., the designer). It does raise the interesting problem of how to integrate the rationale from the two designs that are involved in a crossover.

A final suggestion for improvement is that, as far as I know, GA research has spent little effort in addressing how to make crossovers in `realistic' design representations directly. This would allow tight integration with other computational design approaches. In addition, existing design evaluation systems could be applied directly to the design representation.


References

P. J. Bentley, Call for Papers, Evolutionary Design Workshop, AID'98, http://www.cs.ucl.ac.uk/staff/P.Bentley/AID98wksh.html

P. J. Bentley & J. P. Wakefield, The Table: An Illustration of Evolutionary Design using Genetic Algorithms. Proc. Conf. Genetic Algorithms in Engineering Systems: Innovations and Applications, IEE Conference Publication No. 414, Sept. 1995.

M. Campbell, J. Cagan & K. Kotovsky, A-Design: Theory and implementation of an adaptive, agent-based method of conceptual design, Proc. AI in Design conference, AID'98, Lisbon, Portugal.

M. Rosenman, The Generation of Form using an Evolutionary Approach, Artificial Intelligence in Design '96, (Eds.) J. S. Gero & F. Sudweeks, Kluwer Academic Publishers, 1996, pp. 643-662.

A. C. Thornton, Genetic Algorithm versus Simulated Annealing: Satisfaction of Large Sets of Algebraic Mechanical Design Constraints. Proc. Conf. Artificial Intelligence in Design, Switzerland, August 1994, pp. 15-18.


Biographical Information


Version: Wed May 13 21:37:52 EDT 1998