An Entry for THE 13th ANNUAL (2016) "HUMIES" AWARDS FOR HUMAN-COMPETITIVE RESULTS PRODUCED BY GENETIC AND EVOLUTIONARY COMPUTATION HELD AT THE GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, GECCO 2016


(1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result: 

M. Bidlo, "On Routine Evolution of Complex Cellular Automata," in IEEE Transactions on Evolutionary Computation, vol.PP, no.99, pp.1-13, doi: 10.1109/TEVC.2016.2516242, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7377086&isnumber=4358751

The paper was accepted for the final publication in January 2016, current status: in print.


(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper: 

The author:
Michal Bidlo, Faculty of Information Technology, Brno University of Technology, IT4Innovations Centre of Excellence, Bozetechova 2, 612 66 Brno, Czech Republic, e-mail: bidlom@fit.vutbr.cz, phone: +420541141206

of the paper:
M. Bidlo, "On Routine Evolution of Complex Cellular Automata," in IEEE Transactions on Evolutionary Computation, vol.PP, no.99, pp.1-1, doi: 10.1109/TEVC.2016.2516242, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7377086&isnumber=4358751


(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition):

Michal Bidlo


(4) the abstract of the paper(s):

The paper deals with a special technique, called conditionally matching rules, for the representation of transition functions of cellular automata and its application to the evolutionary design of complex multi-state cellular automata. The problem of designing replicating loops in two-dimensional cellular automata and the square calculation in one-dimensional cellular automata will be treated as case studies. It will be shown that the evolutionary algorithm in combination with conditionally matching rules is able to successfully solve these tasks and provide some innovative results compared to existing solutions. In particular, a novel replication scheme will be presented that exhibits a higher replication speed in comparison with the existing replicating loops. As regards the square calculation, some results have been obtained that allow a substantial reduction of the number of steps of the cellular automaton against the currently known solution. The utilization of the conditionally matching rules in the proposed experiments represents the first case of a successful automatic evolutionary design of complex cellular automata for solving non-trivial problems in which the existing conventional approaches have failed.


(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies:

B, D, G


(6) a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission): 

Cellular automata (CA) represent a computing platform in which the behavior (or computation) is a subject of LOCAL interactions of elementary computing elements (cells). Therefore, the behavior of a CA is viewed as an EMERGENT process that is based on the cooperation of ALL the cells according to their (transition) rules. Each cell exhibits a STATE (from a finite set of states) that synchronously changes in discrete time steps according to the rules. The transitions of cell states depend on the combinations of states in the (local) neighbourhood of each cell. In case of UNIFORM CA the cells share a single set of rules (a transition function) that specify their behavior. Its means that the (global) CA behavior is given by the sequence of cell states during a series of time steps -- a CA DEVELOPMENT. Although many CA have been designed analytically since the introduction of their concept by John von Neumann in 1966, there has been a lack of efficient AUTOMATIC methods for the design of complex MULTI-STATE CA (i.e. those working with more than 2 cell states). For example, Adamatzky's method (A. Adamatzky, Identification of Cellular Automata. CRC Press, 1994) assumes that an exact series of cell states for a given CA development is known in order to identify the transition rules. Sipper's Cellular Programming (M. Sipper, Evolution of Parallel Cellular Machines -- The Cellular Programming Approach, LNCS Vol. 1194, Berlin: Springer, 1997) is not suitable for uniform CA, moreover, this method has mostly been evaluated on binary (2-state) CA only. Wolfram studied CA using various application-specific analytical techniques (S. Wolfram, A New Kind of Science. Champaign IL: Wolfram Media, 2002).

In the proposed paper a method for representing transition functions of uniform CA is described, which allows us to automatically design complex multi-state CA for various applications using evolutionary algorithm. Our approach is based on CONDITIONAL RULES as basic elements of the transition function, which can effectively reduce the size of the genotypes compared to conventional techniques, while still allowing to generate elementary rules if needed for the given CA. Our goal was to design BOTH the TRANSITION RULES and corresponding CA BEHAVIOR suitable for the given application. In particular, we were able to design one-dimensional CA for the GENERIC square calculations with substantially better properties (complexity of the transition function and the number of steps needed to produce the result) in comparison with the existing solution published in S. Wolfram, A New Kind of Science. Champaign IL: Wolfram Media, 2002, page 638. Moreover, we discovered two-dimensional CA that is able to replicate a given non-trivial structure several times faster than Byl's loop can replicate (a structure of comparable complexity and size, see J. Byl, “Self-reproduction in small cellular automata,” Physica D: Nonlinear Phenomena, vol. 34, no. 1–2, pp. 295–299, 1989). Our method showed that various CA behavior can be obtained to solve a given application, more results are described in the proposed paper.

The substantiation for the aforementioned human-competitive criteria B, D and G is the following:

(B) We discovered using the proposed method (1) a structure in 2D CA that is able to replicate much more effectively than the existing structure of comparable complexity and size (Byl's loop -- see J. Byl, “Self-reproduction in small cellular automata,” Physica D: Nonlinear Phenomena, vol. 34, no. 1–2, pp. 295–299, 1989) and (2) a generic algorithm for squaring in 1D CA for which less than 50% of steps is needed in comparison with the existing solution published in S. Wolfram, A New Kind of Science. Champaign IL: Wolfram Media, 2002, page 638. Therefore we claim our results are equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.

(D) The results are publishable in its own right as a new scientific result independent of the fact that the result was mechanically created because completely new algorithms were discovered using our method for the problems mentioned in the previous paragraph, which exhibit better properties compared to existing solutions.

(G) In the author's opinion the proposed method solves a problem of indisputable difficulty in its field (i.e. automatic evolutionary design of multi-state cellular automata) because no similar results have yet been published using the existing approaches.


(7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable):

M. Bidlo, "On Routine Evolution of Complex Cellular Automata," in IEEE Transactions on Evolutionary Computation, vol.PP, no.99, pp.1-13, doi: 10.1109/TEVC.2016.2516242, URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7377086&isnumber=4358751

Please note: currently (May-June 2016) the paper is published in preprint (PP) mode and available on the journal web site; the final volume and number has not been assigned yet.


(8) a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors:

Any prize money, if any, is to be divided equally among the co-authors.


(9) a statement stating why the judges should consider the entry as "best" in comparison to other entries that may also be "human-competitive": 

The main result represents a method that allows automatically evolving multi-state CA "from scratch", i.e. just on the basis of a target behavior specified and evaluated within the fitness function. It was demonstrated that the method is able to discover complex behavior in CA, which have never been observed before, performed in various ways for a given application. In all experiments presented in the paper the results showed some improvements in comparison with the known solutions (optimization of the generic squaring in 1D CA and replication in 2D CA). Moreover, the proposed method was evaluated on various types of problems in CA, therefore we believe it can be widely applicable on both benchmark and real-world problems for which further innovative solutions may be discovered. In general, the design of complex multistate uniform CA represents a difficult task, hence the technique that allows automatizing this process represents a significant progress in this domain, which may contribute to other emerging fields too.


(10) A custom evolutionary algorithm based on GA was utilized in our experiments, more details are described in the paper.