A sociologically inspired heuristic for optimization algorithms: A case study on ant systems

https://doi.org/10.1016/j.eswa.2012.09.020Get rights and content

Abstract

This paper discusses how social network theory can provide optimization algorithms with social heuristics. The foundations of this approach were used in the SAnt-Q (Social Ant-Q) algorithm, which combines theory from different fields to build social structures for state-space search, in terms of the ways that interactions between states occur and reinforcements are generated. Social measures are therefore used as a heuristic to guide exploration and approximation processes. Trial and error optimization techniques are based on reinforcements and are often used to improve behavior and coordination between individuals in a multi-agent system, although without guarantees of convergence in the short term. Experiments show that identifying different social behavior within the social structure that incorporates patterns of occurrence between states explored helps to improve ant coordination and optimization process within Ant-Q and SAnt-Q, giving better results that are statistically significant.

Highlights

Social network theory can provide optimization algorithms with social heuristics. ► Social Ant-Q: combine theory from different fields to build social structures. ► Coordination mechanism through autonomous behavior, without a need for central coordination. ► Social interaction used to improve coordination between agents. ► Social interaction is fundamental for the development of collective behavior.

Introduction

The collective behavior of social groups has inspired the development of computational models for generating solutions to optimization problems. This behavior results from patterns of interaction between individuals in a population, and is not merely a property of a single control system but is a consequence of individuals’ behavior. In such a system, each individual’s structure is relatively simple, but complex social structures emerge from their collective behavior.

A social structure is built from social behavior and interactions, and changes in this structure producing effects on all individuals and eliminating their idiosyncratic behavior. Social interaction is the main driver in the construction of a social structure, which shows how individuals are related. The social structure reflects the characteristics and behavior of individuals which in turn can influence or modify the structure. Interaction is necessary because in most social systems there are processes by which individuals adapt, and such processes are needed if the collective behavior of the group as a whole is to evolve.

Social systems are mainly characterized by the relationships between a population’s individuals who interact, giving rise to patterns of behavior that improve the coordination of the group when taking collective decisions (Ribeiro, 2010). Individuals in a multi-agent system, denoted agents, usually learn from their own behavior and from the influence of others, improving their utility whilst interacting with the stronger agents in the group. The social structure can be determined by the superposition of the ‘best’ agents in the group, where the stronger agents influence the others through individual or collective reinforcement, following the principles of the theory of social impact (Latané, 1981) and learning by experience (Sutton & Barto, 1998).

From the behavior of agents and the application of this theory, it is possible to identify coherent social structures and patterns of behavior in a complex system, describing who interacts with whom, and the frequency and intensity of their interactions (Ribeiro, 2010). The social structure emerges without a central system of coordination but through the sociability of agents in their own local behavior patterns.

In a multi-agent system, agents need to interact and to coordinate themselves for carrying out tasks. Coordination between agents can help to avoid problems with redundant solutions, inconsistency of execution, waste of resources and situations of deadlock. In this context, models of coordination based on the collective behavior of social groups, e.g., swarm intelligence (Beni and Wang, 1989, Eberhart and Kennedy, 1995), have been shown to be capable of solving complex problems involving social and individual behavior.

The paradigm of coordination based on swarm intelligence has been studied intensively in recent decades (Annaluru et al., 2004, Bastos Filho et al., 2008, Bean and Costa, 2005, Dorigo and Stützle, 2010, Engelbrecht, 2010, Gambardella and Dorigo, 1995, Guntsch and Middendorf, 2001, Kennedy and Eberhart, 1995, Lim et al., 2006, Shyu et al., 2006, Su et al., 2005). This paradigm was suggested by colonies of social insects, leading to computational systems which reproduce the behavior used to solve collective problems in colonies of ants, bees, fish or wasps.

Social insects in a swarm act locally but must satisfy the global objective of the system, forming a community of agents. The community can be formed by a set of agents whose connectivities show their social relationships. This description is also shown to be the underlying concept of social networks (Wasserman & Faust, 1994). Social networks may consist of a set of individuals, computers, organizations or computational elements connected by some kind of relationship. A group of persons, for example, may be linked together through friendship, acquaintance, parentage or work, just as insects in a swarm can be related by spatial proximity, type of specialization or mutual ability.

Thus methods of swarm intelligence, reinforcement learning and models of social structure are based on principles that are often complementary and which allow the impacts of established relationships to be observed.

It can be seen that each agent in a multi-agent system experiences influences from the others; so far, however, there has been only limited research on how this process can be formalized, and on the construction of dynamic social structures for decision-making for the purpose of improving methods for coordination and distributed learning available in the literature. Another important issue concerns the use of principles of social networks to improve the adaptation of agents who become coordinated through reinforcement. The purpose of the research described here is to answer the following questions which at present are still open: (i) how is a social structure constructed from knowledge acquired by agents through their interactions? (ii) how are principles of social interaction used to improve coordination between agents within the social structure? (iii) how can these influences be formalized? and (iv) how can the relevant agents be identified?

These issues are approached in this paper by developing a method using such principles to establish a social structure from interactions between agents in a multi-agent system, leading to improvement in algorithms based on swarms or reinforcement learning. The method is termed Social Ant-Q (SAnt-Q) (Ribeiro, 2010) and is one of the main contributions of this paper.

