Optimization Parameters

A modified version of the simple genetic algorithm described by Goldberg (1989) was used in this work. Each generation had 200 chromosomes. The first generation consisted of 200 chromosomes chosen randomly. Successive generations were composed of chromosomes that were chosen through crossover, mutation and reproduction. The crossover probability was 0.7, which means that, on the average, we choose 70% of the chromosomes in a generation through crossover. The remainder are simply clones of chromosomes that existed in the previous generation.

To implement a crossover, we need to choose two chromosomes from the previous generation. For reproduction (cloning), we need to choose one chromosome from the previous generation. We choose these chromosomes through probabilistic selection, i.e. a better fit chromosome has a better likelihood of being selected. As explained in Section c., the raw fitness values are scaled using sigma truncation and linear scaling to obtain fitness values that can be used to provide different survival characteristics for different chromosomes. A chromosome with a scaled fitness value of 0.3 is twice as likely as a chromosome with fitness value of 0.15 to be chosen as one of the pair for a crossover. It can be shown (see, for example, Goldberg (1989) and Holland (1975)) that using this kind of probabilistic selection ensures that the ``schemata'' or parts of chromosomes that are good solutions to the problem are chosen with exponentially increasing frequency, ensuring that after a few generations, the regions of the search space with the best chromosomes are identified by the GA.

Having chosen the entire population for a single generation of the GA, we mutate the chromosomes. Recall that when we mutate a chromosome, we wish to perturb its genetic code slightly. We use the mutation probability, $p_m$, to calculate the standard deviation, $\sigma$, of the normal function of $x$ that satisfies

$$P( x < (1/\sigma) ) = 1.0 - p_m$$ (12)

the rationale being that $floor(x)$ will then give us the number of discrete mutation steps such that $x \ne 0$ with probability $p_m$. We solve Eq. 12 through numerical integration⁷ and use the $\sigma$ so obtained to get a random gaussian process with zero mean and standard deviation $\sigma$ (see Sedgewick (1990) for a way to do this). The stepsize of the mutation is determined by this normally distributed random variable and $x_{quant}$. We used a $p_m$ of 0.005 in the BWER algorithm. We generate one such step-size for each $x_i$ of each gene of the chromosome and increment the $x_i$ by that amount.