Thursday , August 16 2018

Calibrating Agent-Based Models
Using a Genetic Algorithm

Enrique CANESSA1, Sergio CHAIGNEAU2
1 Facultad Ingeniería y Ciencias, CINCO, Universidad Adolfo Ibáñez,
Avda. Padre Hurtado 750, Viña del Mar, Chile
ecanessa@uai.cl
2 Centro de Investigación de la Cognición, Facultad de Psicología,
Universidad Adolfo Ibáñez,
Diagonal las Torres 2640, Santiago, Chile
sergio.chaigneau@uai.cl

Abstract: We present a Genetic Algorithm (GA)-based tool that calibrates Agent-based Models (ABMs). The GA searches through a user-defined set of input parameters of an ABM, delivering values for those parameters so that the output time series of an ABM may match the real system’s time series to certain precision. Once that set of possible values has been available, then a domain expert can select among them, the ones that better make sense from a practical point of view and match the explanation of the phenomenon under study. In developing the GA, we have had three main goals in mind. First, the GA should be easily used by non-expert computer users and allow the seamless integration of the GA with different ABMs. Secondly, the GA should achieve a relatively short convergence time, so that it may be practical to apply it to many situations, even if the corresponding ABMs exhibit complex dynamics. Thirdly, the GA should use a few data points of the real system’s time series and even so, achieve a sufficiently good match with the ABM’s time series to attaining relational equivalence between the real system under study and the ABM that models it. That feature is important since social science longitudinal studies commonly use few data points. The results show that all of those goals have been accomplished.

Keywords: Agent-based modelling, genetic algorithms, calibration, validation, relational equivalence, complex adaptive systems.

>Full text
CITE THIS PAPER AS:
Enrique CANESSA, Sergio CHAIGNEAU, Calibrating Agent-Based Models Using a Genetic Algorithm, Studies in Informatics and Control, ISSN 1220-1766, vol. 24 (1), pp. 79-90, 2015.

  1. Introduction

Agent-Based Models (ABMs) (among other tools) are particularly well-suited to studying Complex Adaptive Systems (CAS) [1], cf. [2]. Generally speaking, a CAS is one where numerous elements, parts, or agents (homogeneous or not) interact non-linearly with each other and with their environment such as that their properties may be modified as a result of those interactions [3]. Traditional approaches to studying CAS [4] often limit our ability to understand the full complexity of these systems, in part because the characteristics of CAS (e.g., path dependent dynamics) violate many of the statistical assumptions necessary to use those approaches (i.e., survey research, controlled experiments, game theory) [1].

The distinguishing feature of ABMs is that they are constructed in a “bottom-up” manner, by defining the model in terms of entities and dynamics at a micro-level, i.e., at the level of individual actors and their interactions with each other and with the environment [5], [6], [7]. An ABM consists of one or more types of agents, and possibly a non-agent environment (e.g. in a prey-predator ABM, the environment could be the prey’s food; e.g.: if the prey are sheep and predators are wolves, the environment could be the grass.). Agent definitions include specification of their capabilities to determine particular behaviours, as well as decision-making rules and other mechanisms that agents use to choose their own behaviours. Agents may also have adaptive mechanisms that allow them to change based on their experience (e.g., changing the state of agents’ memory to reflect prior interactions). While an ABM is running, agent behaviour is generated as agents choose which other agents to interact with and what to do in a given interaction. Thus, ABMs embody complex interlaced feedback relationships, leading to the non-linear, path-dependent dynamics often observed in CAS.

While ABMs and all formal models increase our knowledge about the behavior of any system consisting of similar processes, the use of such models to make inferences about particular real-world systems requires model validation (i.e., showing that model behavior or parameters are comparable to those of a real system). However, model validation is not trivial [8], [9], [10]. For exploratory CAS models, one approach to validation is to focus on relational equivalence [11]. In general it is impossible to expect matching the detailed behavior of a CAS model to the real system [4], [8]. Thus, validation can be done by matching patterns and relationships between the model and the system being modeled, rather than matching details [11], [9].

Bearing in mind the above mentioned characteristics of the validation of ABMs that model CAS, we present a tool based on Genetic Algorithms (GA) that allows to find the combination of values for input variables to the ABM that establishes relational equivalence between the ABM and the real system it represents. The general idea is to have a GA that will deliver combinations of input parameters to a certain ABM, which will produce outputs of the ABM that match as close as possible the corresponding time series of data gathered from the real system. Because values delivered by the GA must then be judged by a domain expert to finally see whether they are reasonable and

select the ones that better make sense from a substantive point of view, we prefer to refer to the GA-based tool as a calibration method, instead of a validation one.

In the next sections we discuss the limitations of current GA-based calibration methods and present a new tool that tries to lessen those drawbacks. Then, we apply the new tool to calibrate three increasingly complex ABMs and conclude that the tool works as expected, but that new improvements may be desirable.

