Implementierung des Hill Climbing-Algorithmus für KI in Python

Tutorials
Python

Der Hügelsteigalgorithmus ist einer der ältesten und einfachsten Optimierungsalgorithmen in der künstlichen Intelligenz und Informatik. Er gehört zu einer Kategorie von Algorithmen zur lokalen Suche, die Lösungen durch inkrementelle Verbesserungen finden.

Der Name des Algorithmus stammt von einer hilfreichen Analogie: Stellen Sie sich einen blinden Wanderer vor, der versucht, den Gipfel eines Hügels zu erreichen. Da er die gesamte Landschaft nicht sehen kann, kann er nur den Boden unmittelbar um sich herum spüren. Bei jedem Schritt bewegt er sich in diejenige Richtung, die nach oben führt. Dies spiegelt wider, wie der Algorithmus funktioniert – er bewertet nahegelegene Lösungen und bewegt sich iterativ zu besseren Lösungen, um die optimale Lösung (den Gipfel des Hügels) zu finden.

In diesem Artikel werden wir den Hill Climbing-Algorithmus eingehend untersuchen, seine Variationen und wie Sie ihn in Python implementieren können. Wenn Sie neu in KI sind, sollten Sie unbedingt unseren AI-Grundlagen-Skill-Track besuchen, um die Grundlagen abzudecken. 

Was ist ein Hill Climbing-Algorithmus in der KI?

Hill Climbing ist eine einfache Möglichkeit für Computer, Probleme zu lösen, indem sie die bestmögliche Antwort finden, genau wie ein Wanderer, der versucht, den Gipfel eines Berges zu erreichen. In der künstlichen Intelligenz (KI) müssen wir oft die beste Lösung unter vielen möglichen Optionen finden. Dies wird als Optimierung bezeichnet.

Stellen Sie sich vor, Sie versuchen, den höchsten Punkt zu finden, während Sie ein Spiel von „Heiß und Kalt“ spielen. In diesem Spiel können Sie nur überprüfen, ob es „wärmer“ (besser) oder „kälter“ (schlechter) wird, während Sie sich bewegen. Das Hill Climbing funktioniert auf die gleiche Weise – es betrachtet nahegelegene Lösungen und bewegt sich zu den besseren.

So funktioniert es in einfachen Schritten:

  1. Beginnen Sie mit einer möglichen Lösung
  2. Betrachten Sie nahegelegene Lösungen
  3. Wenn eine nahegelegene Lösung besser ist, wechseln Sie zu dieser
  4. Wiederholen Sie die Schritte 2-3, bis keine besseren Lösungen mehr gefunden werden können

Zum Beispiel, wenn Sie einem Roboter das Laufen beibringen wollen, könnte Hill Climbing:

  • Mit zufälligen Beinbewegungen beginnen
  • Leicht unterschiedliche Bewegungen ausprobieren
  • Die Bewegungen beibehalten, die dem Roboter besseres Laufen ermöglichen
  • Wiederholen, bis das beste Laufmuster gefunden ist

Obwohl das Bergsteigen nicht immer die fortschrittlichste Methode in der KI ist, ist es ein wichtiger Baustein, der uns hilft zu verstehen, wie Computer Probleme eigenständig lösen können, ähnlich dem Minimax-Algorithmus.

Arten von Bergsteigeralgorithmen

Es gibt drei Hauptarten von Bergsteigeralgorithmen, von denen jeder auf seine eigene Weise nach der besten Lösung sucht:

1. Einfaches Bergsteigen

Beim einfachen Bergsteigen geht es darum, den ersten guten Schritt zu machen, den Sie finden. In dieser Version:

  • Der Algorithmus betrachtet benachbarte Lösungen nacheinander
  • Sobald er eine bessere Lösung findet, übernimmt er sie
  • Er überprüft die anderen Optionen nicht
  • Dies ist schnell, könnte jedoch bessere Lösungen verpassen, die nur etwas weiter entfernt sind

2. Steilster Anstieg beim Bergsteigen

Diese Version ist gründlicher als einfaches Bergsteigen:

  • Sie betrachtet ALLE benachbarten Lösungen, bevor sie einen Schritt macht
  • Wählt die beste Option aus allem, was es gefunden hat
  • Benötigt mehr Zeit, findet aber in der Regel bessere Lösungen
  • Es ist wie das sorgfältige Überprüfen jedes Pfades, bevor man einen Schritt macht

3. Stochastischer Bergsteigalgorithmus

