Wikiszótár

hegymászó algoritmus

Magyar

Kiejtés

  • IPA: [ ˈhɛɟmaːsoːɒlɡoritmuʃ]

Főnév

hegymászó algoritmus

  1. (matematika, algoritmusok) A hegymászó algoritmus egy heurisztikus keresési algoritmus, amelyet optimalizációs problémák megoldására használnak. Az algoritmus iteratív módon működik, mindig az aktuális megoldás legjobb “szomszédját” választva. Nevét onnan kapta, hogy a folyamat hasonló egy hegy megmászásához, ahol mindig felfelé haladunk, amíg el nem érjük a csúcsot.


Működési elv

  1. Inicializáció:
    • Kezdj egy véletlenszerű megoldással.
  2. Szomszédos megoldások vizsgálata:
    • Az aktuális megoldás környezetében (szomszédságában) keresd meg a legjobb alternatívát.
  3. Frissítés:
    • Ha találsz egy jobb szomszédot, lépj át oda, és ismételd a folyamatot.
    • Ha nincs jobb szomszéd, az algoritmus megáll.
  4. Lokális optimum:
    • Az algoritmus akkor ér véget, ha elér egy olyan pontot, ahol nincs jobb szomszéd (lokális optimum).


Algoritmus típusai

  1. Egyszerű hegymászó algoritmus:
    • Mindig a legjobb szomszédot választja.
  2. Stochastic Hill Climbing:
    • Véletlenszerűen választ egy szomszédot, amely jobb az aktuálisnál.
  3. Simulated Annealing:
    • Bizonyos valószínűséggel kevésbé jó megoldásokat is elfogad, hogy elkerülje a lokális optimumokat.
  4. First-Choice Hill Climbing:
    • Az első jobb szomszédot választja, amit talál.
  5. Random Restart Hill Climbing:
    • Ha lokális optimumot ér el, újraindítja a keresést egy másik véletlenszerű kiindulópontból.


Előnyök

  1. Egyszerű implementáció:
    • Könnyen érthető és megvalósítható algoritmus.
  2. Gyors futás:
    • Kisebb problémák esetén hatékony.


Hátrányok

  1. Lokális optimumok:
    • Nem garantálja a globális optimum elérését.
  2. Korlátozott keresési tér:
    • Az algoritmus csak a szomszédságban keres, nem veszi figyelembe a globális struktúrát.
  3. Nincs visszalépési lehetőség:
    • Ha egy pontot már elhagyott, nem tér vissza oda.


Példa

Függvény maximalizálása

Maximalizálni akarjuk az alábbi függvényt egy adott tartományban:  

  1. Inicializáció:
    • Válassz véletlenszerű kezdőpontot  .
  2. Szomszédos megoldások:
    • Nézd meg  -et  -nél ( ).
  3. Frissítés:
    • Haladj a jobb irányba (ahol   nagyobb).

Python implementáció

import numpy as np

def hill_climbing(func, start, step_size, max_iterations):
    current_point = start
    current_value = func(current_point)

    for _ in range(max_iterations):
        # Két szomszédos pont: balra és jobbra
        neighbors = [current_point - step_size, current_point + step_size]
        neighbor_values = [func(x) for x in neighbors]

        # Legjobb szomszéd kiválasztása
        best_neighbor = neighbors[np.argmax(neighbor_values)]
        best_value = max(neighbor_values)

        # Ha nincs javulás, állj meg
        if best_value <= current_value:
            break

        # Lépj a legjobb szomszédba
        current_point = best_neighbor
        current_value = best_value

    return current_point, current_value

# Függvény definiálása
def f(x):
    return -x**2 + 4*x + 6

# Hegymászó algoritmus futtatása
start_point = 0.0
step = 0.1
max_iters = 100

opt_point, opt_value = hill_climbing(f, start_point, step, max_iters)
print(f"Optimum pont: {opt_point:.2f}, Optimum érték: {opt_value:.2f}")

Kimenet: 

Optimum pont: 2.00, Optimum érték: 10.00

C++ implementáció

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

// Függvény definiálása
double f(double x) {
    return -x * x + 4 * x + 6;
}

// Hegymászó algoritmus
pair<double, double> hill_climbing(double start, double step_size, int max_iterations) {
    double current_point = start;
    double current_value = f(current_point);

    for (int i = 0; i < max_iterations; ++i) {
        // Két szomszédos pont: balra és jobbra
        vector<double> neighbors = {current_point - step_size, current_point + step_size};
        vector<double> neighbor_values = {f(neighbors[0]), f(neighbors[1])};

        // Legjobb szomszéd kiválasztása
        auto max_it = max_element(neighbor_values.begin(), neighbor_values.end());
        double best_value = *max_it;
        double best_neighbor = neighbors[max_it - neighbor_values.begin()];

        // Ha nincs javulás, állj meg
        if (best_value <= current_value) {
            break;
        }

        // Lépj a legjobb szomszédba
        current_point = best_neighbor;
        current_value = best_value;
    }

    return {current_point, current_value};
}

int main() {
    double start_point = 0.0;
    double step = 0.1;
    int max_iters = 100;

    auto [opt_point, opt_value] = hill_climbing(start_point, step, max_iters);

    cout << "Optimum pont: " << opt_point << ", Optimum érték: " << opt_value << endl;

    return 0;
}

Kimenet: 

Optimum pont: 2, Optimum érték: 10

Alkalmazások

  1. Mesterséges intelligencia:
    • Heurisztikus keresési problémák.
  2. Robotika:
    • Mozgástervezés és pályatervezés.
  3. Optimalizáció:
    • Matematikai és mérnöki problémák megoldása.


Összegzés

A hegymászó algoritmus egyszerű, hatékony eszköz optimalizációs problémák megoldására, különösen akkor, ha a keresési tér jól viselkedő és lokálisan konvex. Hátránya, hogy könnyen elakad lokális optimumokban, ezért más algoritmusokkal (pl. simulated annealing vagy genetikus algoritmus) kombinálva hatékonyabbá tehető.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=hegymászó_algoritmus&oldid=3479698”