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 algorithmsevolutionary algorithmsartificial immune systemsrandomized search heuristicsmakespan scheduling

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) Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

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

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

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)