Dieser Typ fügt etwas Zufälligkeit hinzu, um die Suche interessanter zu gestalten:

  • Anstatt immer die beste Lösung zu wählen, wählt es zufällig aus den besseren Optionen aus
  • Bessere Lösungen haben eine höhere Chance ausgewählt zu werden
  • Diese Zufälligkeit hilft, nicht an schlechten Stellen stecken zu bleiben
  • Es ist wie manchmal einen anderen Weg einschlagen, nur um zu sehen, wohin er führt

Jede Art hat ihre eigenen Stärken und funktioniert besser für verschiedene Arten von Problemen. Einfaches Bergsteigen ist schnell, aber grundlegend, steilster Aufstieg ist gründlich, aber langsamer, und stochastisches Hinzufügen von hilfreicher Zufälligkeit, um nicht stecken zu bleiben.

So funktioniert der Bergsteigungsalgorithmus

Der Bergsteigungsalgorithmus funktioniert, indem er schrittweise kleine Verbesserungen vornimmt, bis er die bestmögliche Lösung findet. Lassen Sie uns aufschlüsseln, wie er in seine Hauptteile aufgeteilt ist.

1. Los geht’s

Jeder Hill-Climbing-Algorithmus benötigt einen Ausgangspunkt. Denken Sie daran, es wie die Wahl zu betrachten, wo man mit dem Wandern auf einem Berg beginnen möchte. Sie könnten zufällig anfangen oder das, was Sie über das Problem wissen, nutzen, um einen guten Ausgangspunkt auszuwählen.

Wo Sie starten, ist wirklich wichtig — wählen Sie einen guten Ort, und Sie könnten die beste Lösung schnell finden. Wählen Sie einen schlechten Ort, und Sie könnten auf einem kleinen Hügel stecken bleiben, anstatt den Gipfel des Berges zu finden.

Zum Beispiel, beim Trainingneuronaler Netzwerke bedeutet der Ausgangspunkt die Auswahl der Anfangsgewichte für die Verbindungen zwischen Neuronen. Sie könnten diese Gewichte zufällig initialisieren, was dem Starten Ihrer Wanderung an einer zufälligen Stelle am Berg entspricht. Oder Sie könnten Techniken wie die Xavier-Initialisierung verwenden, die kluge Anfangsgewichte basierend auf der Netzwerkstruktur auswählen.

Eine gute Initialisierung hilft dem Netzwerk schneller zu lernen und bessere Lösungen zu finden, während eine schlechte Initialisierung das Netzwerk mit einer niedrigen Genauigkeit zurücklassen könnte, die sich nie verbessert.

2. Betrachten von naheliegenden Lösungen

Sobald der Algorithmus mit seiner Suche beginnt, bewertet er benachbarte Lösungen, die dem aktuellen Standort ähnlich sind. Stellen Sie sich vor, es geht darum, die unmittelbare Umgebung in kleinen Schritten zu erkunden. Wenn Sie beispielsweise versuchen, eine Lieferstrecke zwischen Städten zu optimieren und Ihre aktuelle Route [A -> B -> C -> D] ist, würde der Algorithmus ähnliche Routen wie [A -> B -> D -> C] oder [A -> C -> B -> D] prüfen, um zu sehen, ob sie die Gesamtdistanz verringern. Jede kleine Änderung an der Route stellt eine „Nachbar“ -Lösung dar, die potenziell besser sein könnte als die aktuelle.

Um diese Vergleiche anzustellen, verlässt sich der Algorithmus auf das, was als Ziel- oder Zielfunktion bezeichnet wird — eine mathematische Formel, die jeder möglichen Lösung eine Punktzahl oder einen Wert zuweist.

Diese Funktion fungiert wie ein Kompass und hilft dem Algorithmus zu verstehen, welche Richtungen „bergab“ zu besseren Lösungen führen und welche „bergab“ zu schlechteren. Für eine Lieferstrecke würde die Ziel Funktion die Gesamtdistanz berechnen – eine kürzere Gesamtdistanz bedeutet eine bessere Lösung.

Wenn also Route X 100 Meilen und Route Z 90 Meilen dauert, hätte Route B eine bessere (niedrigere) Punktzahl. Der Algorithmus würde dann wissen, sich in Richtung von Lösungen ähnlich wie Route B zu bewegen. Die Ziel Funktion verwandelt im Wesentlichen das komplexe Problem der Routenoptimierung in eine einfache Zahl, die verglichen und minimiert werden kann.

3. Die nächste Schritt wählen

