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

DOI10.1016/J.ARTINT.2019.03.001zbMATH Open1478.68283arXiv1806.00300OpenAlexW2924776344WikidataQ128137074 ScholiaQ128137074MaRDI QIDQ2321315FDOQ2321315

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

Publication date: 28 August 2019

Published in: Artificial Intelligence (Search for Journal in Brave)

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$}.

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

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

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)

Cites Work

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

Cited In (10)

• Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation
• 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 some similarity of finite sets (and what we can say today about certain old problem)
• Self-adjusting evolutionary algorithms for multimodal optimization
• A binary algebraic differential evolution for the multidimensional two-way number partitioning problem
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem

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)