extrema.h

Implementation of genetic algorithm, to search for desired extreme n-variable function.

//---------------------------------------------------------------------------
#ifndef extremaH
#define extremaH

//---------------------------------------------------------------------------
#include <cstdlib>
#include <string>
#include <boost/scoped_ptr.hpp>
#include <boost/array.hpp>
#include <boost/lexical_cast.hpp>
#include "shared_list.h"
#include "sorted_list.h"
#include "tablica.h"
#include <vector>
#include <math.h>

// DEFINICJE POJEC ZWIAZANYCH Z ZASTOSOWANYM ALGORYTMEM GENETYCZNYM
// CHROMOSOM - lancuch, ciag uporzadkowany genow, tutaj dwa ciagi
// binarne w postaci stringu oraz liczba 'int' okreslajaca znak (+1 lub -1)
// GEN - pojedynczy element chromosomu, tutaj znak "0" lub "1"
// LOCUS - pozycja genu w chromosomie
// GENOTYP - zespol chromosomow, tutaj dwa lancuchy genow i znak +1 lub -1
// FENOTYP - punkt przestrzeni poszukiwan, ktorego zakodowana postacia jest genotyp,
//           tutaj liczba rzeczywista okreslajaca wartosc wspolrzednej
// POPULACJA - zespol genotypow
// FUNKCJA OCENY (PRZYSTOSOWANIA) - przystosowanie genotypu, wartosc fitnes,
// tutaj wynik funkcji

//---------------------------------------------------------------------------
namespace EXTR { // okreslamy wlasna przestrzen nazw

//---------------------------------------------------------------------------
using std::string;
// nowy typ do przechowywania ciagu znakow binarnych, np. "1001101001..",
// czyli czesci rzeczywistej i ulamkowej liczby w zapisie dwojkowym,
// ta postac upraszcza operacje mutacji i krzyzowania
typedef string TBinary;

//---------------------------------------------------------------------------
const int PRZEDZIAL = 1e6;  // max. dokladnosc generowanego fenotypu po przecinku

/////// TWSPOLRZEDNA ////////////////////////////////////////////////////////
// wspolrzedna przestrzeni poszukiwan
typedef struct TW
{
	char Sign; // 'A' ... 'Z'
	double Value; // wartosc liczbowa wspolrzednej
     // konstruktory
	TW(void) {}
	TW(char Sign_, double Value_) : Sign(Sign_), Value(Value_) {}
} TWspolrzedna;
//---------------------------------------------------------------------------
// nowy typ do przechowywania wskaznikow do obiektow 'TWspolrzedna'
typedef TSharedList<TWspolrzedna> TWektorOfWsp;
// definicja typu wskaznika do funkcji przystosowania
typedef double __fastcall (*TPFuncOceny)(TWektorOfWsp* WektorOfWsp);

/////// TZAKRES /////////////////////////////////////////////////////////////
typedef struct TZ
{
	char Sign; // os wsp. 'A' ... 'Z'
	double Begin, End;  // np. [X1;X2] - przedzial
     // konstruktor
	TZ(char Sign_, double Begin_, double End_)
		:
		Sign(Sign_), Begin(Begin_), End(End_) {}

} TZakres;

// typ
typedef TSharedList<TZakres> TWektorZakresow;

/////// TGENY ///////////////////////////////////////////////////////////////
typedef struct TG
{
	TBinary BinaryC;  // zapis binarny czesci calkowitej np. "101110110"
	TBinary BinaryU;  // zapis binarny czesci ulamkowej np. "0101100...011"
	int Znak;        // -1 lub 1
	char Sign;       // oznaczenie osi, wspolrzdenej
	//-----------------------------------------------------------------
	// konstruktory
	TG(){}
	TG(TG const* Geny)
	{ BinaryC = Geny->BinaryC; BinaryU = Geny->BinaryU; Znak = Geny->Znak; Sign = Geny->Sign;}
	TG(TBinary const& BinaryC_, TBinary const& BinaryU_, int Znak_, char Sign_)
	:
	BinaryC(BinaryC_), BinaryU(BinaryU_), Znak(Znak_), Sign(Sign_) {}
} TGeny;

// typ kontenera do przechowywania wskaznikow do tworzonych typow 'TGeny'
typedef TSharedList<TGeny> TWektorGenow;

/////// TGENERATOR //////////////////////////////////////////////////////////
class TGenerator
{
  private:
	int ValueC;    // wygenerowana czesc calkowita
	int ValueU;    // wygenerowana czesc ulamkowa
	int   Znak;    // ustalony znak (1 lub -1)

