The Owner Placement algorithm takes in consideration the problem’s conditions; which are:
- Four flats are available for each week.
- No more than 22 people for each week.
As each owner will might have its week number, this will be used to establish the total cost of the chromosome (Evaluation).
Tournament selection
For the initial algorithm, we have taken the tournament selection size of three. It means that three parents randomly taken from the population will be taken and compared; the parent with the lowest cost will be used to create a child.
We need two successive tournaments to obtain two winner parents. These will be recombined to create a child.
Note: Redundancy can occur when tournament selection happens (a parent can be picked many times)
Recombination
Once the two parents are created, they are recombined to create the child.
The child must inherit from both parents’ genes, i.e. first gene (owner number) is taken from parent one, the second gene from parent two, and so forth. We have to take care by avoiding gene’s redundancy to obtain a valid chromosome.
Once the child created, the “Owner Placement” algorithm is applied to it in order to assign each owner a week and to evaluate the child’s cost.
At this level of the programme, we can call it a recombined child (not a final offspring)
Mutation
Once the child created and evaluated, we will consider the week attribution for the mutation. it will be affected by the several mutations described as follow:
This is applied for each owner’s week, i.e. owner 32 with week 9 will generate 63 possibilities (9 with 6, 9 with 4…9 with 2) and so on without repeating the weeks already swapped. If the swapping is valid (number of people and number of flat still valid), the result will be evaluated and kept for further comparison.
At the end, we compare every result, keep the fittest one, and compare it again with the recombined child (to be sure that the child that will go into the population is better or equal than the “recombined child”. The fittest one will go to the population through the replacement.
Replacement
Find the worst individual from the population, compare this one with the offspring, if the child is better, it will replace it in the population, its week attribution is also kept, whereas the worst will be removed; and the loop is over.
These different successive steps will last until the generation limit is reached, before this, the population will get better and better through the loops.
Generation, population size and tournament selection size have an important influence on the result. In the next part, we will investigate the sensitiveness and the impact of these values on the result.
The evolutionary cycle can be represented as follow:
2. Testing and Result interpretation
For testing the software, we ran it several times for each given problem. To find out the influence of the parameters on our algorithm, we tested them one by one. To see exactly what a parameter’s variation does, we changed them one at time in each evaluation:
- Generation size
- Population size
- Tournament selection size
- Seed number
2.1 Setting parameters results
For the Generation size test, the parameters were fixed as follow:
Population size: 500
The Tournament size: 3
Seed number: the number given in the problem
Interpretation:
We notice that the cost decreases with the generation size, more we recombine and mutate a population and better is the result. We also notice that the cost becomes stable between 8 000 and 10 000, this may explain the limit of recombination and mutation, and similarity of the population.
The problems with a big number of people (problems: 01, 04, 10) have the worst results; in fact the total number of people in a problem has an effect on the result certainly regarding to the family size. This could lead us to think about an algorithm that would place the big families first, that might reduce the total cost.
For the Population size test, the parameters were fixed as follow:
Generation size: 1000
Tournament size: 3
Seed number: the number given in the problem
Interpretation:
Increasing the population size might relatively decrease the cost; as the population is bigger, we increase the chance to obtain a good result and a bad result at same time, with that, we have more possibilities of recombination and mutation. However, we have noticed that the population size is in a certain way linked to the generation size, and we will demonstrate it in another further test.
For the Tournament size test, the parameters were fixed as follow:
Generation size: 50
Population size: 100
Seed number: the number given in the problem
Interpretation:
We notice that changing the tournament has consequences on results. It can be either good or bad whether the problem given. It is up to us to set this parameter for each problem and find out the best value.
For the test of two parameters (Population and Generation size, test above), we have initialised:
The tournament size: 3
The seed number used in the last tests.
Interpretation:
This was an interesting and a useful test, since we noted an improvement of the results when we took a population size of 1000 and a generation size of 10000. In fact, we have a big initialised population which increases the chance to get a low cost; applying several recombinations and mutations decreases relatively the cost. But in our algorithm, at a certain point, we have noticed a stagnation of the results i.e. the population becomes similar; this is when there are no more recombination and mutation possibilities.
Seed variation
We notice that varying the seed number has a consequence on the result, there is no rule about setting a seed number for a problem, it is up to us to find the best one by running the programme using different values.
Conclusion
Throughout this project we implemented a Genetic Algorithm to solve a given problem; nevertheless, the algorithm can be improved in order to obtain better results as follow:
- Implementing another algorithm to give each owner a week.
- Using another recombination method, and obtain two children from it instead of one.
- Using another mutation method. Mutate each child came up from the recombination.
- Using crossover and mutation rates.
My personal conclusion about setting parameters in an Evolutionary algorithm, is that there is no best specific setting for a genetic algorithm, we have to test and run the programme, investigate and analyse the results, and focus the setting on the best results parameters.