اکتشاف الهام گرفته از جامعه شناسی برای الگوریتم های بهینه سازی : یک مطالعه موردی بر روی سیستم های مورچه

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.

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 and 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 and 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.

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 and 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 and 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.