Initial Version of State Transition Algorithm

Xiaojun Zhou, Chunhua Yang, Weihua Gui

TL;DR

The State Transition Algorithm (STA) is a novel optimization framework that reimagines finding the best solution as a series of "state transitions" rather than just gradient descent or biological evolution. By using three distinct geometric operators—rotation, translation, and expansion—STA provides a simple yet powerful way to balance local fine-tuning with global exploration in both continuous and discrete search spaces.

What Problem Does This Paper Address?

In the world of optimization, there is often a divide between "classical" methods (like steepest descent) and "intelligent" methods (like Genetic Algorithms or Particle Swarm Optimization). Classical methods are mathematically rigorous but often get stuck in local optima, while intelligent methods are robust but can be complex and computationally heavy.

The authors identify a common thread: almost all optimization involves moving from one candidate solution (a state) to another. They propose the State Transition Algorithm to unify these perspectives into a single, flexible framework that is easier to understand and implement, while remaining powerful enough to handle complex, non-linear problems.

Methods

The core of STA is the representation of a solution as a state and the search process as a state transition. The authors define a general state-space transformation: $$x(k+1) = A_k x(k) + B_k u(k)$$

For continuous function optimization, they introduce three specialized operators:

  1. Rotation Transformation: Designed for local search. It explores the vicinity of the current best solution within a "hyper-sphere," controlled by a rotation factor ($\alpha$).
  2. Translation Transformation: Performs a line search along the direction of the last successful move, helping the algorithm "stride" toward better regions quickly.
  3. Expansion Transformation: Aimed at global search. It uses a random diagonal matrix (following a Gaussian distribution) to expand the search into the entire space, helping the algorithm escape local optima.

For discrete problems (like the Traveling Salesman Problem), they introduce a General Elementary Transformation, which involves randomly swapping elements in a sequence to rearrange the solution structure.

Datasets

The algorithm was evaluated using standard mathematical benchmarks rather than traditional "data" sets:

  • Continuous Benchmarks: Sphere function, Rosenbrock function, Rastrigin function, and Griewank function. These were tested across 10, 20, and 30 dimensions.
  • Discrete Benchmark: A 16-city Traveling Salesman Problem (TSP), where the goal is to find the shortest path that visits every city exactly once.

Key Insights and Ideas

  • Unified Framework: The biggest "aha" moment is that classical iterative methods and bio-inspired algorithms can all be viewed as specific types of state transitions. This simplifies the "zoo" of optimization algorithms into a single conceptual model.
  • Geometric Search: Instead of relying on complex biological metaphors (like ants or birds), STA uses clear geometric operations. Rotation handles the "near," Translation handles the "direction," and Expansion handles the "far."
  • Search Enforcement: The authors use a "search enforcement" parameter (set to 32 in their tests), which dictates how many times a transformation is attempted before moving on. This ensures a thorough search of the current state's neighborhood.
  • Dynamic Scaling: In this version, the rotation factor ($\alpha$) decreases exponentially. This allows the algorithm to start with a wide search and gradually narrow its focus to fine-tune the final result.

Key Results

  • High Precision: On the Sphere and Griewank functions, STA consistently found the global optimum (0) across all tested dimensions (10, 20, and 30).
  • Global Search Capability: For the Rastrigin function—notorious for having many local optima—STA successfully found the global optimum in 10 and 20 dimensions, though it struggled slightly as the dimensionality increased to 30.
  • Discrete Success: In the 16-city TSP, the algorithm successfully transitioned from a chaotic initial path (length 113.65) to a highly optimized, clean circuit.
  • Efficiency: The algorithm proved to be "advantageous" for functions like Griewank, where the mean error actually decreased as the problem became more complex (higher dimensions).

Limitations and Future Work

The authors are transparent about this being an "initial version." Some notable limitations include:

  • Rosenbrock Performance: The algorithm struggled to find the absolute global optimum for the Rosenbrock function, though the results were still considered "acceptable."
  • Single-State Focus: This version of STA is not population-based; it only performs transformations on the single "best" state found so far. The authors suggest that future versions could incorporate "group" transitions to improve diversity.
  • Strategy Integration: While the framework is "open" to incorporating other strategies, this paper only explores the basic geometric operators. Future work could involve hybridizing STA with other intelligent search heuristics.

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},
}

Loading related content...

Figure