×

Evolutionary strategy of lexicographic order for combinational problem. (Chinese. English summary) Zbl 1240.90493

Summary: In order to construct a fast and effective algorithm to solve large-scale combinational problems in desirable computational time rather than being trapped in weakness as with some existing algorithms, a novel encoding approach is proposed in this paper which applies a one-to-one mapping from a discrete space to a continuous integer section. Assembled with a successful exploration and exploitation mechanism of evolutionary strategy, the performances of the algorithm are largely promoted. Since the one-to-one mapping is between codes and combinational vectors, the new scheme only provides feasible solutions, which can help to avoid redundant computation existing in some algorithms effectively and the search space is further reduced. Secondly, a queue of elites is added in evolutionary mechanism combined with some particular learning strategy. The queue is refreshed frequently in evolution. This can help the algorithm to maintain better gene blocks. Finally, its convergence to a global optimal solution with probability one is proved. The numerical experiments based on the Benchmarks of the traveling salesman problem library (TSPLIB) show the effectiveness of the proposed algorithm.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
68R15 Combinatorics on words
PDFBibTeX XMLCite