I have been busy for the past few months and it reflects on the time
it took to bring out another post on my very beloved blog. Since getting
admitted to post-graduate studies I have been fascinated by
non-deterministic algorithms that are used to solve NP hard problems
with reasonable accuracy. The branch of study I am referring to is known
as "Soft-Computing".
There are various such algorithms that are based on the natural actions or inspired from nature. Some examples are Genetic Algorithms, Artificial Neural Networks, Fuzzy Logic, et cetera. What is so fascinating about this branch is that non-determinism and confusion are the concepts that determine the solution! When I say determine the solution I never mean to imply it finds out the exact solution always, it does not. These computations will find out the approximate results that are good enough for humans to understand and apply.
Let me try to elaborate each of these wonderful concepts to the best I can. In this part I shall be elaborating on Genetic algorithms.
These are algorithms that mimic the natural evolutionary mechanism among genes. Darwins "Survival of the Fitness" is the mantra used in this class of algorithms. The basic structure goes like this-
||
\/
||
\/
||
\/
The initial population of genes is generally randomly generated with a seed that can be reused so that the same results can be reproduced. The fitness value is a value generated by a function that determines the goodness of a gene.
In real life problems, genes are nothing but solutions to a problem. The solutions are then coded as a gene that can then be evaluated with the help of a fitness function.
When do we reach a termination condition? It depends on the implementation. Genetic Algorithms are known to converge some time which means that the average fitness of the population will be equal to the maximal fitness value of the pool and the minimal as well. The implementation can write an infinite loop for this or he might as well limit the number of generations to a pre-defined value. Playing God has its' advantages after all!
The internal details of the algorithms are all flexible and have no hard and fast rules. The wiki page on Genetic Algorithm can present you with a lot more. Selection can be performed in various fashions, the Roulette Wheel Selection, Tournament Selection are articles that you might want to look up if you want to implement such a solution.
In the above model we find two user defined constants Pcrossover and Pmutation. Pcrossover is generally large and Pmutation is generally very small.
So, you get to play God! You define your genes and watch them evolve or grow just as you wish. However this chaos bring in another aspect that we never thought bring : beauty and peace.
There are various such algorithms that are based on the natural actions or inspired from nature. Some examples are Genetic Algorithms, Artificial Neural Networks, Fuzzy Logic, et cetera. What is so fascinating about this branch is that non-determinism and confusion are the concepts that determine the solution! When I say determine the solution I never mean to imply it finds out the exact solution always, it does not. These computations will find out the approximate results that are good enough for humans to understand and apply.
Let me try to elaborate each of these wonderful concepts to the best I can. In this part I shall be elaborating on Genetic algorithms.
These are algorithms that mimic the natural evolutionary mechanism among genes. Darwins "Survival of the Fitness" is the mantra used in this class of algorithms. The basic structure goes like this-
| Select the best fittest from a pool of genes |
\/
| Perform crossover among genes (mating) with Probability Pcrossover |
\/
| Mutation in the pool of genes may occur with Probability Pmutation |
\/
| If we have not reached termination condition, we restart from beginning with the new pool of genes |
The initial population of genes is generally randomly generated with a seed that can be reused so that the same results can be reproduced. The fitness value is a value generated by a function that determines the goodness of a gene.
In real life problems, genes are nothing but solutions to a problem. The solutions are then coded as a gene that can then be evaluated with the help of a fitness function.
When do we reach a termination condition? It depends on the implementation. Genetic Algorithms are known to converge some time which means that the average fitness of the population will be equal to the maximal fitness value of the pool and the minimal as well. The implementation can write an infinite loop for this or he might as well limit the number of generations to a pre-defined value. Playing God has its' advantages after all!
The internal details of the algorithms are all flexible and have no hard and fast rules. The wiki page on Genetic Algorithm can present you with a lot more. Selection can be performed in various fashions, the Roulette Wheel Selection, Tournament Selection are articles that you might want to look up if you want to implement such a solution.
In the above model we find two user defined constants Pcrossover and Pmutation. Pcrossover is generally large and Pmutation is generally very small.
So, you get to play God! You define your genes and watch them evolve or grow just as you wish. However this chaos bring in another aspect that we never thought bring : beauty and peace.
No comments:
Post a Comment