Search

The quantum alternating operator ansatz (QAOA) and its predecessor, the quantum approximate optimization algorithm, are one of the most widely used quantum algorithms for solving combinatorial optimization problems. However, as there is yet no rigorous proof of convergence for the QAOA, we provide one in this paper. The proof involves retracing the connection between the quantum adiabatic algorithm and the QAOA, and naturally suggests a refined definition of the 'phase separator' and 'mixer' keywords. [ABSTRACT FROM AUTHOR]

As a classical combinatorial optimization problem, the traveling salesman problem (TSP) has been extensively investigated in the fields of Artificial Intelligence and Operations Research. Due to being NP-complete, it is still rather challenging to solve both effectively and efficiently. Because of its high theoretical significance and wide practical applications, great effort has been undertaken to solve it from the point of view of intelligent search. In this paper, we propose a two-stage probe-based search optimization algorithm for solving both symmetric and asymmetric TSPs through the stages of route development and a self-escape mechanism. Specifically, in the first stage, a reasonable proportion threshold filter of potential basis probes or partial routes is set up at each step during the complete route development process. In this way, the poor basis probes with longer routes are filtered out automatically. Moreover, four local augmentation operators are further employed to improve these potential basis probes at each step. In the second stage, a self-escape mechanism or operation is further implemented on the obtained complete routes to prevent the probe-based search from being trapped in a locally optimal solution. The experimental results on a collection of benchmark TSP datasets demonstrate that our proposed algorithm is more effective than other state-of-the-art optimization algorithms. In fact, it achieves the best-known TSP benchmark solutions in many datasets, while, in certain cases, it even generates solutions that are better than the best-known TSP benchmark solutions. [ABSTRACT FROM AUTHOR]

Combinatorial optimization problems (COPs) play an important role in both industrial production and theoretical research. As a classical class of optimization algorithms, evolutionary algorithms have shown good performance in COPs. However, as the size of the problem increases, it becomes difficult for evolutionary algorithms to produce satisfactory solutions within the specified time. In recent years, neural network algorithms have been applied to solve COPs and have shown superior effects. Inspired by this, this paper proposes a new algorithm based on graph structure for solving COPs. Through relaxation, COPs are transformed into their corresponding continuous optimization problems. The output state of our algorithm is converted to a discrete solution by approximation method. Compared with previous algorithms, our algorithm can not only solve COPs with general form such as binary quadratic programming (BQP), but also solve COPs with special form, which greatly expands the application scope of neural network algorithms. In addition, our algorithm can be embedded into other problem frameworks such as solving multi-objective combinatorial optimization problem (MOCOP) through scalarization method. A new penalty function is added to the objective function, which enables our algorithm to overcome the inconsistency between the optimal solution of the original problem and the corresponding continuous problem, so that our algorithm can perform well on various problems. Several numerical simulations are used to illustrate the effectiveness of our algorithm in solving COPs. Experimental results show that our algorithm can effectively solve COPs with general form and has a shorter solving time compared to traditional evolutionary algorithms. [ABSTRACT FROM AUTHOR]