Genetic algorithms for the exploration of parameter spaces in agent-based models
Uri J. Wilensky, Forrest Stonedahl · 2011
This work provides the first comprehensive investigation of the use of genetic algorithms for exploring the range of behaviors produced by agent-based models. Agent-based modeling (ABM) is a powerful computer simulation technique in which many agents interact according to simple rules resulting in the emergence of complex aggregate-level behavior. However, as ABM is increasingly employed in both natural and social sciences, the methods and tools for understanding, exploring, and analyzing the behavior of agent-based models have not kept pace. In particular, models may be characterized by a large number of parameters, and the task of discovering parameter settings for which a model will produce a certain behavior is both difficult and time-consuming. Genetic algorithms (GAs) offer a flexible metaheuristic search mechanism which has previously been successful in a variety of combinatorial optimization and search problems. There is a rich space of possible model exploration tasks, and we offer a new unified framework for the creation and application of quantitative measures to perform these tasks using an evolutionary-search paradigm. We demonstrate the utility of GAs for ABM parameter exploration through a sequence of case studies in various application domains, including behavioral biology, viral marketing, archeology, and web-based journalism. This work advances agent-based modeling methodology by exploring when and how GAs can be useful in the model development and analysis process. It also contributes to a deeper understanding of GAs, by evaluating their strengths and weaknesses with regard to the particular challenges posed by this problem domain. We develop novel heuristics for dealing with model stochasticity in conjunction with fitness caching techniques. We also present the first set of benchmark models/tasks for automated ABM parameter search and exploration, and we rigorously investigate the performance of GAs on these benchmarks, with varying levels of stochasticity. An important product of this research is BehaviorSearch, a new automated software tool for efficient exploration of ABM parameter spaces. The design and affordances of BehaviorSearch are discussed with respect to improving model exploration and analysis by ABM practitioners.