Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Wstęp do algorytmów ewolucyjnych
Koordynator przedmiotu:
Dr hab. inż. Jarosław Arabas
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
2 / rok ak. 2009/2010
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
Podstawowe informacje z zakresu rachunku prawdopodobieństwa i analizy matematycznej 
Limit liczby studentów:
Cel przedmiotu:
do uzupełnienia
Treści kształcenia:
Zakres tematyczny Wykładu 1. Zadanie optymalizacji kombinatorycznej i w Rn .Metoda optymalizacji jako sposób uszeregowania punktów z przestrzeni przeszukiwań. Ograniczenia funkcyjne i zbiór dopuszczalny. 2. Przegląd metod optymalizacji w Rn jako  ilustracja zasady uszeregowania punktów z przestrzeni. Wzmiankowane metody to sympleks Neldera-Meada oraz metody dwufazowe, np. największego spadku i zmiennej metryki. 3. Metoda symulowanego wyżarzania. Zadanie optymalizacji globalnej jako zadanie opuszczania obszaru przyciągania minimum lokalnego (przekraczania siodeł). Sprzeczność między zbieżnością do minimum lokalnego a zdolnością odnajdowania minimum globalego. 4. Algorytm ewolucyjny: metody selekcji, operacje genetyczne dla optymalizacji w Rn  i {0,1}n 5. Techniki uwzględniania ograniczeń – zewnętrzna funkcja kary, specjalizowane kodowanie, naprawa rozwiązań niedopuszczalnych. 6. Technika poprawy zbieżności – hybrydyzacja z metodami optymalizacji lokalnej, darwinowski a lamarkowski schemat ewolucji. 7. Metody analizy algorytmu ewolucyjnego – twierdzenie o schematach, analiza bazująca na dynamice rozkładu próbkowania populacji nieskończonej, analiza wykorzystująca model  Markowa (wg Vose'a), inne podejścia 8. Dostosowywanie algorytmu ewolucyjnego do niestandardowych przestrzeni przeszukiwań – specjalizowane reprezentacje i operacje genetyczne. Jak projektować operacje genetyczne aby algorytm ewolucyjny działał prawidłowo. 9. Optymalizacja metodą immunologiczną – podobieństwa i różnice z algorytmem ewolucyjnym. 10. Optymalizacja metodą trajektorii cząstki. Optymaliazacja rojem cząstek. Podobieństwo z wielostartową metodą największego spadku. 11. Optymalizacja globalna algorytmem bazującym na grupowaniu (wg Toerna) 12. Usprawnianie metod  optymalizacji globalnej poprzez modyfikacje zbioru rozwiązań dopuszczalnych (metoda tabu) lub wprowadzanie funkcji kary skoncentrowanych w minimach lokalnych.   Zakres tematyczny Projektu Testowanie wybranego algorytmu optymalizacji na zadaniach testowych. Algorytm wymaga zakodowania w języku programowania (np. C/C++ i pochodne lub R). W ramach projektu przygotowane jest jedno lub kilka zadań praktycznych, wymagających nietypowego użycia
Metody oceny:
Łączną ocenę punktową przelicza się na stopnie według poniższych zasad: b)  3.5 jeżeli uzyskali od 61 do 70  pkt. c)  4.0 jeżeli uzyskali od 71 do 80  pkt. d)  4.5 jeżeli uzyskali  od 81 do 90  pkt. e)  5.0 jeżeli uzyskali powyżej 90  pkt.
Egzamin:
Literatura:
J. Arabas: Wykłady z algorytmów ewolucyjnych, WNT, 2001 Z. Michalewicz, D. Fogel: Jak to rozwiązać czyli nowoczesna heurystyka, WNT, 2005 A.Stachurski, A. Wierzbicki: Podstawy optymalizacji, PW, 2001 
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się