REFERENCES

  1. CANESSA, E., R. RIOLO, An Agent-based Model of the Impact of Computer-mediated Communication on Organizational Culture and Performance: An Example of the Application of Complex Systems Analysis Tools to the Study of CIS, Journal of Information Technology, vol. 21, 2006, pp. 272-283.
  2. QUEZADA, A., E. CANESSA, Agent-based Modeling: A Tool for Complementing the Analysis of Social Phenomena, Avances en Psicología Latinoamericana, vol. 28 (2), 2010, pp. 226-238.
  3. MILLER, J., PAGE, S., Complex Adaptive, Systems: An Introduction to Computational Models of Social Life, Princeton: Princeton University Press, NJ, USA, 2007.
  4. HOLLAND, J. H., Hidden Order: How adaptation builds complexity, Addison-Wesley, Redwood City, 1995.
  5. BANKES, S. C., Agent-based modeling: A revolution? PNAS 99, vol. 3, 2002, pp. 7199-7200.
  6. BONABEAU, E., Agent-based Modeling: Methods and Techniques for Simulating Human Systems, PNAS 99, vol. 3, 2002, pp. 7280-7287.
  7. CONTE, R., R. HEGSELMANN, P. TERNA, Simulating Social Phenomena, Berlin: Springer-Verlag, 1997.
  8. BANKES, S. C., Exploratory Modeling for Policy Analysis, Operations Research, vol. 41(3), 1993, pp. 435-449.
  9. GRIMM, V., S. F. RAILSBACK, Individual-based Modeling in Ecology, Princeton: Princeton Univ. Press, 2005.
  10. GRIMM, V., E. REVILLA, U. BERGER, F. JELTSCH, W. M. MOOIJ, S. F. RAILSBACK, H.-H. THULKE, J. WEINER, T. WIEGAND, D. L. DEANGELIS, Pattern-oriented Modeling of Agent-based Complex Systems: Lessons from Ecology, Science, vol. 310 (5750), 2005, pp. 987-991.
  11. AXELROD, P., Advancing the Art of Simulation in the Social Sciences, in: R. Conte, R. Hegselmann, P. Terna eds., Lecture Notes in Economics and Mathematical Systems: Simulating Social Phenomena, Berlin: Springer-Verlag, 1997.
  12. HEPPENSTALL, A. J., A. J. EVANS, M. H. BIRKIN, Genetic Algorithm Optimisation of an Agent-based Model for Simulating a Retail Market, Environment and Planning B: Planning and Design, vol. 34, 2007, pp. 1051-1070.
  13. CAPORALE, G. M., A. SERGUIEVA, H. WU, Financial Contagion: Evolutionary Optimization of a Multinational Agent-based Model, Intl. J. of Intelligent Systems in Accounting and Finance Management, vol. 16(1-2), 2009, pp. 111-125.
  14. ROGERS, A., P. VON TESSIN, Multi-objective Calibration for Agent-based Models, Proc. of 5th Workshop on Agent-based Simulation, May 2004, pp. 17-22.
  15. SKOLICKI, Z., T. ARCISZEWSKI, M. HOUCK, K. D. JONG, Co-evolution of Terrorist and Security Scenarios for Water Distribution Systems, Advances in Engineering Software, vol. 39(10), 2008, pp. 801-811.
  16. NARZISI, G., V. MYSORE, R. MISHRA, Multi-objective Evolutionary Optimization of Agent-based Models: an Application to Emergency Response Planning, Proc. the 2nd IASTED International Conference on Computational Intelligence, 2006.
  17. CALVEZ, B., G. HUTZLER, Automatic Tuning of Agent-Based Models Using Genetic Algorithms, Proc of 6th Workshop on Multi-Agent Based Simulation (MABS’05), Netherlands, 2005.
  18. ZWIJZE-KONING, K. H., M. D. T. DE JONG, Auditing Information Structures in Organizations: A Review of Data Collection Techniques for Network Analysis, Organizational Research Methods, vol. 8 (4), 2005, pp. 429-453.
  19. WILENSKY, U., NetLogo. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL, 1999.
  20. MACAL, C. M., M. J. NORTH, Agent-based Modeling and Simulation, Proc. Winter Simulation Conference 2009, M. D. Rossetti, R. R. Hill, B. Johansson, A. Dunkin and R. G. Ingalls, eds., Austin, TX, Dec. 2009, pp. 86-98.
  21. CHAIGNEAU, S., E. CANESSA, J. GAETE, Conceptual Agreement Theory, New Ideas in Psychology, vol. 30, 2012, pp. 179-189.
  22. CHAIGNEAU, S., E. CANESSA, A. QUEZADA, The Spreading and Demise of Concepts in Social Groups, Proc. IEEE XXIX Intl. Conf. of the Chilean Computer Science Society (SCCC 2010), IEEE Computer Society, Mar. 2011, pp. 139-145.
  23. CHAIGNEAU, S., E. CANESSA, The Power of Collective Action: How Agents Get Rid of Useless Concepts without Even Noticing Their Futility, Actas XXX Intl. Conf. of the Chilean Computer Science Society, Curicó, Chile, 7-11 Noviembre, 2011.


https://doi.org/10.24846/v24i1y201509