-
Notifications
You must be signed in to change notification settings - Fork 0
Research project
The representation of individuals in the memory influences the speed and the convergence of the algorithm. In nature, various genes are encoded differently. We can find useless genes, repeated sequences, etc. In this project we consider a binary representation and analyse the impact of adding different kind of redundancies.
The study will try to optimize a Facility Location Problem with metric distances.
Several instances, randomly generated, will be analysed. Customers and facilities will have a random 2D position in the square [0,1]×[0,1]. The probability law may vary from one instance to the other. Two laws have been used : a uniform law and a flawed uniform law. In this second law, the square is divised into 9 parts (9 identical squares). Each square has a proper probability to be selected, and then the position is choosen uniformly within the square.
The delivery cost is the euclidean distance between the facility and the customer. The opening cost of each facility is picked up between 10 and 20 after an uniform law. The cost of the result seems to naturally equilibrate between delivery and openning cost whatever the basic costs are. So this law of openning costs had been fixed arbitrally.
In the algorithm, a solution is represented as an array of boolean which size is the number of facility. Each item in this array is true if the facility associated is openned, and false otherwise. Each facility has its boolean in the array, but nothing dictate the order of facilities.
A variant is also used where the order is managed to reflect the proximity of facilities on the map into the proximity of associated booleans in the array.
Therefore, instances are differenciated by their number of customer and facility, and whether or not they are ordered.
- 10, 100
- 10, 100, ordered
- 20, 200
- 20, 200, ordered
- 50, 500
- 50, 500, ordered
- 100, 1000
- 100, 1000, ordered
The choosen selection method is elitism : a given percentage of best individuals of the population are kept in the new population. For the sake of the diversity in this project, the rate is set at 5%, even if higher rates gives faster results with the Facility Location Problem.
Random individuals from the initial population, called parents (before the selection) are mixed after the following process: the index of a cut is uniformally choosen in the array (representing an individual), each parents are cut at this index and finally the first part of the first parent is concatened to the second part of the second parent to form a new individual.
One could imagine to use not only one, but many cuts. This doesn't look to modify the performances of the algorithm, neither in good or in bad. So the classical one-cut have been choosen.
Each individual generated after a crossover is mutated before being add to the new population. Each value of the array representing the individual is flipped with a fixed probability. The best value for this probability have been empirically found to be 1/N where N is the size of the array. This value represent an average of 1 value flipped per individual.
The first redundancy is to add unused bits in the representation. Theses bits are contiguously inserted at a fixed position.
The execution of the genetic algorithm will last 1 second for every instances. In order to have reliable statistics about the evolution, these executions will be repeated a hundred times.
The best score will be tracked during the execution. The result of an algorithm (solving of a given instance with a given redundancy method) is summarized with a mean curve through the time of execution. The standard deviation is also computed in order to decide if there are significative differences in algorithms.