accl.h

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

Run Algorithm as follows:

- Construct accl object (constructor requires a pointer
  to a configuration object, to a data collection,
  and an evaluation object)

- Call initialisation routine init()

- Call main routine run()

- Possibly convert spatial distribution to explicit
  partitioning using constructclustering()

- Solution can be visualised by calling routine
  visualize() from parent class clalg
  
- Evaluation object must be initialised by the
  spatial distribution or the explicit partitioning
  or an array of the grid-positions of all data
  elements; subsequently evaluation functions
  can be called


***************************************************/

#ifndef ACCL_JH_2003
#define ACCL_JH_2003

#include "clalg.h"



/*
 class accl


*/

class accl:public clalg {

    class ant;
    class antcolony;


 private:

    antcolony * colony;
    int generation_ctr;



    /* Class Antcolony */
    class antcolony {


    private:

    	/* Array of ants that make up the colony */
	ant * ants;

	/* Toroidal grid, the ants "live" on */
	grid * env;

	/* Pointer to the configuration object encapsulating all parameter settings */
	conf * par;
	





    public:
    	/* Constructor: requires a pointer to the current configuration object
	and a pointer to a grid object */
	antcolony(conf * c, grid * e);

	/* Destructor */
	~antcolony();

	/* Read/Write access to individual members / ants of the colony */
	ant &operator[](int i);

	/* Starting phase: all ants are randomly placed on the grid
	and pick up a data elements */
	void init();

	/* Main phase: members of the colony are subsequently
	activated and transport data elements */
	void cometolive();

	/* Ending phase: all ants drop their data items at the
	position where they picked them up */
	void finish();

    };


    class ant {

    
    	/* Short term memory of an ant */
	class memory {

	    friend class ant;

	public:

	    /* Array of the last transported data items */
	    int * index;

	    /* Array of corresponding dropping positions */
	    position<int>* pos;

	    /* Flag to indicate whether the memory is full.
	       Only then it will be used */
	    int initialized;

	    /* Flag for the intermediate deactivation of the memory
	       until next picking operation */
	    int braindead;
	    
	    /* Pointer to the next writing position in the memory */
	    int ptr;
	    
	    /* Size of the memory */
	    int size;


	    /* Each ant needs a pointer to the environment:
	       this environment provides access to local neighbourhood and
	       permits the comparison of data items
	    */
	    grid * env;

	    /* Constructor:
	       requires a pointer to the environment and the desired size
	       if the memory 
	    */
	    memory(grid * e, int s);

	    /* Desctructor:
	       deletion of the allocated memory
	    */
	    ~memory();

	    /* store a new data item <data> and its corresponding dropping position <p> in the memory */
	    void remember(int data, position<int>& p, double alpha);

	    /* find the best matching data item (for <data>) in the memory and
	       set <p> to the corresponding dropping position */
	    double bestmatch(int data, position<int>&p, ant & a, int clusterphase, int lookahead);

	};

	friend class antcolony;
	friend class memory;

    public:

	/* parameters that can be set individually for each ant */
	double kd;
	double kp;
	double alpha;
	double scalefactor;
	int radius;
	double nsize;
	int size;
	int memsize;
	int speed;

	int failure_ctr;
	int activation_ctr;
	int adapt;

	/* each ant has a memory, a pointer to the grid and a pointer to
	   the current configuration object */
	memory * mem;
	grid * env;
	conf * par;

	/* current ant position on the grid */
	position<int>pos;

	/* grid position where currently carried data item was picked up */
	position<int> lastpos;

	/* currently carried data item */
	int dat;

    public:
    
    	/* Constructor:
	   requires a pointer to the current configuratio object
	   and to the environment 
	*/
	ant(conf * , grid * ec);

	/* Destructor:
	*/
	~ant();

	/* randomly pick up a first data item */
	void init();

	/* drop down the carried data item at the position
	   where it was picked up 
	*/
	void finish();

	/* do one random (possibly biased) move on the grid
	*/
	void move();

	/* try to drop data item; if successful pick up a new one */
	void dropandpick();

	/* threshold function for pickup operation */
	double th_pick(double f);

	/* theshold function for dropping operation */
	double th_drop(double f);

	double square(double x);

	/* memory access for data index and the corresponding position (x and y coordinate respectively) */
	int ithmemory(int i);
	int ithmemoryx(int i);
	int ithmemoryy(int i);


    };


 public:


    /* Construcor:
       requires pointer to the current configuration object,
       the current data collection <bin> and an evaluation
       object */
    accl(conf * par, databin<USED_DATA_TYPE> * bin, evaluation * e);
    
    /* Destructor:
       free all resources
       */
    ~accl();
    
    /* Initialisation:
       construct grid and ant colony
    */
    void init();
    
    /* Run ant algrithm; must be preceeded by initialisation */
    void run();
    
    /* Transform ant solution to explicit clustering using agglomerative clustering */
    void constructclustering();

    /* Single link linkage criterion for agglomerative clustering algorithm */
    double minlink(int * cluster1, int * cluster2, position<double> ** docindex);


};


#endif