1 May 2016
In part I of this blog, we showed a simple simulation that modeled the airplane boarding process, and in part II we showed how this simulation model could be used to compare different boarding strategies. In this final installment we will examine a method for automatically designing effective boarding strategies.
While it is possible to manually design a series of boarding strategies and to compare their effectiveness through simulation, as we did in the last installment, it is also possible to automate the design process. In this case, the computer does the work of figuring out what the 'best' strategy should be. One method for doing this uses a technique known as an Evolutionary Algorithm, or EA.
EA's are used to find optimal configurations for complex systems, and are particularly useful in cases where the system's behavior is difficult to analyze or is difficutl to cast into a form where other more traditional techniques such as linear programming can be used. In an EA, the system configuration is encoded into a representation called a chromosome, which is essentailly just a list of numbers in which the values and order describe key features of the system of interest. In the case of our 6-
Organization of Boarding Strategy 'Chromosome'
One of the key features of an EA is that it works with not a single a single chromosome, but uses a population of different chromosomes. The intent is to mimic some of the features of natural evolution, specifically natural selection and mutation. when you use an EA to solve a problem, you are selectively breeding a solution to meet some desired characteristics, much as you might breed plants or animals.
An EA Requires a Population of Chromosomes with varying 'Fitness' Levels
To start off, an EA requires that an initial population be selected. This initial population is typically chosen to have random characteristics. In the case of this boarding problem we will build the initial population with differing 'random' boarding assignments. For this problem we will use a population comprising 50 member chromosomes.
After an initial population has been selected, the EA progresses by repetitively performing a series of steps. Each cycle through these steps results in a new generation of population. These steps are:
1) Evaluation -
2) Selection -
3) Reproduction -
These three steps are then repeated until the process ceases to provide significant improvements to the population's fitness level.
While the overall EA process is applicable to a wide range of optimization problems, the details needed to sucessfully adapt the EA technique to a given problem may vary greatly. For the boarding problem, since the boarding time is dependent on the actual seating order that occurs within each zone, so just simulating the order specified in the chromosome may not provide a particularly representative of how the boarding order performs over all conditions. To get a more accurate measurement of quality requires randomly shuffling the seats within each zone and performing multiple runs (in this case 25) to obtain an average boarding time over possible variations.
Evaluating the 'Fitness' of a Chromosome requires multiple simulations with intra-
Another detail that is specific to this problem is that of how to 'mutate' a chromosome. A mutation for this problem is implemented by swapping seats between different boarding zones. Additionally, between 0 and 10 mutations can occur when a chromosome reproduces -
To 'Mutate' a Chomosome Requires Exchanging Seats Between Different Boarding Zones
For this problem we ran the EA for 2000 generations. Below you can see a chart showing the both the fitness of the entire population (blue), and the fitness of the most fit member (red) over the different generations. Note that since better 'fitness' is defined as shorter boarding times, these lines go down over time. The improvement starts out fast from the initial random state, and tends toward better with suceeding generations. One reason the trend is not monotonic (continually decreasing) is that there is some uncertainty in fitness measurement. This uncertainty comes from the shuffle-
Convergence of the Average Population Fitness and that its Best Individual Chromosome
The final result of the above process is the 6-
Best Evolved Boarding Strategy 2000 generations -
One frequent characteristic of 'evolved' solutions is that they may not appear to make much sense. This is certainly the case here, as the solution appears pretty 'random'. Buried in it, however, are some islands of order. For example, the final boarding zone (6-