  public:
	// klasa bez jawnego konstruktora
	// po utworzeniu nalezy wywolac funkcje 'Generuj'
	void __fastcall Generuj(TZakres const* Zakres);
	int  __fastcall Get_CzescC(void);
	int  __fastcall Get_CzescU(void);
	int  __fastcall Get_Znak(void);
};

/////// TCHROMOSOM /////////////////////////////////////////////////////////
class TChromosom
{
  private:
	char Sign; // oznaczenie wlasciwej osi wsp.,  'A' ... 'Z'
	//--------------------------------------------------------
	TBinary BinaryC;  // zapis binarny czesci calkowitej
	TBinary BinaryU;  // zapis binarny czesci ulamkowej
	int Znak;        // znak -1 lub 1
	double Fenotyp;  // postac rzeczywista, chromosom w formie nie zakodowanej
	//--------------------------------------------------------

	TGeny* Geny;      // tworzony obiekt pomocniczy

	void __fastcall IntToBinary(int Value, TBinary& Binary);
	int    __fastcall BinaryToInt(string const& Binary);
	double __fastcall BinaryToFenotyp(void);
	double __fastcall IntToFenotyp(int CzescC, int CzescU);
	string __fastcall IntToString(int Value)
	{return boost::lexical_cast<string>(Value);}
	int StringToInt(string Value)
	{return boost::lexical_cast<int>(Value);}
  public:
	// konstruktory
	explicit __fastcall TChromosom(TZakres const* Zakres);
	explicit __fastcall TChromosom(TGeny const* Geny);
	// destruktor
	__fastcall ~TChromosom(void);

	char __fastcall Get_Sign(void);
	double __fastcall Get_Fenotyp(void);
	TGeny* __fastcall Get_Geny(void);
	// polecenie mutacji, w rezultacie zwraca geny do budowy
	// nowego osobnika, parametr pozycja okresla locus od ktorego
	// losowany jest gen do mutacji po przecinku, domyslnie zero
	TGeny* __fastcall Mutacja(int Pozycja = 0);
};

// definicja typu kontenera do przechowywania wskaznikow do tworzonych
// typow 'TChromosom'
typedef TSharedList<TChromosom> TArrayOfCh;

/////// TGENOTYP ////////////////////////////////////////////////////////////
enum TPRECYZJA{P0, P1, P2, P3, P4, P5, P6}; // cyfra - liczba miejsc po przecinku
//---------------------------------------------------------------------------
class TGenotyp
{
  private:
	// wektor chromosomow, czyli np. dla trzech zmiennych trzy chromosomy,
	// jeden dla kazdej osi, tworzony dynamicznie w konstruktorze
	boost::shared_ptr<TArrayOfCh> ArrayOfCh;

	// wynik oceny genotypu, przystosowanie
	double Fitnes;
     TPRECYZJA PRECYZJA;
	// tworzony obiekt pomocniczy
	boost::shared_ptr<TWektorGenow> WektorGenow;

     //-------------------------------------------------------------
     void __fastcall Formatuj(double& Value);

  public:
	// konstruktor, jako argumenty przyjmuje wektor obiektow
	// 'TZakres' w ilosci takiej ile jest zmiennych, oraz wskaznik do
	// funkcji przystosowania
	explicit __fastcall TGenotyp(TWektorZakresow const* WektorZakresow,
                                  TPFuncOceny PFuncOceny, TPRECYZJA PREC);
	// konstruktor, jako argumenty przyjmuje wskaznik do funkcji i geny do budowy
	// chromosomow
	explicit __fastcall TGenotyp(TPFuncOceny PFuncOceny,
                                  TWektorGenow const* WektorGenow, TPRECYZJA PREC);
	__fastcall ~TGenotyp(void);

	// zwraca strukture 'TGeny'
	TWektorGenow const* __fastcall Get_Geny(void);
	// metoda zwraca wartosc fenotypu danego chromosomu
	double __fastcall Get_Fenotyp(int Index) const;
	// metoda zwraca wartosc oceny przystosowania
	double __fastcall Get_Fitnes(void) const;
	// metoda mutacji, zwraca geny do budowy nowego genotypu,
	// mutowany jest chromosom o podanej sygnaturze 'Sign'
	TWektorGenow const* __fastcall Mutacja(char Sign, unsigned Pozycja = 0);
};

// operatory porownania, niezbedne w celu sortowania listy genotypow
bool operator<(TGenotyp const& G1, TGenotyp const& G2)
{return G1.Get_Fitnes() < G2.Get_Fitnes();}
bool operator>(TGenotyp const& G1, TGenotyp const& G2)
{return G1.Get_Fitnes() > G2.Get_Fitnes();}

/////// TPOPULACJA //////////////////////////////////////////////////////////
// typy
typedef TSortedList<TGenotyp, true> TArrayOfGenotyp;
enum TEXTREMUM{MAXIMUM, MINIMUM};  // poszukiwane maksimum badz minimum

//---------------------------------------------------------------------------
class TPopulacja
{
  private:  public:
	// wskazniki
	// wskaznik do wektora genotypow, wektor tworzony dynamicznie
	boost::shared_ptr<TArrayOfGenotyp> ArrayOfGenotyp;
	boost::shared_ptr<TArrayOfGenotyp> GenotypyPoczatkowe;

