A Deterministic Annealing Neural Network Algorithm for Some Classical Graph Problems
一種求解部分經典圖論問題的確定性退火神經網絡算法
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution | |
---|---|
Supervisors/Advisors |
|
Award date | 20 Aug 2024 |
Link(s)
Permanent Link | https://scholars.cityu.edu.hk/en/theses/theses(21aa54dd-eaa3-458a-a2e0-4f4bbefbb9a7).html |
---|---|
Other link(s) | Links |
Abstract
Graph theory is an ancient subject. In the field of discrete mathematics, graph theory occupies a dominant position. Many problems in practice can be divided into equivalent graph theory problems. Graph theory is an adequate mathematical model for algorithm design in solving many engineering problems, which is convenient for computational analysis and computer storage. Many algorithmic problems are directly or indirectly related to graphs. For example, many NP-complete problems are graph theory problems or problems related to "graphs." Solving graph theory problems is significant to academic research and industrial applications.
The annealing algorithm is a common optimization technique that is vital in engineering. This algorithm simulates the annealing process and finds the minimum value of the system energy with the system temperature reduction. The deterministic annealing algorithm is a variant of the simulated annealing algorithm, first proposed by Rose et al. and used in the vector quantization algorithm. In this thesis, we select several typical graph theory problems (the max-bisection problem, the min-bisection problem, the maximum clique problem, and the traveling salesman problem) and introduce several different barrier functions to develop the deterministic annealing neural network algorithms.
The max-bisection problem has extensive applications in network engineering, making it imperative to develop effective methods to solve this problem. However, efficient computation of this problem remains challenging due to its NP-hard computational complexity. In this thesis, we transform the max-bisection problem to an artificial linearly constrained optimization problem and develop a deterministic annealing neural network algorithm by introducing a square-root barrier function. The barrier parameter of this function acts as the temperature in the annealing process and decreases from a large positive number to zero. The initial value of the barrier parameter promises that the artificial problem is convex and can be easily solved at the beginning of the descending process. The solution to the original max-bisection problem is finally obtained through a descent algorithm, in which the bound limit of the solution is always satisfied as long as the iteration step length is less than one. Numerical results demonstrate that the proposed algorithm has several advantages over the approximation algorithms and metaheuristic methods.
The min-bisection problem is also an NP-hard optimization problem. This problem has attracted much attention from researchers for its extensive applications in scientific computing, VLSI design, etc. However, due to the computational complexity of this problem, it is challenging to solve this problem optimally with an exact solution. We adopt the deterministic annealing neural network algorithm in the second chapter to approximate a solution to the min-bisection problem. We transform the min-bisection problem into an equivalent linearly constrained continuous optimization problem and propose a deterministic annealing neural network algorithm. We derive this algorithm from introducing a square-root barrier function, where the barrier parameter acts as the temperature in the annealing procedure and decreases from a sufficiently large positive number to zero. Numerical results show that the deterministic annealing neural network algorithm is much faster than other methods while they produce more or less the same quality solution.
The maximum clique problem is a classic combinatorial optimization problem in graph theory, which has a wide range of applications in fault diagnosis, scheme selection, signal transmission, market analysis, computer vision, and other fields. Many exact algorithms have been proposed to solve the maximum clique problem. However, with the increase of the size of the problem (the increase of vertices and the increase of edge density), the time complexity of solving the problem becomes higher and higher, and the exact algorithms are powerless to solve this NP-complete problem effectively. In this thesis, we first transform the maximum clique problem into a general nonconvex quadratic programming problem with box constraints. Then, we propose a deterministic annealing neural network algorithm based on the barrier function to approximate a solution to the maximum clique problem. In the annealing procedure of the barrier parameter, the algorithm searches for the optimal solution to the problem in a descent direction, with the property that the constraints are always satisfied. Numerical results demonstrate that the algorithm proposed in this thesis always generates an optimal or near-optimal solution to the maximum clique problem while using less time than the classical branch and bound algorithm.
The traveling salesman problem is a typical NP-hard problem in combinatorial optimization problem domain, which is very important in operations research and theoretical computer science. Since the feasible solution to this problem is a complete arrangement of all vertices, a combinatorial explosion occurs as the number of vertices increases, and the exact algorithms become powerless as the size of the problem increases. This thesis proposes a globally convergent deterministic annealing neural network algorithm to solve the traveling salesman problem. The algorithm employs the Lagrange and barrier function iterative method, where the Lagrange function is used to deal with the linear equality constraints, and the barrier function iterative method is used to force the solution to move to the global optimal solution. The barrier parameter acts as the temperature in the annealing process and decreases to zero from a sufficiently large number. The solution to the original traveling salesman problem is finally obtained through a descent direction. At each iteration of the calculation process of the feasible descent direction, the Lagrange multipliers are updated with a globally convergent iterative procedure. The computer simulations of the problems are made, and the numerical experiments show that solutions generated from the deterministic annealing neural network algorithm are always global or near-global optimal.
The annealing algorithm is a common optimization technique that is vital in engineering. This algorithm simulates the annealing process and finds the minimum value of the system energy with the system temperature reduction. The deterministic annealing algorithm is a variant of the simulated annealing algorithm, first proposed by Rose et al. and used in the vector quantization algorithm. In this thesis, we select several typical graph theory problems (the max-bisection problem, the min-bisection problem, the maximum clique problem, and the traveling salesman problem) and introduce several different barrier functions to develop the deterministic annealing neural network algorithms.
The max-bisection problem has extensive applications in network engineering, making it imperative to develop effective methods to solve this problem. However, efficient computation of this problem remains challenging due to its NP-hard computational complexity. In this thesis, we transform the max-bisection problem to an artificial linearly constrained optimization problem and develop a deterministic annealing neural network algorithm by introducing a square-root barrier function. The barrier parameter of this function acts as the temperature in the annealing process and decreases from a large positive number to zero. The initial value of the barrier parameter promises that the artificial problem is convex and can be easily solved at the beginning of the descending process. The solution to the original max-bisection problem is finally obtained through a descent algorithm, in which the bound limit of the solution is always satisfied as long as the iteration step length is less than one. Numerical results demonstrate that the proposed algorithm has several advantages over the approximation algorithms and metaheuristic methods.
The min-bisection problem is also an NP-hard optimization problem. This problem has attracted much attention from researchers for its extensive applications in scientific computing, VLSI design, etc. However, due to the computational complexity of this problem, it is challenging to solve this problem optimally with an exact solution. We adopt the deterministic annealing neural network algorithm in the second chapter to approximate a solution to the min-bisection problem. We transform the min-bisection problem into an equivalent linearly constrained continuous optimization problem and propose a deterministic annealing neural network algorithm. We derive this algorithm from introducing a square-root barrier function, where the barrier parameter acts as the temperature in the annealing procedure and decreases from a sufficiently large positive number to zero. Numerical results show that the deterministic annealing neural network algorithm is much faster than other methods while they produce more or less the same quality solution.
The maximum clique problem is a classic combinatorial optimization problem in graph theory, which has a wide range of applications in fault diagnosis, scheme selection, signal transmission, market analysis, computer vision, and other fields. Many exact algorithms have been proposed to solve the maximum clique problem. However, with the increase of the size of the problem (the increase of vertices and the increase of edge density), the time complexity of solving the problem becomes higher and higher, and the exact algorithms are powerless to solve this NP-complete problem effectively. In this thesis, we first transform the maximum clique problem into a general nonconvex quadratic programming problem with box constraints. Then, we propose a deterministic annealing neural network algorithm based on the barrier function to approximate a solution to the maximum clique problem. In the annealing procedure of the barrier parameter, the algorithm searches for the optimal solution to the problem in a descent direction, with the property that the constraints are always satisfied. Numerical results demonstrate that the algorithm proposed in this thesis always generates an optimal or near-optimal solution to the maximum clique problem while using less time than the classical branch and bound algorithm.
The traveling salesman problem is a typical NP-hard problem in combinatorial optimization problem domain, which is very important in operations research and theoretical computer science. Since the feasible solution to this problem is a complete arrangement of all vertices, a combinatorial explosion occurs as the number of vertices increases, and the exact algorithms become powerless as the size of the problem increases. This thesis proposes a globally convergent deterministic annealing neural network algorithm to solve the traveling salesman problem. The algorithm employs the Lagrange and barrier function iterative method, where the Lagrange function is used to deal with the linear equality constraints, and the barrier function iterative method is used to force the solution to move to the global optimal solution. The barrier parameter acts as the temperature in the annealing process and decreases to zero from a sufficiently large number. The solution to the original traveling salesman problem is finally obtained through a descent direction. At each iteration of the calculation process of the feasible descent direction, the Lagrange multipliers are updated with a globally convergent iterative procedure. The computer simulations of the problems are made, and the numerical experiments show that solutions generated from the deterministic annealing neural network algorithm are always global or near-global optimal.