Genetic Algorithms

Genetic Algorithms

Description

Genetic algorithms "represent a powerful and robust approach for developing heuristics for large-scale combinatorial optimisation problems" (The contribution of neural networks and genetic algorithms to business decision support-Academic myth or practical solution. Metaxiotis, Kostas & Psarras, John) This means that a genetic algorithm is a process that follows a set of instructions or parameters set and repeats itself until they find the more adequate, optimum solution. Nonetheless the process of doing so is much more complex.

The invention of Genetic Algorithms is attributed to John Holland, a professor at the University of Michigan. Nonetheless he had assistant from his colleagues and students at the university. The first investigations on the matters were carried away in the 1960s; it was not until 1975 were John Holland published the findings in the book Holland J.H., Adaptation in natural and artificial system, Ann Arbor, The University of Michigan Press, 1975. It has been suggested that J. Holland had two basic aims when developing this: "to improve the understanding of natural adaptation process and to design artificial systems having properties similar to natural systems" (Goldberg, David Genetic Algorithms, Addison Wesley, 1988.) The findings provided "the basic tools for the fabrication of reliable, robust, self-guided software codes" (Nuziale, Tony & Vagenas, Nick Genetic algorithms for reliability assessment of mining equipment) Genetic algorithms therefore represent a set of algorithms that follow the principles of natural selection. Thus it can be said that the fundamental idea behind Genetic Algorithms is the same idea behind Charles Darwin theory of evolution, survival of the fittest. Hence, before running the algorithms the definition of certain terms must be defined since they simulate certain biological aspects of the theory of evolution (for this please refer to Appendix 1). So the process of developing the fittest solution goes as follow at the beginning it is necessary to develop a set of solutions, which can be called a random population of chromosomes, the latter are usually made up of bit strings, real numbers amongst others. It is followed by an evaluation of the fitness of each chromosome in the population. The creation of a new population follows and the steps taken to find that new population is what makes this method so effective in finding an optimum solution. Obviously the first step is selection of two parents chromosomes and the one's that are the fittest have the biggest chance of being chosen. The following two steps Crossover and Selection make the method "effective because he not only considered the role of mutation (mutations improve very seldom the algorithms), but he also utilized genetic recombination, (crossover): these recombination, the crossover of partial solutions greatly improve the capability of the algorithm to approach, and eventually find, the optimum. (Emmeche C., Garden in the Machine. The Emerging Science of Artificial Life, Princeton University Press, 1994, pp. 114 ss) Thus once the optimum combination is found, the next process is to accept the offspring in the new population. These same steps will be repeated until the optimum population is generated according to the conditions given.

Benefits

The using of genetic provides several benefits, certainly one of them is that it is not too difficult to understand as long as the algorithm used is understood, the end product is something is expected as hence does not create much confusion. Since, the algorithm can constantly repeat itself over and over again not only there are several answers, but answers tend to get better with time, therefore achieving the optimum solution. Furthermore looking into the fact that there are several answers available this helps provide better customer service since the customers are able to choose the answer they think it's the best or more suitable for their needs. Also, the different solutions always provide the same/similar operating costs so; it avoids the customer taking into consideration a cost-benefit analysis of each and every one of the solutions. It is also worthwhile taking into consideration the cost savings achieved by using Genetic Algorithms, one of the most important is, the reduction in time. It would take much longer for someone to solve mathematically or work out the optimization of certain functions than it takes if it is done by a computer. Moreover, probably if someone tries to do so they will probably need more than one person in charge, which will result in more costs in the form of wages. It also saves time in the fact that unless there is a system failure, which is extremely rare it will provide flawless and errorless solutions. There are other important benefits raising from using genetic algorithms rather than "conventional mathematical models including: simplicity of randomized searches while retaining important historial information with the population; computational simplicity; GAs (Genetic Algorithms) search from a population of solutions, not just from a single solution; and they can handle any kind of objective function linear or non-linear constraints defined in discrete, continuous or mixed search spaces" (Nuziale, Tony & Vagenas, Nick Genetic algorithms for reliability assessment of mining equipment) Another important consideration is the fact that genetic algorithms are intrinsically parallel. Therefore as Genetic Algorithms have "multiple offspring, they can explore the solution space in multiple directions at once. If one path turns out to be a dead end, they can easily eliminate it and continue work on more promising avenues, giving them a greater chance each run of finding the optimal solution."(Marzcyk, Adam Genetic Algorithms and Evolutionary Computation www.talkorigins.org, 2004) Another important benefit is that when the algorithm start running there are all based on no previous knowledge, so they start randomly. Hence, they are going to look for all the possible paths to get their solutions.

Limitations

Genetic algorithms do have some drawbacks, especially when setting the parameters that need to be met to generate the necessary solutions required by those using the algorithm. Sometimes there are problems when doing so and sometimes it is said that the algorithms "cheat", however what actually happens is that the instructions set are not adequate. Therefore, the algorithm just follows the wrong instructions and gives out the wrong solutions for the client/customer, although it has not malfunctioned. It is important