Local Search in Continuous Spaces

Local Search in Continuous Spaces

As we know that environment can be descrete or continuous, but the most real-world environment are continuous.

1) It is very difficult to handle continuous state space. The successor for real-world problem are many infinite states.

2) Origin of local search in continuous spaces lies in Newton and Leibnitz in the 17th century.

3) Optimal solution for given problem in continuous spaces can be found with "Local search techniques".

Search and Evaluation Theory

1) Search is basic problem solving technique. Basically it is always related with evolution theory.

2) Charles Darwin is father of evolutionary theory. The theory was based on the origin of species by means of natural selection (1859).

3) The variations (mutations) are well known attributes of reproduction and best features are preserved in next generation in proper propagation.

4) The qualities are inherited or modified. This fact was not associated with Darwin theory.

5) Gregor Mendel (1866) theory found the fact of inheritance. He performed artificial fertilization on peas.

6) DNA module structure was identified by Watson and Crick.

A → Adenin, G- Guanine,

T→ Thymine, C - Cytosine

7) The key difference between stochastic beam search and evolution is that successors are generated from multiple organisms (states) rather than one organism (state).

8) The theory of evolution is very much rich than genetic algorithm.

9) The process of mutations involves duplication, reversals and motion of large group of DNA.

10) Most important is the fact that the genes themselves encode the mechanisms whereby the genome is reproduced and translated into an organism. In genetic algorithms, those mechanisms are a separate program that is not represented within the strings being manipulated.

11) French naturalist Jean Lamarck (1809) proposed a theory of evolution whereby traits acquired by adaptation during an organism's lifetime would be passed on to its offspring. Such a process would be effective, but does not seem to occur in nature.

12) James Baldwin (1896) proposed a superficially similar theory : - that behavior learned during an organism's lifetime could accelerate the rate of evolution.

For example -

Suppose we want to place three new airports anywhere in India, such that the sum of squared distances from each city to its nearest airport is minimized.

i) The state space, is defined by the co-ordinates of the airports: (x₁, y₁), (x₂, y₂) and (x₃, y₃).

ii) This is a six-dimensional space: We also say that states are defined by six variables. (In general, states are defined by an n-dimensional vector of variables, x).

iii) Moving around in this space corresponds to moving one or more of the airports on the map.

iv) The objective function f (x₁, y₁, x₂, y₂, x₃, y₃) is relatively easy to compute for any particular state, once we compute the closest cities, but rather tricky to write down in general.

Problems Associated with Local Search

• Local search methods suffer from local maxima, ridges and plateaux in continuous state spaces just as much as in discrete spaces. Random restarts and simulated annealing can be used and are often helpful. High-dimensional continuous spaces are, however, big places in which it is easy to get lost.

Constrained Optimization Problems

• An optimization problem is constrained if solutions must satisfy some hard constraint like sites to be inside India and on dry land (rather than in the middle of rivers). The difficulty of constrained optimization problems depends on the nature of the constraints and the objective function. The best-known category is that of linear programming problems, in which constraints must be linear inequalities forming a convex region and the objective function is also linear. Linear programming problems can be solved in time which is polynomial in the number of variables.