Het implementeren van het Hill Climbing-algoritme voor AI in Python

Python

Het heuvelklimmingsalgoritme is een van de vroegste en eenvoudigste optimalisatiealgoritmen in kunstmatige intelligentie en informatica. Het behoort tot een categorie genaamd lokale zoekalgoritmen, die oplossingen vinden door incrementele verbeteringen aan te brengen.

De naam van het algoritme komt van een handige analogie: stel je een geblinddoekte wandelaar voor die de top van een heuvel probeert te bereiken. Omdat ze het hele landschap niet kunnen zien, kunnen ze alleen de grond direct om hen heen voelen. Bij elke stap bewegen ze in de richting die omhoog leidt. Dit weerspiegelt hoe het algoritme werkt – het evalueert nabijgelegen oplossingen en beweegt iteratief naar betere, in een poging de optimale oplossing te vinden (de top van de heuvel).

In dit artikel zullen we de hill climbing-algoritme grondig verkennen, de variaties ervan, en hoe je het in Python kunt implementeren. Als je nieuw bent in AI, zorg er dan voor dat je onze AI Fundamentals vaardigheidstrack bekijkt om de basisprincipes te begrijpen.

Wat is een Hill Climbing Algorithm in AI?

Hill climbing is een eenvoudige manier voor computers om problemen op te lossen door het vinden van het beste mogelijke antwoord, net zoals een wandelaar die probeert de top van een berg te bereiken. In kunstmatige intelligentie (AI) moeten we vaak de beste oplossing vinden tussen vele mogelijke keuzes. Dit wordt optimalisatie genoemd.

Denk aan het proberen te vinden van het hoogste punt tijdens het spelen van het spel “heet en koud”. In dit spel kun je alleen controleren of je “warmer” (beter) of “kouder” (slechter) wordt terwijl je rondloopt. Hill climbing werkt op dezelfde manier – het kijkt naar nabije oplossingen en beweegt naar de betere.

Zo werkt het in eenvoudige stappen:

Begin met een willekeurige mogelijke oplossing
Kijk naar nabije oplossingen
Als een nabije oplossing beter is, ga er dan naartoe
Blijf stappen 2-3 herhalen totdat er geen betere oplossingen meer kunnen worden gevonden

Bijvoorbeeld, als je een robot probeert te leren lopen, zou Hill Climbing kunnen:

Beginnen met willekeurige bewegingen van de benen
Proberen iets andere bewegingen
De bewegingen behouden die de robot helpen beter te lopen
Herhalen totdat het het beste looppatroon vindt

Hoewel heuvelklimmen niet altijd de meest geavanceerde methode is in AI, is het een belangrijke bouwsteen die ons helpt begrijpen hoe computers problemen zelfstandig kunnen oplossen, vergelijkbaar met het minimax-algoritme.

Soorten Heuvelklimalgoritmen

Er zijn drie hoofdtypen heuvelklimalgoritmen, elk met zijn eigen manier van zoeken naar de beste oplossing:

1. Simpel heuvelklimmen

Simpel heuvelklimmen is als de eerste goede stap die je vindt nemen. In deze versie:

Het algoritme bekijkt nabijgelegen oplossingen één voor één
Zodra het een betere oplossing vindt, neemt het die
Het controleert niet de andere opties
Dit gaat snel, maar het kan betere oplossingen missen die net iets verder weg waren

2. Steepest-ascent hill climbing

Deze versie is grondiger dan eenvoudig hill climbing:

Het bekijkt ALLE nabijgelegen oplossingen voordat het een zet maakt
Kiest de allerbeste optie uit alles wat het vindt
Kost meer tijd, maar vindt meestal betere oplossingen
Het is alsof je elke weg zorgvuldig controleert voordat je een stap zet

3. Stochastisch heuvelklimmen

Deze soort voegt wat willekeur toe om de zoektocht interessanter te maken:

In plaats van altijd de beste oplossing te kiezen, selecteert het willekeurig uit de betere opties
Betere oplossingen hebben een grotere kans om gekozen te worden
Deze willekeurigheid helpt voorkomen vast te komen zitten op slechte plekken
Het is alsof je soms een andere weg neemt om te zien waar het naartoe leidt

Elk type heeft zijn eigen sterke punten en werkt beter voor verschillende soorten problemen. Simpel bergbeklimmen is snel maar basis, steilste-helling is grondig maar langzamer, en stochastisch voegt nuttige willekeur toe om vastlopen te voorkomen.

Hoe het Bergbeklimmen Algoritme Werkt

Het bergbeklimmen algoritme werkt door stap voor stap kleine verbeteringen te maken totdat het de best mogelijke oplossing vindt die het kan. Laten we uiteenzetten hoe het werkt in zijn belangrijkste onderdelen.

1. Aan de slag

Elk heuristisch algoritme voor bergbeklimmen heeft een startpunt nodig. Denk eraan als het kiezen van waar je begint met wandelen op een berg. Je zou willekeurig kunnen beginnen, of je zou kunnen gebruiken wat je weet over het probleem om een goede startplek te kiezen.

Waar je begint is echt belangrijk – kies een goede plek en je zou snel de beste oplossing kunnen vinden. Kies een slechte plek en je zou vast kunnen komen te zitten op een kleine heuvel in plaats van de bergtop te vinden.

Bijvoorbeeld, bij het trainen van neurale netwerken, betekent het startpunt het kiezen van initiële gewichten voor de verbindingen tussen neuronen. Je kunt deze gewichten willekeurig initialiseren, wat vergelijkbaar is met het starten van je wandeling op een willekeurige plek op de berg. Of je kunt technieken gebruiken zoals Xavier-initialisatie die slimme startgewichten kiezen op basis van de netwerkstructuur.

Een goede initialisatie helpt het netwerk sneller te leren en betere oplossingen te vinden, terwijl een slechte initialisatie ervoor kan zorgen dat het netwerk vastloopt met een lage nauwkeurigheid die niet verbetert.

2. Het bekijken van nabijgelegen oplossingen

Zodra het algoritme begint met zoeken, evalueert het naburige oplossingen die vergelijkbaar zijn met de huidige positie. Denk eraan alsof je de directe omgeving in kleine stappen verkent. Bijvoorbeeld, als je probeert een bezorgingsroute tussen steden te optimaliseren, en je huidige route is [A -> B -> C -> D], zou het algoritme vergelijkbare routes bekijken zoals [A -> B -> D -> C] of [A -> C -> B -> D] om te zien of ze de totale afstand verminderen. Elke kleine verandering aan de route vertegenwoordigt een “buur” oplossing die potentieel beter kan zijn dan de huidige.

Om deze vergelijkingen te maken, vertrouwt het algoritme op wat een objectieve functie wordt genoemd – een wiskundige formule die een score of waarde toekent aan elke mogelijke oplossing.

Deze functie werkt als een kompas en helpt het algoritme begrijpen welke richtingen “bergopwaarts” leiden naar betere oplossingen en welke “bergafwaarts” naar slechtere. Voor een bezorgroute zou de doelfunctie de totale afgelegde afstand berekenen – een kortere totale afstand betekent een betere oplossing.

Dus als route X 100 mijl is en route Z 90 mijl is, zou route Z een betere (lagere) score hebben. Het algoritme zou dan weten om in de richting van oplossingen vergelijkbaar met route Z te bewegen. De doelfunctie verandert het complexe probleem van route-optimalisatie feitelijk in een eenvoudig getal dat kan worden vergeleken en geminimaliseerd.

3. De volgende stap kiezen

Na het bekijken van nabijgelegen oplossingen, moet het algoritme beslissen waar het naartoe moet. Het algoritme vergelijkt de scores van nabijgelegen oplossingen met de huidige. Als het een betere oplossing vindt, verplaatst het zich daarheen. Verschillende versies van hill climbing maken deze keuze op verschillende manieren:

De eenvoudige versie neemt de eerste betere oplossing die het vindt
De zorgvuldige versie controleert alle nabijgelegen oplossingen voordat de beste wordt gekozen
De willekeurige versie kiest soms oplossingen die niet de allerbeste zijn, wat kan helpen om vastlopen te voorkomen

4. Weten wanneer te stoppen

Het algoritme moet weten wanneer het moet stoppen met zoeken naar betere oplossingen. Meestal stopt het wanneer een van deze dingen gebeurt:

Er geen betere oplossingen in de buurt te vinden zijn
Het algoritme te lang heeft gedraaid
Het heeft een oplossing gevonden die goed genoeg is

Terwijl het algoritme werkt, volgt het meestal een patroon. In het begin vindt het snel betere oplossingen, zoals grote stappen nemen op een steile heuvel. Dan vertraagt het naarmate het dichter bij de top komt, waardoor het kleinere verbeteringen maakt totdat het uiteindelijk stopt.

Soms is het pad soepel en rechtlijnig, maar andere keren kan het lastig zijn met veel ups en downs.

Voordelen en beperkingen van Hill Climbing in AI

Laten we eens kijken naar wat hill climbing nuttig maakt en tegen welke problemen je kunt aanlopen bij het gebruik ervan.

Voordelen

Hill climbing is een van de eenvoudigste optimalisatiealgoritmen om te begrijpen en te programmeren. Het is als het volgen van een basisregel: “Als iets beter is, ga daarheen.” Dit maakt het een uitstekend startpunt voor het oplossen van veel problemen.

Als het probleem eenvoudig is, kan hill climbing snel goede oplossingen vinden. Het verspilt geen tijd aan het verkennen van elke mogelijke oplossing – het volgt gewoon het pad omhoog.

Het algoritme heeft niet veel computergeheugen of verwerkingskracht nodig. Het hoeft alleen te onthouden waar het is en naar nabijgelegen oplossingen te kijken, waardoor het praktisch is voor veel real-world problemen.

Beperkingen

Natuurlijk zijn er, net als bij elke methode, enkele mogelijke nadelen:

1. Vastlopen op kleine heuvels

Het grootste probleem met heuvelklimmen is dat het kan vastlopen op wat we “lokale maxima” noemen — dit zijn als kleine heuvels terwijl er in de buurt eigenlijk een berg is. Zodra het algoritme de top van een kleine heuvel bereikt, stopt het omdat alles eromheen lager is, ook al kunnen er elders veel betere oplossingen zijn.

2. Het probleem van de vlakke grond

Soms bevindt het algoritme zich op vlakke grond (een plateau genoemd), waar alle nabijgelegen oplossingen even goed zijn. Stel je voor dat je probeert de hoogste punt te vinden terwijl je op een vlak voetbalveld loopt — het is moeilijk te weten welke kant je op moet!

3. Het probleem van de kam

Denk aan proberen te lopen langs de top van een smalle bergkam. Het algoritme kan tijd verspillen met zigzaggen heen en weer over de kam in plaats van vooruit te bewegen naar de piek. Dit gebeurt omdat elke stap naar de zijkant net zo goed lijkt als op koers blijven.

4. Het startpunt is erg belangrijk

Waar je begint kan een groot verschil maken in hoe goed het algoritme werkt. Het is net als het beginnen van een wandeling – begin op de verkeerde plek en je vindt misschien nooit de hoogste piek.

Deze beperkingen betekenen niet dat hill climbing een slechte keuze is – ze betekenen gewoon dat we voorzichtig moeten zijn over wanneer en hoe we het gebruiken. Soms kunnen we het combineren met andere technieken om deze problemen te overwinnen, waar we het in de volgende sectie over zullen hebben.

Strategieën om Beperkingen te Overwinnen

Als we hill climbing gebruiken, kunnen we verschillende slimme strategieën gebruiken om de problemen op te lossen die we eerder hebben besproken. Laten we twee belangrijke benaderingen verkennen die helpen om hill climbing beter te laten werken.

