Konfliktusok módszerei

A minimális konfliktusok módszere a mesterséges intelligenciában egy jól működő módszer. Itt véletlen módon választunk egy elemet, és azt próbáljuk úgy elhelyezni, hogy minimális számú konfliktust generáljon az új helyén. Természetesen azt nem tudhatjuk, hogy hány lépésre lesz szükség, így egy előre megadott határig hajtjuk végre a lépéseket. Bár alapvetően kényszer kielégítési problémára lett megfogalmazva ez a módszer, átfogalmazhatjuk a mi feladatunkra is, ha a célfüggvény-érték az egyes dimenziókhoz tartozó konfliktusokból áll össze.

Ennek módszernek elkészítettük egy variánsát: a max-min konfliktusok módszerét. A módszer egy lépése a következő: kiválasztjuk azt a szűkített környezetet, amelyhez jelenleg a maximális konfliktus tartozik. Majd ezután megvizsgáljuk, hogy a szűkített környezetben melyik értékhez tartozik minimális konfliktus, és erre a szomszédra lépünk. Ezt a lépést addig folytatjuk, amíg csökkenteni tudjuk a konfliktusok számát, azaz a célfüggvény értékét.

Ha valamely feladatban n szűkített környezet van, és mindegyik m elemmel rendelkezik, akkor a hegymászó keresés esetén O(mn) egy lépés bonyolultsága. Max-min konfliktusok esetén O(n) a bonyolultsága annak, hogy a környezetek közül kiválasszuk a legtöbb konfliktust tartalmazót; és O(m) annak, hogy a környezeten belül kiválasszuk az optimális (minimális) elemet, és e kettőnek az összegét kell venni.

Ebben a fejezetben először bemutatjuk a régi módszert, majd a sajátunkat, sőt annak még egy javítását is.

3.13. ábra - Konfliktusok módszereinek osztálydiagramja

Konfliktusok módszereinek osztálydiagramja

Minimális konfliktusok

package hu.unideb.inf.optimization.methods;
import java.util.Random;
/**
 * Minimális konfliktusok módszere:
 * véletlen módon kiválasztott elemet a legjobb helyre rak át.
 * @author ASZALÓS László
 */
public class MinConflict extends SolvingMethod<StateR> {

Az elemek, és azok optimális helyének meghatározását tartalmazó osztály:

protected MinMaxTools mm;

Ez a lépéssorozat használ egy paramétert:

private int MAX_STEPS;

A paraméter értékét a szokott módon állítjuk be:

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

A véletlen indítást követően a megadott lépésszámig új irányokat generálunk, és ott kiválasztjuk a legmegfelelőbb értéket:

@Override
public StateR solve(StateR x) {
    mm = new MinMaxTools();
    x.fillRandom();
    Random r = new Random();
    for (int i = 0; i < MAX_STEPS; i++) {
        int index = r.nextInt(x.numberOfRestrictedNeighbours());
        int value = mm.getOptimalValue(x, index);
        x.setRestrictedValue(index, value);
    }
    return x;
}}

Max-min konfliktusok

A minimális konfliktusok módszerének egy javítása: mindig a leginkább kilógó elemet tekinti, és azt teszi a helyére. Amíg ezzel lehet javítani a célfüggvény értékén, addig folytatja ezt a módszer:

package hu.unideb.inf.optimization.methods;
/**
 * Max-min konfliktusok módszere:
 * minden elemet a neki legjobban megfelelő csoportba helyez át.
 * @author DUSZA Anikó, SZATMÁRI László
 */
abstract public class MaxMinConflictHC extends SolvingMethod<StateR> {

A kilógó elem és annak helyét meghatározó módszerek külön osztályba lettek elhelyezve:

protected MinMaxTools mm;

A módszer előnye, hogy nem függ paraméterektől, amit a keretrendszerrel is tudatni kell:

@Override
public void constants(String name, int numerator, int denominator) {
}

A módszer lényegi részét átemeltük az alábbi metódusba: amíg lehetséges javítani, addig keressük a leginkább kilógó elemet (direction), és annak helyét (best):

/**
 * Gatyába rázza a rendszert.
 * @param x aktuális állapot
 */
protected void MaxMinConflict(StateR x) {
    mm = new MinMaxTools();
    int worst, bestValue; // index
    do {
        worst = mm.getWorstRestrictedNeighbour(x);
        bestValue = searchBestValue(x, worst);
        x.setRestrictedValue(worst, bestValue);
    } while (mm.getDiff() < 0);
}

Nyitva hagyjuk annak kérdését, hogy hogyan lehet megtalálni a legjobb helyet:

/**
 * Mely érték adja a legjobb eredményt a direction indexhez?
 * @param x aktuális csoportosítás
 * @param direction leginkább kilógó elem indexe
 * @return minimális index
 */
abstract protected int searchBestValue(StateR x, int direction);

A megoldás a véletlen kezdőpont megadása után csak a módszer lényegét rejtő eljárás meghívásából áll:

@Override
public StateR solve(StateR x) {
    x.fillRandom();
    MaxMinConflict(x);
    return x;
}}

