Lokaler Suchalgorithmus (Local Search) in C++ – Erklärung, Beispiel und Code

Der Local Search-Algorithmus ist eine Methode zum Finden der besten Lösung in der Nähe des aktuellen Zustands. Diese Technik wird häufig verwendet, um Näherungslösungen durch iteratives Modifizieren einzelner Komponenten zu verfeinern, um bessere Zustände zu ermitteln.

Wie es funktioniert

1. Initialisierung: Beginnen Sie mit einem Anfangszustand.
2. Nachbarn generieren: Generieren Sie benachbarte Staaten, indem Sie eine Komponente des aktuellen Staates ändern.
3. Bewertung: Bewerten Sie die Qualität benachbarter Staaten anhand einer Zielfunktion.
4. Besten Staat auswählen: Wählen Sie den Nachbarstaat mit dem besten objektiven Wert.
5. Wiederholen: Wiederholen Sie die Schritte 2 bis 4, bis kein besserer Nachbarstaat gefunden werden kann.

Beispiel: Optimierung der Fibonacci Funktion

Betrachten Sie das Optimierungsproblem der Fibonacci Funktion F(x) = F(x-1) + F(x-2) mit F(0) = 0, F(1) = 1. Wir wollen den Wert von x finden, für den F(x) wird maximiert. Wir können den Ansatz der lokalen Suche verwenden, um von jedem Schritt aus iterativ weiter zu erkunden.

Codebeispiel in C++

#include <iostream>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int localSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    for(int x = 0; x < maxIterations; ++x) {  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = localSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

In diesem Beispiel verwenden wir die Methode der lokalen Suche, um die Fibonacci Funktion zu optimieren. Wir durchlaufen verschiedene x-Werte und berechnen den Fibonacci Wert für jedes x. Wenn ein besserer Wert gefunden wird, aktualisieren wir den besten Wert und das entsprechende x.