August 12, 2004

Genetic Algorithms-are here to stay

"Everything that can be invented has already been invented" was the famous quote of a scientist named Albert Michaelson in 1894. It was quoted long before some of the powerful inventions of mankind such as atomic bomb,aeroplanes.

Mankind has therefore never been left to feel complascent of its achievements.Time and again a new discovery revolutionises the world and creates a completely new environment for the people to live in.

The mechanical problem solvers,later came to be known as computers, were thought to be a mere science fiction until john von neuman laid down his architecture for a practical computer.It was the turn of the Transistors, in the early 60s, to revolutionise the computing world.The screeching,gigantic mechanical devices were scaled down to 'compact' ones to fit into a room. contemporary inventions in the field of electronics have further helped to diminish their size.

The computers of today have shrunk the world into a single entity,a global village.Information exchange,Email,file sharing would have remained one of those Michael Chriton thingies but for the Internet. Evidently such complex services require complex algorithms that strive to reduce the computing time to a minimum.

The computing problems can be broadly divided into two categories -P(polynomial complexity) and the NP(Non-polynomial complexity). The former class has specific algorithms to solve them efficiently while the conventional algorithms suffer with the latter. One such NP problem is the Travelling Sales Man (TSP) problem which has a time complexity of O(2^n), ie for every addition of a city the complexity of the problem doubles.

It is to tackle such problems that we need a more intelligent approach. An approach that's totally different,since the conventional algorithms have accepted a sullen defeat. A revolutionary concept to combat problems stated above is the Genetic Algorithms(GA).

GA differs from its conventional counterpart in a lot of ways. The solution offered by the GA is unpredictable. Most of the times,however,it gifts its users with an incredibly good solution. Having made the reader come upto this, the author feels a sense of responsibility to bestow him/her with some of his (mis)interpretations of the concept.

A baby baring a few basic instincts,such as sucking the mother's milk(takes a lot of concentration to adhere to the topic),is born naive. It however learns as it grows older. Its intelligence therefore increases with time. GA adpots a similar approach.

The solutions produced in the first generation are quite unacceptable while the one's produced by the later generations are better.Generation 1 therefore consists only of a set of random solutions. One among this is chosen depending on how well it satisfies the fitness function.

Fitness function hence is responsible to select one out of the many samples in a generation. It embodies the concept of Charles Darwin's theory - "survival of the fittest". Once the fitness function is properly defined, the programmer can sit back to watch the program grow intelligent!

After a sample is picked by the above mentioned function, it is subjected to Cross-over and Mutation to give rise to the next generation which is more "intelligent" and adapted to its environment.It is evident that as the number of generations increases the solution obtained gets bettered.

The author feels confident of the immense potential of the GA, atleast until the project work is over, they have certainly come here to stay,more importantly revolutionise.


Sriram said...

Actually, I'm not convinced nowadays (as I once used to be) that GAs are the solution to everything. GAs are mostly too slow - and they're based on one fundamental assumption - that evolution is the best way of finding the best solution.

For example, let us look at ourselves - the human - the pinnacle of evolution. Why don't we have eyes at the back of our head? it would protect us from a lot of danger. Why do we have mouths in our face and not on our stomachs? Why bother with sending food down that long fragile path called the oesaphagus?

Now, you could say that you can solve this problem by random mutation - but I don't think it solves the problem entirely. Sometimes you just have to think out of the box - and GA may not be the best thing for that.

Another hyped-field is AI - I see so many people putting in so much effort into it - effort which may not prove so fruitful.

vikraman said...
This comment has been removed by the author.
vikraman said...

My reply comes a good 4 years after you posted your comment. I really have the traits of a bureaucrat don't i? ;) But better late than never.

I think GA may not give you the 'Best' solution, but it surely gives one of the 'optimal' solutions. The reason why mouth cannot be attached to the stomach is because cellulose digestion starts right from the mouth with the aid of saliva and gets partially digested by the time it reaches the stomach. There could be reasons for the other questions too.
But one can always argue that evolution has produced man who exploits the environment without replenishing it adequately. So evolution has in effect created an organism that acts in a self destructing manner!