Nachdem nahegelegene Lösungen betrachtet wurden, muss der Algorithmus entscheiden, wohin er als nächstes gehen soll. Der Algorithmus vergleicht die Punktzahlen der nahegelegenen Lösungen mit der aktuellen. Wenn er eine bessere Lösung findet, bewegt er sich dorthin. Unterschiedliche Versionen von Hill Climbing treffen diese Wahl auf unterschiedliche Weise:

  • Die einfache Version wählt die erste bessere Lösung, die sie findet
  • Die sorgfältige Version überprüft alle nahegelegenen Lösungen, bevor sie die beste auswählt
  • Die zufällige Version wählt manchmal Lösungen, die nicht die allerbesten sind, was ihr helfen kann, nicht festzustecken

4. Zu wissen, wann man aufhören sollte

Der Algorithmus muss wissen, wann er aufhören soll, nach besseren Lösungen zu suchen. Normalerweise hört er auf, wenn eines dieser Dinge eintritt:

  1. Er kann keine besseren Lösungen in der Nähe finden
  2. Er läuft zu lange
  3. Es hat eine Lösung gefunden, die gut genug ist

Wie der Algorithmus funktioniert, folgt er normalerweise einem Muster. Zunächst findet er schnell bessere Lösungen, wie große Schritte auf einem steilen Hügel. Dann verlangsamt er sich, je näher er dem Gipfel kommt, und macht kleinere Verbesserungen, bis er schließlich stoppt.

Manchmal ist der Weg glatt und unkompliziert, aber andere Male kann er knifflig sein mit vielen Höhen und Tiefen.

Vorteile und Einschränkungen des Hill Climbing in der KI

Lass uns anschauen, was Hill Climbing nützlich macht und auf welche Probleme du stoßen könntest, wenn du es verwendest.

Vorteile

Das Bergsteigen ist einer der einfachsten Optimierungsalgorithmen, die man verstehen und programmieren kann. Es ist wie das Befolgen einer grundlegenden Regel: „Wenn etwas besser ist, gehe dorthin.“ Das macht es zu einem großartigen Ausgangspunkt für die Lösung vieler Probleme.

Wenn das Problem einfach ist, kann das Bergsteigen schnell gute Lösungen finden. Es verschwendet keine Zeit damit, jede mögliche Lösung zu erkunden – es folgt einfach dem Weg nach oben.

Der Algorithmus benötigt nicht viel Computerspeicher oder Rechenleistung. Er muss nur wissen, wo er sich befindet, und sich nahegelegene Lösungen ansehen, was ihn für viele reale Probleme praktikabel macht.

Einschränkungen

Natürlich gibt es wie bei jeder Methode einige potenzielle Nachteile:

1. Steckenbleiben auf kleinen Hügeln

Das größte Problem beim Bergsteigen ist, dass es sich auf dem festfahren kann, was wir „lokale Maxima“ nennen – das sind wie kleine Hügel, während in der Nähe tatsächlich ein Berg ist. Sobald der Algorithmus den Gipfel eines kleinen Hügels erreicht, stoppt er, weil alles um ihn herum tiefer ist, obwohl es anderswo viel bessere Lösungen geben könnte.

2. Das Problem des flachen Bodens

Manchmal findet sich der Algorithmus auf flachem Boden (genannt Plateau), wo alle nahegelegenen Lösungen gleich gut sind. Stellen Sie sich vor, Sie versuchen, den höchsten Punkt zu finden, während Sie auf einem flachen Fußballfeld laufen – es ist schwer zu wissen, in welche Richtung man gehen soll!

3. Das Problem des Grats

Stellen Sie sich vor, Sie versuchen, entlang der Spitze eines schmalen Gebirges zu gehen. Der Algorithmus könnte Zeit damit verschwenden, im Zickzack über den Grat zu laufen, anstatt vorwärts zum Gipfel zu gehen. Dies passiert, weil jeder Schritt zur Seite genauso gut aussieht wie auf Kurs zu bleiben.

4. Der Ausgangspunkt ist sehr wichtig

Wo Sie beginnen, kann einen großen Unterschied darin ausmachen, wie gut der Algorithmus funktioniert. Es ist wie eine Wanderung zu beginnen – starten Sie am falschen Ort und Sie finden vielleicht nie den höchsten Gipfel.

Diese Einschränkungen bedeuten nicht, dass das Bergsteigen eine schlechte Wahl ist – sie bedeuten nur, dass wir vorsichtig sein müssen, wann und wie wir es verwenden. Manchmal können wir es mit anderen Techniken kombinieren, um diese Probleme zu überwinden, worüber wir im nächsten Abschnitt sprechen werden.

Strategien zur Überwindung von Einschränkungen

