Optimization

139

5

Guided Random Search Methods

5.1 Introduction

The solution techniques for unconstrained optimization problems that have

been described in earlier chapters invariably use the gradient information

to locate the optimum. Such methods, as we have seen, require the objec-

tive function to be continuous and differentiable, and the optimal solution

depends on the chosen initial conditions. These methods are not efcient in

handling discrete variables and are more likely to stay at a local optimum for

a multimodal objective function. Gradient-based methods often have to be

restarted to ensure that the local optimum reached is indeed the global one.

In this chapter we explore ve different types of solution techniques that

do not require the objective function to be either continuous or differentia-

ble. The solution techniques are

• Genetic algorithms (GAs)

• Particle swarm optimization (PSO)

• Simulated annealing (SA)

• Ant colony optimization (ACO)

• Tabu search

All these methods are based on random searches in locating the optima.

However, these methods are different from pure “random walk” methods

in the sense that they use information from the previous iteration in locat-

ing the next best point(s). These methods are hence classied under guided

random search methods. The guided random search techniques can be

subclassied into evolutionary methods. GA and PSO methods fall under

the heading of evolutionary methods. Instead of using a single point in the

search space, both GA and PSO techniques use population of points in the

search space and hence have a better chance of locating the global optima.

The GA technique mimics the biological process (genetics) whereas the PSO

technique is based on the idea of natural phenomena such as birds ocking

together or school of shes moving together. The SA method is based on

140 Optimization: Algorithms and Applications

the physical analogy of the annealing process of a material that is heated to a

high temperature and then slowly cooled in a controlled manner. The prop-

erties of the material get improved through this process. In a similar way,

using the SA technique, the transformation is made from the nonoptimal

solution for an optimized solution. Some other popular methods such as ant

colony optimization and tabu search, which are used for solving combinato-

rial problems, are briey discussed in the last section. The road map of this

chapter is shown in Figure 5.1.

5.2 Genetic Algorithms

Genetic algorithms (GAs) are search algorithms based on the mechanism

of natural selection. They rely on one of the most important principles of

Darwin: survival of the ttest. Globally the population is submitted to many

transformations. After some generations, when the population is enduring

no more, the best individual in the population is assumed to represent the

optimal solution. GA mimics the genetic process in which hereditary char-

acteristics are transmitted from a parent to an offspring. The basic unit of

inheritance is a gene. Several such genes, encoding specic characteristics

(eye color, height, etc.) are present on a chromosome. For example, humans

Guided random search methods

Genetic algorithm

Initialize population

Fitness evaluation

Reproduction

Crossover

Mutation

Multimodal test function

Particle swarm optimization

Simulated annealing

Other methods

Ant colony optimization

Tabu search

FIGURE 5.1

Road map of Chapter 5.