A comprehensive program for solving QAP using a hybrid genetic algorithm with many optional improvements.

This program applies Ring Moves [1], and allows for the following improvements:

  1. Parent selection using the distance criterion [2].

  2. Using gender in parents selection [3].

  3. Using the Scatter approach (ESH) in selecting the population member to be removed from the population [4].

The parent selection using the distance criterion is controlled by the variable "many". One parent is randomly selected and "many" parents are selected as candidates for the second parent. The candidate farthest from the first parent is selected as the second parent. To ignore this option use many=1. Complete details are given in [2].

In the gender option each population member is assigned a gender (male or female) and the selected parents must be one male and one female. The offspring is randomly assigned a gender with 50% chance of being a male and 50% chance of being a female. To ignore this option select gender=0. For complete details see [3].

In the scatter approach we define a parameter "p" between 0 and 1. In the "standard" approach the worst population member is discarded when a new member joins the population. In the ESH approach the worst population member is discarded with probability of 1-p, and with probability p the following rule applies:

  1. Check all pairs of population members and find the pair(s) which are closest to one another. The closest two members are at distance "min" from one another.

  2. Create a list of all population members in the union of all these pair members. The list contains all population members that are at distance "min" from another population member.

  3. Select the population member in this list with the worst value of the objective function for removal.

To run the program you need to set the following parameters (in addition to the data file):

  1. The number of runs for each problem.

  2. Population size (100 is recommended).

  3. The parameter "many" for the distance option (many=1 is equivalent to not using this option).

  4. The gender (0 no use of gender, 1 use of gender).

  5. Number of levels for the ring moves [1]. I recommend 10 levels.

  6. The random seed (a positive number, such as "3").

  7. The factor. The number of generations is automatically calculated depending on n and the population size as G=max{50,n}*pop/5. If you wish to run a different number of generations , the "standard" number of generations, G,  is multiplied by "factor". factor=1 is the standard number of generations.

  8. Ratio is the value of p used in ESH. ratio=0 is the standard approach.

  9. fact2 is also multiplied by the standard number of generations and produces intermediate results. For example Factor=2 and fact2=0.5 will produce four values of the objective function recorded  after 0.5G, G, 1.5G, and 2G generations. The total run times (for all runs) at each step is also part of the output.

References

[1] Drezner Z. "Extended Concentric Tabu for the Quadratic Assignment Problem," European Journal of Operational Research, in press.

[2] Drezner Z. and G.A. Marcoulides (2003) "A Distance-Based Selection of Parents in Genetic Algorithms" in Metaheuristics: Computer Decision-Making, in Mauricio G. C. Resende and Jorge P. de Sousa, (Eds.), Kluwer Academic Publishers.

[3] Drezner Z. and T. Drezner "Gender Specific genetic Algorithms," under review.

[4] Drezner Z. "The Evolutionary-Scatter-Hybrid (ESH) Search," in preparation.