A Multiagent Co-Evolutionary Algorithm With Penalty-Based Objective for Network-Based Distributed Optimization

Abstract

The emergence of networked systems in various fields brings many complex distributed optimization problems, where multiple agents in the system need to optimize a global objective cooperatively when they only have local information. In this work, we take advantage of the intrinsic parallelism of evolutionary computation to address network-based distributed optimization. In the proposed multiagent co-evolutionary algorithm, each agent maintains a subpopulation in which individuals represent solutions to the problem. During optimization, agents perform local optimization on their subpopulations and negotiation through communication with their neighbors. In order to help agents optimize the global objective cooperatively, we design a penalty-based objective function for fitness evaluation, which constrains the subpopulation within a small and controllable range. Further, to make the penalty more targeted, a conflict detection method is proposed to examine whether agents are conflicting on a certain shared variable. Finally, in order to help agents negotiate a consensus solution when only the local objective function is known, we retrofit the processes of negotiating shared variables, namely, evaluation, competition, and sharing. The above approaches form a multiagent co-evolutionary framework, enabling agents to cooperatively optimize the global objective in a distributed manner. Empirical studies show that the proposed algorithm achieves comparable solution quality with the holistic algorithm and better performance than existing gradientfree distributed algorithms on gradient-uncomputable problems.