Genetic Algorithms - Part II
Following on from my introduction to the theory of Genetic Algorithms I will now discuss a very simple implementation of a GA written in PHP. While PHP is not a language one would ordinarily associate with Artificial Intelligence it is very useful for web design and for the purposes of this example is suitable.
As noted in part I our GA needs to have 3 elements to make it functional and the source code for the project reflects this:
Genetic Representation - Our representation will be an almost direct mapping of an 18 hex digit string into the three 6 digit hex coded colours that will make up our colour schemes. The source code contains the methods getRandomGenome(), which is used to create a random 18 digit hex string, and decodeGenome($genome), which decodes a genome into the 3 corresponding colours.
Selection - Since the selection is done by the user in this example there is no need to code anything for this particular part of the process.
Variation - For this example only the simplest methods of variation have been implemented. The mutate($genome) method provides a mutated version of the supplied genome via the typical 'point mutation' process. The crossover($genome) method provides a greater amount of variation via the process of asexual reproduction - in reality all this does is rearrange the 'genetic material' of the supplied genome and better results could be gained using a better method of crossover.
The programs flow of execution is quite simple and follows the following outline:
A working example of the Genetic Colour Chooser is available as well as the full PHP source code.
As noted in part I our GA needs to have 3 elements to make it functional and the source code for the project reflects this:
Genetic Representation - Our representation will be an almost direct mapping of an 18 hex digit string into the three 6 digit hex coded colours that will make up our colour schemes. The source code contains the methods getRandomGenome(), which is used to create a random 18 digit hex string, and decodeGenome($genome), which decodes a genome into the 3 corresponding colours.
Selection - Since the selection is done by the user in this example there is no need to code anything for this particular part of the process.
Variation - For this example only the simplest methods of variation have been implemented. The mutate($genome) method provides a mutated version of the supplied genome via the typical 'point mutation' process. The crossover($genome) method provides a greater amount of variation via the process of asexual reproduction - in reality all this does is rearrange the 'genetic material' of the supplied genome and better results could be gained using a better method of crossover.
The programs flow of execution is quite simple and follows the following outline:
- The page is loaded and a check is made to see if a genome has been passed via the URL (indicating the page has been loaded at least once) or not (indicating this is the first page view).
- If a genome has been passed then that is used as the basis for the new generation of colour schemes - if not then a random colour scheme genome is generated.
- A population of 8 variations is generated from the original genome using mutation.
- A random number of these variations are then chosen for further variation using crossover.
- The final task is to display the nine colour schemes (the original and 8 variations) on the page.
- The user selects a more suitable colour scheme and the page is reloaded with the corresponding genome passed as part of the URL.
A working example of the Genetic Colour Chooser is available as well as the full PHP source code.