accl.c

C++蚂蚁实现/C++蚂蚁实现 C++蚂蚁实现

/*  Ant-based Clustering
    Copyright (C) 2004 Julia Handl
    Email: [e-mail]

    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.2003

author: Julia Handl ([e-mail])

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) {
   // cerr << q << " " << a.radius << " " << q/double(a.radius) << " " << a.th_drop(q) << endl;
       return a.th_drop(q);
       // return a.th_drop(q/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))) {
	(ran0(&idum) < 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 */