State transition algorithm
This article may require copy editing for improvement of English: clearly not written by a native speaker.. (August 2018) (Learn how and when to remove this template message)
In global optimization, a state transition algorithm (STA) is an iterative method that generates a sequence of improving approximate solutions for an optimization problem. Due to its intrinsic properties, an STA has the ability to find a global optimal solution in probability and can guarantee an optimal solution.
The state transition algorithm  was first proposed by Zhou et al. It is a stochastic global optimization method and aims to find a possible global or approximate optimal solution in a reasonable amount of time. In the context of the STA, a solution to an optimization problem is regarded as a state, and updating a solution can be regarded as a state transition. Using the state-space representation, it describes solutions updating in a unified framework, and the execution operators to update solutions are expressed as state transition matrices, which make it easy to understand and flexible to implement:
- stands for a current state, corresponding to a solution to an optimization problem;
- is a function of and historical states;
- is the fitness value at ;
- are state transformation matrices, which can be considered as execution operators;
- is the objective function or evaluation function.
As a stochastic global optimization method, STA has the following properties:
- globality, STA has the ability to search the whole space;
- optimality, STA can guarantee to find an optimal solution;
- convergence, the sequence generated by STA is convergent;
- rapidity, inherent advantages existing in STA to reduce the computational complexity;
- controllability, STA can control the search space flexibly.
Continuous state transition algorithm (CSTA)
In continuous STA, is a continuous variable, and four special state transformation operators are designed to generate new candidate solutions.
State transformation operators
(1) Rotation transformation (RT)
where is a positive constant, called the rotation factor, is a random matrix with its entries being uniformly distributed random variables defined on the interval [-1,1], and is the 2-norm of a vector. The rotation transformation has the functionality to search in a hypersphere with maximal radius , that is to say, .
(2) Translation transformation (TT)
where is a positive constant, called the translation factor, and is a uniformly distributed random variable defined on the interval [0,1]. The translation transformation has the functionality to search along a line from to at the starting point with maximal length .
(3) Expansion transformation (ET)
where is a positive constant, called the expansion factor, and is a random diagonal matrix with its entries obeying the Gaussian distribution. The expansion transformation has the functionality to expand the entries in to the range of , searching in the whole space.
(4) Axesion transformation (AT)
where is a positive constant, called the axesion factor, and is a random diagonal matrix with its entries obeying the Gaussian distribution and with only one random position having nonzero value. The axesion transformation aims to search along the axes.
Regular neighbourhood and sampling
For a given solution , a candidate solution is generated by using one time of the aforementioned state transformation operators. Since the state transition matrix in each state transformation is random, the generated candidate solution is not unique. Based on a given point, it is not difficult to imagine that a regular neighbourhood will be automatically formed when using certain state transformation operators.
Since the entries in state transition matrix obey certain stochastic distribution, for any given solution, the new candidate becomes a random vector and its corresponding solution (the value of a random vector) can be regarded as a sample. Considering that any two random state transition matrices in each state transformation operator are independent, several times of state transformation (called the degree of search enforcement, for short) based on the given solution are performed for certain state transformation operator, yielding samples.
An update strategy
As mentioned above, based on the incumbent best solution, a total number of SE candidate solutions are sampled. A new best solution is selected from the candidate set by virtue of the evaluation function, denoted as . Then, an update strategy based on greedy criterion is used to update the incumbent best solution:
- , if
- , otherwise
Algorithm procedure of the basic continuous STA
With the state transformation operators, sampling technique and update strategy, the basic continuous STA can be described as follows:
Step 1: Initiate a random solution and set
Step 2: Generate samples based on incumbent using Expansion Transformation, and then update the incumbent using greedy criterion incorporating samples and incumbent . Let us denote the best solution in samples, if , then perform the Translation Transformation similarly to update the incumbent ;
Step 3: Generate samples based on incumbent using Rotation Transformation, and then update the incumbent using greedy criterion incorporating samples and incumbent . If , then perform the Translation Transformation similarly to update the incumbent ;
Step 4: Generate samples based on incumbent using Axesion Transformation, and then update the incumbent using greedy criterion incorporating samples and incumbent . If , then perform the Translation Transformation similarly to update the incumbent ;
Step 5: set , if , set , else set , and return to Step 2 until the maximum of iterations is met.
Philosophy behind the continuous STA
- The expansion transformation contributes to the globality since it has the functionality to search the whole space;
- The rotation transformation benefits the optimality since when is sufficiently small, the incumbent best solution becomes a local optimal solution;
- The update strategy based on greedy criterion contributes to the convergence, that is to say, the sequence is convergent due to and the monotone convergence theorem;
- The sampling technique (it can avoid complete enumeration) and the alternate use of state transformation operators help to reduce computational complexity;
- The parameters like can be adjusted to control the search space.
Applications of STA
STA has found a variety of applications, like image segmentation, task assignment, energy consumption in the alumina evaporation process, resolution of overlapping linear sweep voltammetric peaks, PID controller design, volterra series identification, and system modeling, and it is shown that STA is comparable to most existing global optimization methods.
- X.J., Zhou; C.H., Yang; W.H., Gui (2012). "State transition algorithm". Journal of Industrial and Management Optimization. 8 (4): 1039–1056.
- X.J., Zhou; C.H., Yang; W.H., Gui (2014). "Nonlinear system identification and control using state transition algorithm". Applied Mathematics and Computation. 226: 169–179.
- X. J., Zhou; D.Y., Gao; A.R., Simpson (2016). "Optimal design of water distribution networks by discrete state transition algorithm". Engineering Optimization. 48 (4): 603–628.
- X. J., Zhou; D.Y., Gao; C.H., Yang; W.H., Gui (2016). "Discrete state transition algorithm for unconstrained integer optimization problems". Neurocomputing. 173: 864–874.
- Friedland, Bernard (2005). Control System Design: An Introduction to State-Space Methods. Dover. ISBN 0-486-44278-0.
- J., Han; X.J., Zhou; C.H., Yang; W.H., Gui (2015). "A multi-threshold image segmentation approach using state transition algorithm". Proceedings of the 34th Chinese Control Conference: 2662–2666.
- T.X., Dong; X.J., Zhou; C.H., Yang; W.H., Gui (2015). "A discrete state transition algorithm for the task assignment problem". Proceedings of the 34th Chinese Control Conference: 2692–2697.
- Y.L., Wang; H.M., He; X.J., Zhou; C.H., Yang; Y.F., Xie. "Optimization of both operating costs and energy efficiency in the alumina evaporation process by a multi-objective state transition algorithm". Canadian Journal of Chemical Engineering. 94: 53–65.
- G.W., Wang; C.H., Yang; H.Q., Zhu; Y.G., Li; X.W., Peng; W.H., Gui. "State-transition-algorithm-based resolution for overlapping linear sweep voltammetric peaks with high signal ratio". Chemometrics and Intelligent Laboratory Systems. 151: 61–70.
- G., Saravanakumar (2015). "Tuning of Multivariable Decentralized PIP Controller Using State Transition Algorithm". STUDIES IN INFORMATICS AND CONTROL. 24 (4): 367–378.
- G., Saravanakumar (2016). "Lagrangian-based state transition algorithm for tuning multivariable decentralised controller". International Journal of Advanced Intelligence Paradigms. 8 (3): 303–317.
- C., Wang (2016). "Volterra Series identification Based on State Transition Algorithm with Orthogonal Transformation". TELKOMNIKA (Telecommunication Computing Electronics and Control). 14 (1): 171–180.
- Y., Xie; S., Wei; X., Wang; S., Xie; C., Yang (2016). "A new prediction model based on the leaching rate kinetics in the alumina digestion process". Hydrometallurgy. 164: 7–14.