Random-restart hill climbing

Een van de beste manieren om vast te komen te zitten op kleine heuvels te vermijden is door te proberen vanaf verschillende startpunten te klimmen. Deze aanpak wordt random-restart hill climbing genoemd en werkt precies zoals het klinkt – als je vastzit, begin je ergens anders opnieuw.

Stel je voor dat je probeert de hoogste berg in een mistige bergketen te vinden. Als je begint met het beklimmen van de eerste heuvel die je tegenkomt en de top bereikt, loop je het risico een veel hogere berg in de buurt te missen. Maar als je naar verschillende plekken zou kunnen teleporteren en opnieuw zou beginnen met klimmen, zou je uiteindelijk veel meer kans hebben om de hoogste piek te vinden.

Zo werkt het: Allereerst voer je het normale heuvelklimalgoritme uit totdat het vastloopt. In plaats van op te geven, sla je de beste oplossing die je hebt gevonden op en begin je opnieuw op een willekeurig nieuw punt. Dit herhaal je meerdere keren en aan het einde kies je de beste oplossing uit al je pogingen.

De schoonheid van random-restart is dat het eenvoudig maar effectief is. Elke herstart geeft je een nieuwe kans om de hoogste piek te vinden. Hoewel het meer tijd kost dan regulier heuvelklimmen, is het veel waarschijnlijker dat je de beste oplossing vindt.

Simulated annealing

Hoewel het technisch gezien geen heuvelklimmen is, is gesimuleerd annealing een slimme variatie die helpt bij het oplossen van veel van de problemen van heuvelklimmen. Het is geïnspireerd op hoe metalen afkoelen en uitharden bij metaalbewerking. Wanneer metaal langzaam afkoelt, vinden de atomen betere posities, waardoor het metaal sterker wordt.

In deze aanpak accepteert het algoritme soms opzettelijk slechtere oplossingen, vooral in het begin. Na verloop van tijd wordt het kieskeuriger over welke oplossingen het accepteert. Het is als een bal die stuitert over een hobbelig oppervlak — in het begin heeft het genoeg energie om over heuvels heen te stuiteren, maar naarmate het energie verliest, komt het tot rust op een goede plek.

Zo werkt het: In het begin kan het algoritme een oplossing accepteren die slechter is dan de huidige met een vrij hoge waarschijnlijkheid. Deze waarschijnlijkheid hangt af van twee dingen: hoeveel slechter de nieuwe oplossing is en hoelang het algoritme al draait. Naarmate de tijd verstrijkt, wordt het algoritme minder geneigd om slechtere oplossingen te accepteren, uiteindelijk meer als regulier Hill Climbing.

De echte kracht van simulated annealing is dat het kan ontsnappen aan kleine heuvels en vlakke gebieden, vooral vroeg in de zoektocht. Door soms slechtere oplossingen te accepteren, kan het:

Ontsnappen aan lokale maxima (kleine heuvels)
Plateaus oversteken (vlakke gebieden)
Navigeer door richels (smalle pieken)
Verken meer van de oplossingsruimte

Stel je bijvoorbeeld voor dat je probeert meubels in een kamer te ordenen om de ruimte te maximaliseren. Het verplaatsen van een stoel kan de kamer tijdelijk meer druk maken, maar het zou je kunnen toestaan om andere stukken vervolgens in veel betere posities te verplaatsen. Gesimuleerde annealing zou bereid zijn om deze tijdelijk slechtere arrangementen te proberen, vooral in een vroeg stadium van het proces, om het beste totale arrangement te vinden.

Deze strategieën laten ons zien dat soms de beste manier om een probleem op te lossen niet altijd de voor de hand liggende stap vooruit is. Door elementen van willekeur en gecontroleerde chaos toe te voegen, kunnen we vaak betere oplossingen vinden dan wanneer we altijd de rechtlijnige weg zouden volgen.

