A differential BPSO-GA hybrid algorithm for discrete combination optimization
Yimin Zhou, Zhifei Li, Chaofang Hu · 2017
There are a lot of typical statistical problems in discrete combination optimization, including integer linear programming, covering problem, knapsack problem, graph theory, network flow and dispatching. As for the NPC (Non-deterministic Polynomial complete) problems, many algorithms have been developed for the discrete optimization where the heuristic algorithm is one kind of the important and effective methods. In this paper, a new swarm intelligent algorithm is proposed, combined with BPSO (Binary Particle Swarm Optimization), GA (Genetic Algorithm) and maximum difference calculation, to solve the TSP and Knapsack two typical discrete combination optimal problems. The proposed algorithm can search the historical memory and differentiated search strategy is introduced to keep the diversity of the group so as to select the elite gene features as the candidates. Experiments are designed and performed to analyze the convergence of the algorithm and the solutions are obtained in high-dimensional searching space. As for the binary combination problem, results demonstrate that the developed algorithm has faster convergence speed and higher quality compared to the traditional swarm intelligent algorithms.