Effect of changing the basis in genetic algorithms using binary encoding.

Abstract

We examine the performance of genetic algorithms using binary encoding, with respect to a change of basis. Changing the basis can result in a change in the linkage structure inherent in the fitness function. We test three simple functions with differing linkage strengths and analyze the results. Based on an empirical analysis, we show that a better basis results in a smoother fitness landscape, hence genetic algorithms based on the new encoding method provide better performance.

Keywords: Genetic algorithms, binary encoding, change of basis, coordinate-change, non-singular binary matrix

1. Introduction

Traditional approaches dealing with binary encoding generally use the inherent standard basis. When we consider a basis other than the standard one, the linkage structure between basis elements and the ruggedness of the problem space can be completely different from the original ones. Via a change of basis, a complex problem can be transformed into a simple one, and vice versa. In this paper, we provide an idea for changing the basis in binary encoding. We also investigate and analyze its effect on genetic algorithms.

The paper is organized as follows. In Section 2 we explain the method of changing the basis in the vector space [Z.sup.n.sub.2] ([{0,1}.sup.n], [direct sum]). (1) We introduce previous work related to the concept of changing the basis in Section 3. In Section 4 we introduce test functions with different linkage structures, and new bases for the functions, and in Section 5 we analyze the experimental results. We provide discussion including future work in Section 6.

2. Change of Basis

2.1 Binary Matrix

A matrix A is defined as binary if A [member of] [M.sub.nxn] ([Z.sub.2]). Binary matrices have been widely used to deal with the adjacency of a graph . In particular, Anderson and Feil  transformed the light bulb puzzle into the problem of solving a linear system = Ax b from its graph structure, where A A [member of] [M.sub.nxn] ([Z.sub.2]) and n,b [member of] [Z.sup.n.sub.2] . Then, the solution is obtained by computing the inverse of A , i.e., x = [A.sup.-1]b. Binary matrices are also useful in dealing with the cut/cycle subspace of a graph, which is a vector space over [Z.sub.2] . They can also be used to represent a change of basis of a vector space over [Z.sub.2] in combinatorial problems. In this paper, we present this new application of binary matrices.

2.2 Change of Basis in [Z.sup.n.sub.2]

A basis for a vector space of dimension n is a sequence of n vectors, where every vector in the space can be uniquely expressed as a linear combination of basis vectors. Since it is often desirable to utilize more than one basis for a vector space, it is important to understand the means of easily transforming coordinate-wise representations of vectors and linear transformations, with respect to one basis, to their equivalent representations, with respect to another basis. Such a transformation is called a change of basis. The following theorem is easily derived from the basic theory of linear algebra .

Theorem 1. Let [B.sub.1] and [B.sub.2] be two bases for [Z.sup.n.sub.2]. Then there exists a nonsingular matrix T [member of] [M.sub.nxn] ([Z.sub.2]) such that for every [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], where [(v).sub.B] is the representation of v with respect to the basis B .

The matrix T in Theorem 1 is called coordinate-change matrix from the basis [B.sub.1] to [B.sub.2]. The standard basis [B.sub.s] for [Z.sup.n.sub.2] is {[e.sub.1],[e.sub.2], ... ,[e.sub.n]}, where [e.sub.j] = (0, ... , 0, 1, 0, ... , 0) is the element of [Z.sup.n.sub.2] with 1 only in the j-th place and 0s in all other positions. Given a nonsingular matrix T [member of] [M.sub.nxn] ([Z.sub.2]), the matrix T can be regarded as a coordinate-change matrix from the standard basis to another basis [B.sub.T] related to T. For every v [member of] [Z.sup.n.sub.2] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and then [B.sub.T] = {[Te.sub.1],[Te.sub.2], ... , [Te.sub.n]}. Hence, the problem of finding a new basis is equivalent to that of finding a proper nonsingular binary matrix.

3. Prior Work

In this section, we provide a brief literature survey on the basis change in real-coded genetic algorithms as well as binary-coded ones.

Chryssomalakos and Stephens  theoretically dealt with the bases of function space on [Z.sup.n.sub.2]. However, in this paper, we investigate the bases of more a fundamental space, i.e., those of the vector space [Z.sup.n.sub.2].

Gene reordering  can be considered as a special case of a change of basis. If T is just a permutation matrix, a change of basis means a reordering of gene positions in encoding. The concept of changing the basis is much more general than that of gene reordering. Coordinate changes based on eigenspace and orthogonalization have been studied . But, they focused on real-code representation. These results are not applicable to problems using binary encoding, because of the following proposition.

Proposition 1. Let T be a nonsingular binary matrix. Then, if T is not the identity matrix I , the eigenspace of T does not span [Z.sup.n.sub.2].

