Algorytmy genetyczne

kde-nsplugin-generatedWiele problemów optymalizacji cechuje się tym, że znalezienie dokładnego rozwiązania może zajmować bardzo dużo czasu. Istnieje sporo metod optymalizacji, wśród których wyróżnić można metody ukierunkowanego poszukiwania optimum oraz metody poszukiwania przypadkowego.
Poszukiwanie ukierunkowane zwykle oparte jest na jakiejś odmianie metody najszybszego spadku. Źródłem problemów przy ukierunkowanej optymalizacji są głównie ekstrema lokalne. Stochastyczne poszukiwanie rozwiązań także nie gwarantuje sukcesu.
Na bazie tych obserwacji powstała koncepcja, żeby poszukiwaniami optymalnego rozwiązania (uzyskiwanego za pomocą komputera) kierował proces ewolucji. Metody ewolucyjne powstały i zostały rozwinięte w tym celu, żeby znajdować przybliżone rozwiązania problemów optymalizacyjnych w taki sposób, by znajdować wynik w miarę szybko oraz uniknąć pułapek minimów lokalnych.

Algorytmy genetyczne, oparte są na mechanizmach doboru naturalnego i genetyki. Zasady ich funkcjonowania zostały zaczerpnięte z biologii. Idea działania takich algorytmów, jak sama nazwa wskazuje, opiera się na genetycznych zmianach wywoływanych w procesie ewolucji. Podstawą tych algorytmów jest teoria Darwina, a więc teoria ewolucji.

Algorytmy genetyczne nie wymagają od użytkownika znajomości szczegółów procesu optymalizacji danego zadania. Wymagane jest jedynie określenie pewnej funkcji, zwanej funkcją przystosowania, której wartość będzie maksymalizowana w kolejnych przebiegach algorytmu. Algorytmy tego typu doskonale nadają się do rozwiązywania problemów, w których nie są znane zależności między parametrami, czyli problemów nieprecyzyjnie określonych. Określa się je jako metody odporne, czyli metody dające dobre rezultaty w większości problemów. Takich cech nie posiada wiele tradycyjnych metod optymalizacyjnych.

Zastosowanie algorytmu genetycznego nie musi dać rozwiązania najlepszego. Jednak jedno jest pewne — są to rozwiązania najlepsze przy założeniu rozsądnego czasu poszukiwań.

Symulowane wyżarzanie (Simulated Annealing) to algorytm z rodziny algorytmów „Generuj i Testuj” i stanowi modyfikację algorytmu wspinaczki (ang. Simple Hill Climbing), w którym dopuszcza się na początku przejścia ze stanu bieżącego także do stanów gorszych. Dzięki temu można uniezależnić się od punktu startowego i uzyskać możliwość przebadania znacznie większego obszaru przestrzeni rozwiązań.

SA jest chętnie stosowaną techniką optymalizacyjną w różnorodnych zadaniach ze względu na swoje zalety, do których należą:

  • zdolność do znajdowania rozsądnego rozwiązania niezależnie od punktu startowego;
  • ograniczona i możliwa do ścisłego kontrolowania złożoność;
  • stosunkowo łatwa kontrola nad algorytmem przez dobór temperatury i kryteriów stopu;

Jednak, dla efektywnego stosowania SA musimy umieć:

  • zakodować nasz problem optymalizacyjny;
  • kontrolować parametry procesu, w tym temperaturę;
  • wybrać punkt startowy tak, aby szansa sukcesu była duża;

Symulowane wyżarzanie może rozwiązywać silnie nieliniowo zależne, nieuporządkowane modele z dużym poziomem szumów i z wieloma zależnościami. W związku z stosunkowo dobrym rozwiązywaniem problemów nieuporządkowanych chaotycznych w przypadku modeli finansowych tj. modelowanie rynku czy prognozowanie popytu.

 

Uważasz, że artykuł był ciekawy i chcesz otrzymywać powiadomienia o moich kolejnych wpisach lub projektach?
Wpisz swoje imię oraz adres e-mail a następnie kliknij "ZAPISZ MNIE"

Twoje imię:


Adres email:



Polecam w HELIONIE:

Świat przyrody i algorytmy genetyczne
Metody uczenia liniowych sieci neuronowych

Podobne wpisy

 

Komentarze

Umieść swój komentarz jako pierwszy!
Gość
niedziela, 17 listopad 2019

Zdjęcie captcha

Najnowsze komentarze

Gość - Studio Jak wybrać hosting dla Joomla!?
13 wrzesień 2019
Warto jeszcze dopisać punkt, żeby przy wyborze wybrać panel między DirectAdmin/cPanel. Niektóre hostingi mają swoje własne rozwiązania - czasami bardzo specyficzne, co niekoniecznie jest dobrą rzeczą
Gość - Marek Szyfrowanie symetryczne a niesymetryczne
09 czerwiec 2019
"Klucz przekazany do publicznej wiadomości, nazywany jest kluczem publicznym lub jawnym. Może on być stosowany do szyfrowania lub deszyfrowania informacji otrzymanych od osoby, która go wygenerowała. ...
Gość - Marek Tworzenie szablonów dla Joomla! Helix Ultimate
10 maj 2019
Witam, napotkałem problem pojawiający się przy zmianie kolorów tła czy czcionek oraz importowaniem ustawień. W pierwszym przypadku, po zmianie kolorów i ich zapisaniem, panel podglądu strony przeładow...
Gość - Andy SSL i Joomla! w Smarthost
03 styczeń 2019
Dzięki, jak zwykle dobra robota! Warto dodać, że instalacja certyfikatu SSL nie zapewnia bezpieczeństwa transmisji danych. To jest możliwe po wdrożeniu polityki bezpieczeństwa w firmie. Co do SSL - to...
Gość - Henryk Jak utworzyć menu poziome w szablonie protostar?
02 styczeń 2019
Robię punkt po punkcie i nie wyświetla się poziome menu Nie wiem gdzie tkwi błąd i co robię źle?Jeśli to możliwe to proszę o pomocps. posiadam książkę "Joomla! 3x" i tu również niema pomocy Pozdrawiam...