Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem

DOI10.1016/J.ARTINT.2019.03.001MaRDI QIDQ2321315zbMATH OpenOpenAlexWikidataFDO

Authors Pietro S. Oliveto, Donya Yazdani, Doğan Çörüş

Publication date 28 August 2019

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.00300, http://eprints.whiterose.ac.uk/144833/1/1-s2.0-S000437021830345X-main.pdf

zbMATH Keywords

approximation algorithmsartificial immune systemsevolutionary algorithmsmakespan schedulingrandomized search heuristics

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Approximation algorithms (68W25) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Typical artificial immune system (AIS) operators such as hypermutations with mutation potential and ageing allow to efficiently overcome local optima from which evolutionary algorithms (EAs) struggle to escape. Such behaviour has been shown for artificial example functions constructed especially to show difficulties that EAs may encounter during the optimisation process. {color{black}However, no evidence is available indicating that these two operators have similar behaviour also in more realistic problems.} In this paper we perform an analysis for the standard NP-hard partition problem from combinatorial optimisation and rigorously show that hypermutations and ageing allow AISs to efficiently escape from local optima where standard EAs require exponential time. As a result we prove that while EAs and random local search (RLS) may get trapped on 4/3 approximations, AISs find arbitrarily good approximate solutions of ratio (1+$epsilon$) {color{black}within $n(epsilo{n}^{-(2/epsilon)-1})(1-epsilon{)}^{-2}{e}^3{2}^{2/epsilon}+2n^3{2}^{2/epsilon}+2n^3$ function evaluations in expectation. This expectation is polynomial in the problem size and exponential only in $1/epsilon$}.

Recommendations

• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• On the utility of the population size for inversely fitness proportional mutation rates
• On the effectiveness of immune inspired mutation operators in some discrete optimization problems
• scientific article; zbMATH DE number 1974042
• Problem space local search for number partitioning

Cites work

• Algorithms for Scheduling Independent Tasks
• Analyzing evolutionary algorithms. The computer science perspective.
• Approximating vertex cover using edge-based representations
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Black-box search by unbiased variation
• Bounds on Multiprocessing Timing Anomalies
• Drift analysis and evolutionary algorithms revisited
• From black-box complexity to designing new genetic algorithms
• scientific article; zbMATH DE number 6019547 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2013466 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Improved time complexity analysis of the simple genetic algorithm
• Introduction to algorithms.
• More effective crossover operators for the all-pairs shortest path problem
• On easiest functions for mutation operators in bio-inspired optimisation
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• On the runtime analysis of the simple genetic algorithm
• Probability and Computing
• Reducibility among combinatorial problems
• Scheduling independent tasks to reduce mean finishing time
• Scheduling. Theory, algorithms, and systems
• STACS 2005
• Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems
• Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms

Cited in

(12)

• Does comma selection help to cope with local optima?
• Self-adjusting evolutionary algorithms for multimodal optimization
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• On the utility of the population size for inversely fitness proportional mutation rates
• A binary algebraic differential evolution for the multidimensional two-way number partitioning problem
• Lower bounds from fitness levels made easy
• Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution
• Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem
• On some similarity of finite sets (and what we can say today about certain old problem)
• Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation

This page was built for publication: Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem

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