Search results for: Pietro S. Oliveto

Items from 1 to 11 out of 11 results

article

On the Analysis of Trajectory-Based Search Algorithms: When is it Beneficial to Reject Improvements?

Samadhi Nallaperuma, Pietro S. Oliveto, Jorge Pérez Heredia, Dirk Sudholt

Algorithmica > 2019 > 81 > 2 > 858-885

We investigate popular trajectory-based algorithms inspired by biology and physics to answer a question of general significance: when is it beneficial to reject improvements? A distinguishing factor of SSWM (strong selection weak mutation), a popular model from population genetics, compared to the Metropolis algorithm (MA), is that the former can reject improvements, while the latter always accepts...

article

How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism

Pietro S. Oliveto, Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, more

Algorithmica > 2018 > 80 > 5 > 1604-1633

Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function...

article

On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation

Dogan Corus, Jun He, Thomas Jansen, Pietro S. Oliveto, more

Algorithmica > 2017 > 78 > 2 > 714-740

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that OneMax is an easiest function with unique optimum while Trap...

chapter

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

Pietro S. Oliveto, Carsten Witt

Lecture Notes in Computer Science > Parallel Problem Solving from Nature – PPSN X > Formal Theory > 82-91

Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on the optimization time of EAs. However, this drift theorem is tedious to read and to apply since it requires two bounds on the moment-generating (exponential) function of the drift. A recent...

chapter

On the Analysis of the Immune-Inspired B-Cell Algorithm for the Vertex Cover Problem

Thomas Jansen, Pietro S. Oliveto, Christine Zarges

Lecture Notes in Computer Science > Artificial Immune Systems > Theory of Immunological Computation > 117-131

The runtime of the immune inspired B-Cell Algorithm (BCA) for the NP-hard vertex cover problem is analysed. It is the first theoretical analysis of a nature-inspired heuristic as used in practical applications for a realistic problem. Since the performance of BCA in combinatorial optimisation strongly depends on the representation an encoding heuristic is used. The BCA outperforms mutation-based evolutionary...

article

Improved time complexity analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

Theoretical Computer Science > 2015 > 605 > C > 21-41

A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μ≤n1/8−ε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μ≤n1/4−ε which is an improvement...

article

Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

Pietro S. Oliveto, Christine Zarges

Theoretical Computer Science > 2015 > 561 > Part A > 37-56

Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the Balance function for which the poor expected performance of the (1+1) EA at low frequencies of change has been shown in the literature. We analyse the impact of populations and diversity mechanisms towards the robustness of evolutionary algorithms with respect to frequencies...

article

On the runtime analysis of the Simple Genetic Algorithm

Pietro S. Oliveto, Carsten Witt

Theoretical Computer Science > 2014 > 545 > Complete > 2-19

For many years it has been a challenge to analyze the time complexity of Genetic Algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known Simple Genetic Algorithm (SGA) for OneMax. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to μ⩽n1/8−ε for some arbitrarily...

article

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

Pietro S. Oliveto, Carsten Witt

Algorithmica > 2011 > 59 > 3 > 369-386

chapter

On the Convergence of Immune Algorithms

Vincenzo Cutello, Giuseppe Nicosia, Mario Romeo, Pietro S. Oliveto

2007 IEEE Symposium on Foundations of Computational Intelligence > 409 - 415

2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007)

Immune Algorithms have been used widely and successfully in many computational intelligence areas including optimization. Given the large number of variants of each operator of this class of algorithms, this paper presents a study of the convergence properties of Immune Algorithms in general, conducted by examining conditions which are sufficient to prove their convergence to the global optimum of...

article

Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results

Pietro S. Oliveto, Jun He, Xin Yao

International Journal of Automation and Computing > 2007 > 4 > 3 > 281-293

Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the (1+1)-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated...

Filter options

Publication date

Set your own date range

INFONA - science communication portal

Search results for: Pietro S. Oliveto

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Publication type

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options