rian.ie - Browse

Author(s)
Institution
Publication types
Funder
Year

Limited By:	Subject = Problem hardness;

3 items found

Sort by

Order

per page

Displaying Results 1 - 3 of 3 on page 1 of 1

Marked Mark

Defining locality as a problem difficulty measure in genetic programming (2012)

Galván-López, Edgar; McDermott, James; O'Neill, Michael; Brabazon, Anthony

Defining locality as a problem difficulty measure in genetic programming (2012)

Galván-López, Edgar; McDermott, James; O'Neill, Michael; Brabazon, Anthony

Abstract:

A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if most genotypic neighbours are mapped to phenotypic neighbours. Locality is seen as a key element in performing effective evolutionary search. It is believed that a representation that has high locality will perform better in evolutionary search and the contrary is true for a representation that has low locality. When locality was introduced, it was the genotype-phenotype mapping in bitstring-based Genetic Algorithms which was of interest; more recently, it has also been used to study the same mapping in Grammatical Evolution. To our knowledge, there are few explicit studies of locality in Genetic Programming (GP). The goal of this paper is to shed some light on locality in GP and use it as an indicator of problem difficulty. Strictly speaking, in GP the g...

http://hdl.handle.net/10197/3512

Marked Mark

From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP (2018)

Escamocher, Guillaume; Siala, Mohamed; O'Sullivan, Barry

From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP (2018)

Escamocher, Guillaume; Siala, Mohamed; O'Sullivan, Barry

Abstract:

Many studies have been conducted on the complexity of Constraint Satisfaction Problem (CSP) classes. However, there exists little theoretical work on the hardness of individual CSP instances. In this context, the backdoor key fraction (BKF) [17] was introduced as a quantifier of problem hardness for individual satisfiable instances with regard to backtracking search. In our paper, after highlighting the weaknesses of the BKF, we propose a better characterization of the hardness of an individual satisfiable CSP instance based on the ratio between the size of the solution space and that of the search space. We formally show that our measure is negatively correlated with instance hardness. We also show through experiments that this measure evaluates more accurately the hardness of individual instances than the BKF.

http://hdl.handle.net/10468/6632

Marked Mark

Neutrality in evolutionary algorithms... what do we know? (2012)

Galván-López, Edgar; Poli, Riccardo; Kattan, Ahmed; O'Neill, Michael; Brabazon, An...

Neutrality in evolutionary algorithms... what do we know? (2012)

Galván-López, Edgar; Poli, Riccardo; Kattan, Ahmed; O'Neill, Michael; Brabazon, Anthony

Abstract:

Over the last years, the effects of neutrality have attracted the attention of many researchers in the Evolutionary Algorithms (EAs) community. A mutation from one gene to another is considered as neutral if this modification does not affect the phenotype. This article provides a general overview on the work carried out on neutrality in EAs. Using as a framework the origin of neutrality and its study in different paradigms of EAs (e.g., Genetic Algorithms, Genetic Programming), we discuss the most significant works and findings on this topic. This work points towards open issues, which the community needs to address.
Science Foundation Ireland
ti, ke, ab, li - TS 02.12 12 month EMBARGO

http://hdl.handle.net/10197/3532

Displaying Results 1 - 3 of 3 on page 1 of 1