Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy genetyczne
Tok studiów:
2018/2019
Kod:
JIS-2-028-GK-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Grafika komputerowa i przetwarzanie obrazów
Kierunek:
Informatyka Stosowana
Semestr:
0
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
dr hab. inż. Haberko Jakub (haberko@fis.agh.edu.pl)
Osoby prowadzące:
dr hab. inż. Haberko Jakub (haberko@fis.agh.edu.pl)
Krótka charakterystyka modułu

Algorytmy Genetyczne są nowoczesną techniką optymalizacji często wykorzystywaną w zagadnieniach sztucznej inteligencji. W ramach modułu student będzie się mógł zapoznać z teorią i zastosowaniami AG.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W008 Student wie czym są algorytmy genetyczne. Zna ich obszary zastosowań i ograniczenia. IS2A_W01, IS2A_W04, IS2A_W02 Kolokwium,
Projekt
Umiejętności
M_U007 Potrafi rozwiązać problem optymalizacyjny z wykorzystaniem metody algorytmów genetycznych. IS2A_U05, IS2A_U06, IS2A_U04, IS2A_U02, IS2A_U03 Sprawozdanie,
Wykonanie ćwiczeń laboratoryjnych
M_U008 Potrafi przeprowadzić krytyczną analizę różnych metod stosowanych w algorytmach genetycznych oraz określić ich przydatność w konkretnym zadaniu inżynierskim. IS2A_U05, IS2A_U10, IS2A_U06, IS2A_U04, IS2A_U07, IS2A_U02 Aktywność na zajęciach,
Sprawozdanie,
Wykonanie ćwiczeń laboratoryjnych
M_U009 Potrafi przygotować kompletną dokumentację wykonanego zadania optymalizacyjnego. IS2A_U10, IS2A_U09, IS2A_U04, IS2A_U02, IS2A_U03 Aktywność na zajęciach,
Wykonanie ćwiczeń laboratoryjnych
Kompetencje społeczne
M_K002 Potrafi kumikatywnie przedsatwić na forum grupy swoje rozwiązanie oraz aktywnie uczesniczyć w dyskusji na nim. IS2A_K03, IS2A_K01, IS2A_K02 Aktywność na zajęciach,
Wykonanie ćwiczeń laboratoryjnych
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W008 Student wie czym są algorytmy genetyczne. Zna ich obszary zastosowań i ograniczenia. + - + - - - - - - - -
Umiejętności
M_U007 Potrafi rozwiązać problem optymalizacyjny z wykorzystaniem metody algorytmów genetycznych. - - + + - - - - - - -
M_U008 Potrafi przeprowadzić krytyczną analizę różnych metod stosowanych w algorytmach genetycznych oraz określić ich przydatność w konkretnym zadaniu inżynierskim. - - + + - - - - - - -
M_U009 Potrafi przygotować kompletną dokumentację wykonanego zadania optymalizacyjnego. - - + + - - - - - - -
Kompetencje społeczne
M_K002 Potrafi kumikatywnie przedsatwić na forum grupy swoje rozwiązanie oraz aktywnie uczesniczyć w dyskusji na nim. - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Biologiczne podstawy AG

    Życie. Ewolucja. Pojemność środowiska. Mutacje. Rekombinacja genów. Dostosowanie do środowiska. Presja środowiskowa. Krótka historia ewolucji.

  2. AG jako metoda optymalizacji

    Metody optymalizacyjne: analityczne, przeglądowe, losowe. Podobieństwa i różnice z AG. Elementarny algorytm genetyczny (“ręczna symulacja”). Schematy. Terminologia.

  3. Podstawy teoretyczne AG. Podstawowa implementacja AG (SGA)

    Rząd, rozpiętość i rozmiar schematu. Twierdzenie o schematach. Geometryczna interpretacja schematów. Hipoteza cegiełek. Podstawowa implementacja algorytmów genetycznych SGA (Simple Genetic Algorithm).

  4. MDP i zasady kodowania

    Minimalny problem zwodniczy (MDP – minimal deceptive problem). Ogólne zasady kodowania. Metryka w przestrzeni genotypu i fenotypu. Kodowanie Graya. Zasada znaczących cegiełek. Zasada minimalnego alfabetu. Kodowanie wieloparametryczne.

  5. Efektywność. Funkcja przystosowania. Populacja bazowa.

    Efektywność on-line. Efektywność off-line. Zbieżność fbest. Zbieżność faverage. Koszt wywołań funkcji celu. Badanie zdolności algorytmu do opuszczania minimum lokalnego. Funkcja kosztu, zysku i przystosowania. Skalowanie funkcji przystosowania. Problem więzów. Metoda kar. Inicjalizacja populacji bazowej: równomierna, losowa, dopełniająca, na podstawie przeszukiwania lokalnego. Dyskrepancja.

  6. Metody selekcji

    Reprodukcja i sukcesja. Reprodukcja: ruletkowa, zmodyfikowana ruletkowa, deterministyczna, losowa według reszt z powtórzeniami, losowa według reszt bez powtórzeń, rangowa (rankingowa), turniejowa, pojedynkowa, progowa. Sukcesja: z całkowitym zastępowaniem, z częściowym zastępowaniem, elitarna.

  7. Podstawowe operatory genetyczne

    Spójność przestrzeni chromosomów. Operatory obciążone i nieobciążone. Krzyżowanie: wymieniające, równomierne, uśredniające. Mutacja: bitowa, rzeczywistoliczbowa. Strojenie krzyżowania. Strojenie mutacji. Badania de Jonga.

  8. Biblioteka GALib

    Opis biblioteki. Przykłady użycia.

  9. Techniki zabezpieczające

    Metoda losowych emigrantów. Metoda podziału przystosowania (algorytm niszowy). Zapobieganie przedwczesnej zbieżności. Limitowanie czasu życia. Selekcja sterowana czasem życia.

  10. Techniki specjalne 1

    Optymalizacja wielokryterialna. Diploidalny aparat genetyczny. Operatory permutacyjne: inwersja, PMX, OX, CX. Duplikacja, delecja i genotypy wielochromosomalne.

  11. Techniki specjalne 2

    Specjacja. Zróżnicowanie płciowe. Kodowanie macierzowe. Kodowanie kaskadowe. Kodowanie drzewiaste. Algorytmy genetyczne w zmiennym środowisku.

  12. Niestandardowe AG i strategie ewolucyjne.

    Algorytmy koewolucyjne: wyspowy, komórkowy. Strategie ewolucyjne.

  13. Typowe zastosowania AG

    Krótkie reduktory bazy wiedzy. Logika rozmyta. Problem magazynowy. Problem harmonogramowania. Genetyczne systemy uczące się.

  14. AG – przykłady i zastosowania
