A Collection of the ThingS: Search Methods GA

Search Methods and Optimization Techniques

Labels: imported , My Project , Optimisation , Search Methods GA

Search Methods and Optimization Techniques

Related Posts:

Search Methods and Optimization Techniques – Section 3

Labels: imported , My Project , Search Methods GA

An optimization algorithm is a numerical method or algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values. If x is continuous, then the study of the algorithm is part of numerical analysis^†.

In general the optimization techniques may be classified as: Exact methods and Heuristic methods.

Exact methods like the branch and bound method are only of theoretical relevance due to their exponential runtime complexity.

Heuristic methods also referred as Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.^‡

Heuristic methods such as Simulated Annealing, Ant Colony Optimisation, Tabu Search, Evolutionary Algorithm, Local search, etc… are some of the developing methods. On these Genetic Algorithm is classified under Evolutionary Algorithm.

References:

^†Category: Optimization algorithms - Wikipedia, the free encyclopedia, last modified 02:43, 12 February 2006, http://en.wikipedia.org/wiki/Category:Optimization_algorithms

^‡Genetic algorithm - Wikipedia, the free encyclopedia, last modified 00:36, 15 February 2006, http://en.wikipedia.org/wiki/ Genetic_algorithm

Search Methods and Optimization Techniques – Section 2

Table of Contents

Search Methods and Optimization Techniques – Section 2

Labels: imported , My Project , Search Methods GA

On basis of current literature shows the three main types of traditional or conventional search method: calculus-based, enumerative, and random.^†

· Calculus-based methods are also referred to as gradient methods. These methods use the information about the gradient of the function to guide the direction of search. i.e., it seeks local optima by solving the usually nonlinear set of equations resulting from setting the gradient of the objective function equal to zero. If the derivative of the function cannot be computed, because it is discontinuous, these methods often fail.

· Enumerative methods are a very human kind of search and are fairly straight forward within a finite search space, or at least a discretized infinite search space. The algorithm then starts looking at objective function values at every point in the space, one at a time.

· Random search methods are strictly random walks through the search space while saving the best and have recognized the shortcomings (Calculus-based method has lack of robustness and Enumerative method have lack of efficiency) of above two methods. GA is one such kind of Random search method.

References:

^†David Edward Goldberg (1989), “Genetic Algorithms in Search, Optimization and Machine Learning” Addison-Wesley.

Table of Contents

Search Methods and Optimization Techniques – Section 1

Labels: imported , My Project , Optimisation , Search Methods GA

A search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer scientists that solve problems are kinds of search algorithms. The set of all possible solutions to a problem is called the search space. Brute-force search or "naïve"/uninformed search algorithms use the simplest, most intuitive method of searching through the search space, whereas informed search algorithms use heuristics to apply knowledge about the structure of the search space to try to reduce the amount of time spent searching.^†

References:

^†Search algorithm - Wikipedia, the free encyclopedia, last modified 04:37, 24 February 2006, http://en.wikipedia.org/wiki/ Search_algorithm

Related Posts:

Table of Contents