An evolutionary strategy based on partial imitation for solving optimization problems

DOI10.1016/J.PHYSA.2016.07.053zbMATH Open1400.90309arXiv1602.04186OpenAlexW2271974295MaRDI QIDQ1620009FDOQ1620009

Authors: Marco Alberto Javarone 

Publication date: 13 November 2018

Published in: Physica A (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1602.04186

Recommendations

• Evolution Strategies in Optimization Problems
• scientific article; zbMATH DE number 2013517
• scientific article; zbMATH DE number 1785849
• An empirical study about the usefulness of evolution strategies to solve constrained optimization problems
• scientific article; zbMATH DE number 1247171

zbMATH Keywords

combinatorial optimizationheuristicsocial influence

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Ant colony optimization theory: a survey
• Statistical field theory. An introduction to exactly solved models in statistical physics.
• Evolution strategies. A comprehensive introduction
• Quantum computation and quantum information. 10th anniversary edition
• Title not available (Why is that?)
• Discrete choice with social interactions
• ``Neural computation of decisions in optimization problems
• Title not available (Why is that?)
• A novel population initialization method for accelerating evolutionary algorithms
• SOCIOPHYSICS: A REVIEW OF GALAM MODELS
• Notes on ferromagnetic diluted \(p\)-spin model
• Shannon-Theoretic Limits on Noisy Compressive Sampling
• The mean field Ising model trough interpolating techniques
• Modeling Brain Function
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• Hierarchical neural networks perform both serial and parallel processing
• Statistical Physics and Network Optimization Problems

This page was built for publication: An evolutionary strategy based on partial imitation for solving optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1620009)