Archive

Posts Tagged ‘Algorithm’

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.

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.

Best-First Search (Greedy Search)

September 4th, 2010 2 comments

Best-first search is a search algorithm, which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a “heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.”

Some authors have used “best-first search” to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths, which are judged closer to a solution, are extended first. This specific type of search is called greedy best-first search.

Efficient selection of the current best candidate for extension is typically implemented using a priority queue

Uniform Cost Search

September 4th, 2010 No comments

Uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. The search begins at the root node. The search continues by visiting the next node, which has the least total cost from the root. Nodes are visited in this manner until a goal state is reached.

Typically, the search algorithm involves expanding nodes by adding all unexpanded neighboring nodes that are connected by directed paths to a priority queue. In the queue, each node is associated with its total path cost from the root, where the least-cost paths are given highest priority. The node at the head of the queue is subsequently expanded, adding the next set of connected nodes with the total path cost from the root to the respective node.

Types of AI search Techniques

September 4th, 2010 No comments

Solution can be found with less information or with more information. It all depends on the problem we need to solve. Usually when we have more information it will be easy to solve the problem. There are two kinds of AI search techniques:

Uninformed search and Informed search.

Uninformed Search

Sometimes we may not get much relevant information to solve a problem. Suppose we lost our car key and we are not able to recall where we left, we have to search for the key with some information such as in which places we used to place it. It may be our pant pocket or may be the table drawer. If it is not there then we have to search the whole house to get it. The best solution would be to search in the places from the table to the wardrobe. Here we need to search blindly with fewer clues. This type of search is called uninformed search or blind search. There are two popular AI search techniques in this category:

Breadth first search and Depth first search.

Informed search

We can solve the problem in an efficient manner if we have relevant information, clues or hints. The clues that help solve the problem constitute heuristic information. So informed search is also call heuristic search. Instead of searching one path or many paths, just like that informed search uses the given heuristic information to decide whether to explore the current state further. Hill climbing is an AI search algorithm that explores the neighboring states, chooses the most promising state as successor, and continues searching for the subsequent states. Once a state is explored, hill climbing algorithm simply discards it. Hill climbing search technique can make substantial savings if it has reliable information. It has to face three challenges: foothill, ridge and plateau. Best first search is a heuristic search technique that stores the explored states as well so that it can backtrack if it realizes that the present path proves unworthy.