<?
/*
* This file is part of the 'Science Fair In A Box' project
* SFIAB Website: http://www.sfiab.ca
*
* Copyright (C) 2005-2008 Sci-Tech Ontario Inc <info@scitechontario.org>
* Copyright (C) 2008-2012 Youth Science Ontario <info@youthscienceontario.ca>
* Copyright (C) 2005-2012 James Grant <james@lightbox.org>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License as published by the Free Software Foundation, version 2.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; see the file COPYING. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
?>
<?
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;
// if we go 1 million iterations without changing the cost, lets give up
if ($last_cost_count > 1000000)
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);
}
}
}
?>