Kombinált módszerek

Az összevonás önmagában is felfogható keresési algoritmusnak, ám más módszerekkel összekapcsolva is használhatjuk.

6.2. ábra - Kombinált összevonások osztálydiagramjai

Kombinált összevonások osztálydiagramjai

Minimális konfliktusok és összevonás

A kísérletek alapján a Min-Conflict algoritmus nem adja meg az optimális eredményt. Ezért egy másik módszerrel házasítjuk össze.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
import java.util.Random;
/**
 * Min-Conflict és a Contract kombinációja
 * @author ASZALÓS László
 */
public class MCContract extends SolvingMethod<Cluster> {

Továbbra is szükség van egy korlátra, mely megmondja, hogy a Min-Conflict módszer hány lépését alkalmazhatjuk egymás után:

private int MAX_STEPS;

Ezt a paramétert a szokott módon beolvassuk:

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

A két módszert egy közös ciklusba szerveztük. Ha valamely módszer képes javítani a célfüggvény értékén, akkor teret adunk a másik módszernek. Ha már egyik sem képes javításra, akkor pedig befejezzük a számítást.

@Override
public Cluster solve(Cluster x) {
    MinMaxTools mm = new MinMaxTools();

Mivel összevonással kezdünk a véletlen feltöltés helyett az átlós feltöltést választjuk. Minden elem külön klaszterbe kerül.

ContractTools cnt= new ContractTools();
x.fillDiagonal();

boolean better;
int direction, best;
Random rand = new Random();
do {
    better = false;

amíg van lehetőség hasznos összevonásra, addig összevonunk:

while (cnt.getMaxValue(x) > 0) {
    cnt.contract((Cluster) x);
    better = true;
}

a min-konfliktusnak is végrehajtjuk pár lépését:

for (int i = 0; i < MAX_STEPS; i++) {
    direction = rand.nextInt(x.numberOfRestrictedNeighbours());
    best = mm.getOptimalValue(x, direction);
    if (mm.getDiff() < 0) {
        x.setRestrictedValue(direction, best);
        better = true;
    }
}
} while (better);
return x;
}}

Max-min konfliktusok és összevonás

A Max-min konfliktusok módszerére is ráfér a javítás. Ezt is összekapcsoljuk az összevonás módszerével.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Max-min konfliktusok és Contract kombinációja
 * @author ASZALÓS László
 */
public class MMCContract extends SolvingMethod<Cluster> {

A Max-min konfliktusok módszere nem igényel paramétert, de ezt a keretrendszerrel is tudatosítani kell:

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

A megoldási módszer lényegében megegyezik a korábbival. Egyetlen eltérés az, hogy míg ott egy előre adott lépésig megy az elemek áthelyezése, míg itt addig, amíg javítani tudunk a célfüggvényen:

@Override
public Cluster solve(Cluster x) {
    MinMaxTools mm = new MinMaxTools();
    ContractTools cnt = new ContractTools();
    x.fillDiagonal();

    boolean better;
    int direction, best;
    do {
        better = false;
        while (cnt.getMaxValue(x) > 0) {
            cnt.contract((Cluster) x);
            better = true;
        }
        do {
            direction = mm.getWorstRestrictedNeighbour(x);
            best = mm.getOptimalValue(x, direction);
            if (mm.getDiff() < 0) {
                x.setRestrictedValue(direction, best);
                better = true;
            }
        } while (mm.getDiff() < 0);
    } while (better);
    return x;
}}

Max-min variáns és összevonás

A kilógó elemek vizsgálatánál újra és újra ugyanazokat a szűkített állapotokat kell megvizsgálni. Az itt kapott értékeket tárolva bizonyos számítások megtakaríthatóak, így a módszer felgyorsulhat:

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Segédtömb használata a módszer gyorsítására
 * @author ASZALÓS László
 */
public class MMCContractV extends SolvingMethod<Cluster> {

Összevonás felgyorsítására használt segédtömb hossza:

private int LENGTH;

Ezt a paramétert is be kell olvasni a szokott módon:

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

@Override
public Cluster solve(Cluster x) {
    MinMaxToolsV mm = new MinMaxToolsV(x.numberOfRestrictedNeighbours());

Mivel összevonással kezdünk, a kezdeti feltöltés nem véletlen, hanem átlós lesz:

ContractVectorTools cnt;
x.fillDiagonal();
boolean better;
int direction, best;
do { // common loop
    better = false;
    cnt = new ContractVectorTools(LENGTH);

Amíg hasznos az összevonás, addig vonjunk össze:

while (cnt.getMaxValue(x) > 0) {
        cnt.contract((Cluster) x);
        better = true;
}

Ha az összevonás nem használható, akkor nézzük, van-e kilógó elem?

do { 
    direction = mm.getWorstRestrictedNeighbour(x);
    if (direction >= 0) {

Előfordulhat, hogy minden irányt kimerítettünk, például lokális minimumnál. Ellenkező esetben kapunk egy használható irányt/elemet, és annak kell megkeresni a helyét:

best = mm.getOptimalValue(x, direction);

Ha használható az irány, lépjük meg és könyveljük le. Mivel az elemet más klaszterbe tettük, megváltozhat a kapcsolata más elemekkel: ez csak a korábbi és az új csoportjára jellemző, más csoportoknál nem változik a konfliktusok száma! Ha nem érdemes átrakni az elemet, akkor ezt az információt kell feljegyezni:

if (mm.getDiff() < 0) {
    x.setRestrictedValue(direction, best);
    mm.clean();
} else {
    mm.setOld(direction);
}
better=true;
}

Akkor hagyjuk abba a keresést, ha már minden irányt kimerítettünk.

} while (direction > 0);
} while (better);
return x;
}}