Ćwiczenia laboratoryjne:
  1. Powtórka ze statystyki

    Efekty kształcenia:

    • student potrafi zastosować twierdzenie o prawdopodobieństwie całkowitym
    • student zna i potrafi wykorzystać rozkład normalny i rozkład Bernoulliego
    • student potrafi dokonać zamiany zmiennych losowych

  2. Osobnik vs. schemat

    Efekty kształcenia:

    • student potrafi wyjaśnić czym różni się schemat od osobnika
    • student potrafi sprawdzić jakie schematy odpowiadają jakim osobnikom i vice versa
    • student potrafi oszacować jaką liczbę schematów statystycznie reprezentuje populacja złożona z n osobników będących ciągami k-elementowymi

  3. Podstawowy algorytm genetyczny

    Efekty kształcenia:

    • student potrafi rozwiązać prosty problem przy pomocy klasycznego algorytmu genetycznego (Simple Genetic Algorithm)

  4. Metoda kar

    Efekty kształcenia:

    • student wie czym jest metoda kar i potrafi ją zastosować
    • student potrafi porównać, korzystając z różnych miar efektywności algorytmu, skuteczność zastosowania maetody kar

  5. Populacja bazowa. Metody selekcji.

    Efekty kształcenia:

    • student potrafi wybrać i zastosować właściwą metodę inicjalizacji populacji bazowej
    • student zna różne metody selekcji
    • student potrafi ocenić, która metoda selekcji będzie najlepsza w zastosowaniu do konkretnego problemu

  6. Testowanie metod selekcji i krzyżowania

    Efekty kształcenia:

    • student zna różne metody selekcji
    • student zna różne metody krzyżowania
    • student potrafi zastosować różne kombinacje selekcji i krzyżowania oraz ocenić ich użyteczność w rozwiązywaniu konkretnego problemu

  7. Wykorzystanie biblioteki AGLib

    Efekty kształcenia:

    • student potrafi napisać aplikację korzystającą z biblioteki AGLib
    • student potrafi rozwiązać prosty problem z wykorzystaniem biblioteki AGLib

  8. Badanie zmienności funkcji wielowymiarowej

    Efekty kształcenia:

    • student potrafi napisać aplikację poszukującą minimum funkcji wielu zmiennych bazującą na algorytmie genetycznym
    • student potrafi przeprowadzić szczegółową analizę pracy algorytmu genetycznego, dopierając właściwe metody kodowania, selekcji, zapobiegania przedwczesnej zbieżności oraz wykorzystać optymalne operatory genetyczne
    • student potrafi przeanalizować otrzymane wyniki i udzielić wiarygodnej odpowiedzi na temat minimum funkcji

  9. Rozwiązywanie zagadnień nienumerycznych

    Efekty kształcenia:

    • student potrafi stworzyć algorytm genetyczny rozwiązujący problem nienumeryczny

  10. Mini-projekt

    Efekty kształcenia:

    • student potrafi dokonać analizy problemu wymagającego optymalizacji
    • student potrafi zaproponować rozwiązanie oparte na algorytmie genetycznym
    • student potrafi stworzyć alpikację rozwiązującą problem
    • student potrafi przeanalizować otrzymane wyniki
    • student umie napisać kompetentny raport z wykonanej pracy