	// wskaznik pomocniczy do wektora zakresow
	boost::shared_ptr<TWektorZakresow> WektorZakresow;
	// wektor pomocniczy
	boost::shared_ptr<TWektorGenow> WektorGenow;

	// wskaznik pomocniczy do funkcji przystosowania
	TPFuncOceny PFuncOceny;

	// pozycja indeksu 'locus' - procedura krzyzowania
	unsigned PosLocus;
	// numer genu - procedura krzyzowania
	short NrGenu;

	// pomocniczy typ do przechowania wskaznikow genow
	typedef TTablica<TGeny const*, 10> TTab;
	// pomocniczy typ do chwilowego przechowania wskaznikow
	// do obiektow powyzszego typu
	typedef std::vector<TTab*> TWektorTablic;
	boost::shared_ptr<TWektorTablic> WektorTablic;

	// zmienne
	TEXTREMUM EXT;    // poszukiwane maksimum badz minimum

	//----------------------------------------------------------------
	// static constans
	static const unsigned CP_MUTACJI = 20;         // prawdopodobienstwo mutacji (%)
	static const unsigned CP_KRZYZOWANIA = 100;    // prawdopodobienstwo krzyzowania (%)
     static const unsigned CSIGMA = 20;
	static const unsigned CL_GENOTYPOW_POCZ = 5;   // poczatkowa liczba genotypow
	static const TPRECYZJA CPRECYZJA = 4;          // dokladnosc po przecinku - I warunek zatrzymania
	static const unsigned CL_CYKLI = 200;          // max. liczba cykli petli algorytmu - II warunek zatrzymania
     static const unsigned CL_GENOTYPOW_DOC = 100;  //  docelowa liczba genotypow

	// zmienne inicjalizowane wartoscia domyslna
	//----------------------------------------------------------------
     TPRECYZJA Precyzja;
	unsigned PMutacji;
	unsigned PKrzyzowania;
     unsigned Sigma;
	unsigned LGenotypow;
	unsigned LCykli;
     unsigned LGenotypowDoc; 
     unsigned PozycjaLocus;

	//----------------------------------------------------------------
	unsigned LiczbaWspolrzednych; // liczba osi (zmiennych)
	//double Value;     // wartosc extremum

	// metody prywatne
	//--------------------------
	void __fastcall Algorytm(void);
	void __fastcall UtworzPopulacje(void);

     //--------------------------
	void __fastcall Selekcja(void);
	void __fastcall Mutacja(void);
	void __fastcall Krzyzowanie(void);

     void __fastcall WykonajCykle(void);
     void __fastcall Wysegreguj(void);

	double __fastcall SzukajMaximum(void);
	double __fastcall SzukajMinimum(void);
	//--------------------------
	bool __fastcall SprawdzFenotypy(TGenotyp* Genotyp);

     //--------------------------

  public:
	// konstruktor i destruktor
	explicit __fastcall TPopulacja(std::vector<TZakres> const& WektorZakresow,
			 TPFuncOceny PFuncOceny, TEXTREMUM EXT);
	__fastcall ~TPopulacja(void);

	// metody dostepu
	//----------------------------------------
	void __fastcall Set_PMutacji(int PMutacji);           // w procentach
	void __fastcall Set_PKrzyzowania(int PKrzyzownaia);   // w procentach
     // liczebnosc populacji poczatkowej
	void __fastcall Set_LGenotypow(int LGenotypow);
     // parametr majacy wplyw na stopien selekcji
     void __fastcall Set_Sigma(int Value);
     // dokladnosc wyniku po przecinku
	void __fastcall Set_PRECYZJA(TPRECYZJA PRECYZJA);
     // liczba cykli petli selekcja-mutacja-krzyzowanie
	void __fastcall Set_LCykli(int LCykli);
     // liczebnosc populacji ograniczajaca
     void __fastcall Set_PopulacjaDocelowa(int Value);

	//----------------------------------------
	void __fastcall Execute(void);

	TArrayOfGenotyp* __fastcall Get_Array(void);
     TArrayOfGenotyp* __fastcall Get_GenotypyPoczatkowe(void);
};

//---------------------------------------------------------------------------
};    // end of namespace EXTR

//---------------------------------------------------------------------------
#endif   /* plik 'extrema.h' */