Читать книгу Power Magnetic Devices - Scott D. Sudhoff - Страница 19

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 2²³ = 8,388,608 genotypes for the gametes. A set of parents could thus produce 8,388,608² 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 are not noticeable because they are a part of the genetic code that is unused. When mutation has a noticeable effect, it is generally for the worse. However, occasionally beneficial mutations occur which improve the ability of an individual (and eventually a species) to survive.

A final concept from biology that will serve our needs for an optimization engine is the idea of natural selection and the survival of the fittest, an idea stemming from Charles Darwin’s voyages of the H.M.S Beagle, during a period of time roughly contemporary with the work of Mendel and the American Civil War. The idea that the most fit individuals of a population survive to reproduce is directly used in GAs. These algorithms are based on an explicit fitness function, which will be used to determine which individuals “survive” and will be placed into a mating pool.

Clearly, the discussion in this section is at a high level and has been greatly simplified. The interested reader is referred to Crow [2] for a more thorough introduction to the topic.