forked from science-ation/science-ation
de761c8b3e
on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
364 lines
9.4 KiB
PHP
364 lines
9.4 KiB
PHP
<?php
|
|
|
|
|
|
class annealer {
|
|
|
|
var $num_buckets;
|
|
var $bucket;
|
|
var $bucket_cost;
|
|
var $bucket_cost_new;
|
|
var $cost;
|
|
var $start_temp, $start_moves;
|
|
var $cost_function_callback;
|
|
var $pick_move_callback;
|
|
var $update_callback;
|
|
var $delta_cost_bucket_ids_callback;
|
|
var $iterations;
|
|
var $items_per_bucket;
|
|
var $max_items_per_bucket;
|
|
var $rate;
|
|
var $move_bucket_ids;
|
|
|
|
function annealer($num_buckets, $start_temp, $start_moves, $rate,
|
|
$cost_function_cb, $items)
|
|
{
|
|
$this->num_buckets = $num_buckets;
|
|
$this->start_temp = $start_temp;
|
|
$this->start_moves = $start_moves;
|
|
$this->cost_function_callback = $cost_function_cb;
|
|
unset($this->pick_move_callback);
|
|
unset($this->update_callback);
|
|
unset($this->delta_cost_bucket_ids_callback);
|
|
|
|
$this->bucket_cost = array();
|
|
$this->bucket_cost_old = array();
|
|
$this->bucket = array();
|
|
$this->iterations = 0;
|
|
$this->items_per_bucket = ceil(count($items) / $num_buckets);
|
|
$this->rate = $rate;
|
|
$this->max_items_per_bucket = 0;
|
|
$ipb = ceil($this->items_per_bucket);
|
|
$i=0;
|
|
$this->cost = 0;
|
|
/* Assign to buckets */
|
|
for($x=0; $x<$num_buckets; $x++) {
|
|
unset($b);
|
|
$b = array();
|
|
for($y=0;$y<$ipb; $y++) {
|
|
if($i == count($items)) break;
|
|
$b[] = $items[$i];
|
|
$i++;
|
|
}
|
|
$this->bucket[] = $b;
|
|
}
|
|
|
|
/* Then do costs after all bucket assignments are done */
|
|
for($x=0; $x<$num_buckets; $x++) {
|
|
$c = $this->cost_function($x);
|
|
$this->bucket_cost[] = $c;
|
|
$this->cost += $c;
|
|
}
|
|
TRACE("Annealer setup: T={$this->start_temp}, ".
|
|
"M={$this->start_moves}, Bkts={$this->num_buckets}, ".
|
|
"Cost={$this->cost}\n");
|
|
}
|
|
|
|
function set_pick_move($func)
|
|
{
|
|
$this->pick_move_callback = $func;
|
|
}
|
|
function set_update_callback($func)
|
|
{
|
|
$this->update_callback = $func;
|
|
}
|
|
function set_delta_cost_bucket_ids_callback($func)
|
|
{
|
|
$this->delta_cost_bucket_ids_callback = $func;
|
|
}
|
|
function set_max_items_per_bucket($num)
|
|
{
|
|
$this->max_items_per_bucket = $num;
|
|
}
|
|
|
|
|
|
|
|
function pick_move()
|
|
{
|
|
/* Pick a bucket and item */
|
|
while(1) {
|
|
$b1 = rand(0, $this->num_buckets - 1);
|
|
if(count($this->bucket[$b1]) > 0) break;
|
|
}
|
|
$i1 = rand(0, count($this->bucket[$b1]) -1);
|
|
|
|
/* Pick a second bucket that is different than the first */
|
|
$b2 = rand(0, $this->num_buckets - 2);
|
|
if($b2 >= $b1) $b2++;
|
|
|
|
|
|
if($this->max_items_per_bucket > 0 && count($this->bucket[$b2]) >= $this->max_items_per_bucket) {
|
|
/* Can't move b1 into b2, it would exceed the max items per bucket, pick an
|
|
* item to swap with */
|
|
$i2 = rand(0, count($this->bucket[$b2])-1);
|
|
} else {
|
|
/* Pick an item, or a blank, in the second bucket */
|
|
$i2 = rand(0, count($this->bucket[$b2]));
|
|
if($i2 == count($this->bucket[$b2])) $i2 = -1;
|
|
}
|
|
// TRACE("Move ($b1,$i1)<->($b2,$i2)\n");
|
|
return array($b1, $i1, $b2, $i2);
|
|
}
|
|
|
|
function cost_function($b)
|
|
{
|
|
$bkt = $this->bucket[$b];
|
|
$cb = $this->cost_function_callback;
|
|
$c = $cb($this, $b, $bkt);
|
|
// $this->print_bucket($b);
|
|
// print("Computed cost to be: $c\n");
|
|
return $c;
|
|
}
|
|
|
|
function compute_delta_cost($move)
|
|
{
|
|
list($b1, $i1, $b2, $i2) = $move;
|
|
|
|
if($b1 == $b2) {
|
|
echo "Called on same bucket, not supported!\n";
|
|
exit;
|
|
// return $this->compute_delta_cost_same_bucket($move);
|
|
}
|
|
|
|
$cost = 0;
|
|
|
|
/* Save the old lists for easy restore */
|
|
$b1_old = $this->bucket[$b1];
|
|
$b2_old = $this->bucket[$b2];
|
|
|
|
/* Setup new costs */
|
|
$this->bucket_cost_new = $this->bucket_cost;
|
|
|
|
/* Compute new lists with swapped elements */
|
|
if($i2 != -1) { /* Swap */
|
|
array_splice($this->bucket[$b1], $i1, 1, $b2_old[$i2]);
|
|
array_splice($this->bucket[$b2], $i2, 1, $b1_old[$i1]);
|
|
} else { /* Move one to other */
|
|
array_splice($this->bucket[$b1], $i1, 1);
|
|
$this->bucket[$b2][] = $b1_old[$i1];
|
|
}
|
|
|
|
/* Get the lists of buckets we need to recompute, by default
|
|
* just b1 and b2 */
|
|
if(isset ($this->delta_cost_bucket_ids_callback)) {
|
|
$cb = $this->delta_cost_bucket_ids_callback;
|
|
$ids = $cb($this, $b1);
|
|
$ids = array_unique(array_merge($ids, $cb($this, $b2)), SORT_NUMERIC );
|
|
} else {
|
|
$ids = array($b1, $b2);
|
|
}
|
|
|
|
// TRACE("Recompute IDs:\n");
|
|
// TRACE_R($ids);
|
|
|
|
|
|
/* Save that list */
|
|
$this->move_bucket_ids = $ids;
|
|
|
|
/* Compute a delta cost, recompute all costs for all buckets */
|
|
foreach($ids as $bucket_id) {
|
|
/* Compute costs */
|
|
$cost -= $this->bucket_cost[$bucket_id];
|
|
$this->bucket_cost_new[$bucket_id] = $this->cost_function($bucket_id);
|
|
$cost += $this->bucket_cost_new[$bucket_id];
|
|
}
|
|
|
|
|
|
/* Save the new lists */
|
|
$b1_new = $this->bucket[$b1];
|
|
$b2_new = $this->bucket[$b2];
|
|
|
|
/* Return to the original bucket lists */
|
|
$this->bucket[$b1] = $b1_old;
|
|
$this->bucket[$b2] = $b2_old;
|
|
|
|
return array($cost, array($b1_new, $b2_new));
|
|
}
|
|
/*
|
|
function compute_delta_cost_same_bucket($move)
|
|
{
|
|
list($b1, $i1, $b2, $i2) = $move;
|
|
|
|
$cost = 0;
|
|
|
|
$b_old = $this->bucket[$b1];
|
|
|
|
$b_new = array();
|
|
/* Make a new bucket list
|
|
for($x=0; $x<count($b_old); $x++) {
|
|
if($x == $i1) {
|
|
/* Swap or remove this index
|
|
if($i2 != -1) $b_new[] = $b_old[$i2];
|
|
} else if($x == $i2) {
|
|
$b_new[] = $b_old[$i1];
|
|
} else {
|
|
$b_new[] = $b_old[$x];
|
|
}
|
|
}
|
|
|
|
/* Assign the new item lists to the buckets
|
|
$this->bucket[$b1] = $b_new;
|
|
|
|
/* Compute costs
|
|
$cost -= $this->bucket_cost[$b1];
|
|
|
|
$c1 = $this->cost_function($b1);
|
|
$cost += $c1;
|
|
|
|
/* Return to the original bucket lists
|
|
$this->bucket[$b1] = $b_old;
|
|
|
|
return array($cost, array($c1, $b_new, 0, array()));
|
|
}
|
|
*/
|
|
|
|
function accept_move($move, $movedata)
|
|
{
|
|
list($b1, $i1, $b2, $i2) = $move;
|
|
list($b1_new, $b2_new) = $movedata;
|
|
|
|
$this->bucket[$b1] = $b1_new;
|
|
if($b1 != $b2) $this->bucket[$b2] = $b2_new;
|
|
|
|
$this->bucket_cost = $this->bucket_cost_new;
|
|
}
|
|
|
|
function anneal()
|
|
{
|
|
$temperature = $this->start_temp;
|
|
$current_cost = $this->cost;
|
|
$last_cost = 0;
|
|
$last_cost_count = 0;
|
|
|
|
if($this->num_buckets <= 1) {
|
|
TRACE("Only one Bucket, nothing to anneal.\n");
|
|
return;
|
|
}
|
|
// $this->print_buckets();
|
|
$estimated_iterations = ceil(log(0.1 / $this->start_temp, $this->rate));
|
|
|
|
// print_r($this);
|
|
$iterations = 0;
|
|
while(1) {
|
|
$moves = $this->start_moves;
|
|
for($m = 0; $m<$moves; $m++) {
|
|
// $this->print_buckets();
|
|
/* Pick 2 moves at random */
|
|
if(isset ($this->pick_move_callback)) {
|
|
$cb = $this->pick_move_callback;
|
|
$move = $cb($this);
|
|
} else {
|
|
$move = $this->pick_move();
|
|
}
|
|
/* See what the new cost is compared to the old */
|
|
list($delta_c, $movedata) =
|
|
$this->compute_delta_cost($move);
|
|
|
|
|
|
$r = floatval(rand()) / floatval(getrandmax());
|
|
/* Decide if we want to keep it */
|
|
$e = exp(-$delta_c / $temperature);
|
|
// TRACE("r=$r, exp=$e, delta=$delta_c\n");
|
|
if($r < exp(-$delta_c / $temperature)) {
|
|
/* Yes, we do, record the move */
|
|
$this->accept_move($move, $movedata);
|
|
$current_cost += $delta_c;
|
|
$n_accepted++;
|
|
// if($current_cost < $this->cost)
|
|
$this->cost = $current_cost;
|
|
|
|
// TRACE("Move accepted, cost=$current_cost\n");
|
|
} else {
|
|
// TRACE("Move rejected\n");
|
|
}
|
|
$this->iterations++;
|
|
if($this->iterations % 10000 == 0) {
|
|
TRACE(" {$this->iterations} iterations, cost={$this->cost}, temperature=$temperature\n");
|
|
// $this->print_buckets();
|
|
}
|
|
|
|
if($this->cost == 0) {
|
|
/* If we manage to get to a 0 cost
|
|
* solution, don't look any more */
|
|
break;
|
|
}
|
|
}
|
|
$iterations++;
|
|
|
|
if(isset ($this->update_callback)) {
|
|
$cb = $this->update_callback;
|
|
$cb($iterations, $estimated_iterations);
|
|
}
|
|
if($this->cost == 0) break;
|
|
|
|
if($this->cost == $last_cost) {
|
|
$last_cost_count ++;
|
|
} else {
|
|
$last_cost = $this->cost;
|
|
$last_cost_count=0;
|
|
}
|
|
|
|
if($temperature < 0.1 && $last_cost_count > 10)
|
|
break;
|
|
// TRACE("Cost is {$this->cost}\n");
|
|
$temperature *= $this->rate;
|
|
/*
|
|
FIXME: README: NOTE: TODO:
|
|
From Kris, 2009-03-24
|
|
Dave do you think we should consider something like this?
|
|
|
|
<Kris_School_1> here's the schedule i use in my academic annealer:
|
|
if( _params._useVPRTempSchedule ) {
|
|
// This is VPR's temperature schedule...
|
|
if( successRate > 0.96 ) {
|
|
_temp *= 0.5;
|
|
} else if( successRate > 0.8 ) {
|
|
_temp *= 0.9;
|
|
} else if( successRate > 0.15 || !windowsSized ) {
|
|
_temp *= 0.95;
|
|
} else {
|
|
_temp *= 0.8;
|
|
}
|
|
} else {
|
|
// This is identical to Aaarts and Van Laarhaven.
|
|
real64 kappa = _params._tempReduction; // 1.0 == slow, 10 = reasonable, 100 == fast
|
|
real64 sqrvar = std::sqrt( variance );
|
|
if( variance <= EPSNEG || sqrvar <= EPSNEG ) {
|
|
_temp = 0.;
|
|
} else {
|
|
_temp = _temp * ( sqrvar / ( sqrvar + kappa * _temp ) );
|
|
}
|
|
}
|
|
*/
|
|
}
|
|
TRACE("Annealing complete. {$this->iterations} iterations. Final cost is {$this->cost}\n");
|
|
}
|
|
|
|
function print_bucket($x)
|
|
{
|
|
$b = $this->bucket[$x];
|
|
print("Bucket $x: (cost: {$this->bucket_cost[$x]})\n");
|
|
print(" ");
|
|
for($y=0;$y<count($b); $y++) {
|
|
print("{$b[$y]} ");
|
|
}
|
|
print("\n");
|
|
}
|
|
function print_buckets()
|
|
{
|
|
for($x=0; $x<$this->num_buckets; $x++) {
|
|
$this->print_bucket($x);
|
|
}
|
|
}
|
|
}
|
|
?>
|