14-07-2012, 12:11 PM
Classical and Advanced Techniques for Optimization
Classical and Advanced Techniques for Optimization.pdf (Size: 34.21 KB / Downloads: 101)
Classical Optimization Techniques
The classical optimization techniques are useful in finding the optimum solution or unconstrained maxima or minima of continuous and differentiable functions. These are analytical methods and make use of differential calculus in locating the optimum solution. The classical methods have limited scope in practical applications as some of them involve objective functions which are not continuous and/or differentiable. Yet, the study of these classical techniques of optimization form a basis for developing most of the numerical techniques that have evolved into advanced techniques more suitable to today’s practical problems. These methods assume that the function is differentiable twice with respect to the design variables and that the derivatives are continuous. Three main types of problems can be handled by the classical optimization techniques, viz., single variable functions, multivariable functions with no constraints and multivariable functions with both equality and inequality constraints.
Advanced Optimization Techniques
• Hill climbing
Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path.
In simple hill climbing, the first closer node is chosen whereas in steepest ascent hill climbing all successors are compared and the closest to the solution is chosen. Both forms fail if there is no closer node. This may happen if there are local maxima in the search space which are not solutions. Steepest ascent hill climbing is similar to best first search but the latter tries all possible extensions of the current path in order, whereas steepest ascent only tries one.
Simulated annealing
The name and inspiration come from annealing process 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.
Genetic algorithms
A genetic algorithm (GA) is a search technique used in computer science to find approximate solutions to optimization and search problems. Specifically it falls into the category of local search techniques and is therefore generally an incomplete search. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).
Ant colony optimization
In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but instead follow the trail laid by earlier ants, returning and reinforcing it, if they eventually find any food.