A Stop at Genetic Programming Basics

AUTHORS : Abhishek Kumar Annamraju, Adhesh Shrivastava, Akashdeep Singh

Hello Everyone,

Over the years Computer vision lovers have have developed a genuine interest in the field of genetic programming.But why has this field been chosen????

Lets have a close look at what actually is this genetic programming???

In our real world,only the fortunate or the fitter ones survive.Obviously we cannot use the fortune element in computer vision,so fitness was taken into account.In real world,population never remains steady and the children do not replace the parents.On the other hand,in computer world of genetic programming,any population is fixed and the child replaces the least fit parent or any other individual in the population.

gaimg1

The diagram above shows the very basic genetic programming cycle.Each and every individual from the population is selected for fitness evaluation and then selected for mating as per their fitness levels.Now,their child(the descriptor) enters the population and the procedure continues till you get the fittest descriptor according to the user’s need.

For example there are primitive functions present int the population like adding pixels of two images,finding means,medians etc.Now if I set my goal as finding the chain of these primitives which selects my region of interest.For this I have a training image and a ground truth to evaluate the fitness.I put everything in the cycle and start evaluation and finally select the best possible one.This is what the algorithm does for us.

Most popularly used genetic programming is the multiple tree based algorithm since it is accurate and covers most of the population.Others are linear genetic programming and graphical genetic programming.

The linear genetic programming if further divided into three parts,stack based,register based and machine code.
Just to brief you up in stack based GP,each program instruction takes its primitive descriptor from a stack,performs the task and puts it back into the stack.On the other hand the register based and machine code one are similar,here,instead of stack permanent storage registers are used.I will not go much deep into it.

Lets stick to tree based one.To move further you should have a basic knowledge of fer terminologies:-

1)Fitness measure: Now with genetic programming a huge amount of composite feature operators will be generated. So, to give them a rank this fitness measure is introduced. Let G be the foreground in the ground truth image and G’ be the foreground in the composite feature image formed from the primitive feature image after being passed over by the composite feature operator. Let n(X) be the number of pixels within a region X. Therefore, the fitness measure of that composite operator will be n(G∩G’) / n(G U G’).

2) Selection: It is the process of selecting a composite operator from current population of composite operators generated. The number of individuals are randomly selected and the one with highest fitness value is copied to new population.

3) Code bloat problem: This is the basic problem in generation using genetic algorithm. In this the sizes of composite parameters by crossover may become very large. This slows down the process and consumes a lot of memory.

4) Crossover: It is a process similar to gene crossovers. First we select two composite operators on the basis of good fitness measures and term them as parents. Then one inter-node in each parent is selected randomly and the two subtrees rooted at that node are exchanged to generate two new composite operators called offspring. Here many times code bloat problem occurs, so, as a remedy they have come up with limiting the operator size with a soft size limit. If size of offspring > limit, then genetic programming keeps it, but evaluates it further. If the evaluation results in best fitness then it is kept otherwise discarded.

5) Mutation: This is done to avoid premature convergence which means that the resultant population halted too early with less generations or small generations. It is done in any of three ways:
a)Randomly select a node of a composite operator, and replace it(along with the selected node) with a subtree at this node by another operator(tree).
b)Randomly select a node of a composite operator, replace the primitive operator stored in the node with any other primitive operator with same input capacity.
c)Select any two subtrees from two operators and swap them.

6) Crossover probability/rate: It defines ratio of how many couple composite operators will be taken with respect to the number of couple composite operators present during a devised loop. A couple composite operator is any two operators taken at random.

7) Mutation probability/rate: It sets a maximum limit rate to which a how many mutation method can be applied to single composite operator. If probability is 5% and number of nodes in it 100,then only 5 times mutation will be done.

I think this much is enough for the introduction.I will get more deeper into the genetic programming in my next posts.

Thank you 🙂

Also see :- http://blindperception.wordpress.com/

Advertisements

One thought on “A Stop at Genetic Programming Basics”

  1. I believe this is one of the most significant info for me. And i’m happy studying your article. But wanna observation on few normal issues, The website style is great, the articles is really nice : D. Excellent process, cheers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s