NDLI: Resampling vs Recombination: a Statistical Run Time Estimation

Please wait, while we are loading the content...

Fast and Powerful Hashing using Tabulation

An Application of Stochastic Differential Equations to Evolutionary Algorithms

Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax

Resampling vs Recombination: a Statistical Run Time Estimation

On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms

Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints

Analysis of the Clearing Diversity-Preserving Mechanism

Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax

Convergence of Factored Evolutionary Algorithms

Hypervolume Subset Selection for Triangular and Inverted Triangular Pareto Fronts of Three-Objective Problems

Quality Gain Analysis of the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions

On the Statistical Learning Ability of Evolution Strategies

Qualitative and Quantitative Assessment of Step Size Adaptation Rules

Linearly Convergent Evolution Strategies via Augmented Lagrangian Constraint Handling

Resampling vs Recombination: a Statistical Run Time Estimation

Content Provider	ACM Digital Library
Author	Kötzing, Timo Friedrich, Tobias Quinzan, Francesco Sutton, Andrew M.
Abstract	Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-off between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.
Starting Page	25
Ending Page	35
Page Count	11
File Format	PDF
ISBN	9781450346511
DOI	10.1145/3040718.3040723
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-01-12
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Ant colony optimization Genetic algorithm Noise Evolutionary algorithm Robustness Crossover Estimation of distribution algorithm
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in