Implementacja AG z uwzględnieniem kilku wątków

0

Cześć! Bardzo proszę o pomoc doświadczone osoby w następującej kwestii:
Chcę napisać prosty "interface"(?) do optymalizowania własnych funkcji (obiektów). Całość chcę zorganizować w ten sposób, że:

  1. Mam pewną klasę bazową (Interface) typu:
class FunkcjaBazowa //Interface
	{
	public:
		virtual double funkcja(vector<double>& data) = 0;
		//... inne funkcje i ew. jakieś zmienne
	};
  1. Po klasie Interface chcę dziedziczyć tworząc własne typy funkcji np.:
class MojaFunkcja1 : public FunkcjaBazowa	// np. jakiś prosty liniowy model
	{
	public:
		double funkcja(vector<double>& data);
		//...
	private:
		vector<double> parametry;	//f(x) = p1*X1 + p2*X2 ...
		//...
	};

class MojaFunkcja2 : public FunkcjaBazowa	//jakaś bardziej skomplikowana funkcja
	{
	public:
		double funkcja(vector<double>& data);
		
	private:
		//zmienne do modelu:
		double zmiennaD1, zmiennaD2, zmiennaD3;
		bool zmiennaB1, zmiennaB2;
		int zmiennaI1, zmiennaI2, zmiennaI3;
	};
  1. Do tego chcę zrobić klasę typu tester, która wprowadzałaby do moich funkcji nowe zmienne i porównywałaby wyniki ze wzorcami oraz zapisywałaby statystyki etc. np.
class tester
	{
	public:
		vector<vecotr<double> > dane;
		vector<double> wzorce;
		void tester(FunkcjaBazowa* moja_funkcja);
		//... inne funkcje/zmienne
	};

Teraz mam do was pytanie, jak najlepiej byłoby do tak zorganizowanego kodu zaprogramować algorytmy genetyczne, które optymalizowałyby kolejne funkcje (pochodne po FunkcjiBazowej)?
Drugie pytanie jak to zorganizować tak, by program korzystał z N wątków (rdzeni)?

Najlepszy pomysł, na który obecnie wpadłem to taki, że klasy pochodne przekazywałyby "jakoś" wskaźniki do zmiennych, które mają być optymalizowane a klasa odpowiedzialna za optymalizację (AG) zapisywałaby te wskaźniki i odpowiednio je modyfikowała. tzn. każdy "osobnik" w AG miałby osobną tablicę wskaźników do optymalizowanych zmiennych w optymalizowanym obiekcie (funkcji).
Problem jaki teoretycznie tu występuje to taki, że zmienne mogą być różnych typów - ale to wydaje mi się, że da się stosunkowo prosto rozwiązać (byłyby różne typy chromosomów).

Nieco większy problem mam z organizacją tego kodu tak, by wykorzystywał maksymalną liczbę rdzeni. No i zastanawiam się czy da się to jakoś "ładnie" rozwiązać ;-)
Bo póki co mam dość niewygodną koncepcję polegającą na tym, że trzeba:
Utworzyć N obiektów Tester, MojaFunkcja i ew. Optymalizator (gdzie N to liczba rdzeni w komputerze) i w każdym wątku przeprowadzać oddzielną optymalizację lub
Utworzyć N obiektów Tester i MojaFunkcja a w optymalizatorze podzielić osobników na N podgrup i każda podgrupa miałaby wskaźniki do n-tego obiektu MojaFunkcja.

Całość ma wyglądać mniej więcej tak:

  1. Tworzymy własną funkcję, która ma być optymalizowana
  2. Przekazujemy wskaźniki do zmiennych, które mają być optymalizowane do obiektu Optymalizator
  3. Optymalizator tworzy N osobników etc.
  4. Każdy osobnik losuje zmienne
  5. Po kolei każdy osobnik wprowadza do obiektu Funkcja swój zestaw zmiennych a następnie uruchamia tester i sprawdza wynik
  6. inne czynności dot. AG (losowanie osobników do krzyżowania, mutacji etc.)

Macie może jakieś lepsze rozwiązanie szczególnie odnośnie wykorzystania wielu wątków lub jakieś uwagi do tego co napisałem?
Z góry bardzo dziękuję za każdą pomoc!