Proof. The spectrum of T is a subset of [Z.sub.2] . Since T is nonsingular, zero cannot be an eigenvalue of T . If T has an eigenvalue, it must be one. Suppose that the eigenspace of T spans [Z.sup.n.sub.2]. Then there exist linearly-independent n eigenvectors with eigenvalues of one. Let A be the matrix in columns of which has such n eigenvectors. Then TA = A. Since A is nonsingular, = T I. This is a contradiction.

To the best of the author's knowledge, the only non-trivial change of basis in a vector space over [Z.sub.2] is from . In cut space, which is a subspace of [Z.sup.n.sub.2], there are other bases corresponding to spanning trees of the given connected graph, besides the standard basis.

4. Test Functions

We tested n-dimensional functions of binary variables. These functions are simplified adaptations of Kauffman's NK landscapes . Kauffman defined a function with n bits, in which each bit's fitness contribution depends on its k neighbors. NK landscapes thus have "tunable ruggedness" and are often used to test genetic algorithms. We defined three functions, where k = 1,2, n - 2, respectively. Each variable's fitness contribution depends on its next k variables. Three test functions are provided in the following.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where each [x.sub.i] [member of] [Z.sub.2].

Suppose that T is a nonsingular binary matrix. Let x = [([x.sub.1][x.sub.2] ... [x.sub.n]).sup.T] be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and y = [([y.sub.1][y.sub.2] ... [y.sub.n]).sup.T] be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], where v [member of] [Z.sup.n.sub.2]. Then Tx = y. Hence, [F.sub.2](x) = [F.sub.2]([T.sup.-1]y), [F.sub.3](x) = [F.sub.3](T.sup.-1]y), [F.sub.n-1](x) = [F.sub.n-1]([T.sup.-1]y).

For the function [F.sub.2], we select the coordinate-change matrix T = ([t.sub.i,j]) such that [t.sub.i,j] = [t.sub.i,j+1] = [t.sub.i,j] = 0 in all other positions. For the function [F.sub.3], we select the matrix T = ([t.sub.i,j]) such that [t.sub.i,j] = [t.sub.i,i+1] = [t.sub.i,i+2] = 1 and [t.sub.i,j] = 0 in all other positions. We can easily check that these two T s are nonsingular for all n . For the function [F.sub.n-1], we select the matrix T = ([t.sub.i,j]) such that [t.sub.i,j] = 0 and [t.sub.i,j] = 1 in all other positions. Then T is nonsingular when n is even, because [T.sup.2] = [(1-I).sup.2] = O - 2.1 + I = I where 1 is an n x n binary matrix in which all elements are 1 and O is an n x n binary matrix in which all elements are 0. Given a coordinate-change matrix T, its inverse [T.sup.-1] can be efficiently computed by the Gaussian elimination method. Hence we can express the functions [F.sub.2], [F.sub.3], and [F.sub.n-1] on the new basis [B.sub.T] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where each [y.sub.i] [member of] [Z.sub.2] and [S.sub.k] are proper subsets of {1, 2, ... ,n}.

Here, we examine the test functions before and after changing the basis. For convenience, we set the number of binary variables n to 6. Fig. 1, 2, and 3 show the linkage structures among terms of the functions [F.sub.2], [F.sub.3], and [F.sub.n-1], respectively. They also show coordinate-change matrices (T and its inverse [T.sup.-1]). Here, each node denotes one term in the corresponding function. Each edge between two nodes denotes that the values of the two terms corresponding to the two nodes are dependent on their common variables. If the resultant graph has a complex topology, the corresponding function seems to be difficult to solve. Conversely, a simple sparse topology suggests that it is an easy problem. It is clear that the topologies obtained after changing the basis are simpler than those obtained beforehand. In particular, in the case of [F.sub.n-1], a completely-linked topology can be changed into a completely discrete one, just by changing the basis. In the next section, we show that such a change of topology intuitively affects the performance of a genetic algorithm.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

4. Empirical Results

