A A A

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ść
czwartek, 25 kwiecień 2019

Zdjęcie captcha

Najnowsze komentarze

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...
Gość - Joanna Jak utworzyć własny szablon dla Joomla! nie dotykając kodu? EF4 cz.2
09 grudzień 2018
Czy jest jakaś możliwość, żeby zmienić układ top-bar i tej linii, w której jest logo? Tam niby są flexibloki ale nie można zmienić ich szerokości, a tego potrzebuję bardzo. Jak tego dokonać???
Gość - Informatyk Tworzenie bazy danych w CPanelu na Smarthost - instalacja Joomla!
19 listopad 2018
Dziękuje za ten wpis joomla zawsze była dla mnie problematyczna
Gość - Sławomir DJ Image Slider
04 listopad 2018
co robić? Zdjęcia wyświetlają się pionowo, jedno pod drugim. Żadna zmiana w opcjach, nic nie daje??? Pomożecie?