Source-linked AI summary
State Transition Algorithm
Xiaojun Zhou, Chunhua Yang, Weihua Gui
TL;DR
The paper reframes continuous optimization as state transitions to address the limitations of gradient-based local information. It proposes transformation-based state transition algorithms and evaluates them on 10 benchmark functions, finding good global search ability and convergence accuracy, while leaving control-parameter design insufficiently studied.
Problem
Gradient-based iterative methods are computationally difficult and provide only local information, motivating a state-transition view of global optimization.
Method
The paper models solutions as states and uses state-transition operators, including rotation, expansion, translation, and axesion, with communication and intermittent exchange for high-dimensional optimization.
Results
Across 10 benchmark functions, state transition algorithms show fine global search ability and convergence accuracy compared with distinguished optimization algorithms.
Takeaways & Limitations
State transition algorithms offer a non-nature-inspired optimization approach that exploits function-space structure and supports global search and convergence.
Takeaways & Limitations
The control parameters are not studied deeply and are determined by experimental experience or simplicity, with occasional failures on f4 and f7.
Abstract
from arXiv · showhide
In terms of the concepts of state and state transition, a new heuristic random search algorithm named state transition algorithm is proposed. For continuous function optimization problems, four special transformation operators called rotation, translation, expansion and axesion are designed. Adjusting measures of the transformations are mainly studied to keep the balance of exploration and exploitation. Convergence analysis is also discussed about the algorithm based on random search theory. In the meanwhile, to strengthen the search ability in high dimensional space, communication strategy is introduced into the basic algorithm and intermittent exchange is presented to prevent premature convergence. Finally, experiments are carried out for the algorithms. With 10 common benchmark unconstrained continuous functions used to test the performance, the results show that state transition algorithms are promising algorithms due to their good global search capability and convergence property when compared with some popular algorithms.
1. Introduction.
The paper introduces state transition algorithm as a metaheuristic random-search method for continuous nonlinear optimization, motivated by the broad use and limitations of existing optimization approaches.
- Optimization methods are widely used across engineering applications, including system design, planning, analysis, management, control, and parameter adjustment.
- Existing optimization methods include deterministic, evolutionary, metaheuristic, direct-search, and gradient-based approaches.
- The state transition algorithm is founded on state and state-transition concepts and belongs to metaheuristic random search.
- The paper focuses on rotation, translation, expansion, and axesion operators, plus communication strategy for optimization.
- The study evaluates the algorithm on unconstrained continuous optimization problems using ten benchmark functions.
2. The basic state transition algorithm.
The basic state transition algorithm represents solutions as states and generates new candidates through transformation operators, balancing exploration and exploitation with greedy selection and adjustable parameters.
- State representation: An optimization solution is represented as a state, while algorithm operators and solution updates form state transitions.
- State representation: The state-transition model expresses a new state using transition matrices, the current state, and a function of current and historical states.
- Transformation operators: Rotation searches locally in a hypersphere, translation searches along a line, expansion explores the whole space, and axesion strengthens single-dimensional search.
- Algorithm process: STA generates candidate solution sets through four operators and selects a new state using the same greedy criterion as basic random optimization.
- Search balance: Rotation supports exploitation, expansion supports exploration, translation helps maintain their balance, and axesion strengthens single-dimensional search.
- Parameter adjustment: Search enforcement controls search intensity and computational complexity, while α, β, γ, and δ control the four transformation factors.
3. Communication strategy into state transition algorithm.
STAII extends the individual-based state transition algorithm with a population of states that share information through crossover. Intermittent exchange regulates this communication to balance information sharing against premature convergence.
- Population-based approach: STAII uses a population of states, with each individual developing through state transformation and self learning.The number of states is denoted by SN.
- Crossover operator: The proposed crossover exchanges or preserves each component of a pair of individuals completely.This operation is used for communication among states.
- Intermittent exchange: High-frequency communication can make individuals imitate one another and cause premature convergence.The communication frequency is denoted by CF.
- Intermittent exchange: Intermittent exchange controls communication by allowing individual contact only at a specified frequency.Each state communicates with all other states when the exchange condition is satisfied.
- STAII framework: The algorithm performs self learning through four state transformation operators and applies communication intermittently during the iterative search.The pseudocode invokes self learning each iteration and communication when mod(iter, CF)=0.
- Experiments: Experiments compare STAI and STAII with RCGA, CLPSO, and SaDE on two- and ten-dimensional functions.The first experiment targets two-dimensional functions, while the second tests ten-dimensional functions.
4. Experiments and results.
Experiments evaluated STAI and STAII on ten benchmark functions in two and ten dimensions against RCGA, CLPSO, and SaDE. Across the tests, STAs generally showed strong search ability and faster convergence, although occasional failures remained in ten-dimensional cases.
- Test setup: Ten benchmark functions, including seven multidimensional and three two-dimensional functions, were used to evaluate the algorithms.The experiments covered both two-dimensional and ten-dimensional optimization settings.
- Test setup: Thirty independent trials used population size 30 and a maximum of 1000 iterations for each run.STAI and STAII parameters were reported separately in Tables 2 and 3.
- Function-wise results: On Spherical and Rastrigin functions, STAs found the global optimum reliably, with faster convergence than the other algorithms in both dimensional settings.For Rastrigin, STAI and STAII also had better ten-dimensional statistical performance, especially on the worst result.
- Function-wise results: STAII performed especially strongly on Griewank, achieving the fastest convergence and highest solution precision among the tested algorithms.For ten-dimensional Griewank, STAII was the only method described as having excellent statistical performance.
- Function-wise results: For Rosenbrock, only SaDE and the STAs found the ten-dimensional best with low probability, while SaDE had higher solution precision and STAII better statistics than STAI.STAs still converged faster than the other algorithms on this function.
- Overall results: STAs generally converged faster than the comparison algorithms and often achieved higher solution precision across the tested functions.The reported average-fitness curves were used to assess search ability and convergence performance.
- Limitations: The method occasionally failed to find the global optimum on ten-dimensional f4 and f7, suggesting that experimentally chosen global-search transformation factors were not always effective.Rotation supports local search, whereas expansion, translation, and axesion support global search.
5. Conclusion.
The paper presents STA as a simple, geometrically interpretable approach to unconstrained optimization, using four state transformations and communication strategies for high-dimensional search. Benchmark tests report effective global search and convergence, while control-parameter selection remains insufficiently studied.
- STA uses rotation, translation, expansion, and axesion transformations for unconstrained optimization.
- Communication strategy and intermittent exchange are introduced to strengthen high-dimensional search and prevent premature convergence.
- Tests on 10 benchmark functions show fine global search ability and convergence accuracy compared with distinguished optimization algorithms.
- STA control parameters are determined mainly by experimental experience or simplicity and are not studied deeply.