from the repeated application of (1.3-7). As can be seen, during the first three iterations, the value of the function decreases rapidly. However, then the rate of reduction of the function slows. Observe that on the 10th iteration the value of the objective function is the minimum value to three significant digits, though there is still some discrepancy in the estimate of the minimizer. In this problem, the minimum is quite shallow, which reduces the speed of convergence.
Newton’s method can be extremely effective on some problems, but prove problematic on others. For example, if f(x) is not twice differentiable for some x, difficulties arise since Newton’s method requires the function, its gradient, and its Hessian. Many optimization methods require similar information and share similar drawbacks. There are optimization methods that do not require derivative information. One example is the Nelder–Mead simplex method. Even so, this algorithm can still become trapped at local minimizers if the function is not convex.
One feature that makes these methods susceptible to becoming trapped at a local minimum is that they take the approach of starting with a single estimated solution and attempt to refine that estimate. If the single estimate is close to a local extrema, it will tend to converge to that extrema. There is another class of optimization methods that are not based on a single estimate of the solution but on a large number (a population) of estimates. These population‐based methods are not as susceptible to convergence to a nonglobal local extrema because there are a multitude of candidate optimizers.
Genetic algorithms (GAs) are a population‐based optimization algorithms that have proven very effective in solving design optimization problems. Other population‐based optimization methods, such as particle swarm optimization, have also been used successfully. While one can engage in a lengthy debate over which algorithm is superior, such a debate is unlikely to be fruitful. The focus of this text is on posing the design problem as a formal optimization problem; once the problem is so posed, any optimization algorithm can be used. A discussion of GAs is included herein in order to provide the reader with a background in at least one method that can be used for the optimization process.
1.4 Genetic Algorithms: Review of Biological Genetics
In this section, we will set the stage for the use of GAs as optimization engines by reviewing some principles of biological genetics. All living things have a set of instructions on how they are constructed. These instructions are written in the deoxyribonucleic acid (DNA) contained within each cell of that living being. The structure of this molecule was first determined by James Watson and Francis Crick in the 1950s and is depicted in Figure 1.6. Therein, the horizontal strands are made of phosphate and a sugar called deoxyribose. These strands are wound into a helix structure. The short vertical dashed lines in Figure 1.6 indicate weak hydrogen bonds that are instrumental in the duplication of DNA. The letters A and G stand for adenine and guanine, respectively, which are compounds known as purines. The letters T and C designate thymine and cytosine, which are pyrimidines. The combinations AT, TA, GC, and CG form a four‐letter alphabet. A sequence of letters from this alphabet forms a gene of a living being. In terms of our discussion on design, we may view the gene as a design parameter of a living organism.
Figure 1.6 Deoxyribonucleic acid (DNA).
Each DNA molecule in a living organism is known as a chromosome. Living organisms generally have multiple chromosomes. For example, humans have 46 chromosomes per cell. These chromosomes are arranged into 22 pairs (one of each pair contributed by the father and one of each pair contributed by the mother). In addition, there are the two sex chromosomes denoted as X and Y. In humans and many other organisms, the existence of chromosomes in pairs leads to dominant and recessive genes, as discovered by Gregory Mendel, a Roman Catholic monk and botanist, who studied the propagation of traits in pea plants. However, not all living creatures have chromosomes organized in pairs; ants, wasps, and bees are haploid and have only one occurrence of each chromosome, while strawberries are octaploid with eight occurrences of each chromosome. This provides something to contemplate while eating strawberry pie.
In addition to some understanding of genes, chromosomes, and DNA, it is important to consider sexual reproduction and, in particular, the formation of gametes (sperm and egg cells). The formation of gametes is through a process known as meiosis, which is illustrated in Figure 1.7. Let us consider a diploid organism with two pairs of chromosomes, a long set and a short set as shown in Figure 1.7. This is consistent with chromosomes in cells that vary in length. The production of gametes begins with the chromosomes lengthening out within the cell as shown in Figure 1.7(a). Note there are two copies of this chromosome, one contributed by the father (darkly shaded) and one contributed by the mother (lightly shaded). Next replication of the chromosomes occurs as seen in Figure 1.7(b). The two copies of a chromosome are referred to as chromatids, and they are connected at a point called the centromere. At this point, meiosis starts with the pairing of the chromosomes given by mother and father. In this pairing process, it is possible for the arms of the chromosomes to interchange, thereby leading to a new chromosome that consists of some genes from the father and some genes from the mother. Note that the crossover point is normally between genes; this is because of the large amount of (apparently) nonfunctional DNA in most chromosomes. While one crossover of one chromosome is shown, multiple crossovers in all chromosomes are possible.
Figure 1.7 Meiosis.
After the chromosome pairing and crossover, the cell, which now contains four versions of each chromosome, splits into four cells. The four chromosomes segregate into these four cells. If crossover did not occur, this two‐chromosome organism could produce four genotypes (genetically unique) of gametes; therefore, a single mother–father pair could produce sixteen genotypes. However, because of the crossover, many additional genotypes of gametes can be produced. In fact, because of crossover, the number of genotypes that can be produced becomes related to the number of genes, not just the number of chromosomes. Thus, crossover is very important in achieving genetic diversity.
Of course, in the case of humans, chromosome distribution alone with 23 pairs of chromosomes, yields 223 = 8,388,608 genotypes for the gametes. A set of parents could thus produce 8,388,6082 genetically different children, which would seem to be an impressively diverse set, even without crossover. However, in artificial GAs, the number of chromosomes is much smaller, often consisting of a single chromosome.
Beyond increasing the sheer number of genotypes of the gametes, crossover plays another critical role because it allows beneficial genes (traits) on a given chromosome to be decoupled from detrimental genes (traits). Crossover will play a very important role in the operation of GAs.
In addition to gamete diversity due to genetic crossover and chromosomal segregation into gametes, additional diversity is brought about because of mutation. Mutation arises from errors in copying DNA. In mitosis, or cell division, mutation often has little effect, since the mutated cell will often die. However, in meiosis, mutation can have a significant impact since the mutated genetic code will propagate into the genetic code of every cell in the child. Even then, many mutations