Beim Einsatz des Bergsteigens können wir mehrere clevere Strategien verwenden, um die Probleme zu lösen, über die wir zuvor gesprochen haben. Lassen Sie uns zwei Hauptansätze erkunden, die dazu beitragen, dass das Bergsteigen besser funktioniert.

Zufallsneustart-Bergsteigen

Einer der besten Wege, um das Feststecken auf kleinen Hügeln zu vermeiden, ist, von verschiedenen Startpunkten aus zu klettern. Dieser Ansatz wird Zufallsneustart-Bergsteigen genannt und funktioniert genau wie es klingt – wenn Sie stecken bleiben, starten Sie an einem neuen Ort von vorne.

Stell dir vor, du versuchst, den höchsten Berg in einem nebligen Gebirgen zu finden. Wenn du mit dem Besteigen des ersten Hügels, den du findest, beginnst und seinen Gipfel erreichst, könntest du einen wesentlich höheren Berg in der Nähe übersehen. Aber wenn du dich an verschiedene Orte teleportieren und erneut mit dem Klettern beginnen könntest, hättest du eine viel bessere Chance, letztendlich den höchsten Gipfel zu finden.

So funktioniert es: Zuerst führst du den normalen Hill-Climbing-Algorithmus aus, bis er stecken bleibt. Anstatt aufzugeben, speicherst du die beste Lösung, die du gefunden hast, und beginnst dann an einem zufälligen neuen Punkt erneut. Du machst dies für mehrere Versuche, und am Ende wählst du die beste Lösung aus all deinen Versuchen aus.

Die Schönheit des Random-Restart-Verfahrens ist, dass es einfach, aber effektiv ist. Jeder Neustart gibt dir eine frische Chance, den höchsten Gipfel zu finden. Während es mehr Zeit als das reguläre Hill Climbing in Anspruch nimmt, ist es viel wahrscheinlicher, die beste Lösung zu finden.

Simulated Annealing

Obwohl es technisch gesehen kein Hügelsteigen ist, ist das simulierte Annealing eine clevere Variation, die hilft, viele Probleme des Hügelsteigens zu lösen. Es ist inspiriert von der Art und Weise, wie Metalle in der Metallbearbeitung abkühlen und aushärten. Wenn Metall langsam abkühlt, finden seine Atome bessere Positionen, wodurch das Metall stärker wird.

In diesem Ansatz akzeptiert der Algorithmus manchmal absichtlich schlechtere Lösungen, insbesondere zu Beginn. Mit der Zeit wird er wählerischer, welche Lösungen er akzeptiert. Es ist wie ein Ball, der über eine holprige Oberfläche hüpft — zuerst hat er genug Energie, um über Hügel zu springen, aber während er Energie verliert, findet er einen guten Platz.

So funktioniert es: Zu Beginn könnte der Algorithmus mit einer relativ hohen Wahrscheinlichkeit eine Lösung akzeptieren, die schlechter ist als die aktuelle. Diese Wahrscheinlichkeit hängt von zwei Faktoren ab: wie viel schlechter die neue Lösung ist und wie lange der Algorithmus bereits läuft. Mit der Zeit wird der Algorithmus weniger wahrscheinlich schlechtere Lösungen akzeptieren und verhält sich schließlich eher wie ein regulärer Hill Climbing-Algorithmus.

Die wahre Stärke des simulierten Annealings liegt darin, dass es aus kleinen Tälern und flachen Bereichen entkommen kann, insbesondere zu Beginn der Suche. Indem es manchmal schlechtere Lösungen akzeptiert, kann es:

  • Aus lokalen Maxima (kleinen Hügeln) herausspringen
  • Plateaus (flache Bereiche) überqueren
  • Navigieren Sie durch Kämme (schmale Gipfel)
  • Erkunden Sie mehr vom Lösungsraum

Zum Beispiel, stellen Sie sich vor, Sie versuchen, Möbel in einem Raum so anzuordnen, dass der Raum maximal genutzt wird. Das Verschieben eines Stuhls könnte den Raum vorübergehend überfüllter machen, aber es könnte Ihnen ermöglichen, dann andere Stücke in viel bessere Positionen zu bewegen. Simulated Annealing wäre bereit, diese vorübergehend schlechteren Anordnungen auszuprobieren, besonders früh im Prozess, um die beste Gesamtanordnung zu finden.

Diese Strategien zeigen uns, dass der beste Weg, ein Problem zu lösen, manchmal nicht immer darin besteht, den offensichtlichen Schritt nach vorne zu machen. Durch Hinzufügen von Elementen der Zufälligkeit und kontrolliertem Chaos können wir oft bessere Lösungen finden, als wenn wir immer den geradlinigen Weg gehen würden.

