Du bist hier: Start › PHP › Scripts › Lokale Suchalgorithmen: Ausglühen, Schwellenwert und ZufallsanstiegDieses Snippet kommentieren

Simuliertes Ausglühen, Schwellenwert und Zufallsanstieg

Berchnet die besten lokalen Lösungen für das TSP-Problem. Das Strecken-Array gibt die Kosten für den Weg zwischen zwei Knoten an. 6 “Städte” werden verwendet.

<?php

/*
SYNOPSIS:
 evola.php [ausgluehen|zufall|schwellenwert] maxDurchlaeufe [Starttemp|Schwellenwert]
*/

$modus   = $argv[1];          // ausgluehen, zufall oder schwellenwert
$T       = intval($argv[3]);  // Starttemperatur (für $modus=ausgluehen)
$PHI     = intval($argv[3]);  // Schwellenwert
$maxRuns = intval($argv[2]);  // maximale Generationen

$strecken = array(
    '1_2' => 5,
    '1_3' => 8,
    '1_4' => 11,
    '1_5' => 3,
    '1_6' => 7,
    '2_3' => 10,
    '2_4' => 4,
    '2_5' => 9,
    '2_6' => 12,
    '3_4' => 6,
    '3_5' => 17,
    '3_6' => 8,
    '4_5' => 6,
    '4_6' => 5,
    '5_6' => 11,
);

$kandidatA = array(6,4,1,5,3,2);
shuffle($kandidatA);

$loesungen   = array();
$loesungen[] = $kandidatA;
$maxDiff     = -20000; // Merkvariable für Ausglühen

for ($runs = 0; $runs < $maxRuns; ++$runs) {
    $fittnessA = bewerte(end($loesungen)); // A(t-1).F
    $kandidatB = mutation(end($loesungen));
    $fittnessB = bewerte($kandidatB); // B.F
    
    if (akzeptanz($fittnessA, $fittnessB, count($loesungen))) {
        $loesungen[] = $kandidatB;
    }
    else {
        $loesungen[] = end($loesungen); // A(t-1)
    }
    
    $T *= 0.95; // für Ausglühen
    if ($runs % 10 == 0 && $runs > 0) $PHI--; // für Schwellenwert
    
    // Ausgabe
    $f = bewerte(end($loesungen));
    print abs($f).": ".str_repeat("#", -$f)."\n";
}

print implode(',', end($loesungen)); // Letzte Lösung ausgeben





function bewerte($kandidat) {
    global $strecken;
    $summe = 0;
    for ($i = 0; $i < 6; ++$i) {
        $von  = $kandidat[$i]; // 0..5
        $nach = $kandidat[($i + 1) % 6]; // 1..0
        
        if ($von>$nach) { $t = $von; $von = $nach; $nach = $t; }
        $summe += $strecken[$von.'_'.$nach];
    }
    return -$summe;
}

function mutation($kandidat) {
    $z1 = rand(0,5);
    $z2 = rand(0,5);
    while ($z1 == $z2) $z2 = rand(0,5);
    $t = $kandidat[$z1];
    $kandidat[$z1] = $kandidat[$z2];
    $kandidat[$z2] = $t;
    return $kandidat;
}

function akzeptanz($a,$b,$t) {
    global $modus, $maxDiff;
    
    switch ($modus) {
        case 'ausgluehen':
            
            global $T;
            
            if ($b-$a > $maxDiff) $maxDiff = $b-$a;
            
            if ($b > $a) return true;
            $u = rand(0,100000) / 100000; // [0..1]
            $k = $maxDiff;
            if ($u <= exp(-(($a-$b) / ($T*$k)))) return true;
            else return false;
            
        case 'schwellenwert':
        
            global $PHI;
            return (($b > $a) || ($a-$b < $PHI));
        
        case 'zufall':
            
            return $b > $a;
    }
}

?>

Kommentar verfassen

Fehler gefunden? Doofer Code? Ein kleines "Danke!"? Hinterlasse einfach einen Kommentar.

(muss sein)
(muss nicht sein, wird nicht angezeigt)

Dein Kommentar wird erst nach einer manuellen Prüfung angezeigt.