hegymászó algoritmus

• IPA:

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.

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).

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.

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

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.

Maximalizálni akarjuk az alábbi függvényt egy adott tartományban: $${\displaystyle f(x)=-x^{2}+4x+6}$$

1. Inicializáció:
   • Válassz véletlenszerű kezdőpontot ${\textstyle x_{0}=1}$.
2. Szomszédos megoldások:
   • Nézd meg ${\textstyle f(x)}$-et ${\textstyle x_{0}\pm \Delta x}$-nél (${\textstyle \Delta x=0.1}$).
3. Frissítés:
   • Haladj a jobb irányba (ahol ${\textstyle f(x)}$ nagyobb).

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 = 
        neighbor_values = 

        # Legjobb szomszéd kiválasztása
        best_neighbor = neighbors
        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

#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), f(neighbors)};

        // 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;

        // 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  = 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

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.

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ő.

• hegymászó algoritmus - Értelmező szótár (MEK)
• hegymászó algoritmus - Etimológiai szótár (UMIL)
• hegymászó algoritmus - Szótár.net (hu-hu)
• hegymászó algoritmus - DeepL (hu-de)
• hegymászó algoritmus - Яндекс (hu-ru)
• hegymászó algoritmus - Google (hu-en)
• hegymászó algoritmus - Helyesírási szótár (MTA)
• hegymászó algoritmus - Wikidata
• hegymászó algoritmus - Wikipédia (magyar)