Nature's way of optimizing
type: Item
instance of: scholarly article
title: Nature's way of optimizing
zbMATH Open document ID: 0949.90075
DOI: 10.1016/S0004-3702(00)00007-2
published in: Artificial Intelligence
publication date: 2000-08-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/cond-mat/9901351
review text: We propose a general-purpose method for finding high-quality solutions to hard optimization problems, inspired by self-organizing processes often found in nature. The method, called extremal optimization, successively eliminates extremely undesirable components of sub-optimal solutions. Drawing upon models used to simulate far-from-equilibrium dynamics, it complements approximation methods inspired by equilibrium statistical physics, such as simulated annealing. With only one adjustable parameter, its performance proves competitive with, and often superior to, more elaborate stochastic optimization procedures. We demonstrate it here on two classic hard optimization problems: graph partitioning and the traveling salesman problem.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 1493172
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: heuristics
zbMATH Keywords: local search
zbMATH Keywords: graph partitioning
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: self-organized criticality
author: Stefan Boettcher
author: Allon G. Percus
Wikidata QID: Q62599736
MaRDI profile type: MaRDI publication profile
cites work: Recent directions in netlist partitioning: a survey
cites work: Q4353479
cites work: Extremal optimization of graph partitioning at the percolation threshold
cites work: Genetic algorithm and graph partitioning
cites work: Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
cites work: Q4198056
cites work: Future paths for integer programming and links to artificial intelligence
cites work: Q4079017
cites work: Q4038710
cites work: Q4365133
cites work: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
cites work: Optimization by simulated annealing
cites work: Combining simulated annealing with local search heuristics
cites work: Q4237477
cites work: Equation of state calculations by fast computing machines
cites work: Q4495496
OpenAlex ID: W2170123469
DBLP publication ID: journals/ai/BottcherP00
Recommended article: Q4409015
Recommended article: Q4668581
Recommended article: Theoretical and numerical studies of extremal optimization
Recommended article: Q4660716
Recommended article: Computational Science – ICCS 2005
description: scientific article; zbMATH DE number 1493172