GEP Book   Home   News   Author   Q&A   Tutorials   Downloads   GEP Biblio   Contacts   Visit Gepsoft

C. FERREIRA In E. Lutton, J. A. Foster, J. Miller, C. Ryan, and A. G. B. Tettamanzi, eds., Proceedings of the 4th European Conference on Genetic Programming, Lecture Notes in Computer Science, Vol. 2278, pages 51-60, Springer-Verlag, Berlin, Germany, 2002. Discovery of the Boolean Functions to the Best Density-Classification Rules Using Gene Expression Programming The Density-Classification Task   The simplest CA is a wrap-around array of N binary-state cells, where each cell is connected to r neighbors from both sides. The state of each cell is updated by a defined rule. The rule is applied simultaneously in all the cells, and the process is iterated for t time steps. In the most frequently studied version of the density-classification task, N = 149 and r = 3. The central cell is represented by “u”; the three cells to the left are represented by “c”, “b”, and “a”; and the three cells to the right are represented by “1”, “2”, and “3”. The task of density-classification consists of correctly determining whether ICs contain a majority of 1’s or a majority of 0’s, by making the system converge, respectively, to an all 1’s state, or to a state of all 0’s. As the density of an IC is a function of N arguments, the actions of local cells with limited information and communication must be coordinated with one another in order to classify correctly the ICs. Indeed, to find by hand, in a search space of 2128 transition rules, CA rules that perform well is an almost impossible task and, therefore, several evolutionary algorithms were used to evolve better rules than the GKL rule [2, 7, 8, 11, 12, 13]. The best rules with performances of 86.0% (Coevolution2) and 85.1% (Coevolution1) were discovered using a coevolutionary approach between ICs and rules evolved by a GA [8]. The Boolean expressions of these rules are not known and little or no knowledge can be extracted from the output bits of their rule tables. In the next section, GEP is used to find the solutions to these rules. Home | Contents | Previous | Next