Implementeren van een eenvoudig algoritme voor het beklimmen van een heuvel in Python

Nu we begrijpen hoe we de bergbeklimming kunnen verbeteren met strategieën zoals random-restart en gesimuleerd gloeien, laten we het toepassen op een echt financieel probleem: portefeuilleoptimalisatie.

Portefeuilleoptimalisatie helpt beleggers beslissen hoe ze hun geld over verschillende investeringen moeten verspreiden. Wanneer beleggers een portefeuille samenstellen, willen ze de hoogst mogelijke rendementen behalen terwijl ze hun risico laag houden. Het vinden van deze balans is lastig – het is als proberen het perfecte recept te vinden met vele ingrediënten.

In 1952 vond een econoom genaamd Harry Markowitz een slimme manier om dit probleem op te lossen. Hij toonde aan dat beleggers hun risico konden verlagen door investeringen te mixen die niet gelijktijdig omhoog en omlaag bewegen. Dit wordt diversificatie genoemd – het is vergelijkbaar met niet al je eieren in één mandje leggen.

Bij het opbouwen van een portfolio moeten we drie belangrijke dingen uitzoeken:

Hoeveel geld we verwachten te verdienen (Verwacht Rendement)
Hoe riskant de investeringen zijn (Portefeuillerisico)
Of de potentiële winsten het risico waard zijn (Risico-gecorrigeerd Rendement)

Hill Climbing werkt goed voor dit probleem omdat kleine veranderingen in hoe we ons geld verdelen meestal leiden tot kleine veranderingen in hoe goed de portefeuille presteert. Stel je een glooiende heuvel voor waar elk punt een andere manier vertegenwoordigt om je geld te investeren. De hogere punten tonen betere investeringskeuzes.

Om een goede portefeuille te vinden met behulp van Hill Climbing, zullen we:

Beginnen met een willekeurige mix van investeringen
Proberen iets andere mixes om te zien of ze beter werken
Kleine verbeteringen blijven maken totdat we geen betere opties kunnen vinden
De beste mix die we hebben gevonden gebruiken

Door hill climbing op deze manier te gebruiken, kunnen we beleggers helpen betere portefeuilles te vinden tussen miljoenen mogelijke combinaties. Het is als het hebben van een slimme assistent die snel veel verschillende beleggingsmixen kan testen om degene te vinden die risico en rendement goed in balans brengen.