First, we investigated the ruggedness of test functions. When we mutated one bit in the encoding using the standard basis, more than one bit could be changed in the encoding of the new basis [B.sub.T]. Thus, the neighborhood structure could differ greatly depending on the selected basis. For six test cases with 40 variables, i.e., n = 40, we examined the function values with respect to mutations of k arbitrary bits from a randomly generated solution, where k = 1, 2, 3, 4. Table 1 shows the results, and Fig. 4 depicts their average values. The figures were obtained from 10,000 trials. After changing the basis, we were able to ensure that all the test functions were smoother, i.e., the fitness landscape of [F.sub.#]([T.sup.-1]y) is smoother than that of [F.sub.#] (x). In particular, it is clear that the new basis of [F.sub.n-1] completely removes deceptiveness inherent in the function using the standard basis.

For the tests, we used the genetic algorithm of  with typical parameters. The genetic algorithm maximizes the test functions provided in Section 4. All genetic parameters except for the evaluation function are the same, and these are provided in Table 2.

[FIGURE 4 OMITTED]

Table 3 shows the results for the same genetic framework. The optimal value of each test function is 40. The table figures were obtained from 100 trials. In every case, after changing the standard basis into another good one, the performance was significantly improved. In particular, the test on the function [F.sub.n-1] shows that the new basis is much better than the standard basis. This is a natural result of the fact that the new basis completely removes the strong linkage structure inherent in the function represented by the standard basis. Also, it is clear that the performance of each function is proportional to the smoothness provided in Table 1.

5. Discussion

In this paper, we provided the simple but important idea of changing the basis in binary representation. The paper was based on the fact that a problem encoded by a binary vector has multiple representations according to the selected basis. We also tested some functions, which demonstrated the advantages of changing the basis. To the best of the author's knowledge, this is the first paper establishing the importance of changing the basis in binary encoding. However, this paper does not provide any indications about which basis should be selected to ensure that the search space is smooth. More studies about the mechanism for finding a good basis, i.e., a good coordinate-change matrix are needed. To this end, it would be good to begin with an investigation of the space of nonsingular binary matrices, i.e., general linear groups over [[Z.sup.n].sub.2]. Some problems may be barely transformed by a change of basis. Research about which problems are transformed by changing the basis and the degree to which the problems are transformed are topics for future study. In the future, this approach can be extended into the case of k-ary encodings.

The authors would like to thank the anonymous referees for their helpful comments and suggestions that improved the quality of this paper. The present research has been conducted through the Research Grant of Kwangwoon University in 2008. The ICT at Seoul National University provided the research facilities for this study. A preliminary version of this paper appeared in Proceedings of the Genetic and Evolutionary Computation Conference, ACM SIGEVO, pp. 1117-1118, 2008.

Received June 17, 2008; revised July 30, 2008; accepted August 4, 2008; published August 25, 2008

References

 M. Anderson and T. Feil, "Turning lights out with linear algebra," Mathematics Magazine, 71(4):300-303, 1998.

 N. Biggs, Algebraic Graph Theory, Cambridge University Press, second edition, 1994.

 R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991.

 T. N. Bui and B. R. Moon, "Genetic algorithm and graph partitioning," IEEE Transactions on Computers, 45(7):841-855, 1996.

 C. Chryssomalakos and C. R. Stephens, "What basis for genetic dynamics?" In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1018-1029, 2004.

 R. Diestel, Graph Theory, Springer-Verlag, Heidelberg, third edition, 2005. Graduate Texts in Mathematics, Volume 173.

 S. H. Friedberg, A. J. Insel, and L. E. Spence, Linear Algebra, Prentice-Hall International, Inc., third edition, 1997.

 I. Hwang, Y.-H. Kim, and B.-R. Moon, "Multi-attractor gene reordering for graph bisection," In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1209-1215, 2006.

 S. Kauffman, "Adaptation on rugged fitness landscapes," Lectures in the Science of Complexity, pages 527-618, 1989.

 Y.-H. Kim, Y.-K. Kwon, and B.-R. Moon, "Problem-independent schema synthesis for genetic algorithms," In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1112-1122, 2003.

 K. Sastry, "Single and multiobjective genetic algorithm toolbox in C++," Technical Report 2007016, IlliGAL, University of Illinois at Urbana-Champaign, June 2007.

 D. Whitley, M. Lunacek, and J. Knight, "Ruffled by ridges: How evolutionary algorithms can fail," In Proceedings of the Genetic and Evolutionary Computation Conference, pages 294-306, 2004.

 D. Wyatt and H. Lipson, "Finding building blocks through eigenstructure adaptation," In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1518-1529, 2003.

(1) [direct sum] is the exclusive-or (XOR) operator. ([a.sub.1], [a.sub.2], ... [b.sub.1],[b.sub.2], ... [b.sub.n]) = ([a.sub.1][direct sum][b.sub.1], [a.sub.2] [direct sum][b.sub.2], ... , [a.sub.n] [direct sum] [b.sub.n])

Yong-Hyuk Kim (1) and Yourim Yoon (2), Non-members

(1) Department of Computer Science and Engineering, Kwangwoon University 447-1, Wolgye-dong, Nowon-gu, Seoul, 139-701, Korea [e-mail: yhdfly@kw.ac.kr]

(2) School of Computer Science and Engineering, Seoul National University Sillim-dong, Gwanak-gu, Seoul, 151-744, Korea [e-mail: yryoon@soar.snu.ac.kr]

* Corresponding author: Yourim Yoon

Yong-Hyuk Kim received the B.S. degree in computer science and the M.S. and Ph.D. degrees in computer science and engineering from Seoul National University (SNU), Seoul, Korea, in 1999, 2001, and 2005, respectively. From March 2005 to February 2007, he was a Postdoctoral Scholar in SNU and also a research staff member at the Inter-University Semiconductor Research Center in SNU. Since March 2007, he has been an assistant professor at Department of Computer Science and Engineering in Kwangwoon University, Seoul, Korea. His research interests include algorithm design/analysis, discrete mathematics, optimization theory, combinatorial optimization, evolutionary computation, operations research, and data/web mining. Dr. Kim has served as a Committee Member of GECCO 2005-2006 and a reviewer for journals (IS, TKDE, TPDS, TC, TSE) of IEEE Computer Society since 2003.

Yourim Yoon received the B.S. degree in computer engineering from Seoul National University (SNU), Seoul, Korea, in 2003. She is currently a Ph.D. candidate and working toward the Ph.D. degree at School of Computer Science and Engineering (CSE) in SNU. She is also a chief of the Optimization Laboratory at School of CSE in SNU. Her research interests include optimization theory, combinatorial optimization, evolutionary computation, discrete mathematics, and operations research. She served as a reviewer for BIC-TA 2007.
Table 1. Variation of Function Value

Test function     Perturbation   Maximum   Average   Standard
strength                         deviation

F.sub.2] (x)         1 bit          2        1.0        1.0
2 bits         4        1.5        1.3
3 bits         6        1.8        1.6
4 bits         8        2.1        1.7

