• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

Evolutionary Computing.

Extracts from this document...


Introduction I have been assigned the task of implementing an Evolutionary algorithm in order to resolve a time-shared ski lodge problem. The issue is to reduce the total cost (compensation) by satisfying the owners' choices and taking in consideration the parameters (number of flat, number of people) The project investigation is as follow: > Elaboration of a genetic algorithm suitable for this problem > Algorithm experimentation and parameters sensitiveness > Results evaluation and conclusion Notes: The programming language used is JAVA. To establish the Genetic algorithm, I have been working with Geraldine Sabbah (01006715), I have helped her for the programming as well. Table of content Introduction - 1 - Table of content - 2 - 1. The Evolutionary Cycle - 3 - 1.1 Initialisation of the population - 3 - 1.2 Tournament selection .- 3 - 1.3 Recombination - 3 - 1.4 Mutation - 4 - 1.5 Replacement - 4 - 2. Testing and Result interpretation - 5 - Conclusion - 10 - Bibliography Error! Bookmark not defined. 1. The Evolutionary Cycle 1.1 Initialisation of the population The population represents the parents or chromosomes, which are the owners numbers (64 numbers, 0-63) randomly taken and initialised (each number must appear once in the chromosome) The chromosome is an order of choosing the owners. this order is applied to an algorithm "Owner placement" that gives for each owner its first choice (if available), if not, try to ...read more.


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. 1.5 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. ...read more.


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. - 0 - ...read more.

The above preview is unformatted text

This student written piece of work is one of many that can be found in our AS and A Level Population & Settlement section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related AS and A Level Population & Settlement essays

  1. Data Interpretation (assignment 1)

    * Proceeds of crime Concealing, disguising, converting, transferring or removing property obtained through criminal activity (i.e. money laundering). * Abstracting electricity dishonestly using, wasting or diverting electricity, without authority. * Other theft or unauthorised taking Stealing not classified elsewhere. * Handling stolen goods dishonestly receiving or handling goods, knowing or believing them to be stolen.

  2. Part of the 'WhenI'm 64' investigation.

    The AIDS toll can be expected to double over the next decade since over 34 million people are now estimated to be living with HIV or AIDS, and around 5 million new infections occur annually. This is a tragedy for people as it effect them and people they know emotional and physically.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work