Fuzzy Multiple Objective Decision Making

17

2

Multi-Objective

Evolutionary Algorithms

In this chapter, we will introduce the use of genetic algorithms for solving multi-

objective programming (MOP) problems and the concrete contents of genetic algo-

rithms (GAs).

2.1 CONCEPTS OF GENETIC ALGORITHMS

In traditional optimization methods, gradients and derivatives are usually used to

guide the search for an optimal solution. However, when the objective function is

not differentiable or the dimensionality of the search space is quite large, these

techniques usually perform poorly. GAs are now considered alternative meth-

ods to solve such optimization problems. GAs were pioneered by Holland (1975)

and the concept is to mimic the natural evolution of a population by allowing

solutions to reproduce, creating new solutions that then compete for survival in

the next iteration. The tness improves over generations and the best solution is

nally achieved.

Holland (1975) tested the ability of GAs for dealing with different kinds of objec-

tive functions. These experimental results indicate that GAs are very robust and

perform better than traditional optimization methods. In addition, Bosworth et al.

(1972) performed one of the earlier studies of GAs to conclude that GAs are not sen-

sitive to increasing dimensionality and noise. These results were consistent with the

experimental results of De Jong’s study (1975). GAs were widely used later for vari-

ous optimization problems, and many revised GAs have been proposed to improve

their capabilities, such as GENOCOP (Michalewicz, 1992) or increase their applica-

tions, such as genetic programming (Koza, 1992).

Let us consider the following notations for describing the procedures of GAs.

The initial population P(0) is encoded randomly by strings. In each generation t, the

more t elements are selected for the mating pool and then processed by three basic

genetic operators (reproduction, crossover, and mutation) to generate new offspring.

On the basis of the principle of survival of the ttest, the best chromosome of a

candidate solution is obtained. The pseudo code of GAs illustrates the computation

procedures as shown in Figure2.1.

The power of the GA lies in its ability of simultaneous searching a population of

points in parallel instead of a single point. Therefore, a GA can nd the approximate

optimum quickly without falling into a local optimum. In addition GAs do not have

the limitation of differentiability, as do other optimization techniques.

18 Fuzzy Multiple Objective Decision Making

2.2 GA PROCEDURES

In order to illustrate how GAs can be used to nd optimal decision variables, we rst

consider the following multi-objective programming (MOP) problem.

2.2.1 string representation

To represent the solutions of a MOP problem in GAs, we should encode these solu-

tions as chromosomes. Usually, each element of a chromosome consists of a binary

string (bit) or real-number string. For binary encoding, the precision of a solution

depends on the number of bits used. However, the binary encoding for a function

optimization problem may suffer critical drawbacks because of the existence of

Hamming cliffs (Ludvig et al., 1997). For example, the 1000000 and 0111111 pair

belong to neighboring points in phenotype space but have maximum Hamming dis-

tance in genotype space. Hence, the binary strings do not preserve the locality of

points in the phenotype space.

In contrast, real-number strings code possible solutions as a vector of real num-

bers of the same length as the solution vector, and are more suitable for dealing with

function optimization problems (Eshelman and Schaffer, 1993; Walters and Smith,

1995; Michalewicz, 1996). This is because the topological structure of the genotype

space for real-number encoding is identical to that of the phenotype space. Hence,

it is easy to form effective genetic operators by borrowing useful techniques from

conventional methods (Gen and Cheng, 2000). In addition, compared with binary

encoding, real-number encoding is capable of representing very large domains or

unknown domains (Michalewicz, 1996).

2.2.2 population initialization

Usually, the initial population P(0) is selected at random. Each genotype in the

population can be initialized to present the degree of variance from the uniform

distribution. Note that there is no standard to determine the size P(0) of the initial

population. Bhandari et al. (1996) showed that as the number of iterations extends

FIGURE 2.1 Genetic algorithm procedures.