Piotr Lipinski

Computational Intelligence Research Group, Institute of Computer Science, University of Wroclaw

Institute of Computer Science, University of Wroclaw, ul. Joliot-Curie 15, 50-383 Wrocław, Poland, Room 203, Email: lipinski@ii.uni.wroc.pl

Wykład z algorytmów ewolucyjnych

Aktualności:

NEW Zaliczenie i egzamin:

Oceny z zaliczenia i egzaminu są tutaj. W przypadku jakichkolwiek wątpliwości proszę o kontakt emailem. Indeksy można zostawiać na mojej półce.

Zaliczenie:

Absolutnie ostateczny termin oddawania projektów, zaległych zadań i jakichkolwiek innych rzeczy związanych z zaliczeniem to 7 lipca 2017. Zainteresowane osoby proszę o kontakt emailem (co najmniej 24h przed planowanym spotkaniem).

Egzamin:

Egzamin z algorytmów ewolucyjnych odbędzie się w dwóch terminach (każdy student może wybrać jeden z tych terminów, nie ma potrzeby wcześniejszego powiadamiania prowadzącego o wyborze terminu): 19 czerwca 2017 o 13.00 w sali 141 i 28 czerwca 2017 o 11.00 w sali 141. Zapraszam!

Informacje organizacyjne:

Przypominam, że zgodnie z zapowiedzią, w piątek 16 czerwca o 12.30 w sali 119 odbędzie się dodatkowy wykład z algorytmów ewolucyjnych. Wykład jest nieobowiązkowy i jego materiał nie będzie wymagany na egzaminie. Niemniej zapraszam!

Informacje organizacyjne:

Proponuje dodatkowe terminy, w których można oddawać zaległe zadania i projekty: piątek 16 czerwca, godzina 15.00, pokój 203; poniedziałek 19 czerwca, godzina 14.00, pokój 203; wtorek 27 czerwca, godzina 11.00, pokój 203. Proszę o przesłanie swoich projektów co najmniej 24h przed przyjściem i pokazaniem go. Będę też wdzięczny za informacje emailem o chęci przyjścia (pozwoli to uniknąć kolejek). Można też umawiać się emailem na inne terminy.

Zasady zaliczenia:

Ze względu na kalendarz tegorocznych zajęć opublikowałem tylko 5 list zadań i do zdobycia było łącznie tylko 60 zamiast zakładanych wstępnie 80 punktów. Proponuję więc, żeby punkty za zadania z list pomnożyć przez 4/3.

Projekt:

Informacje o projektach PDF

Informacja:

Punktacja jest dostępna tutaj

Listy zadań:

Lista zadań nr 1 PDF (termin 21 i 23 marca 2017)

Lista zadań nr 1 - dane ZIP (hasło do pliku to tytuł naszego wykładu pisany małymi literami bez spacji z literami l zamienionymi na wykrzykniki)

Lista zadań nr 2 PDF (termin 4 kwietnia 2017)

Lista zadań nr 2 - parę słów o QAP i Q3AP PDF

Lista zadań nr 3 PDF (termin 25 i 27 kwietnia 2017)

Lista zadań nr 4 PDF (termin 4 i 9 maja 2017)

Skrypt IPythona do listy zadań nr 4 HTML IPYNB

Lista zadań nr 5 PDF (termin 30 maja i 1 czerwca 2017)

Skrypt IPythona do listy zadań nr 5 HTML IPYNB

Prezentacje z wykładów:

Wprowadzenie do algorytmów ewolucyjnych PDF

Algorytm CGA PDF

Algorytm PBIL PDF

Zarys algorytmu ewolucyjnego PDF

Algorytmy genetyczne PDF

Podział obiektów na grupy PDF

Strategie ewolucyjne PDF

Strategie ewolucyjne - ES(m, l, r, k) PDF

Estimation of Distribution Algorithms - część 1 PDF

Estimation of Distribution Algorithms - część 2 PDF

Optymalizacja wielokryterialna PDF

Skrypt IPythona do optymalizacji wielokryterialnej HTML IPYNB

Grammatical Evolution PDF

Ewolucyjna optymalizacja dynamicznych funkcji celu PDF

EA for Dynamic Optimization Problems PDF

Kodowanie i operatory ewolucyjne PDF

Zapobieganie przedwczesnej zbieżności PDF

Genetic Programming PDF

Inne materiały:

Zapis minikursu Matlaba z pracowni 28 lutego 2017 TXT

Zapis minikursu Pythona z NumPy z pracowni 7 marca 2017 TXT

Wskazówki dotyczące korzystania z komputerów w salach 110 i 137 LINK

Platforma Anaconda z Pythonem do obliczeń naukowych i technicznych LINK

Dokumentacja pakietu NumPy do obliczeń macierzowych i wektorowych w Pythonie LINK

Dokumentacja pakietu MatPlotLib do tworzenia wykresów w Pythonie LINK

Propozycje minireferatów:

