Initial version of State Transition Algorithm

Xiaojun Zhou, Chunhua Yang, Weihua Gui

Abstract

In terms of the concepts of state and state transition, a new algorithm—State Transition Algorithm (STA)—is proposed in order to probe into classical and intelligent optimization algorithms. On the basis of state and state transition, it becomes much simpler and easier to understand. As for continuous function optimization problems, three special operators named rotation, translation, and expansion are presented. While for discrete function optimization problems, an operator called general elementary transformation is introduced. Finally, with 4 common benchmark continuous functions and a discrete problem used to test the performance of STA, the experiment shows that STA is a promising algorithm due to its good search capability.

Introduction

The State Transition Algorithm (STA) represents a paradigm shift in optimization, moving away from metaphors of biological evolution or simple gradient descent toward a unified framework based on state-space transformations. By defining the search process as a sequence of transitions between candidate solutions, STA offers a mathematically intuitive approach to solving both continuous and discrete optimization problems. It seeks to bridge the gap between mathematically rigorous classical methods and robust but complex intelligent methods.

Methodology

The fundamental premise of STA is that any optimization process can be modeled as a general state-space transformation: $$x(k+1) = A_k x(k) + B_k u(k)$$ where $x(k)$ is the current state (solution), and $A_k, B_k$ are transformation matrices.

Continuous Operators

For continuous function optimization, the algorithm employs three specialized geometric operators:

  1. Rotation Transformation: A local search operator that explores a "hyper-sphere" around the current best solution, controlled by a rotation factor ($\alpha$).
  2. Translation Transformation: A line search operator that follows the direction of the last successful move, helping the algorithm stride toward better regions quickly.
  3. Expansion Transformation: A global search operator using a random diagonal matrix (following a Gaussian distribution) to expand the search into the entire space, helping the algorithm escape local optima.

Discrete Operators

For discrete optimization, such as the Traveling Salesman Problem (TSP), the algorithm utilizes a General Elementary Transformation. This operator rearranges the solution sequence by swapping elements, effectively navigating the discrete search space through permutation-like matrices.

General Elementary Transformation matrix $E(i,j)$ used for discrete optimization tasks.

Experimental Results

The performance of STA was validated using standard mathematical benchmarks (Sphere, Rosenbrock, Rastrigin, and Griewank) and a 16-city Traveling Salesman Problem.

Continuous Benchmarks

STA demonstrated exceptional precision, finding the global optimum (0) for the Sphere and Griewank functions across 10, 20, and 30 dimensions. For the Rastrigin function—notorious for its many local optima—STA successfully found the global optimum in 10 and 20 dimensions, though performance slightly decreased at 30 dimensions. While the Rosenbrock function proved challenging for finding the absolute global optimum, the results remained within acceptable bounds.

Discrete Benchmark (TSP)

In the 16-city TSP, the algorithm successfully transformed a chaotic initial path into a highly optimized circuit. The iterative application of elementary transformations allowed the state to evolve from a high-cost initial configuration (length 113.65) to a minimal-length path, demonstrating the algorithm's ability to clean up complex discrete circuits.

Comparison of the initial chaotic path (left) and the optimized circuit (right) for a 16-city Traveling Salesman Problem.

Conclusion and Future Work

The initial version of the State Transition Algorithm provides a flexible and powerful framework for optimization. By unifying classical and intelligent methods through geometric state transitions, it simplifies the implementation of complex search strategies.

Key insights include the effectiveness of geometric search operators and the use of "search enforcement" to ensure thorough neighborhood exploration. Future work will focus on expanding this single-state approach into a population-based "group" transition model to improve search diversity and robustness in high-dimensional spaces.

Summary updated

Abstract

In terms of the concepts of state and state transition, a new algorithm-State Transition Algorithm (STA) is proposed in order to probe into classical and intelligent optimization algorithms. On the basis of state and state transition, it becomes much simpler and easier to understand. As for continuous function optimization problems, three special operators named rotation, translation and expansion are presented. While for discrete function optimization problems, an operator called general elementary transformation is introduced. Finally, with 4 common benchmark continuous functions and a discrete problem used to test the performance of STA, the experiment shows that STA is a promising algorithm due to its good search capability.
BibTeX
@inproceedings{zhou2011initial,
  author = {Xiaojun Zhou and Chunhua Yang and Weihua Gui},
  title = {{Initial version of State Transition Algorithm}},
  booktitle = {ICDMA},
  year = {2011},
  url = {https://openreview.net/forum?id=dRd7llfOdl},
}
Figure