A Genetic Algorithm with randomly shifted Gray codes and local optimizations based on quadratic approximations of the fitness

Résultats de recherche: Contribution à un journal/une revueArticle

Résumé

We present a Genetic Algorithm that we developed in order to address computationally expensive optimization problems. In order to accelerate this algorithm, we establish, generation after generation, quadratic approximations of the fitness in the close neighborhood of the best-so-far individual. We then inject in the population an individual that corresponds to the optimum of this approximation. We also introduce a modified mutation operator that acts on randomly-shifted Gray codes. We show that these techniques lead to the global optimum of typical benchmark problems in 5, 10 and 20 dimensions with a probability of success in one run of the order
of 95-97% and an average number of fitness evaluations of the order of 400−750×n, where n refers to the dimension of the problem.
langueAnglais
Pages195
Nombre de pages196
journalProceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17)
Les DOIs
étatPublié - 2017

Empreinte digitale

Gray Code
Quadratic Approximation
Local Optimization
Fitness
Genetic Algorithm
Global Optimum
Accelerate
Mutation
Benchmark
Optimization Problem
Evaluation
Approximation
Operator

mots-clés

  • genetic algorithm

Citer ceci

@article{080943b138224f59a638592e495a4bf6,
title = "A Genetic Algorithm with randomly shifted Gray codes and local optimizations based on quadratic approximations of the fitness",
abstract = "We present a Genetic Algorithm that we developed in order to address computationally expensive optimization problems. In order to accelerate this algorithm, we establish, generation after generation, quadratic approximations of the fitness in the close neighborhood of the best-so-far individual. We then inject in the population an individual that corresponds to the optimum of this approximation. We also introduce a modified mutation operator that acts on randomly-shifted Gray codes. We show that these techniques lead to the global optimum of typical benchmark problems in 5, 10 and 20 dimensions with a probability of success in one run of the orderof 95-97\{%} and an average number of fitness evaluations of the order of 400−750×n, where n refers to the dimension of the problem.",
keywords = "genetic algorithm",
author = "Alexandre Mayer",
year = "2017",
doi = "10.1145/3067695.3075968",
language = "English",
pages = "195",
journal = "Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO \{textquoteleft}17)",
publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - A Genetic Algorithm with randomly shifted Gray codes and local optimizations based on quadratic approximations of the fitness

AU - Mayer,Alexandre

PY - 2017

Y1 - 2017

N2 - We present a Genetic Algorithm that we developed in order to address computationally expensive optimization problems. In order to accelerate this algorithm, we establish, generation after generation, quadratic approximations of the fitness in the close neighborhood of the best-so-far individual. We then inject in the population an individual that corresponds to the optimum of this approximation. We also introduce a modified mutation operator that acts on randomly-shifted Gray codes. We show that these techniques lead to the global optimum of typical benchmark problems in 5, 10 and 20 dimensions with a probability of success in one run of the orderof 95-97% and an average number of fitness evaluations of the order of 400−750×n, where n refers to the dimension of the problem.

AB - We present a Genetic Algorithm that we developed in order to address computationally expensive optimization problems. In order to accelerate this algorithm, we establish, generation after generation, quadratic approximations of the fitness in the close neighborhood of the best-so-far individual. We then inject in the population an individual that corresponds to the optimum of this approximation. We also introduce a modified mutation operator that acts on randomly-shifted Gray codes. We show that these techniques lead to the global optimum of typical benchmark problems in 5, 10 and 20 dimensions with a probability of success in one run of the orderof 95-97% and an average number of fitness evaluations of the order of 400−750×n, where n refers to the dimension of the problem.

KW - genetic algorithm

U2 - 10.1145/3067695.3075968

DO - 10.1145/3067695.3075968

M3 - Article

SP - 195

JO - Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17)

T2 - Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17)

JF - Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17)

ER -