2025-11-10T02:34:50.114959

The Runtime of Random Local Search on the Generalized Needle Problem

Doerr, Kelley
In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius $k$ on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter $k$ on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.
academic

Le Temps d'Exécution de la Recherche Locale Aléatoire sur le Problème Généralisé de l'Aiguille

Informations Fondamentales

  • ID de l'article: 2403.08153
  • Titre: The Runtime of Random Local Search on the Generalized Needle Problem
  • Auteurs: Benjamin Doerr, Andrew James Kelley
  • Classification: cs.NE (Calcul Neuronal et Évolutionnaire), cs.AI (Intelligence Artificielle), cs.DS (Structures de Données et Algorithmes)
  • Date de publication: 21 mars 2024
  • Lien de l'article: https://arxiv.org/abs/2403.08153

Résumé

Cet article complète et améliore les recherches menées par C. Doerr et Krejca en 2023 concernant les bornes supérieures du temps d'exécution attendu de l'heuristique de recherche locale aléatoire sur la fonction Needle généralisée. L'étude originale, basée sur les bornes supérieures, a déduit l'impact significatif du rayon de l'aiguille k sur le temps d'exécution, mais manquait de preuve théorique rigoureuse. Cet article fournit une analyse des bornes inférieures nécessaires en dérivant une expression exacte du temps d'exécution attendu, améliore considérablement les résultats des bornes supérieures antérieures, et fournit des estimations asymptotiques du temps d'exécution attendu.

Contexte et Motivation de la Recherche

  1. Problème à résoudre: Déterminer la complexité exacte du temps d'exécution de l'algorithme de recherche locale aléatoire (RLS) sur le problème Needle généralisé, en particulier l'impact du paramètre k (rayon de l'aiguille) sur la performance de l'algorithme.
  2. Importance du problème:
    • Le problème Needle généralisé est un test de référence important pour comprendre comment les heuristiques de recherche aléatoire traitent les plateaux de fitness constants
    • Ce problème intègre la recherche sur des problèmes classiques tels que les fonctions royal road, les problèmes de plateau et BlockLeadingOnes
    • Il fournit une base théorique pour la conception et l'analyse de tests de référence avec des caractéristiques ajustables
  3. Limitations des méthodes existantes:
    • Le travail de C. Doerr et Krejca ne fournit que des bornes supérieures, manquant d'analyse des bornes inférieures
    • Utilise une analyse de dérive complexe, le théorème d'arrêt optionnel et l'équation de Wald généralisée
    • Pour le cas k = o(n), la borne supérieure est surexponentielle, clairement trop lâche
  4. Motivation de la recherche: Perfectionner l'analyse théorique et simplifier les méthodes de preuve en fournissant des expressions exactes du temps d'exécution et des estimations asymptotiques.

Contributions Principales

  1. Formule exacte du temps d'exécution attendu: Pour une solution initiale ayant i bits à 1, le temps d'exécution attendu est ∑j=in−k−1(n≤j)/(n−1j)\sum_{j=i}^{n-k-1} \binom{n}{\leq j} / \binom{n-1}{j}
  2. Amélioration significative des bornes existantes: En particulier pour le cas k = o(n), amélioration d'une borne surexponentielle à une borne asymptotiquement serrée de 2n(nk)−12^n \binom{n}{k}^{-1}
  3. Simplification de la méthode d'analyse: Remplacement de l'analyse de dérive complexe par la méthode classique des chaînes de Markov
  4. Analyse asymptotique complète: Couvrant différentes plages de valeurs de k, y compris les cas sous-linéaires, linéaires et proches de n/2
  5. Correction des erreurs du texte original: Identification et correction de la conclusion erronée du texte original selon laquelle le temps d'exécution serait constant pour k = n/2 - Θ(1)

Explication Détaillée de la Méthode

Définition de la Tâche

Définition de la fonction Needle généralisée: Pour n∈Nn \in \mathbb{N} et k∈[0..n]k \in [0..n], la fonction Needle généralisée Needlen,k\text{Needle}_{n,k} est définie comme:

undefined