Multiagent evolutionary computation for complex problems

Multiagent evolutionary computation (MAEC) is a new paradigm to efficiently solve a range of complex problems, by combining the advantages of evolutionary computation (EC) and multiagent systems (MAS). In general, there are three categories in MAEC: 1) “agent based EC” incorporates characteristics of intelligent agents, and adopts techniques in MAS to enhance the performance of EC; 2) “evolutionary computation based MAS” utilizes evolutionary techniques to design self-learning agents, to improve the efficiency of interactions between agents, and to increase the effectiveness of the whole system; 3) “the sequential or embedded approach of EC and MAS” employs EC and MAS in either a sequential order or an embedded fashion. The MAEC approaches have been successfully applied to solve benchmark and real world problems. However, most studies in the first category of MAEC focus only on single-objective optimization problems. In the second group of MAEC, the information communicated between agents is often assumed to be truthful. That is, the agents in MAS are assumed to be honest and cooperative. In addition, the two components of EC and MAS have not been integrated effectively in the third direction of MAEC. Thus, the ability of MAEC to solve complex problems has not been fully exploited by the previous studies. In view of this, this thesis proposes three approaches in the respective categories of MAEC for solving three complex problems, which are multiobjective optimization problems (MOPs), robustness of trust in MAS based e-marketplaces and traffic management in transportation systems. Firstly, a multiagent evolutionary framework based on trust is proposed to solve MOPs. This work lies into the first category of MAEC. In particular, the trust concept that is popular in MAS is adopted for measuring the dynamic competency of services (i.e., the pairs of evolutionary operators and control parameters) from generation to generation and on different problems. Then, candidate solutions modeled as intelligent agents will select the services with the probabilities correlated to the trustworthiness of the services. Experimental results demonstrate that the proposed framework significantly improves the performance of the state-of-the-art multiobjective evolutionary algorithms (MOEAs). Secondly, a multiagent evolutionary trust model (MET) is proposed to address the robustness problems in MAS based e-marketplaces, where advisor agents may not provide truthful information about seller agents. This work falls into the second group of MAEC. In MET, each buyer agent evolves its trust network (consisting of information about which advisor agents to include in the network and their trustworthiness) over time and finally constructs accurate and robust trust networks. Experimental results on a multiagent-based e-marketplace testbed show that MET is more robust than existing trust models in resisting typical attacks. Thirdly, a multiagent pheromone-based traffic management framework is proposed for reducing traffic congestion. This study belongs to the third direction of MAEC. In particular, a new digital “pheromone” inspired by EC is defined for bridging MAS based vehicle rerouting and traffic light control. Once congestion is predicted for a road, a proactive vehicle rerouting algorithm is designed for assigning alternative routes to cars before they enter the congested road. At the same time, an online traffic light control strategy is proposed to assign long time duration of green traffic lights to the roads with a large amount of pheromone. Experimental results show that the proposed framework significantly alleviates traffic congestion, saves travel time, and reduces air pollution and fuel consumption. To summarize, with the three kinds of effective MAEC algorithms for solving complex problems, this thesis serves to elicit more research efforts for building powerful MAEC approaches by delicately fusing the high level knowledge and advantages of EC and MAS, and applying them to solve large, open, dynamic, distributed complex problems. This work will also nourish the two related fields towards more intelligent EC and effective MAS.DOCTOR OF PHILOSOPHY (SCE