Kereszt-entrópia

A ritka események szimulációja egy bevett eszköz az optimalizáció területén. Itt a megadott paraméterek alapján véletlen sokaságot generálunk, majd a legjobb elemek alapján egyre pontosítjuk a paramétereket. Ez a módszer, a kereszt-entrópia kakukktojás abban az értelemben, hogy ez nem igazán eredeztethető a természetből. A paramétereket úgy próbáljuk megválasztani, hogy a ritka események igen nagy valószínűséggel forduljanak elő. Ehhez véletlenszerűen generálunk egy kezdeti sokaságot a paramétereink alapján, majd ezeket a paramétereket a legjobb egyedek alapján frissítjük, és kezdődik minden elölről. Ha már a sokaság csak egymáshoz igen hasonló elemekből áll, akkor megállunk.

4.11. ábra - CrossEntropy osztály

CrossEntropy osztály

Kereszt-entrópia implementációja

package hu.unideb.inf.optimization.methods;
import java.util.Arrays;
import java.util.Random;
/**
 * A kis valószínűségű eseményekből közel biztos eseményeket készít.
 * @author Renato MORSIANI
 */
public class CrossEntropy extends SolvingMethod<StateR> {

Három paramétere van a módszernek, az első a sokaság méretét adja meg:

private int N;

A második az elit méretét:

private int E;

A harmadik pedig azt, hogy mekkora eltérést tolerálunk. Ez itt most nem relatív, hanem darabszámban mért abszolút eltérés.

private int epsilon;

A paraméterek beolvasása a szokásos:

@Override
public void constants(String name, int numerator, int denominator) {
    if (name.equals("E")) {
        E = numerator;
    }
    if (name.equals("epsilon")) {
        epsilon = numerator;
    }
    if (name.equals("N")) {
        N = numerator;
    }
}

A módszer által használt adatszerkezet kicsit bonyolultabb, mint korábban. Elsőként szükségünk van a sokaság (pontosabban az elit) tárolására:

private StateR CE[];

Mivel a feladatunk diszkrét, diszkrét eloszlást kell használnunk. A legegyszerűbb módszert használjuk: az egyes állapotokat bináris jelölésben írjuk le, és minden bithez egy Bernoulli elosztást rendelünk. Eme eloszlások p paraméterei helyett azok E-szeresét tároljuk:

private int[] P; 

A következő változó tárolja, hogy egy szűkített környezet elemei hány bittel azonosíthatóak. Ez azt is jelenti, hogy feltesszük, hogy a szűkített környezetek azonos méretűek. Ha ez nem igaz, akkor a program csekély átírására van szükség:

private int bits;

Ahogy korábban többször is, most is mentjük a legjobb megtalált állapotokat:

private StateR xMin;

A korábbiakhoz hasonlóan az adatszerkezetek inicializálásánál a lemásolandó állapotot kapjuk meg, melynek randomizáltját elmentjük a legjobb állapotot tároló változóban. Ezek után kiszámítjuk, hogy hány bit szükséges az állapot kódolására. Majd trükkös módon csak az elit részére foglalunk helyet a memóriában, valamint a generáló paraméterek számára, amelyek számát a szűkített környezetek száma és azok bitekben mért mérete adja meg. Az egyes p paraméterek kezdőértéke 1/2, ami az ábrázolásunk miatt E/2 formában tárolódik:

/**
 * Beállítja a méreteket és feltölti az adatszerkezet
 *  a beolvasott konstansok alapján.
 */
private void ce_initialize(StateR x) {
    x.fillRandom();  
    xMin = (StateR) x.copy();
    bits = (int) Math.ceil((Math.log10(x.sizeOfRestrictedNeighbours(0))
            / Math.log10(2))); 
    CE = new StateR[E];
    P = new int[bits * x.numberOfRestrictedNeighbours()]; 
    Arrays.fill(P, E/2);
}

Először egy szűkített környezetbeli elemet generálunk a p paraméterek alapján. Minden egyes bitről a véletlen dönt. Ha az a paraméternél kisebb, akkor lesz 1 és egyébként 0. Ezekből a bitekből összeállítunk egy számot. Vigyázni kell, ha például a szűkített környezet elemeinek azonosítója 0-tól 5-ig terjed, a generált 6 és 7 értékeket nem fogadhatjuk el. Ilyen esetben újabb elemet generálunk.

/**
 * Egy adott csoport <code>index</code>-edik elemét kiszámító metódus.
 * @param index Szűkített környezet azonosítója 
 * @return a szűkített környezethez rendelt érték
 */
private int generateDataElement(int index) {
    Random rand = new Random();
    int element;
    do {
        element = 0;
        for (int i = 0; i < bits; i++) {
            if (rand.nextInt(E) < P[index * bits + i]) {
                element = element * 2 + 1;
            } else {
                element *= 2;
            }
        }
    } while (element >= xMin.sizeOfRestrictedNeighbours(index));
    return element;
}

Az előbbi metódust alkalmazva minden egyes szűkített környezetre megkaphatunk egy állapotot, melynek kiszámoljuk a célfüggvény-értékét:

/**
 * Egy adott csoportosítás generálása
 */
private void generateState(StateR x) {
    for (int i = 0; i < xMin.numberOfRestrictedNeighbours(); i++) {
        x.setRestrictedValue(i, generateDataElement(i));
    }
    x.calculate(); 
    x.normalize(); 
}

Az előbbi metódust használva generáljuk a sokaságot. E kód korábbi változatában a teljes sokaságot generáltuk és majd rendezés után kiválasztottuk a legjobbakat. Most a tárhely csak az elit tárolására képes. Így kezdetben ennyi állapotot generálunk és egyből tároljuk is. Majd újabb állapot generálásakor a harmónia kereséshez hasonlóan az új állapotot összehasonlítjuk a legrosszabb tárolttal. Ha annál jobb az új, akkor az újat fogjuk tárolni. Ennek eredményeképpen mindig a talált legjobb elemeket tároljuk.

A későbbiekben felhasználjuk, hogy a legjobb állapot az első helyen helyezkedik el:

/**
 * Feltölti a <code>CE</code> tömböt a <code>P</code> vektor alapján.
 */
private void createStates(StateR x) {
    for (int j = 0; j < E; j++) {
        generateState(x);
        CE[j] = (StateR) x.copy();
    }
    Arrays.sort(CE);
    for (int i = E; i < N; i++) {
        generateState(x);
        if (x.getValue() < CE[E - 1].getValue()) {
            CE[E - 1] = (StateR) x.copy();
            Arrays.sort(CE);
        }
    }
}

Az előbb felhasznált rendezések használatát lehetővé teszi az alábbi összehasonlítás:

public int compare(StateR d1, StateR d2) {
    return d1.compareTo(d2);
}

A tárolt legjobb állapotok alapján azok paramétereit meghatározzuk. Ez esetünkben az jelenti, hogy minden tárolt állapot minden egyes szűkített környezete azonosítóját (y) felbontjuk bitekre, és az 1-es biteket a P tömb megfelelő helyén összeszámoljuk:

/**
 * <code>P</code> frissítése a legjobb megoldások alapján.
 */
private void updateP() {
    int y;
    Arrays.fill(P,0);
    for (int i = 0; i < E; i++) {
        for (int j = 0; j < xMin.numberOfRestrictedNeighbours(); j++) {
            y = CE[i].getRestrictedValue(j); 
            for (int k = 1; k <= bits && y > 0; k++) {
                P[j * bits + (bits - k)] += y % 2;
                y /= 2; 
            }
        }
    }
}

A keresési módszer lelke az alábbi metódusban leledzik. Elsőként a paramétereink alapján megkeressünk az N generált állapot közül az E legjobbat.

Ha ezek között az eddig talált legjobbnál is jobb állapotra bukkanunk, természetesen feljegyezzük.

Majd e legjobb állapotok alapján pontosítjuk a paramétereket

private void calculate(StateR x) {
    boolean again;
    do {
        createStates(x); 
        if (CE[0].getValue() < xMin.getValue()) {
            xMin = (StateR) CE[0].copy(); 
        }
        updateP(); 

Ebben az esetben nem lett megadva egy előírt lépésszám. Más módon kell dönteni, hogy befejezzük-e a keresést vagy sem. Erre szolgál az epsilon paraméter: ha valamely p paraméter nem ennyire egyértelmű (azaz szinte nem csak csupa 1-et vagy csupa 0-t kell generálni, akkor újabb fordulóra van szükség:

again = false; 
for (int i = 0; i < P.length && !again; i++) {
    if (P[i] > epsilon && P[i] < (E - epsilon)) {
        again = true;
    }
}
} while (again);}

Ezek után a keresés nem áll másból, mint a kezdeti feltöltés után az előző metódus meghívásából:

@Override
public StateR solve(StateR x) {
    ce_initialize(x);
    calculate(x);
    return xMin;
}}

Feladatok

  1. Változtassa meg az implementációt úgy, hogy a createState metódusban ne kelljen folyamatosan rendezni!

  2. Készítse el a módszer implementációjának egy olyan variánsát, melyben nem bontja bitekre az egészeket!

  3. A valószínűségeket az egész értékek helyett kezelje valósként!

  4. Vizsgálja meg, hogy van-e annak szerepe, hogy a generált állapotokat normalizáljuk!