An evolutionary strategy based on partial imitation for solving optimization problems

DOI10.1016/J.PHYSA.2016.07.053MaRDI QIDQ1620009zbMATH OpenOpenAlexFDO

Authors Marco Alberto Javarone

Publication date 13 November 2018

Published in Physica A (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 43585 (Why is no real title available?)
• scientific article; zbMATH DE number 3497315 (Why is no real title available?)
• scientific article; zbMATH DE number 1277441 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• A Mathematical Theory of Communication
• A novel population initialization method for accelerating evolutionary algorithms
• Ant colony optimization theory: a survey
• Discrete choice with social interactions
• Evolution strategies. A comprehensive introduction
• Hierarchical neural networks perform both serial and parallel processing
• Modeling Brain Function
• Notes on ferromagnetic diluted p-spin model
• Quantum computation and quantum information. 10th anniversary edition
• SOCIOPHYSICS: A REVIEW OF GALAM MODELS
• Shannon-Theoretic Limits on Noisy Compressive Sampling
• Statistical field theory. An introduction to exactly solved models in statistical physics.
• Statistical physics and network optimization problems
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• The mean field Ising model trough interpolating techniques
• ``Neural computation of decisions in 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)