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

 

    By accepting you will be accessing a service provided by a third-party external to https://www.slawop.net/