Jó elem kiválasztása

A max-min konfliktusok módszeréből csak a jó elem megválasztásával maradtunk adósak. Erre egy konkrét metódus létezik a segédosztályban:

package hu.unideb.inf.optimization.methods;

/**
 * Hagyományos max-min konfliktus módszere.
 * @author ASZALÓS László
 */
public class MMCMin extends MaxMinConflictHC {

Ezt a meglévő metódust kell használnunk:

@Override
protected int searchBestValue(StateR x, int direction) {
    return mm.getOptimalValue(x, direction);
}}

Segédosztály konfliktusok kezelésére

A leginkább kilógó elemek, és azok leendő helyének meghatározása:

package hu.unideb.inf.optimization.methods;
/**
 * Minimális konfliktusok módszerének függvényei.
 * @author ASZALÓS László
 */
public class MinMaxTools {

A legrosszabb elem ennyi konfliktust generál:

protected int maxconflicts;

És ennyire lehet lecsökkenteni:

protected int conflicts;   

A lépéssel élért javulás nem lesz más, mint a két érték különbsége:

/**
 * @return javulás értéke
 */
final int getDiff() {
    return conflicts - maxconflicts;
}

Már adott a legrosszabb elem, ennek kell megkeresni a helyét/értékét. Nincs más dolgunk, mint a lehetséges értékek közül kiválasztani azt, melyhez a legkisebb konfliktusszám tartozik, azaz minimum meghatározása szükséges. A visszatérési érték az optimális érték, a minimum értékét a conflicts attribútum tárolja:

/**
 * Megkeresi a leginkább konfliktusos elem optimális helyét.
 * @param x aktuális adatok
 * @param direction legkonfliktusosabb szűkített környezet
 * @return optimális lépés
 */
final int getOptimalValue(StateR x, int direction) {
    int min = 0;
    int actualConflict;
    conflicts = x.possibleConflicts(direction, 0);
    for (int i = 1; i < x.sizeOfRestrictedNeighbours(direction); i++) {
        actualConflict = x.possibleConflicts(direction, i);
        if (actualConflict < conflicts) {
            conflicts = actualConflict;
            min = i;
        }
    }
    return min;
}

A leginkább kilógó elem meghatározása az elemekhez tartozó konfliktusok maximumának meghatározásából áll. A visszatérési érték a leginkább kilógó elem/irány, míg a maximumot a maxconflicts attribútum tárolja:

/**
 * Aktuális állapotban megkeresi a leginkább konfliktusos környezetet.
 * @param x aktuális állapot
 * @return legkonfliktusosabb környezet azonosítója
 */
int getWorstRestrictedNeighbour(StateR x) {
    int max = 0;
    int iConflicts;
    //maximális érték megkeresése
    maxconflicts = x.conflicts(0);
    for (int i = 1; i < x.numberOfRestrictedNeighbours(); i++) {
        iConflicts = x.conflicts(i);
        if (iConflicts > maxconflicts) {
            maxconflicts = iConflicts;
            max = i;
        }
    }
    return max;
}

Ha a programozó maga választ egy irányt, és nem bízza ezt a korábbi metódusra, akkor a conflicts értékét ezzel az eljárással kell beállítani:

/**
 * Átírjuk a megadott szűkített környezet értékét az aktuális állapotban.
 * @param direction szűkített környezet azonosítója
 * @param value szűkített környezethez tartozó érték
 * @param x aktuális adat
 */
void setRNValue(int direction, int value, StateR x) {
    conflicts = x.possibleConflicts(direction, value);
}}

Javított módszer

A módszer szinte egy-egy az egyben megfelel a javítás nélküli párjának, a lényeg a segédosztályban lett elrejtve:

package hu.unideb.inf.optimization.methods;

/**
 * Minimális konfliktusok módszere:
 * minden elemet a neki legjobban megfelelő csoportba helyez át.
 * @author DUSZA Anikó, SZATMÁRI László
 */
