Discrete state transition algorithm for unconstrained integer optimization problems

doi:10.1016/j.neucom.2015.08.041

Neurocomputing

Volume 173, Part 3, 15 January 2016, Pages 864-874

https://doi.org/10.1016/j.neucom.2015.08.041 Get rights and content

Highlights

•
A systematic formulation of discrete state transition algorithm is firstly proposed, including the state space representation and five key elements.
•
A dynamic adjustment strategy called “risk and restoration in probability” is designed to improve the ability to escape from local optima.
•
The proposed algorithm is successfully integrated with several classical integer optimization problems.

Abstract

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.

Introduction

In this paper, we consider the following unconstrained integer optimization problem $\min f (x),$ where, $x = (x_{1}, \dots, x_{n}) \in Z^{n}$ .

Generally speaking, the above optimization problem is NP-hard, which cannot be solved in polynomial time. A direct method is to adopt the so-called “divide-and-conquer” strategy, which separates the optimization problem into several subproblems and then solve these subproblems step by step. Branch and bound (B&B), branch and cut (B&C), and branch and price (B&P) belong to this kind; however, these methods are essentially in exponential time. An indirect method is to relax the optimization problem by loosening its integrality constraints to continuity and then solve the continuous relaxation problem or its Lagrangian dual problem, including LP-based relaxation, SDP-based relaxation, and Lagrangian relaxation. Nevertheless, when rounding off the relaxation solution, they may cause some infeasibility or can only get approximate solutions, and when using Lagrangian dual, there may exist duality gap between the primal and the dual problem [4], [6], [8], [11].

On the other hand, some stochastic algorithms, such as genetic algorithm (GA) [1], [21], simulated annealing (SA) [9], [23], ant colony optimization (ACO) [3], [15], are also widely used for integer optimization problems, which aim to obtain “good solutions” in reasonable time. In terms of the concepts of state and state transition, a new heuristic search algorithm called state transition algorithm (STA) has been proposed recently, which exhibits excellent global search ability in continuous function optimization [24], [25], [26], [27], [28]. In [20], three intelligent operators (geometrical operators) named swap, shift and symmetry have been designed for discrete STA to solve the traveling salesman problem (TSP), and it shows that the discrete STA outperforms its competitors with respect to both time complexity and search ability. In [29], a discrete state transition algorithm is successfully applied to the optimal design of water distribution networks. To better develop discrete STA for medium-size or large-size discrete optimization problems, in the study, we firstly build the framework of discrete state transition algorithm and propose five key elements for discrete STA, of which, the representation of a decision variable, the local and global operators and the dynamic adjustment strategy are mainly studied. Four geometrical operators named swap, shift, symmetry and substitute are designed, which are intelligent due to their adaptability and flexibility in various types of integer optimization. The mixed strategies of “greedy criterion” and “risk and restoration in probability” are proposed, in which, “greedy criterion” and “restoration in probability” are used to guarantee a good convergence performance, and “risk a bad solution in probability” aims to escape from local optimality. Some applications ranging from traveling salesman problem, boolean integer programming, to discrete value selection problem are studied. Experimental results have demonstrated the effectiveness and efficiency of the proposed method.

The main contribution and novelty of this paper is three-fold, which can be summarized as follows: (1) a systematic formulation of discrete state transition algorithm is firstly proposed, including the state space representation and five key elements; (2) a dynamic adjustment strategy called “risk and restoration in probability” is designed to improve the ability to escape from local optima; (3) the proposed algorithm is successfully integrated with several classical integer optimization problems.

Section snippets

The framework of discrete state transition algorithm

