Evolutionary Discrete Optimization Inspired by Zero-Sum Game Theory
Ruiran Yu, Haoliang Wen, Yuhan Xu · 2022
In a zero-sum game, the two players compete against each other, and the gain of one player means the loss of the other. Generative adversarial networks (GANs) are models of this kind of thinking. Evolutionary algorithms (EAs) are popular and high robust methods to solve combinatorial optimization problems. However, in the middle stages of evolution, EAs usually suffer from the problem of a serious lack of population diversity. This often results in that EAs fall into local optima. This paper presents a cooperative evolutionary algorithm driven by policy-based GANs (PGAN-CEA) for solving traveling salesman problems (TSPs). PGAN-CEA adopts a policy-gradient method in reinforcement learning to train GANs to generate discrete data. First, GANs are used to construct an initial population. Then, a cooperative evolution strategy driven by GANs is used in the middle of the evolution. Further, a dual-population mechanism is utilized to assist the co-evolution of the dominant solutions generated by GANs and the solutions from the population of EAs. Test cases from TSPLIB and the Mona Lisa Problems are used to evaluate the proposed algorithm. Compared with other GAN-based algorithms, the proposed algorithm can mitigate the problem of local convergence and achieves certain improvements in quite a few performance indicators.