Archive

Archive for the ‘Natural Algorithms’ Category

Simulated Annealing

September 4th, 2010 No comments
Started with random pixels. Simulated annealing

Image via Wikipedia

Simulated annealing (SA) is a generic probabilistic meta-heuristic for the global optimization problem of applied mathematics, namely locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). Problems, simulated annealing may be more effective than exhaustive enumeration if the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.

Particle Swarm Optimization

September 4th, 2010 2 comments

Particle swarm optimization (PSO) is a method for performing numerical optimization without explicit knowledge of the gradient of the problem to be optimized. PSO is originally attributed to Kennedy, Eberhart and Shi and was first intended for simulating social behaviour. The algorithm was simplified and it was observed to be performing optimization. The book by Kennedy and Eberhart describes many philosophical aspects of PSO and swarm intelligence. An extensive survey of PSO applications is made by Poli.

PSO optimizes a problem by maintaining a population of candidate solutions called particles and moving these particles around in the search-space according to simple formulae. The movements of the particles are guided by the best-found positions in the search-space, which are continually updated as better positions are found by the particles.

Ant Colony Optimization

September 4th, 2010 No comments
Shortest path find by an ant colony

Image via Wikipedia

Ant colony optimization (ACO) is a population-based meta-heuristic that can be used to find approximate solutions to difficult optimization problems.

In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants (hereafter ants) incrementally build solutions by moving on the graph. The solution construction process is stochastic and is biased by a pheromone model, that is, a set of parameters associated with graph components (either nodes or edges) whose values are modified at runtime by the ants.

The easiest way to understand how ant colony optimization works is by means of an example. We consider its application to the traveling salesman problem (TSP). In the TSP a set of locations (cities) and the distances between them are given. The problem consists of finding a closed tour of minimal length that visits each city once and only once.

To apply ACO to the TSP, we consider the graph defined by associating the set of cities with the set of vertices of the graph. This graph is called construction graph. Since in the TSP it is possible to move from any given city to any other city, the construction graph is fully connected and the number of vertices is equal to the number of cities. We set the lengths of the edges between the vertices to be proportional to the distances between the cities represented by these vertices and we associate pheromone values and heuristic values with the edges of the graph. Pheromone values are modified at runtime and represent the cumulated experience of the ant colony, while heuristic values are problem dependent values that, in the case of the TSP, are set to be the inverse of the lengths of the edges.

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.