abstract public class MaxMinConflictHCV extends SolvingMethod<StateR> {

A kilógó elemet és helyét meghatározó módszerek osztálya:

protected MinMaxToolsV mm;

Ez a módszer is paramétermentes:

@Override
public void constants(String name, int numerator, int denominator) {
}

Eltérés a korábbitól, hogy a segédosztálynak szüksége van a szűkített környezetek számára, amit inicializáláskor adunk át. Ha a legrosszabb elem nem létezik, mert minden irányt kipróbáltunk már, akkor abbahagyhatjuk a keresést.

/**
 * Gatyába rázza a rendszert.
 * @param x aktuális állapot
 */
protected void MaxMinConflict(StateR x) {
    mm = new MinMaxToolsV(x.numberOfRestrictedNeighbours());
    int direction, best; // index
    do {
        direction = mm.getWorstRestrictedNeighbour(x);
        if (direction<0){ return; }
        best = searchBestValue(x, direction);
        x.setRestrictedValue(direction, best);
        if (mm.getDiff()<0){
            mm.clean();
        } else{
            mm.setOld(direction);
        }
    } while (true);
}

Most is nyitva hagyjuk a kérdést:

/**
 * Mely érték adja a legjobb eredényt a <code>worst</code> indexhez?
 * @param x aktuális állapot
 * @param direction leginkább kilógó elem indexe
 * @return minimális index
 */
abstract protected int searchBestValue(StateR x, int direction);

Ugyanaz, mint az előbb:

@Override
public StateR solve(StateR x) {
    x.fillRandom();
    MaxMinConflict(x);
    return x;
}}

Jó elem megválasztása

A korábbihoz hasonlóan a variánsban is az előre megadott metódust használjuk:

package hu.unideb.inf.optimization.methods;
/**
 * Hagyományos max-min konfliktus módszer.
 * @author Aszalós László
 */
public class MMCMinV extends MaxMinConflictHCV {

Ugyanaz mint a másik osztályban:

@Override
protected int searchBestValue(StateR x, int direction) {
    return mm.getOptimalValue(x, direction);
}}

Javított segédosztály

A leginkább kilógó elemek és azok helyének meghatározását felgyorsíthatjuk a korábban megismert értékek tárolásával:

package hu.unideb.inf.optimization.methods;

import java.util.Arrays;

/**
 * Minimális konfliktusok módszerének függvényei.
 * @author Aszalós László
 */
public class MinMaxToolsV extends MinMaxTools {

Tárolni fogjuk, hogy mely irányokat látogattuk meg már:

private boolean[] old;

Tárolni fogjuk a már kiszámolt konfliktusok értékét:

private int[] conflictsArray;

Nevesített konstanssal jelöljük, hogy adott értéket még nem számoltunk ki:

private final static int EMPTY = -1;

Az adatszerkezeteinket a feladattól függően kell inicializálni, ezért paraméter a feladat mérete:

/**
 * Az old adatszerkezet inicializálása
 * @param adatszerkezünk mérete
 */
MinMaxToolsV(int size) {
    old = new boolean[size];
    conflictsArray = new int[size];
    clean();
}

Az adatszerkezeteink alaphelyzetbe állítása:

/**
 * kitakarítja a tömböt
 */
final void clean() {
    Arrays.fill(old, 0, old.length-1, false);
    Arrays.fill(conflictsArray, 0, conflictsArray.length, EMPTY);
}

Ha az adott irányt nem érdemes használni, akkor az jelezzük.

/**
 * Megadott irány letiltása
 * @param i irány, melyet nem használhatunk érdemben
 */
void setOld(int i) {
    old[i] = true;
}

Ha a leginkább kilógó elemet keressük, csak azokkal az irányokkal kell foglalkoznunk, melyekkel még érdemes. Egy iránynál fontos tudni, hogy hogy ezt az értéket kiszámoltuk-e már, vagy sem. Ha igen, akkor azt felhasználhatjuk, egyébként számoljuk ki (és tároljuk le)! Az így előkerülő értékek közül továbbra is a maximálist keressük. Ha minden irány haszontalan, akkor a visszatérési érték -1!

@Override
int getWorstRestrictedNeighbour(StateR x) {
    int max = -1;
    int iConflicts;
    //maximális érték megkeresése
    maxconflicts = 0;
    for (int i = 0; i < x.numberOfRestrictedNeighbours(); i++) {
        if (!old[i]) { // csak azokat vizsgálja, melyet érdemes
            if (conflictsArray[i] != EMPTY){ // ha már ismert
                iConflicts = conflictsArray[i];
            } else {
                iConflicts = x.conflicts(i);
                conflictsArray[i]=iConflicts;
            }
            if (iConflicts > maxconflicts) {
                maxconflicts = iConflicts;
                max = i;
            }
        }
    }
    return max;
}}

Feladatok

  1. A javított módszerben a segédosztályának a clean osztályát hívja meg, mely törli a teljes adatszerkezetet. Használjon csak részleges törlést!

  2. A javított módszernél ne mindig a konfliktusokat számítsa, hanem vegye figyelembe az egyes lépések hatását, és ennek megfelelően differenciát tárolja!

  3. Használjon randomizált változatokat! A leginkább kilógó elemet ne rakja egyből a legjobb helyre, hanem a javulás mértékével arányosan helyezze el! (Hasonlóan a sztochasztikus módszerhez.) Hasonlítsa össze az elért eredményeket!