If a solution to a specific optimization problem is described as a state, then the transformation to update the solution becomes a state transition. Without loss of generality, the unified form of generation of solution in discrete state transition algorithm can be described as ${\begin{matrix} x_{k + 1} = A_{k} (x_{k}) \oplus B_{k} (u_{k}) \\ y_{k + 1} = f (x_{k + 1}) \end{matrix},$ where, $x_{k} \in Z^{n}$ stands for a current state, corresponding to a solution of a specific optimization problem; u_k is a function of x_k and historical states; $A_{k} (\cdot)$ , $B_{k} (\cdot)$ are transformation

Theoretical analysis of the discrete STA

In this section, we analyze the convergence performance, global search ability, and time complexity of the discrete state transition algorithm.

Similarly to the continuous case, we give the definition of local and global minima for unconstrained integer optimization as follows: $f (x^{⁎}) \leq f (x), \forall x \in Z^{n},$ $f (x^{⁎}) \leq f (x), \forall | x^{⁎} - x | < 1, x^{⁎}, x \in Z^{n}$ If (4a) is satisfied, we say that $x^{⁎}$ is a global minimizer, and if (4b) is satisfied, the $x^{⁎}$ is called a local minimizer.

Theorem 1

The sequence generated by discrete STA can converge to a

Application for traveling salesman problem

Suppose $N = {1, \dots, n}$ is the set of cities, the traveling salesman problem (TSP) can be described as: given a set of n cities and the distance d_ij for each pair of cities i and j, find a roundtrip of minimal total length visiting each city exactly once. Typically, the traveling salesman problem is usually modeled as the following two representations [17]:

(LP-TSP): $\min_{x_{ij}} \sum_{i = 1}^{n} \sum_{j = 1}^{n} x_{ij} d_{ij} s . t . \sum_{i = 1}^{n} x_{ij} = 1, \forall j \in N \sum_{j = 1}^{n} x_{ij} = 1, \forall i \in N \sum_{i \in S} \sum_{j \in \bar{S}} x_{ij} \geq 1, \forall S \subset N, \bar{S} \subset N ⧹ S x_{ij} \in {0, 1}, \forall i, j \in N,$ where, the decision variable x_ij is

Application for boolean integer programming

In boolean integer programming (BIP), a solution is comprised of a series of boolean values ( $I = {0, 1}$ or $I = {- 1, 1}$ ). Swap, shift and symmetry operators can also be applied to internal transformation (operators aiming to change the internal components of a sequence), and another operator called substitute is designed for external transformation (operator aiming to bring alien components into a sequence). It should be noted that $I = {0, 1}$ is the same to $I = {- 1, 1}$ under such a circumstance, although

Application for discrete value selection

Typically, the formulation of discrete value selection (DVS) problem is different from the model in (1), because the domain is defined as follows: $x_{i} \in U = {u_{1}, \dots, u_{m}}, u_{j} \in R, j = 1, \dots, m .$ By introducing a linear transformation $x_{i} = \sum_{j = 1}^{K} u_{j} y_{ij},$ where $\sum_{j = 1}^{K} y_{ij} = 1, y_{ij} \in {0, 1},$ then the discrete value selection can be rewritten to the equivalent constrained boolean integer programming problem [22].

In discrete STA, we only use the index of u_j to represent a solution, for example, a solution $(1, 3, 2)$ is corresponding to $(u_{1},$

Conclusion

In this paper, a new intelligent optimization algorithm named discrete state transition algorithm is studied for integer optimization problem. It is the first time to build the framework for discrete state transition algorithm, and five key elements are discussed to better develop the algorithm. The representation of a feasible solution and the dynamic adjustment strategy are mainly studied. Various applications have shown the adaptability and flexibility of the designed intelligent operators

Acknowledgments

We would also like to thank the anonymous reviewers for their valuable comments and suggestions that helped improve the quality of this paper. This work was supported by the National Science Foundation for Distinguished Young Scholars of China (61025015), the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (61321003), the National Natural Science Foundation of China (Grant No. 61503416) and the State Key Program of National Natural Science of China

Xiaojun Zhou received his Bachelor's degree in Automation in 2009 from Central South University, Changsha, China and received the Ph.D. degree in Applied Mathematics in 2014 from Federation University Australia. He is currently a lecturer at Central South University, Changsha, China. His main interests include modeling, optimization and control of complex industrial process, optimization theory and algorithms, state transition algorithm, duality theory and their applications.

References (29)

K. Deep et al.
A real coded genetic algorithm for solving integer and mixed integer optimization problems
Appl. Math. Comput.
(2009)
X.T. Geng et al.
Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search
Appl. Soft Comput.
(2011)
P.W. Poon et al.
Genetic algorithm crossover operators for ordering applications
Comput. Oper. Res.
(1995)
M. Schlüter et al.
Extended ant colony optimization for non-convex mixed integer nonlinear programming
Comput. Oper. Res.
(2009)
T. Yokota et al.
Genetic algorithm for non-linear mixed integer programming problems and its applications
Comput. Ind. Eng.
(1996)
D.F. Zhang et al.
A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems
Eur. J. Oper. Res.
(2010)
X.J. Zhou et al.
Nonlinear system identification and control using state transition algorithm
Appl. Math. Comput.
(2014)
Z.H. Ahmed
Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator
Int. J. Biom. Bioinform.
(2010)
M. Dorigo et al.
Ant colony systema cooperative learning approach to the traveling salesman problem
IEEE Trans. Evol. Comput.
(1997)
K. Darby-Dowman et al.
Developments in linear and integer programming
J. Oper. Res. Soc.
(2002)

A.M. Geoffrion et al.

Integer programming algorithmsa framework and state-of-the-art survey

Manag. Sci.

(1972)

B. Hajek

Cooling schedules for optimal annealing

Math. Oper. Res.

(1988)

M. Jünger et al.

50 Years of Integer Programming 1958–2008

(2010)

S. Kirkpatrick et al.

Optimization by simulated annealing

Science

(1983)

Cited by (75)

An interactive feature selection method based on multi-step state transition algorithm for high-dimensional data
2023, Knowledge-Based Systems
Feature selection (FS) has been extensively employed in classification tasks to reduce data dimensionality and enhance prediction performance effectively. Recently, hybrid filter-wrapper methods have exhibited promising results in FS problems by leveraging both advantages. However, the inadequate integration of the filter method into the wrapper method leads to the hybrid algorithms exhibiting poor efficiency in classification as datasets grow in complexity. In this paper, an interactive feature selection framework based on state transition algorithm (STA) is proposed to address high-dimensional FS problems. In this framework, prior knowledge of the features is formed via the mutual information-based filter method. The STA is a powerful search engine that traverses the feature space in the wrapper stage. Moreover, an external trainer with prior knowledge will guide the exploration direction of STA in a simple but efficient way to accelerate the search process. And a self-adaptive mechanism is proposed to adjust the prior knowledge during the search process. Specifically, the external trainer establishes the interactive loop, while the self-adaptive mechanism aims to feed feature information back to the loop. In addition, the search process is prevented from being trapped in local optima by employing a multi-step STA, which allows for continuous transformations of the solution in probability. Finally, the proposed FS method is applied to various public classification datasets. The experimental results demonstrate that the proposed method is a highly competitive FS method, outperforming several state-of-the-art algorithms in generating an optimal subset of features.
Discrete komodo algorithm for traveling salesman problem[Formula presented]
2023, Applied Soft Computing
This work presents a Discrete Komodo Algorithm (DKA) to solve the traveling salesman problem (TSP). Inspired by the Komodo Mlipir Algorithm, a swarm intelligence algorithm based on the behavior of komodo dragons, DKA introduces an enhanced edge-construction operator and a novel edge-destruction operator to explore the discrete search space of TSP. To prioritize the exploration of potential edges, DKA uses a Priority Queue that stores all possible edges with their weights, and its counts appear on tour as its priority. The edges with smaller weights and counts have higher probabilities of being selected for the tour. DKA is tested with 45 different TSP instances from TSPLIB. Experimental results show that DKA guarantees produced the best-known solution for small test problems for up to 24 nodes, and the best solutions are within 6.92% of the known optimal solutions. Compared with some of the previous algorithms, DKA outperforms the recent state-of-the-art algorithms and is significantly better than classical metaheuristic algorithms by achieving a lower relative error.
Population-based discrete state transition algorithm with decomposition and knowledge guidance applied to electrolytic cell maintenance decision
2023, Applied Soft Computing
With continuous scale expansion and higher safety requirements in modern aluminum electrolysis, it is more and more necessary to realize an intelligent decision-making for shutting-down and running of aluminum reduction cells (SRARC). However, this realization needs to solve a special single-objective constrained integer optimization problem (SCIOP), where the key challenge is a high requirement for the constraint-handling ability. In this paper, based on a high-scalability intelligent optimization algorithm called discrete state transition algorithm (DSTA), a population-based DSTA with decomposition and knowledge guidance (PDSTA/D-S) is proposed. This PDSTA/D-S improves the constraint-handling ability of DSTA from three aspects. Firstly, a hybrid framework combining DSTA with genetic algorithm is proposed. Secondly, a decomposition-based multi-objective optimization for constrained problems with uniformly-angled weighted sum vector is proposed. Thirdly, the manual decision-making is transferred to a knowledge-based transformation operator of DSTA. Therefore, a high-level performance of decision-making for SRARC can be obtained. The related experiments on a SRARC which is built from the practical production have demonstrated that the proposed PDSTA/D-S not only makes an effective improvement of DSTA from three aspects, but also has a more advanced performance compared with other existing high-performance intelligent optimization algorithms.
A review on varying-parameter convergence differential neural network
2022, Neurocomputing
Inspired by the nature of actual dynamics systems with time-varying parameters, varying-parameter convergence differential neural network (termed as VP-CDNN) has been put forward and played a crucial role in obtaining the real-time solution of algebraic equations and optimization problems. Plenty of fruitful literatures report that such a neural network breaks the bottlenecks of the conventional algorithms and presents superior convergence performance and strong anti-noise capability in the time-varying problem solving. This paper presents an overall review about VP-CDNN in different mathematical problems solving such as time-varying quadratic-programming equation, time-varying Sylvester equation, nonlinear and nonconvex equation and so on. Besides its extension forms such as anti-noise VP-CDNN, finite-time VP-CDNN, fuzzy VP-CDNN and discrete-time VP-CDNN are briefly introduced in mathematical problems solving. Additionally, the applications of VP-CDNN in robot motion planning, unmanned aerial vehicles, venture investment and other applications are illustrated for practical implementation. The conclusion summarizes the superiority of VP-CDNN and indicates several future research direction.
Discrete sparrow search algorithm for symmetric traveling salesman problem
2022, Applied Soft Computing
Citation Excerpt :
Traditional exact methods such as cutting planes [9], branch-and-bound [10,11], dynamic programming [12,13], and Lagrangian dual [14] are effective for small and medium-size problems, where they can achieve theoretical optima through rigorous mathematical theoretical derivations. However, as the number of cities grows, traditional methods are no longer effective, their solution time increases substantially and they do not always obtain optimal solutions [15]. A new approach, the heuristic algorithm, has been chosen to solve this problem.
The traveling salesman problem (TSP) is one of the most intensively studied problems in computational mathematics. This paper proposes a swarm intelligence approach using a discrete sparrow search algorithm (DSSA) with a global perturbation strategy to solve the problem. Firstly, the initial solution in the population is generated by the roulette-wheel selection. Secondly, the order-based decoding method is introduced to complete the update of the sparrow position. Then, the global perturbation mechanism combined with Gaussian mutation and swap operator is adopted to balance exploration and exploitation capability. Finally, the 2-opt local search is integrated to further improve the quality of the solution. Those strategies enhance the solution’s quality and accelerate the convergence. Experiments on 34 TSP benchmark datasets are conducted to investigate the performance of the proposed DSSA. And statistical tests are used to verify the significant differences between the proposed DSSA and other state-of-the-art methods. Results show that the proposed method is more competitive and robust in solving the TSP.
Wind power forecasting based on stacking ensemble model, decomposition and intelligent optimization algorithm
2021, Neurocomputing
Wind power forecasting has high application value in power systems. However, due to the intermittence and fluctuation of wind power, it is difficult to predict wind power effectively using a single forecasting model. Therefore, to improve the accuracy and stability of wind power forecasting, an ensemble learning model based on stacking framework is proposed in this paper. First, several decomposition techniques are used to pre-process the original wind power data and an optimal decomposition method is selected through experiments. Then, a quadratic interpolation based on state transition algorithm is proposed to optimize the parameters of the Bernstein polynomial model and the weights of the Hermite neural network (HNN) to obtain two base learners. Finally, the Spearman correlation coefficient is used to analyze the correlation of several base learners. The base learners with low correlation and strong prediction ability are selected as the first-layer forecasting model of the stacking model, and the HNN is used as the second-layer prediction model to obtain the stacking ensemble model. To verify the effectiveness of the proposed model, a large number of comprehensive experiments are carried out with wind power data from a wind farm in Xinjiang, China. Experimental results show that the proposed model has higher prediction accuracy and stability than other single forecasting models.

View all citing articles on Scopus

David Yang Gao is the Alex Rubinov Professor of Mathematics at Federation University Australia and a research professor of engineering science at the Australian National University. His research has been mainly focused on duality principles in mathematical physics and general complex systems. He has published nine books (including one monograph and one handbook) and about 140 scientific and philosophic papers. His main research contributions include a canonical duality-triality theory, which can be used to model complex phenomena within a unified framework. This theory has been used successfully for solving a large class of nonconvex/nonsmooth problems in nonlinear sciences as well as a series of well-known NP-hard problems in global optimization and computational science. The main part of the canonical duality theory, i.e., the complementary-dual variational principle he proposed in 1997 solved a 50-years open problem in nonlinear elasticity and is playing an important role in large deformation solid mechanics and nonlinear finite element analysis.

Chunhua Yang received her M.Eng. in Automatic Control Engineering and her Ph.D. in Control Science and Engineering from Central South University, China in 1988 and 2002 respectively, and was with the Electrical Engineering Department, Katholieke Universiteit Leuven, Belgium from 1999 to 2001. She is currently a full professor in the School of Information Science & Engineering, Central South University. Her research interests include modeling and optimal control of complex industrial process, intelligent control system, and fault-tolerant computing of real-time systems.

Weihua Gui received the degree of the B.Eng. (Automatic Control Engineering) and the M.Eng. (Control Science and Engineering) from Central South University, Changsha, China in 1976 and 1981, respectively. From 1986 to 1988 he was a visiting scholar at Universitat-GH-Duisburg, Germany. He is a member of the Chinese Academy of Engineering and has been a full professor in the School of Information Science & Engineering, Central South University, Changsha, China, since 1991. His main research interests are in modeling and optimal control of complex industrial.

View full text

Discrete state transition algorithm for unconstrained integer optimization problems

Highlights

Abstract

Introduction

Section snippets

The framework of discrete state transition algorithm

Theoretical analysis of the discrete STA

Application for traveling salesman problem

Application for boolean integer programming

Application for discrete value selection

Conclusion

Acknowledgments

Appl. Math. Comput.

Appl. Soft Comput.

Comput. Oper. Res.

Comput. Oper. Res.

Comput. Ind. Eng.

Eur. J. Oper. Res.

Appl. Math. Comput.

Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator

Int. J. Biom. Bioinform.

Ant colony systema cooperative learning approach to the traveling salesman problem

IEEE Trans. Evol. Comput.

Developments in linear and integer programming

J. Oper. Res. Soc.