Ćwiczenia projektowe:
Projekt

Efekty kształcenia:

  • student potrafi dokonać analizy problemu wymagającego optymalizacji
  • student potrafi zaproponować rozwiązanie oparte na algorytmie genetycznym
  • student potrafi stworzyć alpikację rozwiązującą problem
  • student potrafi przeanalizować otrzymane wyniki
  • student umie napisać kompetentny raport z wykonanej pracy

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 108 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 30 godz
Samodzielne studiowanie tematyki zajęć 28 godz
Udział w ćwiczeniach laboratoryjnych 15 godz
Udział w ćwiczeniach projektowych 7 godz
Wykonanie projektu 28 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Na zakończenie wykładu odbędzie się kolokwium zaliczeniowe, za które będzie można uzyskać 30 punktów. W trakcie laboratorium komputerowego będzie można zdobyć 70 punktów (w tym 30 punktów za mini-projekt).

Ocena z wykładu będzie wystawiana zgodnie ze skalą ocen podaną w Regulaminie studiów AGH na podstawie procentu punktów zdobytych na kolokwium.

Ocena z laboratorium będzie wystawiana zgodnie ze skalą ocen podaną podaną w Regulaminie studiów AGH na podstawie procentu punktów zdobytych w trakcie laboratorium.

Ocena końcowa z przedmiotu uzależniona będzie od tego jaki procent całości (100pkt.) stanowi suma zdobytych punktów na kolokwium i w trakcie laboratorium.

Wymagania wstępne i dodatkowe:

Elementarna umiejętność programowania w C++.
Podstawowa znajomość statystyki.

Zalecana literatura i pomoce naukowe:

1) Wykłady z algorytmów ewolucyjnych , Jarosław Arabas , WNT , Warszawa 2001 (wyd.I) , 2004 (wyd.II)
2) Algorytmy genetyczne i ich zastosowania , David E. Goldberg , WNT , Warszawa 1995
3) Algorytmy genetyczne. Podstawy i zastosowania , Jerzy Cytowski , Akademicka Oficyna Wydawnicza PLJ , Warszawa 1996
4) An Introduction to Genetic Algorithms , Mitchell Melanie , MIT Press , Cambridge, Massachusetts 1998
5) Trzy ewolucje , Bernard Korzeniewski , Małopolska Oficyna Wydawnicza Korona

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. K.Janc, J.Tarasiuk, A.S.Bonnet, P.Lipinski, Genetic algorithms as a useful tool for trabecular and cortical bone segmentation, Computer Methods and Programs in Biomedicine, III, 72-83 (2013)

2. Janc K., Tarasiuk J., Bonnet A.S., Lipinski P., Semi-automated algorithm for cortical and trabecular bone separation from CT scans, 36th Congress of the Société de Biomécanique, Computer Methods in Biomechanics and Biomedical Engineering, 14, 1, pp. 217-218, Besançon, 2011

3. Janc K., Tarasiuk J., Bonnet A.S., Lipinski P, Bone segmentation from CT scans based on genetic algorithms method, ECCOMAS International Conference IPM 2011 on “Inverse Problems in Mechanics of Structure and Materials”, Rzeszów–Sieniawa, Poland, 2011

4. K. Wierzbanowski, J. Tarasiuk, A. Lodini, Optimization of material properties using genetic alorithms, Materials Science Forum, 652, 1–6 (2010)

5. J. Tarasiuk, Genetic algorithms in texture analysis, European Materials Research Society Fall Meeting, Warszawa, Poland (2007)

6. J. Tarasiuk and K. Wierzbanowski, B. Bacroix, Texture decomposition into gauss-shaped functions. Classical and genetic algorithm methods, Computational Materials Science, 29, 179-186 (2004)

7. P. Salek, J. Tarasiuk, K. Wierzbanowski, Application of Genetic Algorithms to Texture Analysis, Crystal Research and Technology, 34, 1073- 1079 (1999)

Informacje dodatkowe:

Nieobecność na jednych zajęciach obowiązkowych wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału. Nieobecność na więcej niż jednych zajęciach wymaga od studenta
samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie i terminie wyznaczonym przez prowadzącego, lecz nie później niż w ostatnim tygodniu trwania zajęć. Student, który
bez usprawiedliwienia opuścił więcej niż dwa obowiązkowe zajęcia i jego cząstkowe wyniki w nauce były negatywne może nie zaliczyć zajęć obowiązkowych. Należy pamiętać, że warunkiem przystąpienie do egzaminu jest wcześniejsze uzyskanie zaliczenia z zajęć obowiązkowych.