Kinetic description and convergence analysis of genetic algorithms for global optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909503625101312 |
|---|---|
| author | Borghi, Giacomo Pareschi, Lorenzo |
| author_facet | Borghi, Giacomo Pareschi, Lorenzo |
| contents | Genetic Algorithms (GA) are a class of metaheuristic global optimization methods inspired by the process of natural selection among individuals in a population. Despite their widespread use, a comprehensive theoretical analysis of these methods remains challenging due to the complexity of the heuristic mechanisms involved. In this work, relying on the tools of statistical physics, we take a first step towards a mathematical understanding of GA by showing how their behavior for a large number of individuals can be approximated through a time-discrete kinetic model. This allows us to prove the convergence of the algorithm towards a global minimum under mild assumptions on the objective function for a popular choice of selection mechanism. Furthermore, we derive a time-continuous model of GA, represented by a Boltzmann-like partial differential equation, and establish relations with other kinetic and mean-field dynamics in optimization. Numerical experiments support the validity of the proposed kinetic approximation and investigate the asymptotic configurations of the GA particle system for different selection mechanisms and benchmark problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_08562 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Kinetic description and convergence analysis of genetic algorithms for global optimization Borghi, Giacomo Pareschi, Lorenzo Optimization and Control 65C35, 90C26, 90C59, 35Q90, 35Q20 Genetic Algorithms (GA) are a class of metaheuristic global optimization methods inspired by the process of natural selection among individuals in a population. Despite their widespread use, a comprehensive theoretical analysis of these methods remains challenging due to the complexity of the heuristic mechanisms involved. In this work, relying on the tools of statistical physics, we take a first step towards a mathematical understanding of GA by showing how their behavior for a large number of individuals can be approximated through a time-discrete kinetic model. This allows us to prove the convergence of the algorithm towards a global minimum under mild assumptions on the objective function for a popular choice of selection mechanism. Furthermore, we derive a time-continuous model of GA, represented by a Boltzmann-like partial differential equation, and establish relations with other kinetic and mean-field dynamics in optimization. Numerical experiments support the validity of the proposed kinetic approximation and investigate the asymptotic configurations of the GA particle system for different selection mechanisms and benchmark problems. |
| title | Kinetic description and convergence analysis of genetic algorithms for global optimization |
| topic | Optimization and Control 65C35, 90C26, 90C59, 35Q90, 35Q20 |
| url | https://arxiv.org/abs/2310.08562 |