Advanced Computational Technologies

Case Study 6 : Evolutionary Computation and Ant Colony Hybrid for the Preliminary Airframe and Flight Trajectory Design

Constraints relating to those parameter values returned from a mathematical model that have to satisfy a range of equality and inequality are commonplace across design and decision-making problems. When utilizing evolutionary computation it is possible to eliminate such constraints through the introduction of penalty functions or alternative strategies when dealing with constraints within an evolutionary search framework:

Elimination of all infeasible solutions - sudden death

Partial elimination - assign low fitness to infeasible solutions so that such solutions become extinct over a number of generations

Variable penalty function - solution fitness is penalized in proportion to the degree of constraint violation

Dynamic penalty functions - penalty functions are slight in early generations but increase in severity as the generations progress

The following case study relates to work carried out for BAE Systems (Warton) investigating the preliminary air-frame design and definition of flight trajectory for an air-launched winged vehicle that achieves orbit before returning to atmosphere for a conventional landing. The problem is extremely sensitive to five implicit non-linear constraints relating to air-speed, climb angle, and physical parameters describing the air-frame and engine configuration. The task was to minimize the empty weight of the vehicle.

BAE Systems had experienced little success in identifying feasible solutions when searching this heavily constrained solution space with conventional optimization algorithms. We had the same problem during preliminary experimentation using an EC algorithm which attempted to minimize the degree of constraint violation of trial solutions. Although solutions exhibiting minimum constraint violation could be identified using this approach we could not locate feasible regions of the problem space. A two-stage search was therefore introduced where an exploratory Genetic Algorithm (GA) first identified regions of the problem space where constraint violation was minimal. These regions were well-distributed around the solution space. Instances of an Ant Colony (AC) algorithm were then commenced from the low-violation points identified by the GA. The AC algorithm models the foraging activities of ants where high-performance solutions within a problem space are considered analogous to a food source. Multiple software ‘ants’ then move into the high-performance areas and perform a fine-grained, highly non-linear and localised search. In each case the Ant Colony search processes accessed regions of feasibility and returned optimal feasible solutions.

	Fig 1: GA search for minimum constraint violation relating to design of space vehicles. The degree of constraint violation is significantly reduced but the GA alone cannot identify feasible regions of the heavily constrained space.
	Fig 2: A secondary ant colony algorithm search has been initiated from points of least constraint violation identified by the GA. Localised search characteristics of the Ant Colony manage to access feasible space and identify optimal feasible solutions.

This case study again illustrates the manner various search and optimization algorithms can be combined to overcome complexities in terms of multiple variables, constraints and conflicting objectives.