Implementierung eines einfachen Hill Climbing Algorithmus in Python

Jetzt, da wir verstehen, wie wir das Bergsteigen mit Strategien wie Zufallsneustart und simuliertem Abkühlen verbessern können, wenden wir es auf ein echtes finanzielles Problem an: Portfolio-Optimierung.

Die Portfolio-Optimierung hilft Anlegern dabei zu entscheiden, wie sie ihr Geld auf verschiedene Investitionen verteilen sollen. Wenn Anleger ein Portfolio aufbauen, möchten sie möglichst hohe Renditen erzielen, während sie das Risiko niedrig halten. Dieses Gleichgewicht zu finden ist knifflig — es ist wie der Versuch, das perfekte Rezept mit vielen Zutaten zu finden.

Im Jahr 1952 fand ein Ökonom namens Harry Markowitz einen cleveren Weg, um dieses Problem zu lösen. Er zeigte, dass Anleger ihr Risiko reduzieren können, indem sie Investitionen mischen, die sich nicht gemeinsam nach oben und unten bewegen. Dies wird Diversifikation genannt — es ähnelt dem Sprichwort, nicht alle Eier in einen Korb zu legen.

Beim Aufbau eines Portfolios müssen wir drei Hauptpunkte herausfinden:

  • Wie viel Geld wir erwarten zu verdienen (Erwartete Rendite)
  • Wie riskant die Investitionen sind (Portfoliorisiko)
  • Ob die potenziellen Gewinne das Risiko wert sind (Risikoangepasste Rendite)

Das Hill Climbing funktioniert gut für dieses Problem, da kleine Änderungen darin, wie wir unser Geld aufteilen, normalerweise zu kleinen Veränderungen in der Performance des Portfolios führen. Stellen Sie sich einen sanften Hügel vor, bei dem jeder Punkt eine andere Möglichkeit darstellt, Ihr Geld anzulegen. Die höheren Punkte zeigen bessere Anlageentscheidungen.

Um ein gutes Portfolio mit Hill Climbing zu finden, werden wir:

  1. Mit einer zufälligen Mischung von Investitionen beginnen
  2. Etwas unterschiedliche Mischungen ausprobieren, um zu sehen, ob sie besser funktionieren
  3. Kleine Verbesserungen vornehmen, bis wir keine besseren Optionen finden können
  4. Die beste Mischung verwenden, die wir gefunden haben

Indem wir Hill Climbing auf diese Weise nutzen, können wir Anlegern helfen, bessere Portfolios aus Millionen möglicher Kombinationen zu finden. Es ist wie ein intelligenter Assistent, der schnell viele verschiedene Anlagemischungen testen kann, um solche zu finden, die Risiko und Rendite gut ausbalancieren.

Zuerst definieren wir unsere Ziel-Funktion, die ein Maß für die Portfolio-Leistung ist und erwartete Renditen gegen Risiko abwägt. Sie nimmt eine Liste von Portfolio-Gewichten als Eingabe und gibt einen Wert zurück, wobei höhere Werte bessere Portfolios anzeigen.

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # Erwartete jährliche Renditen für Vermögenswerte (Beispielwerte)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, usw.

   # Risiko (Volatilität) für jeden Vermögenswert
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, usw.

   # Überprüfen, ob die Eingabelänge mit den erwarteten Renditen/Volatilitäten übereinstimmt
   if len(state) != len(expected_returns):
       return float("-inf")  # Schlechtesten möglichen Wert für ungültige Zustände zurückgeben

   # Erwartete Portfolio-Rendite berechnen
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Portfolio-Risiko berechnen (vereinfacht, ohne Kovarianzmatrix)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Bestrafen, wenn die Gewichte nicht auf 1 summieren (ungültiges Portfolio)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Negative Gewichte bestrafen (kein Leerverkauf)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Rendite und Risiko mit einem Risikoaversion-Faktor von 2 kombinieren
   # Höherer Wert ist besser: Rendite maximieren, Risiko und Strafen minimieren
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

Die oben genannte objective_function hilft uns zu bewerten, wie gut ein bestimmtes Anlageportfolio ist. Lassen Sie uns herausfinden, wie es funktioniert:

Zunächst nimmt es eine Liste von Zahlen entgegen, die darstellen, welchen Prozentsatz unseres Geldes wir in verschiedene Vermögenswerte investieren möchten (wie Aktien oder Anleihen). Zum Beispiel könnten wir bei fünf Vermögenswerten jeweils 20 % investieren.