1

Z opisu wydaje mi się że nie zrozumiałeś idei algorytmu AG, radzę jeszcze raz przeczytać uważnie.
Z wątkami najprościej następująco:

  1. Tworzysz X wątków (najlepiej ilość rdzeni minus jeden)
  2. Wątek w oblicza po kolei osobników o indeksach w+0*X, w+1*X, w+2*X, w+3*X ... oczywiście tylko mniejsze od N - ilość osobników
    Przy takim podejściu nawet synchronizować wątki nie musisz, owszem trochę tracisz na tym że przeważnie jeden z wątków się spóźnia a pozostałe (przy takim podejściu) nie "pomagają" spóźnialskiemu, jednak moi testy ujawniły że przy jeszcze całkiem nie dużych N (rzędu 1000) wątki pobierające kolejnego nie obsłużonego tracą (sumarycznie) więcej czasu na synchronizacje.
0

Po pierwsze dzięki za odpowiedź ;-).

_13th_Dragon napisał(a):

Z opisu wydaje mi się że nie zrozumiałeś idei algorytmu AG, radzę jeszcze raz przeczytać uważnie.

Czy mógłbyś napisać dlaczego tak sądzisz (co napisałem, że doszedłeś do takich wniosków)? Pytam z ciekawości ;-).

_13th_Dragon napisał(a):

Z wątkami najprościej następująco:

  1. Tworzysz X wątków (najlepiej ilość rdzeni minus jeden)
  2. Wątek w oblicza po kolei osobników o indeksach w+0*X, w+1*X, w+2*X, w+3*X ... oczywiście tylko mniejsze od N - ilość osobników
    Przy takim podejściu nawet synchronizować wątki nie musisz, owszem trochę tracisz na tym że przeważnie jeden z wątków się spóźnia a pozostałe (przy takim podejściu) nie "pomagają" spóźnialskiemu, jednak moi testy ujawniły że przy jeszcze całkiem nie dużych N (rzędu 1000) wątki pobierające kolejnego nie obsłużonego tracą (sumarycznie) więcej czasu na synchronizacje.

Też tak uważam, ale te rozwiązanie ma pewną wadę - przynajmniej w mojej wersji ;). Mianowicie wymaga przekazania do klasy Optymalizator X obiektów klasy mojej funkcji (dla każdego wątku). Chyba, że jednak da się to jakoś ładnie rozwiązać w klasie Optymalizator? - co by mnie bardzo ucieszyło ;-)

Może w skrócie wyjaśnię dokładniej o co mi chodzi (jak chciałbym, żeby to wyglądało):

Chodzi głównie o to, by klasa Optymalizator była uniwersalna dla każdej klasy pochodnej dziedziczonej po klasie FunkcjaBazowa
Czyli:

  1. Tworzę sobie swoją funkcję np. class MojaFunkcja : public FunkcjaBazowa, gdzie ustalam jak ta funkcja ma wyglądać (np. funkcja liniowa typu: f(x) = P1X1 + P2X2 .. PN*XN, gdzie P to parametry, które będą podlegać optymalizacji) -> SUX, tego dziedziczenia zabrakło w pierwszym poście (EDYTOWAŁEM JUŻ)
  2. Tworzę w funkcji main obiekt klasy Optymalizator i przekazuję do niego wskaźnik do mojej nowej funkcji np. tak:
class MojaFunkcja1 : public FunkcjaBazowa
	{
	//...
	};
class MojaFunkcja2 : public FunkcjaBazowa
	{
	//...
	};
//...
//main:
FunkcjaBazowa* moja_funkcja1 = new MojaFunkcja1;
FunkcjaBazowa* moja_funkcja2 = new MojaFunkcja2;
Optymalizator optymalizator;

optymalizator.optymalizuj(moja_funkcja1);
optymalizator.optymalizuj(moja_funkcja2);

Natomiast celem Optymalizatora jest zoptymalizowanie parametrów przekazanej funkcji.
Teraz wymyśliłem, że w klasie FunkcjaBazowa można dodać funkcję, która zwracałaby jakąś strukturę ze wskaźnikami do optymalizowanych zmiennych tj. dodać
virtual ZmienneOptymalizowane& get_zmienne_do_optymalizacji(); //referecja lub ew. wskaźnik - zakładając, że będzie to obiekt klasy FunkcjaBazowa

