Posts Tagged ‘Genetic Programming’

Genetic Algorithms

September 4th, 2010 No comments
Genetic algorithm works to find the "most blue image"

Image via Wikipedia

In a genetic algorithm, a population of strings (called chromosomes or the genotype of the genome), which encode candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem, evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

Genetic algorithms find application in bioinformatics, phylogenetic, computational science, engineering, economics, chemistry, manufacturing, mathematics, physics and other fields.

A typical genetic algorithm requires:

  • A genetic representation of the solution domain.
  • A fitness function to evaluate the solution domain.

A standard representation of the solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming.

Natural Algorithms

September 4th, 2010 No comments

Image via Wikipedia

Nature, a source of minerals and precious stones is a mine of algorithms too.  In nature there are phenomena that resemble sorting action, phenomena which closely resemble division operation and so on.  By observing and studying these phenomena computer algorithms can be extracted.

It is possible to identify or observe natural phenomena from which algorithms can be derived, by accident or through a random search.  At the same time, it is difficult to propose a formal procedure (a set of well-defined steps) to search for a natural system that solves the problem at hand.  Nevertheless, the following suggestions given in the form of an algorithm will be useful in hunting for a suitable natural system.

1. Try to associate the data items that are central to the problem with entities in nature.  Let their attributes (mass, length, volume etc.) represent the magnitude of the data items.

2. Any algorithm transforms the input data, which is in a particular state into another form, which is the output data.  Therefore, keeping the entities in mind, try imagining a particular state of the system that depicts the input data and another state that depicts the output.

3. Now try to conceive a set of activities that can change the system state from the input state to the output state.

The above steps augmented with a little intuition should help the problem solver to zero-in onto a suitable natural system.