NDLI: Non-uniform mutation rates for problems with unknown solution lengths

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

Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering

On the behaviour of the (1,λ)-es for a simple constrained problem

Elementary bit string mutation landscapes

On the practicality of optimal output mechanisms for co-optimization algorithms

Handling expensive optimization with large noise

Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics

The logarithmic hypervolume indicator

Approximating the distribution of fitness over hamming regions

The role of selective pressure when solving symmetric functions in polynomial time

Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets

Analyzing the impact of mirrored sampling and sequential selection in elitist evolution strategies

Using markov-chain mixing time estimates for the analysis of ant colony optimization

Abstract convex evolutionary search

Faster black-box algorithms through higher arity operators

Non-uniform mutation rates for problems with unknown solution lengths

Adaptive population models for offspring populations and parallel evolutionary algorithms

On the movement of vertex fixed points in the simple GA

Simple max-min ant systems and the optimization of linear pseudo-boolean functions

Using multivariate quantitative genetics theory to assist in EA customization

Towards the geometry of estimation of distribution algorithms based on the exponential family

Convergence rates of SMS-EMOA on continuous bi-objective problem classes

Non-uniform mutation rates for problems with unknown solution lengths

Content Provider	ACM Digital Library
Author	Lehre, Per Kristian Cathabard, Stephan Yao, Xin
Abstract	Many practical optimisation problems allow candidate solutions of varying lengths, and where the length of the optimal solution is thereby a priori unknown. We suggest that non-uniform mutation rates can be beneficial when solving such problems. In particular, we consider a mutation operator that flips each bit with a probability that is inversely proportional to the bit position, rather than the bitstring length. The runtime of the (1+1) EA using this mutation operator is analysed rigorously on standard example functions. Furthermore, the behaviour of the new mutation operator is investigated empirically on a real world software engineering problem that has variable, and unknown solution lengths. The results show how the speedup that can be achieved with the new operator depends on the distribution of the solution lengths in the solution space. We consider a truncated geometric distribution, and show that the new operator can yield exponentially faster runtimes for some parameters of this distribution. The experimental results show that the new mutation operator leads to dramatically shorter runtimes on a class of instances of the software engineering problem that is conjectured to have short solutions on average.
Starting Page	173
Ending Page	180
Page Count	8
File Format	PDF
ISBN	9781450306331
DOI	10.1145/1967654.1967670
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Unique input-output sequences Runtime analysis Fsm testing Variable-length solutions Mutation operator Search-based software testing
Content Type	Text
Resource Type	Article

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

Non-uniform Mutation Rates for Problems with Unknown Solution Lengths

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

Runtime analysis of (1+l) EA on computing unique input output sequences

Runtime Analysis of (1+1) EA on Computing Unique Input Output Sequences

Runtime analysis of (1+1) ea on computing unique input output sequences.

Full Theoretical Runtime Analysis of Alternating Variable Method on the Triangle Classification Problem

Crossover can be constructive when computing unique input–output sequences

Automated Unique Input Output sequence generation for conformance testing of FSMs (2006)

A theoretical runtime and empirical analysis of different alternating variable searches for search-based testing

Non-uniform mutation rates for problems with unknown solution lengths

Similar Documents

Non-uniform Mutation Rates for Problems with Unknown Solution Lengths

Solving Problems with Unknown Solution Length at (Almost) No Extra Cost

Runtime analysis of (1+l) EA on computing unique input output sequences

Runtime Analysis of (1+1) EA on Computing Unique Input Output Sequences

Runtime analysis of (1+1) ea on computing unique input output sequences.

Full Theoretical Runtime Analysis of Alternating Variable Method on the Triangle Classification Problem

Crossover can be constructive when computing unique input–output sequences

Automated Unique Input Output sequence generation for conformance testing of FSMs (2006)

A theoretical runtime and empirical analysis of different alternating variable searches for search-based testing

Non-uniform mutation rates for problems with unknown solution lengths