Tak jak pisałem wcześniej, wydaje mi się, że najlepszym rozwiązaniem będzie, gdy każdy osobnik AG będzie posiadał wskaźniki do zmiennych optymalizowanych czyli tak na prawdę do obiektu tej mojej funkcji.
Oczywiście wskaźnik do zmiennych służyłby tylko do szybkiego ustawiania nowych wartości zmiennym.
Innymi słowy w osobniku byłyby zakodowane zmienne w postaci np. ciągu bitów, które ulegałyby procesowi krzyżowania/mutacji etc.
Natomiast w celu oceny owych osobników każdy osobnik odkodowałby przechowywane w sobie zmienne -> ustawiał je w obiekcie MojaFunkcja (mając do niej wskaźnik) -> i przeprowadzając testy z ustawionymi zmiennymi.

Jeszcze trochę pomyślę nad implementacją tego i może opiszę to z podaniem konkretnej implementacji. Ale proszę o ocenę tego co napisałem wyżej - czy jest to wykonalne (taka klasa Optymalizatora)? problem polega na tym, że przekazuję tylko jeden wskaźnik do mojego obiektu...

1

Czemu tak uważam, 5 punktów planu na przygotowanie wstępne, 1 punkt planu na podstawę algorytmu AG, na dodatek nie wspomniano o pokoleniach, funkcji stopu itp.
Przekaż do każdego wątku referencje do Optymalizator'a
Nie twórz żadnej klasy, przyjmuj funktor'a to rozwiąże wszystko:

  1. Klasa genom - w zasadzie typedef lub opakowanie do vector<double>
  2. Przyjmujesz funktora jako parametr, zobacz jak zorganizowany trzeci parametr funkcji sort
0
_13th_Dragon napisał(a):

Czemu tak uważam, 5 punktów planu na przygotowanie wstępne, 1 punkt planu na podstawę algorytmu AG, na dodatek nie wspomniano o pokoleniach, funkcji stopu itp.

Heh, bo podstawy są najważniejsze ;-) -> natomiast sama idea AG ogólnie wydaje się prosta - ja mam głównie problem z samą organizacją kodu tak, by później przyjemnie się z niego korzystało ;).

_13th_Dragon napisał(a):

Przekaż do każdego wątku referencje do Optymalizator'a

Jeszcze tego nie widzę ;/. A to nie lepiej, by w klasie Optymalizator były tworzone wątki? Chodzi o to, by później już się nie zajmować tworzeniem wątków a tworzeniem nowych funkcji.

_13th_Dragon napisał(a):

Nie twórz żadnej klasy, przyjmuj funktor'a to rozwiąże wszystko:

  1. Klasa genom - w zasadzie typedef lub opakowanie do vector<double>
  2. Przyjmujesz funktora jako parametr, zobacz jak zorganizowany trzeci parametr funkcji sort

Trochę się pogubiłem ;-(. Której klasy mam nie tworzyć? ;/
Gdzie przyjmuję funktora jako parametr?

Sorry, za być może głupie pytania, ale ciągle to ogarniam...
Będę ogromnie wdzięczny za kolejną odpowiedź.

0
WojtekMS napisał(a):

A to nie lepiej, by w klasie Optymalizator były tworzone wątki?

A choćby i na księżycu, grunt by miały możliwość pobranie do obróbki kolejnego osobnika z populacji, a to prościej zrobić poprzez referencje na populacje.

WojtekMS napisał(a):

Której klasy mam nie tworzyć? ;/

Żadnej z tych:
FunkcjaBazowa
MojaFunkcja1
MojaFunkcja2

WojtekMS napisał(a):

Gdzie przyjmuję funktora jako parametr?

http://www.cplusplus.com/reference/algorithm/sort/ - patrz na trzeci parametr

0
_13th_Dragon napisał(a):

Żadnej z tych:
FunkcjaBazowa
MojaFunkcja1
MojaFunkcja2

To trochę komplikuje sprawę :/.

No nic, muszę to jeszcze przemyśleć.
Dzięki ;-)

1 użytkowników online, w tym zalogowanych: 0, gości: 1