The paper is organized as follows: Section 2 describes related work using concepts of social networks to improve methods of coordinating multi-agent systems. Section 3 sets out a method using the theory of social networks to improve the convergence of algorithms based on reinforcement, which integrates and adapts procedures for multi-agent coordination, ant colony, reinforcement learning and social networks. Section 4 presents and discusses results showing the gain through the approach, relative to the Ant-Q algorithm. The paper concludes with Section 5 which lists important aspects requiring further study as well as perspectives for future research.

Section snippets

Related work

A system such as a society of agents can be defined as a cognitive and social entity, having identifiable relationships and links between its agents (Panzarasa & Jennings, 2001). In general, societies are organized according to some structure, such as networks or hierarchies. Unlike hierarchies, networks have been identified as social structures. Social networks are made up of a set of states that can be connected by links representing relationships. These relationships can be defined by

SAnt-Q

Coordinating agents who have different objectives and behavior is an important aspect in the study of coordination (Bastos Filho et al., 2008, Comanici and Precup, 2010, Dorigo et al., 1991, Gambardella and Dorigo, 1995, Knox and Stone, 2010) derived from reinforcement learning have been studied by a number of researchers and described in different applications as a form of self-adaptive behavior brought about by the agent’s own experience. Such agents can acquire new behavior which improves

Experiments (evaluation of SAnt-Q)

Experiments were used to compare the utilities of policies generated by agents interacting in the Ant-Q pheromone network and in the SAnt-Q social structure. The experiments were run using benchmark: eil51 and eil76, found in the online library TSPLIB3 (Reinelt, 1991).

The datasets eil51 and eil76 have 51 and 76 states respectively and were constructed by Christofides and Eilon (1969). Such sets have important characteristics for

Conclusions and future work

This paper presented SAnt-Q, an algorithm that uses social network theory to improve convergence of the algorithm Ant-Q. SAnt-Q is implemented by integrating and adapting methods of multi-agent coordination, ant colony development, reinforcement learning and social networks, so that individuals interact and communicate information within a socially dynamic structure.

Collective behavior, when coordinated, gives to individuals of a system abilities (reinforcements through attitudes) and

Acknowledgements

We thank anonymous reviewers for their comments, together with members of the Network Laboratory of the Federal Technological University of Paraná (UTFPR) Campus Pato Branco-Pr. This research is supported by the Program for Research Support of UTFPR – Campus Pato Branco, DIRPPG (Directorate of Research and Post-Graduation) and by the Brazilian Council of Research (CNPq) under Grants 470325/2008-9 and 305847/2008-2.

References (57)

  • Ashri, R., Ramchurn, S., Sabater, J., Luck, M., & Jennings, N. (2005). Trust evaluation through relationship analysis....
  • A.-L. Barabási et al.

    Scale-free networks

    Scientific American

    (2003)
  • Bastos Filho, C. J. A., Lima Neto, F. B., Lins, A. J. C. C., Nascimento, A. I. S., & Lima, M. P. (2008). A novel search...
  • Beni, G., & Wang, J. (1989). Swarm Intelligence in cellular robotic systems. In Proceeding NATO advanced workshop on...
  • L. Bianchi et al.

    An ant colony optimization approach to the probabilistic traveling salesman problem

  • R.S. Bowman et al.

    Agent collaboration and social networks

    Integration of Knowledge Intensive Multi-Agent Systems

    (2005)
  • B. Bulka et al.

    Local strategy learning in networked multi-agent team formation

    Autonomous Agents and Multi-Agent Systems (AAMAS-06)

    (2006)
  • N. Christofides et al.

    An algorithm for the vehicle-dispatching problem

    Operations Research Quarterly

    (1969)
  • Comanici, G., & Precup, D. (2010). Optimal policy switching algorithms for reinforcement learning. In Proceedings of...
  • K. Dautenhahn

    Socially intelligent robots: Dimensions of human-robot interaction

    Philosophical Transactions of the Royal Society B: Biological Sciences

    (2007)
  • J. Demsar

    Statistical comparisons of classifiers over multiple data sets

    Journal of Machine Learning Research

    (2006)
  • Dorigo, M. (1992). Optimization, learning, and natural algorithms. PhD thesis, Dip. Elettronica, Politecnico di Milano,...
  • Dorigo, M., & Stützle, T. (2010). Ant colony optimization: Overview and recent advances. In M. Gendreau & J.-Y. Potvin...
  • Dorigo, M., Maniezzo, V., & Colorni, A. (1991). The ant system: An autocatalytic optimization process. Technical report...
  • Eberhart, R. C., & Kennedy, J. F. (1995). A new optimizer using particle swarm theory. In Proceedings of the sixth...
  • Engelbrecht, A. P. (2010). Heterogeneous particle swarm optimization. In Proceedings of the 7th international...
  • P. Erdös et al.

    A class of Hamiltonian regular graphs

    Journal of Graph Theory

    (1978)
  • Gambardella, L. M., & Dorigo, M. (1995). Ant-Q: A reinforcement learning approach to the traveling salesman problem. In...
  • Cited by (10)

    View all citing articles on Scopus
    1

    This research has been developed as doctoral student.

    View full text