Publication - Genetic Algorithm Aided Optimization of Hierarchical Multi-Agent System Organization

Authors: Yu, Ling; Shen, Zhiqi; Miao, Chunyan; Lesser, Victor
Title: Genetic Algorithm Aided Optimization of Hierarchical Multi-Agent System Organization
Abstract: It has been widely recognized that the performance of a multi-agent system (MAS) is highly affected by its organization. A large-scale MAS may have billions of possible ways of organization, depending on the number of agents, the roles, and the relationships among these agents. These characteristics make it impractical to find an optimal choice of organization using exhaustive search methods. In this report, we propose a genetic algorithm aided optimization scheme for designing hierarchical structures of multi-agent systems. We introduce a novel algorithm, called the hierarchical genetic algorithm, in which hierarchical crossover with a repair strategy and mutation of small perturbation are used. The phenotypic hierarchical structure space is translated to the genome-like array representation space, which makes the algorithm genetic-operatorliterate. A case study with 10 scenarios of a hierarchical information retrieval model is provided. Our experiments have shown that competitive baseline structures which lead to the optimal organization in terms of utility can be found by the proposed algorithm during the evolutionary search. Compared with the traditional genetic operators, the newly introduced operators produced better organizations of higher utility more consistently in a variety of test cases. The proposed algorithm extends the search processes of the state-of-the-art multi-agent organization design methodologies, and is more computationally efficient in a large search space.
Keywords: Information Retrieval, Multi-Agent Systems, Organizational Design
Publication: UMass Amherst Computer Science Technical Report 2011-003
Date: December 2010
Sources: PDF: /Documents/zshen_TR2011_003.pdf
Reference: Yu, Ling; Shen, Zhiqi; Miao, Chunyan; Lesser, Victor. Genetic Algorithm Aided Optimization of Hierarchical Multi-Agent System Organization. UMass Amherst Computer Science Technical Report 2011-003. December 2010.
bibtex: 
@techreport{Yu-499,
  author    = "Ling Yu and Zhiqi Shen and Chunyan Miao and Victor
               Lesser",
  title     = "{Genetic Algorithm Aided Optimization of
               Hierarchical Multi-Agent System Organization}",
  month     = "December",
  year      = "2010",
  url       = "http://mas.cs.umass.edu/paper/499",
}