Ten eerste, laten we onze doelfunctie definiëren, die een maatstaf is voor portefeuilleprestaties die verwachte rendementen afweegt tegen risico. Het neemt een lijst met portefeuillegewichten als invoer en geeft een score terug, waarbij hogere scores betere portefeuilles aangeven.

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
   """
   # Verwachte jaarrendementen voor activa (voorbeeldwaarden)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, enz.

   # Risico (volatiliteit) voor elk actief
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, enz.

   # Valideer dat de lengte van de invoer overeenkomt met verwachte rendementen/volatiliteiten
   if len(state) != len(expected_returns):
       return float("-inf")  # Geef de slechtst mogelijke score terug voor ongeldige toestanden

   # Bereken verwacht portefeuillerendement
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Bereken portefeuillerisico (vereenvoudigd, geen covariantiematrix gebruikt)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Bestraf als gewichten niet optellen tot 1 (ongeldige portefeuille)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Bestraf negatieve gewichten (geen short selling)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Combineer rendement en risico met risico-aversiefactor van 2
   # Hogere score is beter: maximaliseer rendement, minimaliseer risico en boetes
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

De objective_function hierboven helpt ons beoordelen hoe goed een bepaalde beleggingsportefeuille is. Laten we eens bekijken hoe het werkt:

Ten eerste neemt het een lijst met getallen aan die weergeven welk percentage van ons geld we willen investeren in verschillende activa (zoals aandelen of obligaties). Bijvoorbeeld, als we vijf activa hebben, kunnen we in elk 20% investeren.

De functie maakt gebruik van twee belangrijke stukken informatie:

Verwachte rendementen: Hoeveel geld we verwachten te verdienen met elk activum (zoals 8% of 12% per jaar)
Volatiliteiten: Hoe risicovol elk activum is – hogere getallen betekenen dat de waarde van het activum onvoorspelbaarder verandert (zoals crypto)

De functie berekent vervolgens:

Het totale verwachte rendement van onze portefeuille door het verwachte rendement van elk activum te vermenigvuldigen met hoeveel we erin hebben geïnvesteerd
Berekent de totale risico door te kijken naar de volatiliteit van elk activum
Controleert of onze investeringspercentages optellen tot 100% (dat zouden ze moeten doen!)
Zorgt ervoor dat we geen activa proberen te verkopen die we niet bezitten (geen negatieve percentages)

Tenslotte combineert het al deze informatie in één score. Een hogere score betekent een betere portefeuille. De score stijgt met hogere rendementen maar daalt met hogere risico’s. Het wordt ook veel slechter als onze percentages niet tot 100% optellen of als we proberen negatieve percentages te gebruiken.

Deze functie zal ons helpen om de beste mix van investeringen te vinden met behulp van het hill climbing algoritme dat volgt. Als je de doelfunctie niet volledig begrijpt, maak je geen zorgen – het belangrijkste idee is dat het ons vertelt hoe goed een bepaalde investeringsmix is, en we zullen het gebruiken om steeds betere combinaties te vinden.

Nu gaan we een nieuwe functie definiëren om naburige portefeuillestaten te genereren door kleine aanpassingen aan de gewichten te maken.

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 aanpassing aan gewichten (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Overdracht van gewicht van activum i naar activum j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Alleen overdragen als er genoeg gewicht beschikbaar is
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

De functie get_neighbors is een cruciaal onderdeel van ons hill climbing algoritme dat vergelijkbare portefeuilletoewijzingen genereert door kleine aanpassingen aan onze huidige portefeuillegewichten. Zo werkt het:

Voor elk paar activa in onze portefeuille maakt het een nieuwe portefeuilletoewijzing door een klein bedrag (1%) van het ene activum naar het andere over te dragen. Bijvoorbeeld, als we vijf activa hebben, zal het proberen:

Verplaatsen van 1% van Activum 1 naar Activum 2
Verplaatsen van 1% van Activum 1 naar Activum 3
Verplaatsen van 1% van Activum 1 naar Activum 4
Verplaatsen van 1% van Activum 1 naar Activum 5
Verplaatsen van 1% van Activum 2 naar Activum 1 En zo verder voor alle mogelijke paren.

De functie bevat een veiligheidscontrole om ervoor te zorgen dat we alleen gewicht overdragen als het bronactivum voldoende toewijzing heeft (minstens 1%). Dit voorkomt negatieve gewichten, die geen zin zouden hebben in een echte portefeuille.

Elke van deze kleine aanpassingen creëert een “buur” – een portefeuilletoewijzing die erg lijkt op de huidige, maar iets anders is. Het hill climbing-algoritme zal vervolgens deze buren evalueren om betere portefeuilletoewijzingen te vinden.

De stapgrootte van 1% biedt een goede balans tussen het verkennen van verschillende toewijzingen en het maken van gecontroleerde veranderingen. Een grotere stapgrootte zou optimale oplossingen kunnen missen, terwijl een kleinere de zoektocht te langzaam zou maken.

Nu gaan we eindelijk een eenvoudig hill climbing-algoritme implementeren:

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):
       # Haal naburige staten op
       neighbors = get_neighbors(current_state)
      
       # Vlag om te controleren of we een betere buur hebben gevonden
       found_better = False
      
       # Controleer één voor één de buren (Eenvoudig Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # Als we een betere buur vinden, ga er dan onmiddellijk naar toe
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # Als er geen betere buur is gevonden, hebben we een piek bereikt
       if not found_better:
           break
  
   return current_state, current_value

De functie begint vanuit een initiële staat en verplaatst zich iteratief naar betere naburige staten totdat het een lokaal maximum bereikt of het maximale aantal iteraties bereikt.

De functie neemt twee parameters:

initial_state: Het startpunt voor optimalisatie, weergegeven als een lijst van waarden
max_iterations: Een veiligheidsparameter om oneindige lussen te voorkomen, standaard ingesteld op 1000 iteraties

Het algoritme werkt als volgt:

Het begint bij de initial_state en berekent de waarde van de objectiefunctie
Voor elke iteratie doet het het volgende:

Genereert naburige staten met behulp van get_neighbors()
Evalueert elk buurelement één voor één
Zodra het een betere buur vindt (met een hogere doelwaarde), verplaatst het zich naar die staat
Als er geen betere buur wordt gevonden, heeft het een lokaal maximum bereikt en stopt

De functie retourneert een tuple met:

De beste gevonden staat (lijst van waarden)
De doelwaarde van de functie voor die staat

Deze “eenvoudige” variant van hill climbing is hebzuchtig – het verplaatst zich naar de eerste betere buur die het vindt in plaats van alle buren te evalueren om de beste te vinden. Hoewel dit het sneller maakt, kan het betere oplossingen missen die gevonden hadden kunnen worden door grondiger te zijn.

Het algoritme is handig voor het vinden van lokale optima, maar kan vast komen te zitten op deze lokale maxima, waardoor het mogelijk het globale maximum mist. Ondanks deze beperking blijft het populair vanwege zijn eenvoud en efficiëntie.

Laten we het testen op een voorbeeldportfolio:

# Voorbeeldgebruik
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

De output toont de resultaten van ons hill climbing algoritme bij het optimaliseren van een portfolio. Beginnend met willekeurige gewichten voor vijf activa, vond het een nieuwe set gewichten die de waarde van de objectieve functie verbeterden. Hoewel deze oplossing een verbetering was ten opzichte van het oorspronkelijke portfolio, kan het slechts een lokaal optimum zijn omdat het algoritme stopt bij de eerste piek die het vindt.

Toepassingen van Hill Climbing in AI

Hill Climbing-algoritmen vinden praktische toepassingen in vele gebieden van kunstmatige intelligentie en machine learning. Laten we enkele belangrijke toepassingen verkennen:

1. Optimalisatie van machine learning modellen

Hill climbing helpt bij het afstemmen van machine learning modellen op verschillende manieren:

Kenmerkselectie: Het vinden van de beste subset van kenmerken voor een model
Hyperparameter tuning: Het optimaliseren van modelparameters zoals leersnelheid of boomdiepte
Neurale netwerktraining: Aanpassing van netwerkgewichten en architectuur
Modelcompressie: Het verkleinen van het modelformaat terwijl de prestaties behouden blijven

Bijvoorbeeld, bij het selecteren van kenmerken voor een voorspellend model, zou Hill Climbing kunnen beginnen met alle kenmerken en deze iteratief verwijderen of toevoegen op basis van de prestaties van het model. Dit helpt bij het vinden van een optimaal kenmerkenset die modelnauwkeurigheid in balans brengt met complexiteit.

2. Robotica en padplanning

In de robotica helpt hill climbing bij:

Bewegingsplanning: Het vinden van efficiënte paden door fysieke ruimte
Optimalisatie van gewrichtshoek: Het bepalen van optimale posities voor robotarmen
Sensorplaatsing: Het optimaliseren van de plaatsing van sensoren voor maximale dekking
Batterijbeheer: Het optimaliseren van energieverbruikspatronen

Een robotstofzuiger kan ‘hill climbing’ gebruiken om efficiënte reinigingspaden te vinden, waarbij continu de route wordt aangepast op basis van de ruimte dekking en batterijlevensduur.

3. Natuurlijke taalverwerking

NLP toepassingen omvatten:

Tekst samenvatting: Optimalisatie van de selectie van samenvattingsinhoud
Woord embedding: Het verfijnen van woordvectorrepresentaties
Document clustering: Het organiseren van documenten in optimale groepen
Zoekmachineoptimalisatie: Het verbeteren van de rangschikking van zoekresultaten

Bijvoorbeeld, in tekstsamenvatting kan Hill Climbing helpen bij het selecteren van zinnen die de informatieve inhoud maximaliseren terwijl redundantie wordt geminimaliseerd.

4. Computervisie In beeldverwerking en computervisie

Afbeeldingssegmentatie: Het vinden van optimale grenzen tussen objecten
Camera kalibratie: Aanpassen van cameraparameters voor een betere beeldkwaliteit
Objectdetectie: Optimaliseren van de positie van begrenzingskaders
Kenmerkovereenkomst: Het vinden van overeenkomstige punten tussen afbeeldingen

Een gezichtsherkenningssysteem kan hill climbing gebruiken om de uitlijning van gezichtskenmerken te optimaliseren tijdens de voorverwerking.

5. Game AI en besluitvorming

Hill climbing helpt bij:

Spelstrategieoptimalisatie: Het vinden van winnende zetten in bordspellen
Middelen toewijzing: Optimaliseren van de verdeling van middelen in strategische spellen
NPC-gedrag: Verbeteren van de besluitvorming van niet-speler personages
Niveaugeneratie: Het creëren van gebalanceerde en interessante spellevels

Schaakengines gebruiken vaak varianten van hill climbing om zettenreeksen te evalueren en optimaliseren tijdens het spel.

6. Bedrijfsvoering en operaties

Praktische zakelijke toepassingen zijn:

Optimalisatie van de toeleveringsketen: Efficiënte bezorgroutes vinden
Resourceplanning: Optimaliseren van personeelsroosters of machinegebruik
Portefeuillebeheer: Balanceren van beleggingsportefeuilles
Voorraadbeheer: Optimalisatie van voorraadniveaus

Een bezorgingsbedrijf kan hill climbing gebruiken om continu bezorgingsroutes te optimaliseren op basis van verkeerspatronen en pakketprioriteiten.

Hoewel hill climbing niet altijd de allerbeste oplossing vindt, maken de eenvoud en efficiëntie het waardevol voor deze real-world toepassingen. Het is met name handig wanneer:

Snelle oplossingen nodig zijn
Het probleemgebied te groot is voor een uitputtende zoektocht
Benaderende oplossingen acceptabel zijn
De oplossingsruimte relatief glad is
Het algoritme kan worden gecombineerd met andere technieken voor betere resultaten

Conclusie

Hill climbing staat als een fundamenteel algoritme in kunstmatige intelligentie, en biedt een eenvoudige maar krachtige benadering voor optimalisatieproblemen.

Door onze verkenning hebben we gezien hoe dit eenvoudige concept van iteratief bewegen naar betere oplossingen kan worden toegepast op complexe uitdagingen in machine learning, robotica, natuurlijke taalverwerking en bedrijfsactiviteiten.

Hoewel het algoritme zijn beperkingen heeft, zoals vastlopen in lokale optima, zijn strategieën zoals random-restart en gesimuleerde annealing geëvolueerd om deze uitdagingen effectief aan te pakken.

Naarmate AI blijft evolueren, blijft hill climbing relevant, niet alleen als een praktisch hulpmiddel, maar ook als een opstap naar het begrijpen van meer complexe optimalisatie-algoritmen. De intuïtieve aard ervan maakt het een uitstekend startpunt voor degenen die het vakgebied van AI betreden, terwijl de veelzijdigheid ervoor zorgt dat het blijft worden gebruikt in real-world toepassingen.

Of je nu neurale netwerkgewichten optimaliseert, robotpaden plant of investeringsportefeuilles beheert, de principes van hill climbing bieden waardevolle inzichten in hoe computers systematisch betere oplossingen kunnen vinden voor uitdagende problemen.

Als je meer wilt leren over AI en de algoritmen erachter, bekijk dan onze bronnen:

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