Algorytmy ewolucyjne

103000 - Wydział Elektroniki i Technik Informacyjnych
114000 - Wydział Mechatroniki

AE

2

W ramach wykładu zawarty jest przegląd metod rozwiązywania zadań inżynierskich dla osób nieobeznanych z metodami optymalizacji numerycznej. Główny nacisk położony jest na rozwinięcie umiejętności kreatywnego myślenia, a w szczególności umiejętności określenia ram zagadnienia, wydzielenie celów oraz dobranie najbardziej dogodnej reprezentacji problemu. Na początku rozważane są zagadnienia podstawowe: model, i jego znaczenie, reprezentacja, cel i funkcja celu. Następnie przedstawiany jest przegląd klasycznych metod optymalizacji. Na zakończenie prezentowane są metody heurystyczne, takie jak metoda symulowanego wyżarzania, poszukiwań z tabu, kontrolowane przeszukiwanie przypadkowe i algorytmy ewolucyjne. Rozważane algorytmy są łatwe do zrozumienia i implementacji dla każdego inżyniera ze znajomością podstaw programowania.

W ramach wykładu zawarty jest przegląd metod rozwiązywania zadań inżynierskich dla osób nieobeznanych z metodami optymalizacji numerycznej. Główny nacisk położony jest na rozwinięcie umiejętności kreatywnego myślenia, a w szczególności umiejętności określenia ram zagadnienia, wydzielenie celów oraz dobranie najbardziej dogodnej reprezentacji problemu. Na początku rozważane są zagadnienia podstawowe: model, i jego znaczenie, reprezentacja, cel i funkcja celu. Następnie przedstawiany jest przegląd klasycznych metod optymalizacji. Na zakończenie prezentowane są metody heurystyczne, takie jak metoda symulowanego wyżarzania, poszukiwań z tabu, kontrolowane przeszukiwanie przypadkowe i algorytmy ewolucyjne. Rozważane algorytmy są łatwe do zrozumienia i implementacji dla każdego inżyniera ze znajomością podstaw programowania.

Treść wykładu

• Wstęp do metod optymalizacji numerycznej: modelowanie
  zagadnienia, parametryzacja, wymiarowość zadania, kryteria
  optymalizacji i funkcja celu, zagadnienie poszukiwania optimum,
  problemy wielokryterialne, otoczenie i optima lokalne, optymalizacja
  globalna, przekraczanie punktu siodłowego, dynamicznie zmieniające się
  otoczenie. (2h)


• Klasyczne metody optymalizacji: przeszukiwanie lokalne, metody
  najszybszego spadku, programowanie nieliniowe, stochastyczne metody
  optymalizacji, (4h)


• Meta-heurystyczne metody optymalizacji: poszukiwanie optimum
  globalnego, symulowane wyżarzanie, tabu search, metody subgradientowe,
  controlled random search. (2h)


• Algorytmy genetyczne: generatory liczb losowych, kodowanie
  binarne, prosty algorytm genetyczny, (2)


• Zagadnienie podróżującego handlowca: kodowanie całkowitoliczbowe,
  algorytmy naprawy chromosomu (traveling salesman problem TSP). (1h)


• Kryteria oceny algorytmu optymalizacyjnego: koszt funkcji celu,
  ocena zbieżności. (1h)


• Strategie ewolucyjne i programowanie ewolucyjne: kodowanie
  rzeczywisto-liczbowe, strategia (1+1), strategia (?+?) i (?,?),
  programowanie ewolucyjne, ewolujace programy. (2h)


• Kodowanie i operatory genetyczne: reprezentacja genotypowa i
  fenotypowa, wektory symboli/liczb, permutacje, wrażenia
  symboliczne, mutacja i perturbacja (krzyżowanie). (2h)


• Kotrola Populacji: inicjacja, reprodukcja, sukcesja,
  eksploracja i eksploatacja. Wykorzystanie właściwości problemu.
  (2h)


• Optymalizacja z ograniczeniami: znajdowanie rozwiązania
  dopuszczalnego, algorytmy naprawy, karanie niedopuszczalnych osobników,
  specjalne operatory wariacyjne do kontroli populacji, dekodery, (2h)


• Algorytmy Hybrydowe: Algorytmy wielostartowe, operator
  poszukiwania lokalnego. (1h)


• Przetwarzanie równoległe: zrównoleglanie algorytmu ewolucyjnego,
  algorytm wyspowy, zagadnienie migracji, modele dyfuzyjne. (1h)


• Dostrajanie algorytmu ewolucyjnego: przedwczesna zbieżność, efekt
  Baldwin, podejście Lamarkistowskie, techniki kontroli algorytmu,
  parametry kontrolne, algorytmy samoadapcyjne(2h)


• Systemy samouczące: ewoluujące systemy nadzoru i kontroli
  produkcji. (2h)


• Ewolucja Molekularna: wstęp. (2h)

• David E. Goldberg, "Algorytmy genetyczne i ich zastosowanie",WNT. 1995


• Zbigniew Michalewicz, "Algorytmy genetyczne + struktury danych =
  programy ewolucyjne", WNT 1996


• Andrzej Stachurski, "Wprowadzenie do optymalizacji", WPW. 2009


• Andrzej Karbowski, Ewa Niewiadomska, "Programowanie równoległe i
  rozproszone", WPW. 2009


• Zbigniew Michalewicz, David B. Fogel,"Jak rozwiązać, czyli
  nowoczesna heurystyka", WNT 2006

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych

103400 - Instytut Radioelektroniki i Technik Multimedialnych