/********************************************************************************
 * Project: FUSS                                                                *
 * Module : fussTSP.h                                                           *
 * Author : Marcus Hutter                                                       *
 * Content: Fittness uniform selection for TSP                                  *
 * Source : http://www.hutter1.de/ai/fuss.htm                                   *
 * Copyright (c) 2000 by Marcus Hutter                                          *
 ********************************************************************************/

/******************** See fussTSP.cpp for further description *******************/

#include <float.h>   // DBL_MAX
#include <math.h>
#include <stdlib.h>  // rand()
#include <stdio.h>   // printf()

/********************************************************************************/
/*                V a r i a b l e s   &   C o n s t a n t s                     */
/********************************************************************************/

#define rrand() ((rand()+(float)rand()/(RAND_MAX+1))/(RAND_MAX+1)) /* random number in [0..1[ */
#define irand(n) ((int)((n)*rrand()))             /* random number in 0..n-1          */
#define NULL 0
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))

/********************************************************************************/
/*                V a r i a b l e s   &   C o n s t a n t s                     */
/********************************************************************************/

//const int NROUNDS = 10000000;           // number of selection/mutation rounds
#define      SELECTMODE  2              // 1=Fuss, 2=Tournamont, ...
const int    TOURNSIZE = 2;             // Tournament size >1
const double T2SSTRENGTH = 1.0;         // Tournament selection strength (0.5..1)

/********************************************************************************/
/*         C i t i e s   w i t h   D i s t a n c i e s   f o r   T S P          */
/********************************************************************************/

const int NCITIES = 1000;     //100;       // maximal number of cities
const int NCSQRT  = 16;
const int CITYGEOMETY =1;               // 1=random matrix, 2=random euklidian

/*------------------------------------------------------------------------------*
  Description: Cities and distancies class
 *-MH---------------------------------------------------------------------------*/
class CCities
/*------------------------------------------------------------------------------*/
{
  public:
    float dist[NCITIES][NCITIES];       // distance between cities
    int   ncities;                      // actual number of cities
  public:
    CCities(int mode=1);                // 1=random matrix, 2=random 2d-euk
};

CCities *cities;


/********************************************************************************/
/*                   I n d i v i d u a l   T S P   P a t h s                    */
/********************************************************************************/

const int INVMEM  = 10000000;          // maximal memory for individuals

/*------------------------------------------------------------------------------*
  Description: Individual class
 *-MH---------------------------------------------------------------------------*/
class CInv
/*------------------------------------------------------------------------------*/
{
  public:
    short  next[NCITIES];               // array of next city pointer
    double length;                      // pathlength
    int    fitness;                     // fitness(pathlength)
  public:
    CInv(const CInv &source);
    CInv(int mode=0);                   // 0=some, 1=random

    double Mutate();
    double Flip2Links(int city, int link);
    double Fitness();
};


/********************************************************************************/
/*              P o p u l a t i o n   o f   I n d i v i d u a l s               */
/********************************************************************************/

const int NINVS         = INVMEM/sizeof(CInv);  // ma
int tninvs              = INVMEM/sizeof(CInv);  // ma
#if (SELECTMODE==1) // Fuss
const int NFITLVL       = 4;
const int NIPF          = 10;           // number of invs per fitness
#else               // StdGATourn
const int NFITLVL       = 1;
const int NIPF          = 10;           // number of invs per fitness
#endif
/*------------------------------------------------------------------------------*
  Description: Population class
 *-MH---------------------------------------------------------------------------*/
class CPop
/*------------------------------------------------------------------------------*/
{
  public:
    CInv  invs[NINVS];                  // array of individuals
    int   ninvs;                        // actual number of individuals
    CInv  *fits[NFITLVL][NIPF];
    int   fmin,fmax;                    // minimal and maximal nonempty fit-level
    int   nipf[NFITLVL];                // number of invs per fitness level
    int   maxnipf;                      // current maximal value <=NIPF
    CInv  *bestinv;                     // best individual in population (including deleted ones!)
  public:
    CPop();
    AddInv(CInv *inv);
    CInv *FussSelect();
    CInv *TournSelect(int ts, double p);
    CInv *SelectInv(int mode);
};

CPop *pop;

/*----------------------------End-of-File-fussTSP.h-----------------------------*/