Die Funktion verwendet zwei wichtige Informationen:

  1. Erwartete Renditen: Wie viel Geld wir von jedem Vermögenswert erwarten (wie 8 % oder 12 % pro Jahr)
  2. Volatilitäten: Wie risikobehaftet jeder Vermögenswert ist – höhere Zahlen bedeuten, dass der Wert des Vermögenswerts unvorhersehbarer schwankt (wie bei Kryptowährungen)

Die Funktion berechnet dann:

  • Den gesamten erwarteten Ertrag unseres Portfolios, indem sie die erwartete Rendite jedes Vermögenswerts mit unserem Investitionsbetrag multipliziert
  • Bestimmt das Gesamtrisiko, indem sie sich die Volatilität jedes Vermögenswerts ansieht
  • Überprüft, ob unsere Investitionsprozentsätze sich zu 100 % addieren (was sie sollten!)
  • Stellt sicher, dass wir versuchen, keine Vermögenswerte zu verkaufen, die wir nicht besitzen (keine negativen Prozentsätze)

Zuletzt kombiniert sie all diese Informationen zu einem einzigen Wert. Ein höherer Wert bedeutet ein besseres Portfolio. Der Wert steigt mit höheren Renditen, nimmt jedoch mit höherem Risiko ab. Er wird auch viel schlechter, wenn unsere Prozentsätze nicht zu 100 % addieren oder wenn wir versuchen, negative Prozentsätze zu verwenden.

Diese Funktion wird uns helfen, die beste Mischung von Investitionen mithilfe des folgenden Hill-Climbing-Algorithmus zu finden. Wenn Sie die Zielfunktion nicht vollständig verstehen, machen Sie sich keine Sorgen — die Hauptidee ist, dass sie uns sagt, wie gut eine bestimmte Investitionsmischung ist, und wir werden sie nutzen, um immer bessere Kombinationen zu finden.

Jetzt definieren wir eine neue Funktion, um benachbarte Portfoliostände zu generieren, indem wir kleine Anpassungen an den Gewichten vornehmen.

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # Kleine Anpassung der Gewichte (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Gewicht von Anlage i auf Anlage j übertragen
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Übertragen nur, wenn genügend Gewicht verfügbar ist
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

Die Funktion get_neighbors ist ein entscheidender Teil unseres Hill-Climbing-Algorithmus, der ähnliche Portfolioallokationen generiert, indem kleine Anpassungen an unseren aktuellen Portfoliogewichten vorgenommen werden. So funktioniert es:

Für jedes Paar von Anlagen in unserem Portfolio erstellt es eine neue Portfolioallokation, indem es einen kleinen Betrag (1%) von einer Anlage auf eine andere überträgt. Wenn wir beispielsweise fünf Anlagen haben, wird es versuchen:

  • 1% von Anlage 1 auf Anlage 2 zu übertragen
  • 1% von Anlage 1 auf Anlage 3 zu übertragen
  • 1% von Anlage 1 auf Anlage 4 zu übertragen
  • 1% von Anlage 1 auf Anlage 5 zu übertragen
  • 1% von Anlage 2 auf Anlage 1 zu übertragen Und so weiter für alle möglichen Paare.

Die Funktion enthält eine Sicherheitsüberprüfung, um sicherzustellen, dass wir das Gewicht nur übertragen, wenn die Quellanlage genügend Allokation hat (mindestens 1%). Dies verhindert negative Gewichte, die in einem realen Portfolio keinen Sinn machen würden.

Jede dieser kleinen Anpassungen erzeugt einen „Nachbarn“ – eine Portfolioallokation, die unserer aktuellen sehr ähnlich ist, aber leicht unterschiedlich. Der Bergsteigeralgorithmus wird dann diese Nachbarn bewerten, um bessere Portfolioallokationen zu finden.

Die Schrittgröße von 1% bietet ein gutes Gleichgewicht zwischen Erkundung verschiedener Allokationen und kontrollierten Änderungen. Eine größere Schrittgröße könnte optimale Lösungen verpassen, während eine kleinere die Suche zu langsam machen würde.

Jetzt lassen Sie uns endlich einen einfachen Bergsteigeralgorithmus implementieren:

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # Holen benachbarte Zustände
       neighbors = get_neighbors(current_state)
      
       # Flagge, um zu überprüfen, ob wir einen besseren Nachbarn gefunden haben
       found_better = False
      
       # Überprüfen der Nachbarn nacheinander (Einfacher Bergsteigeralgorithmus)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # Wenn wir einen besseren Nachbarn finden, gehen wir sofort dorthin
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # Wenn kein besserer Nachbar gefunden wurde, haben wir einen Höhepunkt erreicht
       if not found_better:
           break
  
   return current_state, current_value

