In my previous article Genetic Algorithms Demystified, I have explained the fundamental concepts of genetic algorithms. We are now ready to explore the design and implementation of a genetic algorithms project to optimize a load distribution problem. The project is code named GALoadDistriMiser. The demo project which was written and compiled in Java is available for download and test run only.
The project is about the optimization of load distribution of 64 packages on a vessel. It is assumed that the holding space for the packages is divided into 64 rectangular spaces (Figure 1).
Figure 1 - Stacks of packages
The problem requirements state that
- The distribution of the weights of the packages should be more or less uniform.
- It is also necessary to ensure that the lighter packages are placed on top of the heavier ones.
Translate these into genetic algorithms objectives, we have:
- Optimize weight distribution horizontally to balance the vessel.
- Optimize weight distribution vertically to maintain low center of gravity.
To make the case study even more challenging, I have added two more requirements:
- Optimize unloading operation at each port of call. i.e. the activities of unloading and loading of obstructing packages have to be minimized at each port.
- Meeting as much as possible objectives 1 and 2 after unloading at each port of call so that no unnecessary reshuffling is needed. (Assuming no loading of new packages at each destination port.)
The following information are provided:
- Package IDs.
- Weights of the 64 packages.
- Location IDs.
The GALoadDistriMiser problem is represented in a model in Figure 2.
Figure 2 - Problem Model
- In the phenotypic space (i.e. the physical world), the candidate solutions are manifested as different configurations of stacks of 64 packages.
- In the genotypic space (i.e. the genetic algorithms space), each candidate solution is represented as a chromosome of 64 genes identified by package IDs.
- The Java program will evolve candidate solutions by permutating the 64 package IDs.
- The found optimal solution is then mapped back to the phenotypic space.
To evaluate the quality of each candidate solution (chromosome) in meeting the four optimization objectives, I have to devise four different evaluation functions for each objective. The overall fitness is the sum of these four evaluation functions. Here, the smaller the overall fitness values the better the solution.
- Fitness function for evaluating objective 1:
- Calculate the sum of the average weight deviation of each vertical stack (four packages per stack) from the overall average weight of the 64 packages,
- F0 = ∑(average weight of each stack of 4 packages - average weight of all 64 packages)
- Fitness function for evaluating objective 2:
Two options are available:
- Impose penalty when a heavier package is placed above a lighter one, PENALTY_WEIGHT += 1; or
- Implement repair method to sort packages in each stack so that the packages are arranged in weight-ascending order from top down. If this option is chosen,then PENALTY_WEIGHT = 0.
- Fitness Function for evaluating objective 3:
- Impose penalty when a package due for later port is placed above one due for earlier port, PENALTY_PORT += 1.
- Fitness Function for evaluating objective 4:
- After unloading at each port, calculate the sum of the average weight deviation of each stack from the overall average weight of the remaining packages,
- At the nth port, Fn = ∑(average weight of each stack - average weight of remaining packages).
Finally, the fitness of a candidate solution is: F0 + PENALTY_WEIGHT + PENALTY_PORT + ∑(Fn) => the smaller the value the better.
Linear Rank Selection method was used to select the parents for reproduction. It goes like this:
- Each chromosome in the population is ranked in increasing order of fitness from 1 to N, where N is the population size, assume Ri is the ranking for the ith chromosome.
- Each chromosome is assigned a new fitness value using the cumulative relative fitness function qi = ∑1..i i, where i = (N - Ri + 1).
- Generate a random number r between 1 and N.
- If r is less than q1 then select the first chromosome, otherwise select the ith chromosome where qi-1 < r < qi.
Order Crossover operator was used to breed offspring from two parent chromosomes. The following example illustrates the algorithm:
- Select two parent chromosomes P1 and P2, each with two cut-points |
- P1: (J K L | M N O | Z Q R)
- P2: (Q J N | L K Z | R M O)
- Create a premature child C1 by copying the elements from P1's mid-section:
- C1: (_ _ _ | M N O | _ _ _)
- From here onwards, only consider P2. Consider the elements from the second cut_point of P2, i.e. R M O. Only copy R to C1 as M and O already exists in C1.
- C1: (_ _ _ | M N O | R _ _)
- Consider P2 from the start, and copy those elements that are not already in C1 to fill out the vacancies after R in C1.
- C1: (_ _ _ | M N O | R Q J)
- Consider P2 from the start, and copy those elements that are not already in C1 to fill out the vacancies from the start of C1.
- C1: (L K Z | M N O | R Q J)
- Child 1 has been delivered.
- The second child can similarly be bred by switching the roles of P1 and P2.
Order crossover operator creates children that preserve the order and position of elements inherited from one parent. It also preserves the relative order of the remaining elements inherited from the second parent.
The optimization process of the GALoadDistriMiser was designed and coded according to the following scheme:
INITIALISE random population with following parameters
POPULATION SIZE (N)
CROSSOVER RATE (CR)
MUTATION RATE (MR)
NUMBER OF EVOLUTIONS (STOPPING CRITERION)
EVALUATE each candidate based on its fitness value;
DO WHILE (STOPPING CRITERION is not met)
IF (ADAPTIVE GA option is selected and best fitness value remains the same for 10,000 generation)
CR = CR * 1.10 (CR capped at 0.7)
MR = MR * 1.10 (MR capped at 0.1)
IF (REPAIR CENTRE OF GRAVITY option is selected)
SORT each stack so that heavier packages are placed below the lighter ones
1 SELECT 2 parents randomly based on Linear Rank Selection method;
2 Generate a random number c, if c < CR, THEN breed 2 offspring from these 2 parents using Order Crossover operator ELSE the 2 parents just move over to the intermediate population;
3 For each member in the intermediate population, generate a random number m, if m < MR, MUTATE this member by randomly swapping 2 genes;
4 IF size of intermediate population < initial population GOTO 1
5 EVALUATE all offspring in the intermediate population;
6 REPLACE the worst offspring with the best solution found so far;
7 COMPLETE the forming of a new generation;
I have conducted many runs of GALoadDistriMiser under different parameter settings and options in an effort to understand the behaviour and performance of genetic algorithms. Some results are capture in Figure 3.
Figure 3 - Performance of GALoadDistriMiser
The main observations are as follows:
- Genetic algorithms evolution process will never follow a fixed path for each re-run because of stochastic nature. However, every well-designed genetic algorithms model will behave identically; they generally improve faster at the initial stage when population diversity is wide spread, but gradually slow down and become sluggish at the later stage when the population is dominated by near homogeneous individuals.
- Owing to the multi-modal and non-continuity of the search space, a better solution could just be next to an infeasible one. So repairing an infeasible solution, if possible, could lead to the discovery of the next best solution, and thus reducing the search effort.
- Static configuration of genetic algorithms parameters that may work very well at the initial stage of evolution will generally be of little use when the population reaches a certain local optimum. This results in genetic algorithms hitting a bottleneck situation after some time. One way to enable the genetic algorithms to break out of the local optimum and explore new search space is to allow genetic algorithms to change the control parameters dynamically based on some criteria. One of these could be to increase the crossover and mutation rates when there is no significant improvement in fitness value over say 10000 generations.
GALoadDistriMiser was developed in Java and integrated with the following components (Figure 4):
- JGAP (Java Genetic Algorithm Package) was included as the genetic algorithms library
- Java Swing provides the GUI for user interaction and monitoring of the genetic algorithms progress;
- MS Access was used for storing genetic algorithms parameters and solutions;
- MS Excel, which links to MS Access, is the excellent and powerful tool for viewing the evolution log and solutions (based on the raw data, one can chart graphs and diagrams in Excel easily).
Figure 4 - System Schema of GALoadDistriMiser
About the Demo
Download the demo project that accompanied this article to a Windows computer, unzip it and read the user manual for details on setting up and test running. Alternatively, you may wish to just take a look at the video clip of how GALoadDistriMiser works by clicking on the cover image at the beginning of this article.
First edition: 11 January 2014