[F.sub.2]            1 bit          2        1.0        1.0
([T.sup.-1] y)       2 bits         2        1.0        1.0
3 bits         4        1.5        1.3
4 bits         4        1.5        1.3

[F.sub.3] (x)        1 bit          3        1.5        0.9
2 bits         6        1.9        1.6
3 bits         9        2.3        1.6
4 bits         12       2.4        2.0

[F.sub.3]            1 bit          3        1.2        1.0
([T-sup.-1] y)       2 bits         4        1.3        1.0
3 bits         5        1.5        1.2
4 bits         6        1.7        1.3

[F.sub.n-1] (x)      1 bits         25       5.0        3.7
2 bits         2        1.0        1.0
3 bits         25       4.9        3.6
4 bits         4        1.5        1.3

[F.sub.n-1]          1 bit          1        1.0        0.0
([T.sup.-1] y)       2 bits         2        1.0        1.0
3 bits         3        1.5        0.9
4 bits         4        1.5        1.3

* Results from 10,000 trials.

Table 2. Input Size and Genetic Parameters

Type                                       Value

Number of variables ( n )                    40
Population size                              50
Selection                       Tournament selection with size 2

Crossover rate                               1.0
Crossover type                         One-point crossover

Mutation rate                               0.05
Mutation type                         Gene-wise mutation

Replacement proportion                      0.5
Maximum number of generations               500

Table 3. Results ( n =40 )

Test function    Best       Average           Std       CPU [dagger]
(Average %-gap)   (Std %-gap)

[F.sub.2] (x)     40     37.08 (7.30)     1.43 (3.58)   0.55
[F.sub.2]         40     39.08 (2.30)     1.12 (2.79)   0.54
([T.sup.-1] y)

[F.sub.3] (x)     39     36.68 (8.30)     1.45 (3.62)   0.55
[F.sub.3]         40     38.60 (3.50)     1.04 (2.61)   0.55
([T.sup.-1] y)

[F.sub.n-1] (x)   37     31.45 (21.38)    2.19 (5.49)   0.89
[F.sub.n-1]       40     39.54 (1.15)     0.61 (1.53)   0.53
([T.sup.-1] y)

Test function                Optimal value

[F.sub.2] (x)                     40
[F.sub.2] ([T.sup.-1] y)          40

[F.sub.3] (x)                     40
[F.sub.3] ([T.sup.-1] y)          40

[F.sub.n-1] (x)                   40
[F.sub.n-1] ([T.sup.-1] y)        40

* Results from 100 trials.

The value of %-gap is computed as follows: 100 x (optimum -- output)
/optimum.[dagger] Average CPU seconds on Intel[R] Xeon[TM] CPU
2.40GHz.
COPYRIGHT 2008 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Author: Printer friendly Cite/link Email Feedback Kim, Yong-Hyuk; Yoon, Yourim KSII Transactions on Internet and Information Systems Report 9SOUT Aug 1, 2008 3348 Cross-layer optimized vertical handover schemes between mobile WiMAX and 3G networks. An algorithm for iterative detection and decoding MIMO-OFDM HARQ with antenna scheduling. Binary system (Mathematics) Coding theory Genetic algorithms