An Evolutionary Strategy based on Partial Imitation for Solving Optimization Problems
arXiv:1602.04186 · doi:10.1016/j.physa.2016.07.053
Abstract
In this work we introduce an evolutionary strategy to solve combinatorial optimization tasks, i.e. problems characterized by a discrete search space. In particular, we focus on the Traveling Salesman Problem (TSP), i.e. a famous problem whose search space grows exponentially, increasing the number of cities, up to becoming NP-hard. The solutions of the TSP can be codified by arrays of cities, and can be evaluated by fitness, computed according to a cost function (e.g. the length of a path). Our method is based on the evolution of an agent population by means of an imitative mechanism, we define `partial imitation'. In particular, agents receive a random solution and then, interacting among themselves, may imitate the solutions of agents with a higher fitness. Since the imitation mechanism is only partial, agents copy only one entry (randomly chosen) of another array (i.e. solution). In doing so, the population converges towards a shared solution, behaving like a spin system undergoing a cooling process, i.e. driven towards an ordered phase. We highlight that the adopted `partial imitation' mechanism allows the population to generate solutions over time, before reaching the final equilibrium. Results of numerical simulations show that our method is able to find, in a finite time, both optimal and suboptimal solutions, depending on the size of the considered search space.
arXiv comment18 pages, 6 figures
References in corpus (16)
- Statistical physics of social dynamics
- Social diversity and promotion of cooperation in the spatial prisoner's dilemma game
- Sociophysics: A review of Galam models
- Statistical physics of inference: Thresholds and algorithms
- Contrarian Deterministic Effect: the "Hung Elections Scenario"
- Evolutionary game dynamics in a growing structured population
- Majority versus minority dynamics: Phase transition in an interacting two-state spin system
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Social Influences in Opinion Dynamics: the Role of Conformity
- Statistical Physics of the Spatial Prisoner's Dilemma with Memory-Aware Agents
- Opinion dynamics in a three-choice system
- The mean field Ising model trough interpolating techniques
- Hierarchical neural networks perform both serial and parallel processing
- Emerging heterogeneities in Italian customs and comparison with nearby countries
- First-passage phenomena in hierarchical networks
- Topological properties of hierarchical networks