Za przygotowanie minireferatu (wystąpienie na ok. 15 minut) można dostać od 0 do 5 punktów bonusowych. Minireferat jest wymagany na ocenę 5.0. Zainteresowane osoby proszę o kontakt emailem (decyduje kolejność zgłoszeń). Termin prezentacji ustalimy indywidualnie.

Co to jest natural gradient? Co to jest Natural Evolution Strategies (NES)?

Krótko o CMA-ES (ale dłużej niż na wykładzie).

O operatorach ewolucyjnych dla problemów kombinatorycznych (innychy niż na wykładzie).

Co to jest low-discrepancy sequence? Czym się różni od liczb pseudolosowych?

Krótko o soft-robots (ale dłużej niż na wykładzie).

Krótko o ewolucji dwuwymiarowych pojazdów kołowych (ale dłużej niż na wykładzie).

O Evolutionary Robotics.

O Vehicle Routing Problem (VRP) i algorytmach ewolucyjnych do jego rozwiązywania.

Opis wykładu:

Algorytmy ewolucyjne to część inteligencji obliczeniowej zajmująca się heurystycznym rozwiązywaniem problemów optymalizacji.


Algorytmy ewolucyjne znajdują zastosowanie w rozwiązywaniu problemów optymalizacji, dla których nie można użyć algorytmów tradycyjnych (m.in. kiedy takie algorytmy nie istnieją lub są zbyt kosztowne obliczeniowo, kiedy problem optymalizacji nie może być zdefiniowany matematycznie, kiedy wystarczające są rozwiązania przybliżone lub dostatecznie dobre z praktycznego punktu widzenia).


Przykładami rozważanych problemów optymalizacji są z jednej strony dobrze znane problemy NP-zupełne (dla których algorytmy ewolucyjne starają się dostarczyć rozwiązania dostatecznie dobre z punktu widzenia praktycznych zastosowań), a z drugiej strony rozmaite problemy praktyczne trudne do sprecyzowania w sposób matematyczny (m.in. takie w których nieznany jest analityczny wzór funkcji celu, ale znana jest metoda liczenia jej wartości, na przykład przez wykonanie pewnych symulacji).


Praktyczne problemy optymalizacji rozwiązywane algorytmami ewolucyjnymi dotyczą systemów ekspertowych, systemów klasyfikacji i rozpoznawania obiektów czy systemów wspomagania decyzji. Popularne jest stosowanie algorytmów ewolucyjnych do analizy obrazów, w tym zdjęć satelitarnych i obrazów medycznych, do analizy danych ekonomicznych i finansowych, zwłaszcza danych wysokiej i ultra wysokiej częstotliwości, do konstrukcji systemów kontroli lotów, do konstrukcji sztucznej inteligencji w grach, itp.


Pierwsza część wykładu dotyczyć będzie podstawowych algorytmów ewolucyjnych do rozwiązywania klasycznego problemu optymalizacji, ich konstrukcji i adaptacji do konkretnych problemów praktycznych i teoretycznych oraz implementacji. Druga część wykładu dotyczyć będzie nowoczesnych algorytmów ewolucyjnych przeznaczonych do rozwiązywania trudniejszych problemów, takich jak optymalizacja wielomodalna, optymalizacja wielokryterialna i optymalizacja dynamiczna.


Wykład wymagać będzie podstawowej wiedzy z zakresu rachunku prawdopodobieństwa i statystyki (na przykład zaliczenie wykładu RPiS). Podczas pracowni wymagana będzie umiejętność programowania w klasycznych językach programowania (C/C++, Java, Python), a przydatna może okazać się też umiejętność programowania w popularnych narzędziach używanych do analizy danych, takich jak Matlab czy Octave (narzędzi tych będzie można nauczyć się samemu w pierwszych tygodniach zajęć lub równocześnie uczęszczać na kurs z nowoczesnych języków przetwarzania danych).

Program wykładu:

1. Wprowadzenie do algorytmów ewolucyjnych.

2. Podstawowe algorytmy ewolucyjne: algorytmy genetyczne, strategie ewolucyjne, programowanie genetyczne, programowanie ewolucyjne.

3. Zaawansowane algorytmy ewolucyjne odkrywające wiedzę o problemie optymalizacji.

4. Równoległe i rozproszone algorytmy ewolucyjne.

5. Algorytmy optymalizacji wielomodalnej.

6. Algorytmy optymalizacji wielokryterialnej.

7. Algorytmy optymalizacji dynamicznej.

8. Wybrane zastosowania algorytmów ewolucyjnych.

Literatura:

J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, 2004.

D. Goldberg, Algorytmy genetyczne i ich zastosowania, WNT, 2003.

Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, 2003.

UWAGA: Książki te zawierają jedynie podstawową wiedzę z tematyki wykładu. Informacji o bardziej współczesnych algorytmach ewolucyjnych należy szukać w artykułach naukowych (część z nich będzie cytowana w prezentacjach z wykładów).