Description:
A discrete version of state transition algorithm is proposed to solve the traveling salesman problem. Three special operators named swap, shift and symmetry transformations are presented for discrete optimization problem. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm efficient, a parametric study is investigated. Experiments are carried out to test its performance, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than other traditional combinatorial optimization methods, indicating that state transition algorithm has strong adaptability.
Description:
Canonical duality theory provides a unified framework which can transform a nonconvex primal minimization problem to a canonical dual maximization problem over a convex domain without duality gap. But the global optimality is guaranteed by a certain positive definite condition and such condition is not always satisfied. The goal of this thesis aims to explore possible techniques that can be used to solve global optimization problems based on the canonical duality theory. Firstly, an algorithmic framework for canonical duality theory is established, which shows that the canonical dual algorithms can be developed in four aspects under the positive definite condition explicitly or implicitly, namely, (i) minimizing the primal problem, (ii) maximizing the canonical dual problem, (iii) solving a nonlinear equation caused by total complementary function, and (iv) solving a nonlinear equation caused by canonical dual function. Secondly, we show that if there exists a critical point of the canonical dual problem in the positive definite domain, by solving an equivalent semidefinite programming (SDP) problem, the corresponding global solution to the primal problem can be obtained easily via off-the-shelf software packages. A specific canonical dual algorithm is given for each problem, including sum of fourth-order polynomials minimization, nonconvex quadratically constrained quadratic program (QCQP), and boolean quadratic program (BQP). Thirdly, we propose a canonical primal-dual algorithm framework based on the total complementary function. Convergence analysis is discussed from the perspective of variational inequalities (VIs) and contraction methods. Specific canonical primal-dual algorithms for sum of fourth-order polynomials minimization is given as well. And a real-world application to the sensor network localization problem is illustrated. Next, a canonical sequential reduction approach is proposed to recover the approximate or global solution for the BQP problem. By fixing some previously known components, the original problem can be reduced sequentially to a lower dimension one. This approach is successfully applied to the well-known maxcut problem. Finally, we discuss the canonical dual approach applied to continuous time constrained optimal control. And it shows that the optimal control law for the n-dimensional constrained linear quadratic regulator can be achieved precisely via one-dimensional canonical dual variable, and for the optimal control problem with concave cost functional, an approximate solution can be obtained by introducing a linear perturbation term.
Description:
Canonical duality theory provides a unified framework which can transform a nonconvex primal minimization problem to a canonical dual maximization problem over a convex domain without duality gap. But the global optimality is guaranteed by a certain positive definite condition and such condition is not always satisfied. The goal of this thesis aims to explore possible techniques that can be used to solve global optimization problems based on the canonical duality theory. Firstly, an algorithmic framework for canonical duality theory is established, which shows that the canonical dual algorithms can be developed in four aspects under the positive definite condition explicitly or implicitly, namely, (i) minimizing the primal problem, (ii) maximizing the canonical dual problem, (iii) solving a nonlinear equation caused by total complementary function, and (iv) solving a nonlinear equation caused by canonical dual function. Secondly, we show that if there exists a critical point of the canonical dual problem in the positive definite domain, by solving an equivalent semidefinite programming (SDP) problem, the corresponding global solution to the primal problem can be obtained easily via off-the-shelf software packages. A specific canonical dual algorithm is given for each problem, including sum of fourth-order polynomials minimization, nonconvex quadratically constrained quadratic program (QCQP), and boolean quadratic program (BQP). Thirdly, we propose a canonical primal-dual algorithm framework based on the total complementary function. Convergence analysis is discussed from the perspective of variational inequalities (VIs) and contraction methods. Specific canonical primal-dual algorithms for sum of fourth-order polynomials minimization is given as well. And a real-world application to the sensor network localization problem is illustrated. Next, a canonical sequential reduction approach is proposed to recover the approximate or global solution for the BQP problem. By fixing some previously known components, the original problem can be reduced sequentially to a lower dimension one. This approach is successfully applied to the well-known maxcut problem. Finally, we discuss the canonical dual approach applied to continuous time constrained optimal control. And it shows that the optimal control law for the n-dimensional constrained linear quadratic regulator can be achieved precisely via one-dimensional canonical dual variable, and for the optimal control problem with concave cost functional, an approximate solution can be obtained by introducing a linear perturbation term.
Description:
A recently new intelligent optimization algorithm called discrete state transition algorithm is considered in this study, for solving unconstrained integer optimization problems. Firstly, some key elements for discrete state transition algorithm are summarized to guide its well development. Several intelligent operators are designed for local exploitation and global exploration. Then, a dynamic adjustment strategy "risk and restoration in probability" is proposed to capture global solutions with high probability. Finally, numerical experiments are carried out to test the performance of the proposed algorithm compared with other heuristics, and they show that the similar intelligent operators can be applied to ranging from traveling salesman problem, boolean integer programming, to discrete value selection problem, which indicates the adaptability and flexibility of the proposed intelligent elements. (C) 2015 Elsevier B.V. All rights reserved.
Description:
A recently new intelligent optimization algorithm called discrete state transition algorithm is considered in this study, for solving unconstrained integer optimization problems. Firstly, some key elements for discrete state transition algorithm are summarized to guide its well development. Several intelligent operators are designed for local exploitation and global exploration. Then, a dynamic adjustment strategy "risk and restoration in probability" is proposed to capture global solutions with high probability. Finally, numerical experiments are carried out to test the performance of the proposed algorithm compared with other heuristics, and they show that the similar intelligent operators can be applied to ranging from traveling salesman problem, boolean integer programming, to discrete value selection problem, which indicates the adaptability and flexibility of the proposed intelligent elements. (C) 2015 Elsevier B.V. All rights reserved.
Description:
In this paper, the stable trajectory of Logistic Map has been investigated by canonical duality theory from the perspective of global optimization. Numerical result of our method shows that it totally differs from traditional chaotic solution solved by Euler method. In addition, we have applied our method to three well-known standard benchmarks in global optimization. Numerical simulations are given to illustrate the effectiveness of the main results.
Description:
In this study, a population-based continuous state transition algorithm (STA) is investigated into continuous constrained optimization problems. After an analysis of the advantages and disadvantages of two well-known constraint-handling techniques, penalty function method and feasibility preference method, a two-stage strategy is proposed for constrained STA, in which, the feasibility preference method is adopted in the early stage of an iteration process whilst it is changed to the penalty function method in the later stage. Several benchmark tests are given to evaluate the performance of the proposed method, and the experimental results show that the constrained STA with a two-stage strategy outperforms other single strategy in terms of both global search ability and solution precision.