/*  Ant-based Clustering    Copyright (C) 2004 Julia Handl    Email: Julia.Handl@gmx.de    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; either version 2 of the License, or    (at your option) any later version.    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; if not, write to the Free Software    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA*//***************************************************date: 7.4.2003author: Julia Handl (Julia.Handl@gmx.de)Description: implementation of ant-based clustering,see header file for more details***************************************************/#include <time.h>#include "accl.h"#include "tmatrix.h"#include "evaluation.h"#include "random.h"extern long idum;/***************************************************     antcolony***************************************************//* Constructor for the antcolony:   allocation of memory, storage of pointers and    initialization of random distribution*/accl::antcolony::antcolony(conf * c, grid * e) {    env = e;		       par = c;    ants = new ant[par->colonysize](c, e);    }/* Destructor for the antcolony:   deletion of memory*/accl::antcolony::~antcolony() {    delete [] ants; }/* Overloaded [] operator:   write-read access to individual ants*/accl::ant & accl::antcolony::operator[](int i) {    return ants[i];}/* Initialization of the antcolony:   initialization of the individual ants with a data element,   must preceed a call of accl::antcolony::cometolive()*/void accl::antcolony::init() {     for (int i=0; i<par->colonysize; i++) {	ants[i].init();     }}/* Main sorting routine (representing one ant "generation")   requires previous initialization with accl::antcolony::init()   requires subsequent completion with accl::antcolony::finish()*/void accl::antcolony::cometolive() {    /* initialization of counters needed       for the individual adaptation of alpha    */    if (par->adaptalpha == TRUE) {	for (int a=0; a<par->colonysize; a++) {	    ants[a].failure_ctr = 0;	    ants[a].activation_ctr = 0;	}    }    int j = 0;    /* main loop */    while (j++ < par->generation_length) {	/* random selection of one ant */	int a = int(ran0(&idum)*par->colonysize);	/* random move of the selected ant on the grid	   possibly biased by the memory 	*/	ants[a].move();	/* attempt to drop the data element at the current position	  a successful dropping operation must be followed by	  a successful picking operation (i.e. the ants keep trying	  until it finds a suitable data item)	*/	ants[a].dropandpick();	/* control of the adaptation of alpha	 */	if (par->adaptalpha == TRUE) {	    ants[a].activation_ctr++;	    /* do alpha adaptation for an ant after it has been	       active 100 times */	    if ( ants[a].activation_ctr >= 100) {		/* decrease alpha, if the ant is too successful*/		if (double(ants[a].failure_ctr) / double(ants[a].activation_ctr) <= 0.99 ) {		     ants[a].alpha -= 0.01;		     ants[a].alpha = max(ants[a].alpha, 0.01);		     ants[a].scalefactor = ants[a].alpha;		     /* reinitialize counters */		     ants[a].failure_ctr = 0;		     ants[a].activation_ctr = 0;		}		/* increase alpha, otherwise */		else {    		    ants[a].alpha += 0.01;		    ants[a].scalefactor = ants[a].alpha;// * par->mu;		    ants[a].failure_ctr = 0;		    ants[a].activation_ctr = 0;		}	    }	}    }}/* completion of the sorting process:   all ants drop their data elements    follows a call of accl::antcolony::cometolive   must preceed a statistical evaluation of the grid data*/void accl::antcolony::finish() {    for (int i=0; i<par->colonysize; i++) {    	ants[i].finish();    }}/***************************************************     memory***************************************************//* constructor for the memory:  memory allocation, iniialization and storage of a pointer to the environment*/accl::ant::memory::memory(grid * e, int s) {    env = e;    size = s;    pos = new position<int>[size];    index = new int[size];    for (int i=0; i<size; i++) {	index[i] = FREE;    }    initialized = FALSE;    ptr = 0;    braindead = TRUE;}/* destructor for the memory:       deletion of memory*/accl::ant::memory::~memory() {    delete [] index;    delete [] pos;}/* memorization of a new data element:   storage of both index and position of a   transported data item   organized as a fifo memory*/void inline accl::ant::memory::remember(int d, position<int> & p, double alpha) {   index[ptr] = d; pos[ptr] = p; ptr = (ptr+1) % size; /* activation of memory after insertion of a new data element    braindead ensures that an ant checks out    the stored position only once */ braindead = FALSE; /* start of memory use once it is "full" */ if ((initialized == FALSE) && (ptr == 0)) {     initialized = TRUE; }}/* brainstorming for a given data element:   scan the memory to look for the best matching data item   the respective grid position is stored within parameter p   the dropping probability dependent on the quality of the match is returned*/double accl::ant::memory::bestmatch(int data, position<int> &p, ant & a, int clusterphase, int lookahead) { double temp; double q; int retindex; /* loop to check similarity */ if (lookahead == TRUE) {     q = env->f(data, pos[0], a.radius, (int)(a.nsize), a.scalefactor, clusterphase); } else {     q = env->dissimilarity(data, index[0]); } retindex = 0; for (int i=1; i<size; i++) {     /* ignore free memory cells */     if (index[i] == FREE) continue;     if (lookahead == TRUE) {	 temp = env->f(data, pos[i], a.radius, int(a.nsize), a.scalefactor, clusterphase);     }     else {	 temp =  env->dissimilarity(data, index[i]);     }     if (lookahead == TRUE) {	 if (temp > q) {	     // best match so far	     retindex = i;	     // quality of match	     q = temp;	 }     }     else {	 if (temp < q) {	     // best match so far	     retindex = i;	     // quality of match	     q = temp;	 }     } } /* set position to that of best found match */ p = pos[retindex]; /* return the threshold for the use of the memory */ if (lookahead == TRUE) {         return a.th_drop(q/double(a.radius)); } else {     return a.th_drop(1.0-q); }}/***************************************************     ant***************************************************//* constructor for an individual ant:   initialization of individual parameter settings,   storage of pointers to the environment, memory allocation  and initialization of random distributions*/accl::ant::ant(conf * c, grid * e) {    env = e;    par = c;    /* individual parameter settings       (for now we just use the common ones)    */    kd = c->kd;    kp = c->kp;    if (c->adaptalpha == TRUE) {	alpha = ran0(&idum);	adapt = TRUE;    }    else {	alpha = c->alpha;	adapt = FALSE;    }    /* compute scaling factor for neighbourhood function ("size" of the neighbourhood) */     nsize = 0;    radius = c->radius;    if (par->weighting == TRUE) {	for (int dx=0; dx <= c->radius; dx++) {	    for (int dy=1; dy <= c->radius; dy++) {		nsize += 4*exp(-double(max(dx, dy))/double(par->radius));	    }	}    }    else {	nsize = (radius*2+1)*(radius*2+1)-1;    }    memsize = c->memorysize;    speed = (int)(0.5*c->imax);    scalefactor = alpha;    failure_ctr = 0;    activation_ctr = 0;    dat = FREE;    if (memsize > 0) {	mem = new memory(env, memsize);    }}/* destructor for an individual ant:   deletion of memory*/accl::ant::~ant() {    if (memsize > 0) delete mem;}/* initialization of an individual ant:   picking of a random data element*/void accl::ant::init() {    /* fill memory right in the beginning */    for (int i=0; i<par->memorysize; i++) {	int index = int(ran0(&idum)*(par->binsize - par->colonysize));	mem->remember(index, env->getposition(index),alpha);    }     /* pick up a random data element from the grid */    dat = env->remove_init(&pos);}/* finishing phase of ant activity:   drop carried data item at pickup position*/void accl::ant::finish() {    /* go to pickup position */    pos = lastpos;    /* drop data item at free grid position */    pos = env->searchdroppingsite(pos, dat);    env->add(pos, dat);    if (memsize > 0) {	mem->remember(dat, pos, alpha);    }    dat = FREE;}/* move of an individual ant:   if the memory is initialized, then   - determine the best match   - make a probabilistic decision whether to use the memory     (bias dependent on quality of match)   else random move*/void inline accl::ant::move() {    position<int> temp;    /* memory-based move */    if ((memsize > 0) &&	(mem->initialized == TRUE) &&	(mem->braindead == FALSE) &&	(ran0(&idum)-0.5 < mem->bestmatch(dat, temp, *this, par->clusterphase, par->lookahead))) {	    	/* go directly to the stored position */	pos = temp;	/* deactivate memory until next picking operation */	mem->braindead = TRUE;     }    /* random move */    else {	/* stepsize is randomly split in x and y part,	   orientation is also randomly determined	*/	double rnd = ran0(&idum);	int dx = (int)(ran0(&idum)*speed);	int dy = speed-dx;	if (rnd < 0.25) {	    dx = -dx;	    dy = -dy;	}	else if (rnd < 0.5) {	    dx = -dx;	}	else if (rnd < 0.75) {	    dy = -dy;	}	/* move with integrated border check (for	   toroidal grid)	*/	pos.add(dx, dy, par->imax, par->jmax);    }}    /* coupled drop and pick operation for an individual ant   a drop is tried, if it succeeds   - a new data element has to be picked up   - the grid index of all "free" data items is used     (currently randomly indexed)                                                  - the ant keeps trying until it's "loaded" again                                else the routine is finished*/void accl::ant::dropandpick() {    /* examine local neighbourhood */    double fvalue = env->f(dat, pos, radius, int(nsize), scalefactor, par->clusterphase);    /* probabilistic dropping decision */    if (ran0(&idum) < th_drop(fvalue)) {