Die Funktion beginnt mit einem Anfangszustand und bewegt sich iterativ zu besseren benachbarten Zuständen, bis sie ein lokales Maximum oder die maximale Anzahl von Iterationen erreicht.

Die Funktion nimmt zwei Parameter:

  • initial_state: Der Ausgangspunkt für die Optimierung, dargestellt als Liste von Werten
  • max_iterations: Ein Sicherheitsparameter, um unendliche Schleifen zu verhindern, standardmäßig auf 1000 Iterationen eingestellt

Der Algorithmus funktioniert wie folgt:

  1. Er beginnt beim initial_state und berechnet seinen Zielfunktionswert
  2. Für jede Iteration:
  • Erzeugt benachbarte Zustände mithilfe von get_neighbors()
  • Bewertet jeden Nachbarn nacheinander
  • Sobald es einen besseren Nachbarn findet (höherer Zielfunktionswert), wechselt es in diesen Zustand.
  • Wenn kein besserer Nachbar gefunden wird, hat es ein lokales Maximum erreicht und beendet den Vorgang.

Die Funktion gibt ein Tupel zurück, das enthält:

  • Den besten gefundenen Zustand (Liste von Werten)
  • Den Zielfunktionswert für diesen Zustand

Diese „einfache“ Variante des Bergsteigens ist gierig – sie wechselt zum ersten besseren Nachbarn, den sie findet, anstatt alle Nachbarn zu bewerten, um den besten zu finden. Obwohl dies den Vorgang schneller macht, kann es bessere Lösungen verpassen, die durch gründlichere Prüfung gefunden werden könnten.

Der Algorithmus ist nützlich, um lokale Optima zu finden, kann jedoch an diesen lokalen Maxima stecken bleiben, wodurch das globale Maximum möglicherweise verpasst wird. Trotz dieser Einschränkung bleibt er aufgrund seiner Einfachheit und Effizienz beliebt.

Lass uns testen, wie er bei einem Musterportfolio funktioniert:

# Beispielhafte Verwendung
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

Die Ausgabe zeigt die Ergebnisse unseres Hill-Climbing-Algorithmus bei der Optimierung eines Portfolios. Ausgehend von zufälligen Gewichten für fünf Vermögenswerte fand er einen neuen Satz von Gewichten, der den Wert der Zielfunktion verbesserte. Während diese Lösung das anfängliche Portfolio verbesserte, könnte es sich nur um ein lokales Optimum handeln, da der Algorithmus beim ersten Gipfel, den er findet, stoppt.

Anwendungen von Hill Climbing in der KI

Hill-Climbing-Algorithmen finden praktische Anwendungen in vielen Bereichen der künstlichen Intelligenz und des maschinellen Lernens. Lassen Sie uns einige wichtige Anwendungen erkunden:

1. Optimierung von Maschinenlernmodellen

Hügelsteigen hilft dabei, Maschinenlernmodelle auf verschiedene Arten anzupassen:

  • Merkmalsaustausch: Finden des besten Merkmalsuntergrunds für ein Modell
  • Hyperparametertuning: Optimierung von Modellparametern wie Lernrate oder Baumtiefe
  • Neuronales Netztraining: Feinabstimmung von Netzwerkgewichten und Architektur
  • Modellkompression: Reduzierung der Modellgröße bei gleichbleibender Leistung

Zum Beispiel kann Hill Climbing bei der Auswahl von Features für ein Vorhersagemodell mit allen Features beginnen und diese iterativ basierend auf der Modellleistung entfernen oder hinzufügen. Dies hilft, einen optimalen Merkmalsatz zu finden, der die Modellgenauigkeit mit der Komplexität in Einklang bringt.

2. Robotik und Pfadplanung

In der Robotik unterstützt Hill Climbing bei:

  • Bewegungsplanung: Effiziente Pfade durch den physischen Raum finden
  • Optimierung des Gelenkwinkels: Bestimmung optimaler Positionen für Roboterarme
  • Sensorplatzierung: Optimierung der Platzierung von Sensoren für maximale Abdeckung
  • Batteriemanagement: Optimierung der Stromverbrauchsmuster

Ein Roboterstaubsauger könnte Hill Climbing verwenden, um effiziente Reinigungswege zu finden, indem er kontinuierlich seine Route basierend auf der Raumabdeckung und der Batterielebensdauer anpasst.

3. Verarbeitung natürlicher Sprache

