This paper presents FEFFuL, an architecture used to estimate the fitness value of a generated artifact in any Evolution Strategy (ES) system that would otherwise require human evaluation, i.e.: Interactive Evolutionary Computation (IEC) systems. By learning directly human preferences, the FEFFuL network aims to reduce user's fatigue to a minimum while also adapting to new emergent artifacts. We apply here FEFFuL in the context of evaluating generated structures in the popular game Minecraft.
interaction needed.
In our experiment, we tackle the generation of interIn Evolutionary Computation (EC) and Evolution Strate- esting structures in the popular videogame Minecraft. gies (ES), a global optimization problem is tackled by Minecraft is a sandbox construction videogame set in taking inspiration from biologic evolution: an initial pop- a voxel-based environment with various basic building ulation of solutions is evolved by selection and mutation, blocks, such as wood, stone, glass, water, etc. The maproducing new solutions with higher values of the task’s jor advantage of Minecraft over most Artificial Life (ALobjective function. In this context, a particular solution ife) domains is that surprisingly complex and functional is referred to as an individual, while its value of the ob- structures (e.g. moving robots, word processors, etc.) can jective function is its fitness . Genetic Algorithms (GA) are all be built from the same basic building blocks, which a family of algorithms in EC in which individuals are en- aligns well with the few chemical building blocks that coded by their genotype, which contains the information produce complex biological systems [10, 11, 12]. to reconstruct the actual solution, called phenotype[1, 2]. User fatigue is a major challenge in IEC, and since the The genotypes are mutated and combined in diferent human fatigue threshold cannot be improved, the availways to produce the next generation of solutions. able evaluations must be exploited as much as possible.
There are several domains in which a fitness function Our approach to this issue builds on the techniques menis unknown or very hard to compute, e.g. visual [3, 4, 5, 6] tioned above, by alternating human evaluation and the or musical [7, 8] appeal. In Interactive Evolutionary Com- training of a fitness estimator model in a single run of putation (IEC), this problem is overcome by using manual the genetic algorithm. This approach allows to use few human evaluation to compute the fitnesses of individu- human interactions while still perfoming a high number als in each generation. One of the main issues of IEC is of generations. Moreover, since the fitness estimator is user fatigue, which greatly limits the amount of human re-aligned with human preferences almost periodically, it evaluations available; this usually poses bounds both can also adapt to artifacts only seen in later generations. on the number of possible generations and the number As a convenient side-efect, more than one human (posof individuals that can be evaluated at each generation. sibly with slightly diferent preferences) can contribute To mitigate this problem the interactions are often care- to a single run, which demonstrates how this approach fully designed so as to minimize psychological fatigue can be extended from IEC to Collaborative Interactive [9]. Function approximators (e.g. neural networks) are Evolution (CIE) [13]. Unlike previous approaches such also often used to learn the preferences of the human as [14] our approach leverages data collected through experimenter [9, 7], so that this information can be used the evolution process to further reduce user fatigue even in subsequent runs of the GA and reduce the amount of when in an IEC setting.
cation of FEFFuL to the Minecraft environment.
where dec is the decoding function. The artifact generation is then simply
depth. These values are user defined. The artifact is the = () phenotype of a genome. Each genome uniquely encodes information used to generate the artifact. We use the Neu- where ∈ 3 and ∈ 2 are, respectively, the inputs roEvolution of Augmenting Topologies (NEAT) [15] to and the outputs of the network, both constrained in the control how these genomes evolve over the generations. real-valued interval [0, 1]. In order to show the artifact Each genome is part of a population of fixed size and, as a structure to the user, is then transformed. By thanks to the NEAT algorithm, is mutated to increase assigning to the number of admissible blocks and to the complexity of the resulting artifact. In fact, NEAT en- the number of admissible block rotations, we have that sures an ever-increasing complexification of the artifacts and, thanks to speciation and the use of elitism, it also 1 = ⌊1 * ( + 1)⌋ ensures a lasting diversification of phenotypes (diversity here is measured as genomic distance). Additionally 2 = ⌊2 * ( + 1)⌋ we set a low stagnation level to ensure low-performing The user has to choose the admissible blocks and valgenomes (i.e.: genomes that generate uninstering arti- ues by modifying a configuration file. The resulting artifacts for the user) are pruned away and leave space in facts are then evaluated in the Minecraft game using the the population for more interesting genomes. During EvoCraft [10] interface. evolution each genome is mutated and new genomes are created by combining two random parent genomes. Since genomes with high fitness are more likely to reproduce 2.2. Artifacts evaluation and pass on their properties to their ofsprings, we ensure The generated artifacts undergo an user defined Minithat the entire population slowly converges to diverse, mum Criterion (MC) step at each generation before evalhigh-fitness solutions. uation. This step removes artifacts that don’t satisfy this
The genomes are used to encode a Compositional Pat- minimum requirement. Only a predefined number of tern Producing Networks (CPPNs) [16]. Such a network artifacts sampled randomly from the artifacts that pass is composed of blocks of elementary activation func- the MC step are then presented to the user for direct tions connected together by weighted connections. The evaluation. In our experiment, the MC consisted in regenomes encode the structure, weights and biases of the moving artifacts that didn’t contain enough air blocks network. Mutations during evolution consist in adding or and enough solid blocks (both values were expressed removing connections or blocks, perturbing the weights as minimum percentages). The number of maximum and biases values and changing the activation functions. artifacts that could be presented to the user was set to The CPPNs thus directly map from genotype to pheno- 24. type without local interaction and are applicable on a The user is then tasked to evaluate the generated arinfinite-sized input space (a typical application is, for tifacts. This is done by looking at the structures on the instance, 2D image generation from pixel coordinates). Minecraft client applet and choosing the most interesting Due to their architecture, CPPNs create patterned out- ones. During manual (human) evaluation the program puts and can develop pure symmetry and symmetry with accepts a list of indexes that correspond to the selected arvariation, which in turn make for appealing artifacts. tifacts. Since the mapping from genomes to artifacts is 1:1,
In our experiment, we use the NEAT Python [17] li- we can assign the fitness value to the correct correspondbrary and the PyTorch-NEAT1 to integrate both the NEAT ing genome that generated the artifact. The possible evolutionary algorithm and the CPPNs architecture. The iftness values are 1 for the genomes the user is interested inputs to the networks are the scaled , and coor- in and 0 for the others. We note that we automatically dinates (∈ [0, 1]) of the artifact and the outputs are the assign a fitness value of 0 to all the genomes that didn’t block type and rotation (both values are output ∈ [0, 1] pass the MC step to discourage their traits to appear and later scaled to the admissible values). again later in the generations, as these are not interest
The artifact generation process can be formally ex- ing to the user. This ensures that only the phenotypically pressed as follows: given a population at the genera- interesting genomes survive throughout the evolution tion of genomes s, we first define the CPPN network process. that the genome encodes as During human evaluation we save the artifacts and their fitness in a memory bufer. Once the bufer is at ca = dec() pacity, the FEFFuL network can be trained in a supervised fashion to directly estimate the user preferences given the artifacts. The network itself is rather simple: a 3D 1The PyTorch-NEAT library is available at https://github.com/ uber-research/PyTorch-NEAT/
maps that are later flattened and passed through multiple residual blocks that in the end output a value ∈ [0, 1] that represent how likely the human would have marked the artifact as interesting. A graphical overview of the FEFFuL network can be found in 1.
Due to the nature of the task, it is expected that the bufer would be unbalanced: it is more likely that there would be more examples of discarded artifacts than accepted artifacts. For this reason, we balance the dataset before training the network. We do this by both oversampling accepted artifacts and then downsampling discarded artifacts. The former is accomplished by augmenting artifacts by rotation: we rotate the structure along the -axis by 90. We can do this since the artifact must be interesting regardless of the orientation. The latter is instead accomplished by removing discarded artifacts from the dataset until a good ratio of accepted artifacts and discarded artifacts is reached.
The output value of the FEFFuL module is directly assigned as fitness value to the corresponding genome. This gives an additional significance to the fitness value: it not only marks the user preference but also the network’s confidence in its output. Thus, a low-fitness genome would have been less likely to have been picked by the user than a high-fitness one. This process is important during the reproduction step of the NEAT algorithm as it heavily relies on the genome’s fitness to order the possible parents of new individuals.
Due to the ever-complexification of the genomes thanks to the NEAT algorithm, both the structures and the user’s preferences change over time. An artifact that the user deemed interesting at generation 0 may not be as interesting if found at generation 100. This implies that also the FEFFuL network has to reflect this behavior. We solved this problem with two simple corrections to the network’s behavior. First, we note that the bufer is constantly updated only with user’s selected artifacts and fitnesses, efectively making it a constantly-updated dataset we can train the network from. The corrections are the following: 1. We first use the network to evaluate the artifacts for a given number of generations at a time. This value is increased as the evolution process goes on, thus leveraging the network more and more as time goes on. 2. We enforce fine-tuning of the network after the aforementioned number of generations. We do this by prompting the user to evaluate the current generation, collect the preferences in the bufer and finetuning the network on the updated dataset. At this point of the process there could be some disalignment between user preferences and network estimates. This would be harmful to the entire experiment as it would diverge the search. We solve this by activating the network only if its accuracy over unseen artifacts is higher than a given threshold. Otherwise the user is prompted again until the network can be activated.
duce our results at 1. These are taken from the experiment configuration file in our repository; we are not going to report the settings for the NEAT algorithm which can be found in the neat configuration file in our repository.
Artifact width Artifact height Artifact depth Max number of artifact shown to the user Min percentage of air blocks in an artifact Min percentage of solid blocks in an artifact Admissible rotations Admissible blocks RNG seed Bufer capacity Batch size Number of convolution channels Number of epochs Interval of training
Activation threshold on test accuracy
evaluated at diferent generations at 2 and 3 respectively.
We note that, while the training metrics behave as expected, in the test we can see a rising trend for the loss metric. The accuracy however remains well over the 80%, which we consider a good value.
We ran the experiment for 100 generations. While this is a rather low number of generations, the aim of this project was not to evolve structures to a certain level of user satisfiability but to show that it was possible Finally, we report a comparison between the artifacts to use a NN to approximate user’s preferences, reduce generated on generation 0 and those generated on genuser fatigue and save time. The metrics prove that we eration 100 at 5. We note how the artifacts are more succeeded in the first part of the task. For what concerns complex on generation 100 as well as in line with user’s user fatigue, it is known that a single user can evaluate preferences during evolution. around 20 generations worth of artifacts before starting to feel fatigued [9]. In the entire evolution process only 29 generations worth of artifacts where evaluated by the 4. Conclusions and future work user, whereas the remaining 71 were evaluated by the FEFFuL network. We report a graph that shows which The results shown in the previous section suggest that evaluator was used at each generation at 4. this approach can efectively be used to mitigate the user
The time gain over the same amount of generations is fatigue problem in IEC tasks. More specifically, most of well apparent: we estimated that the human user takes the interactions with the human experimenter are in the from 2 to 3 minutes to evaluate a single batch of artifacts, ifrst few generations, where the bufer is not completely whereas the FEFFuL network only a few milliseconds. In full and the estimator cannot be trained. After the first fact we noticed that the bottleneck of time consumption alignment, the human evaluations were needed very sporadically, as the estimator maintained good alignment gorithm for individual protection applications, voland usually only needed one generation to adapt to new ume 2768, 2020, pp. 41–45. artifacts chosen by the user. This also means that after [6] M. Wozniak, C. Napoli, E. Tramontana, G. Capizzi, the initial alignment, the cost to perform more genera- G. Lo Sciuto, R. Nowicki, J. Starczewski, A multions, in terms of user evaluations needed is much lower. tiscale image compressor with rbfnn and discrete This can get even lower for further generations, even wavelet decomposition, volume 2015-September, though this descending trend would be fairly moderate 2015. doi:10.1109/IJCNN.2015.7280461. in our specific implementation. [7] B. Johanson, R. Poli, Gp-music: An interactive ge
However, these same results also suggest that a method netic programming system for music generation is needed to avoid the fitness estimator from overfitting with automated fitness raters, Genet. Program. during the fine-tuning step, perhaps with an adaptive (2000). rule that either produces an optimized “expiration date” [8] J. Biles, et al., Genjam: A genetic algorithm for for the model or that dynamically stops the fine-tuning generating jazz solos, in: ICMC, volume 94, Ann process when overfitting occurs. Arbor, MI, 1994, pp. 131–137.
We finally note two possible improvements to the FEF- [9] H. Takagi, Interactive evolutionary computation: FuL network. FEFFuL could use a latent representation of fusion of the capabilities of ec optimization and huthe phenotypes instead of directly mapping the artifacts man evaluation, Proceedings of the IEEE 89 (2001) to their fitness values. This could benefit the re-alignment 1275–1296. doi:10.1109/5.949485. process if the generalization power of the model over [10] G. S. R. Djordje, et al., EvoCraft: A New Challenge unseen artifact improves. This comes with the added for Open-Endedness, arXiv (2020). URL: https:// benefit of keeping a smaller bufer, thus requiring even arxiv.org/abs/2012.04751v1. arXiv:2012.04751. less human evaluation at the beginning of the experi- [11] M. Woźniak, D. Połap, C. Napoli, E. Tramontana, ment. Finally The Minimum Criterion could be enforced Application of bio-inspired methods in intelligent only in generations evaluated by the human, so that the gaming systems, Information Technology and Conadvantage of having a fitness estimator can be exploited trol 46 (2017) 150–164. doi:10.5755/j01.itc.46. to evaluate the entire population and not just a subset. 1.13872.
This would also ensure that no interesting artifact is dis- [12] D. Połap, M. Wózniak, C. Napoli, E. Tramontana, carded a priori during the MC step, allowing a diverse Is swarm intelligence able to create mazes?, Inset of good solutions to remain in the population. ternational Journal of Electronics and Telecommunications 61 (2015) 305–310. doi:10.1515/ eletel-2015-0039.
References [13] S. R. Szumlanski, A. S. Wu, C. E. Hughes, Conlfict resolution and a framework for collaborative [1] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, interactive evolution, in: AAAI, 2006, pp. 512–517.
R. Damaševičius, Is the colony of ants able to rec- [14] P. G. de Prado Salas, S. Risi, Collaborative interognize graphic objects?, Communications in Com- active evolution in minecraft, in: Proceedings of puter and Information Science 538 (2015) 376–387. the Genetic and Evolutionary Computation Condoi:10.1007/978-3-319-24770-0_33. ference Companion, GECCO ’18, Association for [2] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, Computing Machinery, New York, NY, USA, 2018, Real-time cloud-based game management system p. 127–128. URL: https://doi.org/10.1145/3205651. via cuckoo search algorithm, International Journal of Electronics and Telecommunications 61 (2015) [15] 3K2.0O57.2S3t.adnolei:y1,0E.fic1i1en4t5/E3v2o0lu5t6io5n1.o3f2N0e5u7r2a3l.Net333–338. doi:10.1515/eletel-2015-0043. works Through Complexification, Ph.D. thesis, De[3] J. Secretan, et al., Picbreeder: evolving pictures col- partment of Computer Sciences, The University of laboratively online, in: Proceedings of the SIGCHI Texas at Austin, 2004. URL: http://nn.cs.utexas.edu/ Conference on Human Factors in Computing Sys- ?stanley:phd2004.
tems, 2008, pp. 1759–1768. [16] K. O. Stanley, Compositional pattern pro[4] G. Capizzi, G. Lo Sciuto, C. Napoli, E. Tramontana, ducing networks: A novel abstraction of deM. Woźniak, A novel neural networks-based tex- velopment, Genetic Programming and Evolvture image processing algorithm for orange defects able Machines 8 (2007) 131–162. URL: https:// classification, International Journal of Computer doi.org/10.1007/s10710-007-9028-8. doi:10.1007/ Science and Applications 13 (2016) 45–60. [5] R. Avanzato, F. Beritelli, M. Russo, S. Russo, M. Vac- [17] Ss.1S0a7r1ti0,G-0.O07ch-o9a0, 2A8-ne8a.t visualisation of neuroevocaro, Yolov3-based mask and face recognition al- lution trajectories., in: EvoApplications, 2021, pp. 714–728.