Harmónia keresés

Háttér

A harmónia keresés 2001-ig vezethető vissza. Itt a korábbiaktól eltérően nem a biológiából származó ötletekre épül az algoritmus, hanem a zenéből merít, pontosabban a dzsessz az ösztönző. A zenészek ismernek sok jól hangzó harmóniát, mindegyikük kiválaszt egy-egy hangot ezekből, vagy improvizál. Fals hangzás esetén egyik-másik hangon kicsit változtatni kell. Idővel egyre jobban ismerik egymást, egyre jobb és jobb harmóniák születnek.

A módszer a következő paramétereket használja: zenei memória mérete (HARMONY_MEMORY_SIZE), előírt lépésszám (MAX_STEPS), elfogadási arány (ACCEPT), hangolási arány (PITCH). Természetesen szükségünk van egy zenei memóriára is, mely a memory tömbben kap helyet.

4.10. ábra - HarmonySearch osztály

HarmonySearch osztály

Harmónia keresés implementációja

A módszer alapötlete a jazz-ből származik, az ottani harmóniák felelnek meg az állapotainknak:

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
import java.util.Random;
/**
 * Harmony Search (jazz alapján)
 * @author DUSZA Anikó, SZATMÁRI László
 */
public class HarmonySearch extends SolvingMethod<StateR> {

Miután ez is egy sokaságon alapuló módszer több állapotot kell tárolnunk. Ezek számát adja meg az alábbi paraméter:

private int HARMONY_MEMORY_SIZE;

A módszer előírt számú lépésig tart:

private int MAX_STEPS;

Azt, hogy a memóriából dolgozunk, vagy hogy véletlen értéket generálunk, a következő paraméter határozza meg:

private double ACCEPT;

Azt, hogy a memóriából származó értékeket milyen eséllyel kívánjuk megváltoztatni, a következő paraméterrel adhatjuk meg:

private double PITCH;

A paraméterek beolvasása a szokott módon történik:

@Override
public void constants(String name, int numerator, int denominator) {
    if (name.equals("MAX_STEPS")) {
        MAX_STEPS = numerator;
    }
    if (name.equals("HARMONY_MEMORY_SIZE")) {
        HARMONY_MEMORY_SIZE = numerator;
    }
    if (name.equals("r_accept")) {
        ACCEPT = (double) numerator / denominator;
    }
    if (name.equals("r_pa")) {
        PITCH = (double) numerator / denominator;
    }
}

Az adatszerkezetünk egyedül a harmónia memória:

private StateR memory[];

Ennek feltöltése igen hasonlít a korábban alkalmazott feltöltésekre. Újdonság az, hogy megpróbálkozunk az állapot normalizálásával, mert úgy érezzük, hogy ezzel jobb eredményt lehet elérni:

/**
 * A harmónia memória inicializálása.
 */
private void hsInitialize(StateR x) {
    memory = new StateR[HARMONY_MEMORY_SIZE];
    for (int i = 0; i < memory.length; i++) {
        memory[i] = (StateR) x.copy();
        memory[i].fillRandom();
        memory[i].normalize(); 
        memory[i].calculate();
    }
}

Ahogy a harmónia is több hangból áll, az állapotunk is több szűkített környezetből áll össze. Az i-dik hang beállítása következőképpen történik: az ACCEPT paraméter által meghatározott eséllyel kiválasztunk egy véletlen i-dik értéket, melyen a PITCH paraméter szerinti eséllyel hangolunk, azaz valamely szomszédos értékre változtatjuk. Az általunk vizsgált feladatoknál ennek a hangolásnak túl sok szerepe, esélye nem volt, viszont elképzelhető olyan diszkrét feladat is, melynél hasznos. Ha a véletlen úgy döntött, hogy véletlen adatot használunk az i-dik hangra, akkor azt a határok figyelembevételével kell megtennünk. Végezetül tároljuk a kiválasztott értéket:

private void chooseI(StateR x, int i) {
    Random rnd = new Random();
    double ra = rnd.nextDouble();
    double rp = rnd.nextDouble();
    int value;
    if (ra < ACCEPT) {
        value = memory[rnd.nextInt(HARMONY_MEMORY_SIZE)]
                .getRestrictedValue(i);
        if (rp < PITCH) {
            if (rnd.nextBoolean()) {
                if (value < x.sizeOfRestrictedNeighbours(i) - 1) {
                    value++;
                }
            } else {
                if (value > 0) {
                    value--;
                }
            }
        }

    } else {
        value=rnd.nextInt(x.sizeOfRestrictedNeighbours(i));
    }
    x.setRestrictedValue(i, value);
}

A keresés módszere ezután már igen egyszerű. A kezdeti véletlen feltöltés után az előírt lépésszámban végrehajtjuk a ciklusmagot. A ciklusmagban lépésről lépésre megadjuk az állapotot az előbb ismertetett metódus többszöri alkalmazásával, majd kiszámoljuk a célfüggvény értékét erre az új állapotra.

Ha ez jobbnak minősül a harmónia memóriában szereplő legrosszabb állapottól, akkor felváltjuk vele. Ehhez az egyszerűség kedvéért mi rendeztük a memóriát, és a legrosszabb, azaz legutolsó állapottal hasonlítottuk össze.

Ha az összes ciklus véget ért, akkor a rendezett memória elején elhelyezkedő, azaz legjobb állapottal tér vissza a rutin:

/** Harmónikus keresés algoritmusa */
@Override
public StateR solve(StateR x) {
    hsInitialize(x);
    for (int t = 0; t < MAX_STEPS; t++) {
        x.clean();
        for (int i = 0; i < x.numberOfRestrictedNeighbours(); i++) {
            chooseI(x, i);
        }
        x.calculate();
        Arrays.sort(memory);
        if (memory[HARMONY_MEMORY_SIZE - 1].getValue() > x.getValue()) {
            x.normalize();
            memory[HARMONY_MEMORY_SIZE - 1] = (StateR) x.copy();
        }
    }
    return memory[0];
}}

Feladatok

  1. Viszgálja meg, hogy segít-e az eredményeken az, hogy a generált új állapotokat normalizálja, vagy sem.

  2. Az állapotok vektorát kezelje kupacként, hogy ne kelljen a rendezéssel foglalkozni.