Source-linked AI summary
An optimization algorithm inspired by the States of Matter that improves the balance between exploration and exploitation
Erik Cuevas, Alonso Echavarria, Marte A. Ramirez-Ortegon
TL;DR
Evolutionary algorithms need to balance exploration and exploitation, yet the paper describes this as an unresolved issue. SMS addresses it by modeling individuals as interacting molecules and scheduling gas, liquid, and solid phases with progressively different movement behaviors. On standard benchmark functions, SMS achieves good performance over competing evolutionary methods, with the authors attributing this to better exploration–exploitation capability.
Problem
Evolutionary algorithms must balance discovering new search-space regions with refining existing solutions, but the exploration–exploitation dilemma remains unresolved.
Method
SMS models individuals as interacting molecules and divides optimization into gas, liquid, and solid stages with different exploration–exploitation ratios.
Results
SMS achieves good performance over GSA, PSO, DE, and TPSO on standard benchmark functions, while all Wilcoxon pairwise p-values are below 0.05.
Takeaways & Limitations
The reported results support SMS as an evolutionary approach that improves exploration–exploitation balance while preserving good search capabilities.
Abstract
from arXiv · showhide
The ability of an Evolutionary Algorithm (EA) to find a global optimal solution depends on its capacity to find a good rate between exploitation of found so far elements and exploration of the search space. Inspired by natural phenomena, researchers have developed many successful evolutionary algorithms which, at original versions, define operators that mimic the way nature solves complex problems, with no actual consideration of the exploration/exploitation balance. In this paper, a novel nature-inspired algorithm called the States of Matter Search (SMS) is introduced. The SMS algorithm is based on the simulation of the states of matter phenomenon. In SMS, individuals emulate molecules which interact to each other by using evolutionary operations which are based on the physical principles of the thermal-energy motion mechanism. The algorithm is devised by considering each state of matter at one different exploration/exploitation ratio. The evolutionary process is divided into three phases which emulate the three states of matter: gas, liquid and solid. In each state, molecules (individuals) exhibit different movement capacities. Beginning from the gas state (pure exploration), the algorithm modifies the intensities of exploration and exploitation until the solid state (pure exploitation) is reached. As a result, the approach can substantially improve the balance between exploration/exploitation, yet preserving the good search capabilities of an evolutionary approach.
1. Introduction
Evolutionary algorithms must balance exploration of new search-space regions with exploitation of promising neighborhoods, but this remains unresolved. The paper introduces SMS, which uses matter-state-inspired stages and operators to improve that balance while retaining evolutionary search capabilities.
- 1. Introduction: Exploration visits new search-space points, whereas exploitation refines previously visited neighborhoods; global optimization requires balancing both.Pure exploration increases discovery capacity but reduces precision, while pure exploitation can drive the process toward local optima.
- 1. Introduction: Popular algorithms such as PSO, DE, and GSA can suffer ineffective exploration, premature convergence, or loss of diversity.The paper describes control-parameter settings and other proposals as attempts to address this problem.
- 1. Introduction: Changing control parameters alone can leave algorithms vulnerable to premature convergence, while adding operators alone can increase computational cost and weaken exploitation.The paper therefore motivates combining parameter control with diversity-improving operators.
- 1. Introduction: SMS models individuals as interacting molecules and uses thermal-energy-inspired evolutionary operations together with changing operation parameters.The operations are intended to increase population diversity and avoid particle concentration within a local minimum.
- 1. Introduction: SMS divides evolution into gas, liquid, and solid stages, assigning each state a different exploration–exploitation ratio.The process moves from stronger exploration toward stronger exploitation across the three states.
- 1. Introduction: Experiments on standard benchmark functions report good performance over competing evolutionary methods, attributed to SMS’s exploration–exploitation capability.The comparison includes well-known methods and recent variants using diversity-preservation schemes.
2. States of matter
The paper describes gas, liquid, and solid as states distinguished by particle forces and movement capacities. These physical differences motivate progressively smaller molecular displacements in the SMS analogy.
- 2. States of matter: Gas molecules have high kinetic energy, weak intermolecular effects, and large separations, allowing maximum displacement and no definite shape or volume.A gas occupies its container and is represented by displacement 1ρ.
- 2. States of matter: Liquid molecules remain mobile under more restrictive intermolecular forces, producing movement smaller than gas movement but larger than solid movement.A liquid has no definite shape, which is determined by its container.
- 2. States of matter: Solid particles are closely packed and strongly constrained, so they vibrate around minimal displacement rather than move freely.Solids have stable shape and volume and are represented by minimal displacement 3ρ.
- 2. States of matter: SMS uses the three matter states as stages with different exploration–exploitation ratios and individual behaviors.The algorithm treats individuals as molecules whose interactions follow thermal-energy motion principles.
3. States of matter search (SMS)
SMS models individuals as molecules whose movements combine direction, collision, attraction, random-position, and best-element updating operators. Its three asymmetric phases progressively shift from exploration toward exploitation through gas, liquid, and solid states.
- 3.1 Definition of Operators: Molecules move in multidimensional space using operators inspired by thermal-energy motion, including direction, collision, attraction, and random positions.The direction vector controls movement; attraction incorporates the best-so-far molecule, while random positions model molecular randomness.
- 3.1 Definition of Operators: Attraction updates each molecule’s direction toward the best-so-far individual while reducing the relative weight of its past direction as iterations advance.This interaction encourages local neighborhood search and avoids rapid concentration of information among particles.
- 3.1 Definition of Operators: Collisions exchange molecules’ direction vectors when their distance falls below a proximity threshold, helping preserve diversity during the search.The collision radius controls when particles are forced out of overlapping regions, enhancing exploratory behavior.
- 3.2 States of Matter: The algorithm allocates 50% of iterations to gas exploration, 40% to liquid exploration–exploitation, and 10% to solid exploitation.The same general procedure is iteratively applied within each state.
- 3.2 States of Matter: Gas uses severe displacements, frequent collisions, and random positions; liquid moderates these effects, while solid suppresses collisions and random generation so molecules mainly vibrate.Gas sets movement and random-position intensities near one, liquid uses ρ between 0.3 and 0.6, and solid sets ρ near zero.
4. Experimental results
SMS was evaluated against GSA, PSO, DE, and TPSO on 24 benchmark functions spanning four function categories. Across the reported experiments, SMS generally achieved better optimization results, with statistically significant differences in average best-so-far values and stronger performance on several multimodal functions.
- Experimental setup: 24 benchmark functions were organized into unimodal, multimodal, fixed-dimension multimodal, and GECCO contest categories.The comparisons included GSA, PSO, DE, and TPSO, with results averaged over 30 runs.
- Unimodal test functions: SMS delivered better results than GSA, PSO, DE, and TPSO for all unimodal functions tested.Performance was evaluated using Average Best-so-far, Median Best-so-far, and Standard Deviation over 30 runs.
- Statistical analysis: All Wilcoxon rank-sum p-values comparing SMS with GSA, PSO, DE, and TPSO were less than 0.05.The test used average best-so-far data at a 5% significance level.
- Multimodal test functions: SMS yielded much better solutions than the other methods for multimodal functions 8f, 9f, 10f, and 11f.These functions were evaluated at dimension n=30 with a maximum of 1000 iterations.