Fundamental Concepts of Hidden Genes Genetic Algorithms

The optimization of a simple VSDS objective function may be formulated as follows:

where x = [x,X2-...,xj]^r, J is the number of design variables Xj, and UB and LB are the upper and lower bounds of the variables respectively. This section introduces the biologically inspired concept of hidden genes to address this type of VSDS optimization problems. The concept presented in this section was first published in reference [4].

The Hidden Genes Concept in Biology

In genetics, the deoxyribonucleic acid (DNA) is organized into long structures called chromosomes. Contained in the DNA are segments called genes. Each gene is an instruction for making a protein. These genes are written in a specific language. This language has only three-letter words, and the alphabet is only four letters. Hence, the total number of words is 64. The difference between any two persons is essentially because of the difference in the instructions written with these 64 words. Genes make proteins according to these words. Since, not all proteins are made in every cell, not every gene is read in every cell. For example,

Figure 6.3: Chemical tags (purple diamonds) and the "tails” of histone proteins (purple triangles) mark DNA to determine which genes will be transcribed (picture is modified from [111]).

an eye cell doesn’t need any breathing genes on. And so they are shut off in the eye. Seeing genes are also shut off in the lungs. Another layer of coding tells what genes a cell should read and what genes should be hidden from the cell [106]. A gene that is being hidden, will not be transcribed in the cell. There are several ways to hide genes from the cell. One way is to cover up the start of a gene by chemical groups that get stuck to the DNA. In another way, a cell makes a protein that marks the genes to be read; Fig. 6.3 is an illustration for this concept. Some of the DNA in a cell is usually wrapped around nucleosomes but lots of DNA are not. The locations of the nucleosomes can control which genes get used in a cell and which are hidden [106].

Concept of Optimization using Hidden Genes Genetic Algorithms

In this chapter, the concept of hidden genes is implemented to hide some of the genes in a chromosome (solution); these hidden genes represent variables that should not appear in this candidate solution. In this section, the design variables are assumed to be coded in binary format. In a VSDS optimization problem, the number of design variables depends on the specific values of some of the design variables. Selecting different values for some of the design variables, changes the length of the chromosome. Different solutions have different number of design variables. So, in the design space, we have chromosomes of different lengths. Let L_max be the length of the longest possible chromosome. In the hidden genes concept, all chromosomes in the population are allocated a fixed length equal to Lmax. In a general solution (a point in the design space), some of the variables

Figure 6.4: Hidden genes and effective genes in two different chromosomes.

(part of the chromosome) will be ineffective in objective function evaluations; the genes describing these variables are referred to as hidden genes. The hidden genes, however, will take part in the genetic operations in generating future generations. To illustrate this concept, consider Fig. 6.4. Suppose we have two chromosomes, the first chromosome is represented by five genes (represented by five binary bits in this example) and the second chromosome is represented by three genes. Suppose also that the maximum possible length for a chromosome in the population is fixed at 7. The first chromosome is augmented by two hidden genes and the second chromosome is augmented by four hidden genes. The hidden genes are not used to evaluate the the fitness of the chromosomes. Because all chromosomes have the same length, standard definitions of genetic algorithms operations can still be applied. Hidden genes will take part in all genetic operations. Mutation may alter the value of a hidden gene. A crossover operation will swap parts of the chromosome that may have hidden genes. A hidden gene in a parent may become an effective gene in the offspring. These hidden genes that become effective take part in the objective function evaluations in the new generations. Figure 6.5 shows a simple example for two parents with hidden genes and the resulting children after a crossover operation. In Fig. 6.5, the digit number is listed on the top of the figure. The digit number 6 determines the start location of the hidden genes, whereas the digits number 4 and 5 determine the number of hidden genes in the chromosome. The crossover point is between digits 4 and 5. As can be seen from Fig. 6.5, the parent chromosomes swap the digits 0-4. As a result of this swap: the gene values change in both of the resulting chromosomes, the number of hidden genes and/or the location of the hidden gene change.

Outline of a Simple HGGA

A simple version of the HGGA implements the standard GA crossover operation. The differences between the HGGA in this case and a standard GA are in how the chromosome length is computed and in how the fitness function is evaluated. The chromosome length is fixed among all solutions in the population and its length is selected to represent the solution that has the maximum number of

Figure 6.5: Crossover operation in HGGA.

design variables. In evaluating the fitness of a solution, the chromosome hidden genes are excluded. Algorithm 6.1 shows an outline for the HGGA.

Algorithm 6.1 The hidden genes genetic algorithm

Determine the maximum number of design variables DV_max Compute the chromosome length Cl⁴. Cl = DV_max Create a population of chromosomes Initialize the population Evaluate initial population

■ Determine the hidden genes in each chromosome

■ Evaluate fitness of each chromosome - Exclude hidden genes in evaluating fitness

while (some convergence criteria is not satisfied) do Perform competitive selection

Apply genetic operators to generate new chromosomes Evaluate solutions in the population end while

Example 6.1. Branin Function Optimization Using Simple HGGA In this section, an experimental evaluation of the proposed approach on the benchmark Branin function is conducted. The Branin function /(уьУг) is defined as:

The Branin function has three global minima. First, the standard GA is implemented. The chromosome has two genes, one for each variable yi and у2- The resulting solution has / = 0.3979, yi = 3.1416, and уг = 2.2749. This GA implementation has a population of 100 members and the number of generations is 100.

To test the HGGA, two cases are considered. The first case is implementing the HGGA to the same problem. The chromosome, in the HGGA implementation, consists of three genes: >’|, y₂, and n, where n is an integer that specifies which gene of yi and >’2 is hidden. If n = 1, then the gene representing y₂ is hidden. If n = 2, then the gene representing >'1 is hidden. If n = 0, then none of the genes is hidden. The result of implementing the HGGA is / = 0.3979, >'1 = 3.1416, >'2 = 2.2750, n = 0. The population size is 100 and the number of generations is 100. The solution obtained from the HGGA is the same as that obtained from the GA, and the chromosome of the obtained solution has no hidden genes. The second case tests the new capability of the HGGA. Consider another function f = f(y,y₂) +>’3, where уз € [0 10]. Suppose that the number of variables in f is variable: two or three. Clearly, the minimum value for f is the same as that of /. Hence, one global minimum of f has only two variables yi and y₂ or three variables with y₃ = 0. The HGGA is implemented in this problem with a chromosome of four genes: yi, y₂, >’3, and n, where n G {0,1,2,3,4,5,6} and specifies which gene(s) are hidden, as shown in Fig. 6.6 where the hidden genes are marked by H The result of running the HGGA is f = 0.3979, У) = 3.1416, y₂ = 2.2750, y₃ = 0.0001, n = 0. Clearly the obtained solution corresponds to the case described above where f = / and y₃ vanishes. To force the HGGA to search for solutions that have hidden gene(s), the range of n is reduced to be n G {1,2,3,4,5,6}. Hence, any solution will have at least one hidden gene. Running the HGGA for this new case results in the solution: f = 0.3979, yi = 3.1416, У2 = 2.2750, уз = 0.8387, n = 3. This solution has уз as a hidden gene and hence its value does not affect the cost f. The optimal values of yi and У2 are those minimizing /.

Figure 6.6: Assigned hiddene genes for different value of n.