An application of genetic algorithms to a function allocation problem.

摘要

Genetic algorithms (GAs) are randomized search procedures that use the mechanics of natural selection rather than traditional heuristics in an attempt to “evolve” a solution. The main application of GAs are search problems (e.g. solving an equation) and optimization problems (e.g. job scheduling). This thesis examines the question of whether GAs are suitable for use in solving function allocation problems.; The LaHave House Project, an endeavor to create a semi-automated design system for houses, is used as a basis for the function allocation work. In house generation, an entire floor plan has been created, with rooms and sections clearly laid out, after which it must be determined what function each room will serve. There are billions of ways to allocate functions to the rooms, but only a relative few of those ways are architecturally reasonable (for example, the large double-height room in the middle of the house should never be made into a closet).; The main work of this thesis involved developing and testing a genetic algorithm method on the problem. During the earlier stages of designing the GA, many problems with flawed designs were encountered. Three fundamentally different approaches were tried, each substantially improving the quality of the generated designs over those of the previous one. In the final approach, over 99% of the generated designs were free of error.; Previously, a pure heuristic-based planning algorithm written in PROLOG was developed to perform the function allocation. This thesis compares the relative advantages and disadvantages between the GA method and goal based planning. Also discussed are the techniques used to develop and refine the GA method, as well as how they can be generalized to other GA applications, especially ones for solving design problems.