NLP Anwendungen umfassen:

  • Textzusammenfassung: Optimierung der Auswahl von Zusammenfassungsinhalten
  • Wort-Einbettung: Feinabstimmung der Wortvektor-Darstellungen
  • Dokumentenclustering: Organisieren von Dokumenten in optimale Gruppen
  • Suchmaschinenoptimierung: Verbesserung der Suchergebnisplatzierungen

Zum Beispiel kann Hill Climbing bei der Textzusammenfassung dazu beitragen, Sätze auszuwählen, die den Informationsgehalt maximieren und Redundanzen minimieren.

4. Computer Vision In der Bildverarbeitung und Computer Vision

  • Bildsegmentierung: Optimale Grenzen zwischen Objekten finden
  • Kamerakalibrierung: Anpassung der Kameraparameter für eine bessere Bildqualität
  • Objekterkennung: Optimierung der Positionen der Begrenzungsrahmen
  • Merkmalsabgleich: Finden entsprechender Punkte zwischen Bildern

Ein Gesichtserkennungssystem könnte Hill Climbing verwenden, um die Ausrichtung der Gesichtsmerkmale während der Vorverarbeitung zu optimieren.

5. Spiel-KI und Entscheidungsfindung

Hill Climbing hilft bei:

  • Spielstrategieoptimierung: Das Finden von Gewinnzügen in Brettspielen
  • Ressourcenzuweisung: Optimierung der Ressourcenverteilung in Strategiespielen
  • NPC-Verhalten: Verbesserung der Entscheidungsfindung von Nicht-Spieler-Charakteren
  • Levelgenerierung: Erstellung ausgewogener und interessanter Spiellevel

Schach-Engines verwenden oft Varianten des Bergsteigens, um Zugfolgen während des Spiels zu bewerten und zu optimieren.

6. Geschäft und Betrieb

Praktische Geschäftsanwendungen sind:

  • Optimierung der Lieferkette: Effiziente Lieferwege finden
  • Ressourcenplanung: Optimierung von Mitarbeiterplänen oder Maschinennutzung
  • Portfolioverwaltung: Ausgleich von Anlageportfolios
  • Bestandsmanagement: Optimierung der Lagerbestände

Ein Lieferunternehmen könnte Bergsteigen verwenden, um kontinuierlich Lieferwege basierend auf Verkehrsmustern und Paketprioritäten zu optimieren.

Obwohl Bergsteigen nicht immer die absolut beste Lösung findet, macht seine Einfachheit und Effizienz ihn wertvoll für diese Anwendungen im echten Leben. Es ist besonders nützlich, wenn:

  • Schnelle Lösungen erforderlich sind
  • Der Problembereich zu groß für eine erschöpfende Suche ist
  • Annähernde Lösungen akzeptabel sind
  • Der Lösungsraum relativ glatt ist
  • Der Algorithmus mit anderen Techniken kombiniert werden kann, um bessere Ergebnisse zu erzielen

Schlussfolgerung

Bergsteigen gilt als grundlegender Algorithmus in der künstlichen Intelligenz und bietet einen einfachen, aber leistungsstarken Ansatz für Optimierungsprobleme. 

In unserer Untersuchung haben wir gesehen, wie dieses einfache Konzept, sich iterativ auf bessere Lösungen zuzubewegen, auf komplexe Herausforderungen in den Bereichen maschinelles Lernen, Robotik, natürliche Sprachverarbeitung und Geschäftsbetrieb angewendet werden kann.

Obwohl der Algorithmus seine Einschränkungen hat, wie das Steckenbleiben in lokalen Optima, haben sich Strategien wie Random-Restart und Simulated Annealing entwickelt, um diese Herausforderungen effektiv anzugehen.

Während die KI weiterhin fortschreitet, bleibt das Hill Climbing nicht nur als praktisches Werkzeug relevant, sondern auch als Sprungbrett zum Verständnis komplexerer Optimierungsalgorithmen. Seine intuitive Natur macht es zu einem ausgezeichneten Ausgangspunkt für alle, die in das Feld der KI einsteigen, während seine Vielseitigkeit seine fortdauernde Nutzung in realen Anwendungen sichert.

Ob Sie nun die Gewichte neuronaler Netzwerke optimieren, Roboterwege planen oder Investmentportfolios verwalten, die Prinzipien des Hill Climbing bieten wertvolle Einblicke, wie Computer systematisch bessere Lösungen für herausfordernde Probleme finden können.

Wenn Sie mehr über KI und die Algorithmen dahinter lernen möchten, werfen Sie einen Blick auf unsere Ressourcen:

Source:
https://www.datacamp.com/tutorial/hill-climbing-algorithm-for-ai-in-python