EVOLUTIONARY MOTIFS FOR THE AUTOMATED DISCOVERY OF SELF-ORGANIZING DIMER AUTOMATA

It is usually difficult to reverse engineer a simple rule that exhibits some desirable and interesting behavior. We approach this problem by searching for dimer automaton rules exhibiting a broadly defined behavior, self-organization. We expected the simple and asynchronous nature of dimer automata to hinder self-organization, but an exhaustive search quickly yielded three rules that do, in fact, exhibit properties of self-organization. Two of these rules are applicable to actual physical phenomena, motivating searching for additional, more complex rules. However, exhaustive searches scale poorly here because of the rarity of interesting rules combined with the fast growth rate of the search space. To address these challenges we developed the evolutionary motifs algorithm. This algorithm finds the building blocks of the previously found dimer automaton rules, and combines them to form new rules in an evolutionary manner. Our evolutionary algorithm was more effective than an exhaustive search, producing a diverse population of rules exhibiting self-organization.