GENETIC ALGORITHM
ABSTRACT:
This paper attempts to examine the way as how Genetic Algorithm (GA) can be employed in finding the best solution amongst a given number of possible solutions, the basic principle being extracted from the evolution and adaptation of organisms. The thought of Genetic Algorithm primarily originates from the perception of Charles Darwin who thought that combination of selection and variation is what that makes evolution of organisms perfectly adaptable to the environment. As generations pass, better adaptable organisms are born and the system slowly reaches to a most favorable point. GA makes use of this principle and eventually converges to the best “optimal” solution amongst a set of given solutions. In searching for a solution, a population of candidate is generated, evaluated, selected, and reproduced with modification to produce the candidate population until no further improvement can be made or after certain numbers of generations have generations have evolved, as according to the need of the problem.
KEYWORDS:
Evolution, Selection, Mutation, Crossover, Optimum, Adaptation, Fitness.
1. FOUNDATION IN SCIENCE:
As early as 1800, Charles Darwin thoughts on “evolution” and “survival” theory with the publication of “The Origin of Species” laid the groundwork for later developments; most notably, Darwin was also the one who proposed that all creatures, including humans were evolved from other creatures. Over time, creatures change to adapt to their environment to survive and thrive and those having a higher fitness, will survive longer and produce more offspring. This continues to happen and the individuals become more and more suited to their environment every generation. it was this constant improvement that inspired computer scientists, one of the most renowned being John Holland, writer of “Adaptation In Natural And Artificial Systems”, who presented the first ever seminal work in the field of Genetic Algorithms in 1975.
2.INTRODUCTION:
Genetic Algorithms are probabilistic search approach, which are founded on the ideas of evolutionary processes. The Genetic Algorithm procedure is based on Darwinian principle of the survival of the fittest. Genetic Algorithm makes use of the principles of selection and evolution to produce several solutions to a given problem. one must note that the underlying principle of Genetic Algorithm arises from the “evolution” theory only; it is the rigidity and flexibility of this principle which has made Genetic Algorithm so popular amongst optimization field and finding solution to real world problems. As against traditional methods, Genetic Algorithm are suited for many real world problems which involve finding optimal parameters. Not only does Genetic Algorithm provide an alternative method to solving problem, it consistently outperforms other traditional methods in most of the problems link. They do an excellent job of searching through a large and complex search space. Genetic Algorithms are more effective in finding “the optimum”, be it in a state-space search or in surfaces. Selection, Variation and Elimination are the three bricks upon which the whole structure of Genetic Algorithm is constructed.
3. WHO CAN BENEFIT FROM GENETIC ALGORITHM:
Genetic Algorithms are proven to be an enormously powerful and successful problem solving strategy, demonstrating the power of evolutionary principles. Moreover, the solutions they come up with are often more competent, more elegant, more complex as compared to other traditional problem solving techniques. Genetic Algorithm is beneficial to nearly everyone, once the correct mode of representation for the problem is chosen plus the relative fitness of solutions is compared correctly. Genetic Algorithm are useful and efficient when
1. The search space is large, complex or poorly understood.
2. Traditional non-linear search methods fail.
3. No mathematical analysis is available.
4. Fitness landscape is non-linear and changes over time.
5. Multi-modal or n-dimensional search space exists.
4.THE PRINCIPLE,THE ALGORITHM:
Genetic Algorithm is, in its true sense, associated with sexual reproduction in which the genes of two parents combine to form those of their children. When it is applied to problem solving, the basic logic is that we can create an initial population of individuals representing possible solutions to a problem we are trying to solve. Each of these individuals has an associated fitness measure (fitness function) that makes them more or less fit as members of the population. The most fit members will have a higher probability of mating than the less fit member, to produce offspring that have a significant chance of retaining the desirable characteristics of their parents. Therefore the algorithm identifies the individuals with the optimizing fitness values, and those with lower fitness will naturally get discarded from the population. Successive generations improve the fitness of individuals in the population until the optimal solution is met. Hence, the algorithm can be framed as…
1. Encode the problem in a binary string or an array of integers or decimal numbers.
2. Random generate the population representing a group of possible solutions.
3. Calculate the fitness value for each individual
5. METHODS OF REPRESENTATION:
Before employing Genetic Algorithms in finding solution to a problem, the problem (possible solutions) needs to be encoded in a computer recognizable form. There are many ways of representing the problem where each method has its own advantages and disadvantages, few of them being:
1. Encoding the problem in binary string i.e. sequences of 1’s and 0’s, where digit at each position makes up some part of the solution.
2. Encoding the problem in array of decimal numbers or integer numbers where again each digit represents some part of the solution.
3. Encoding the problem in array of strings. This method is used in “grammatical encoding” approach employed to generate neural networks.
4. Making use of “genetic programming” in which problem is represented in form of data structure known as tree.
6. GENETIC OPERATORS:
Genetic operators are applied to improve the performance of the population of behaviors. One cycle of testing all of the candidates is defined as a generation, and is repeated until a good behavior is then applied to the real world. The operators here are described with regard to the “evolution and adaptation” procedure i.e. parents are selected based on their fitness and they reproduce to create offspring which are better adapted to the next generation. The same concept is applied while dealing with extraction of a better solution amongst the given possible solution in the real world.
6.1) SELECTION
The selection procedure randomly selects individuals from current population for development of the next generation. Again, in the next generation the selected candidates are chosen for the next solution or cycle. Various types of selection procedures are available, from which any can be chosen as best suited to programmer, few of them being – Roulette-wheel selection, Generational selection, Hierarchical selection, Rank selection.
6.2) CROSSOVER
The crossover procedure involves combining two selected individuals about a crossover point thereby creating two new individuals which represent the next generation. In case of asexual reproduction, a single individual is replicated into the new population. There are many different kinds of crossover; the most common type is single point crossover. In single point crossover, the children take one section of the chromosome from each parent, thus inheriting good behavior from both each. Sometimes parents are copied directly to the new population when no crossover occurs. The probability of crossover occurring is usually 60% to 70%.
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
Row 3 indicates a new hybrid with crossover (single point) taking place between 4th and 5th positions in the chromosomes of its parents. Row 5 indicates mutation taking place at 5th position.(Here the problem is coated in strings of binary numbers 0’s and 1’s).
6.3) MUTATION
After selection and crossover, there’s a new population full of selected candidates representing next generation (a merely good solution).When no crossover occurs, individuals are copied directly and others are produced by crossover. In order to ensure that the individuals are not exactly the same, a provision for mutation is made. The mutation procedure randomly modifies the genes of an individual subject to a small mutation factor, introducing further randomness into the population. In other words, it periodically makes random changes in one or more members of the current population, yielding a new candidate solution. The probability of mutation is usually between 1 and 2 tenths of a percent. Mutation is important in ensuring genetic diversity within the population.
7. BREEDING EXAMPLE:
The fact that Genetic Algorithm makes use of only good characteristics of each parent based on the fitness in producing new offspring can be best illustrated with the help of a Breeding example.
Consider a Fitness function consisting of a single parameter that takes value between 0.0 and 4.0, and we select two individuals based on their fitness and combine them to get a better solution. Let suppose in a certain run, the numbers 3.273672 and 3.173294 are two selected candidates that now undergo single point crossover to ‘genetically’ in order to produce more stable and secure offspring (solution).
The steps are as follows:
-Encode the two numbers into binary strings.
-Randomly determining the crossover point.
-Swap the two tails ends of the binary strings.
-Recombine the two binary strings to get two new offspring.
-Decode the binary strings back into floating point numbers.
1) Encoding the two numbers into binary strings
Parent 1=3.273672 =>11.0100011000001
Parent 2=3.173294 =>11.0010110001011
2) Randomly choose a crossover point; let suppose be it at bit 6, and we split the gene at position six.
Parent 1=>3.273672=>11.010---0011000001
Parent 2=>3.173294=>11.001---0110001011
3) Swapping the two tails ends of binary strings.
Child 1=>11.010---0110001011
Child 2=>11.001---0011000001
4) Recombining the two binary strings to get two new offspring.
Child 1=>11.0100110001011
Child 2=>11.0010011000001
5) Decoding the binary strings back into floating point numbers.
Child 1=3.298218
Child 2=3.148560
The resulting offspring are close to, but not exact replicas of the two parents. We note that the first three bits were going to be the same (11.0), so that the offspring of these two parents would have to be between 3.0 and 3.5.In this way good genes are passed down from generation to generation, while bad genes are bred out of the population because the parents with bad genes are not often given chance to breed.
8. WHY GENETIC ALGORITHM???
Genetic Algorithms can identify and exploit regularities in the environment, and converges on solutions (can also be regarded as locating the local maxima) that were globally optimal. This method is very effective at finding optimal or near optimal solutions to a wide variety of problems, because it does not impose limitations required by traditional methods such as gradient search, random search etc. The Genetic Algorithm technique have advantages over traditional non-linear solution techniques that cannot always achieve an optimal solution. The method is very different from “classical” optimization algorithms-
a) It uses encoding of the parameters, not the parameters themselves.
b) The search is more exhaustive in a given amount of time.
c) Due to its probabilistic nature rather than deterministic, it yields “different solutions on different runs”.
d) Explores the solution space in multiple directions rather than in single direction.
9.0) APPLICATIONS:
Genetic Algorithm can primarily be employed for problem solving and for modeling. Its plasticity and efficiency of solving problems makes it a more favorite choice among the traditional methods, namely gradient search, random search and others. Genetic Algorithm have been widely studied, experimented and can be applied to many scientific and engineering problems, in business and entertainment, including:
9.1) ARTIFICIAL LIFE:
Genetic Algorithm the most widely and prominently used computational models of evolution in artificial-life systems. Researches on Genetic Algorithm in given illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems.
9.2) ARTIFICIAL NEURAL NETWORK APPLICATIONS:
Genetic Algorithm has been increasingly applied in ANN design in several ways; topology optimization, genetic training algorithms and control parameter optimization. In addition Genetic Algorithm have been used in many other innovative ways, for instance, creating new indicators based on existing ones, selecting good indicators and in complementing fuzzy logic.
9.3) INFORMATION SYSTEM APPLICATIONS:
Distributed computer network topologies are designed by a Genetic Algorithm, using three different objective functions to optimize network reliability parameters, namely diameter, average distance, and computer network reliability. The Genetic Algorithm has successfully designed networks with 100 order of nodes.
9.4) GENETIC ALGORITHM IN BUSINESS AND THEIR SUPPORTIVE ROLE IN DECISION MAKING:
Genetic Algorithms can be used to solve many different types of business problems in functional areas such as finance marketing, information systems, and production/operations. Within these functional areas, Genetic Algorithm can perform a variety of applications such as tactical asset allocation, job scheduling, machine-part grouping, and computer network design.
9.5)ASTRONOMY AND ASTROPHYSICS:
Genetic Algorithm are useful in solving 3 types of problems:
Fitting and rotation curve of a galaxy based on observed rotational velocities of its components, determining the pulsation period of a variable star based on time-series data, and solving for the critical parameters in a magneto hydrodynamic model of the solar wind.
9.6)MACHINE AND ROBOT LEARNING:
Genetic Algorithm can be used for many machine-learning applications, including classification and prediction, protein structure prediction. Genetic Algorithm have also been used to design neural networks, to evolve rules for learning classifier systems or symbolic production systems, and to design and control robots.
9.7)ECONOMIC AND FINANCIAL MARKETS:
Genetic Algorithm have been used to model processes of innovation, the development of binding strategies, and the emergence of economic markets. An investment firm California that manages over $2.2 billion uses Genetic Algorithm to make investment decisions for all their financial services. Genetic Algorithm can also be used to predict exchange rates of foreign currencies up to one month ahead.
9.8)MATHEMATICS AND ALGORITHMIC:
Genetic Algorithm can offer a great help in solving “pure” mathematical problems such as high-order nonlinear partial differential equations. They can also be used in “sorting network” which is a fixed list of comparisons performed on a set of a given size and each comparison; two elements are compared and swapped if not in order.
9.9) OPTIMIZATION:
Genetic Algorithm have been used in a wide variety of optimization tasks, including numerical optimization, and combinatorial optimization problems such as traveling salesman problem(TSP),circuit design, job shop scheduling and video and sound quality optimization.
In addition to these, Genetic Algorithms find their application Aerospace engineering, Geophysics, Military and law enforcement, Data Mining, Cryptography, Immune system models, Ecological models, Machine and robot learning and can be employed with more intensiveness in many other fields.
10.LIMITATIONS
Although because of its simplicity and classiness, Genetic Algorithm have proven themselves as efficient problem solving strategy, yet they cannot be considered as universal remedy. Some limitations do persist with them
1) The method chosen for representing the problem must be strong and firm, it must withstand random changes or otherwise we may not obtain the desired solution.
2) Fitness function must be chosen carefully. It should be able to evaluate correct fitness level of each candidate. If the fitness function is chosen poorly or defined vaguely, the Genetic Algorithm may be unable to find a solution to the problem, or may end up solving the wrong problem.
3) Genetic Algorithms do not work well when the population size is small and the rate of change is too high.
4) Another drawback of Genetic Algorithm is that solution is “better” only in comparison to other, presently known solutions; it cannot make out “the optimum solution” of its own.
5) Sometimes if an individual more fit than its associated competitors arrives before it should have, it abruptly decreases the size of population, leading the algorithm to converge on the local optimum without examining the rest of the search space. This problem is popularly known as “Premature Convergence”.
11.CONCLUSION AND FUTURE WORK:
The power of evolution has surely refined each and every step it has undergone in its way, and one cannot reject its usefulness in anyway because without it none of the immeasurable advances will be indebt to genetic algorithms would have been possible, and of course, the main driving force being Charles Darwin’s simple, powerful intellectual: that the random chance of variation, together with law of selection, is a problem solving technique of massive and limitless application. The algorithm is one of the best problem solving “tool” in the present scientific and commercial world.
Though its theoretical journey, as research continued to be productive, genetic algorithms soon jumped into the commercial sector. Today, Genetic Algorithm are related to “solving problems of everyday interest” in many diverse fields. Due to its intrinsic parallelism, the comprehensiveness with which this algorithm is applied in so many areas is no less than astounding. However, several improvements can be made in order that Genetic Algorithm could be more generally applicable. Future work will continue in process of building robotic system through evolution and many more specific tasks and as research is on going, we would surely witness some of the most flawless advancements in Genetic Algorithm application fields.
12.REFERENCES AND RESOURCES:
[1] Introduction to Genetic Algorithms
-Axcelis
[2] Functioning of a Genetic Algorithm
[3] Creating New Solutions through Mutation
Selecting Solutions via “Survival of the Fittest”
[4] GA White Paper
[5] Introduction to Bioinformatics,
by S. Sundararajan & R. Balaji
[6] Genetic algorithm Warehouse
No comments:
Post a Comment