Algoritmi genetici
FISA DISCIPLINEI

Anul universitar 2011- 2012


   Departament Home

Cod: I3507
Titular curs: Prof. univ. dr. I. Iancu
Forma de invatamant: Cursuri de zi
Ciclul: 1
Anul III,Semestrul 1, Curs: 28h, Laborator: 28h/ AA: 28h
Nr. credite: 5
Profil: informatica
Specializare: informatica
Tip disciplina: optionala
Categoria formativa: de specialitate
Obiective:
  • Cunoasterea principiilor de functionare a algoritmilor genetici si a principalelor aplicatii ale lor
Continutul cursului:

  1. Introducere in calculul evolutiv
    1. Specificul calculului evolutiv
    2. Notiuni de baza
    3. Domenii de aplicabilitate
  2. Spatiul de cautare si functia de adecvare
    1. Codificarea spatiului de cautare
      1. Structuri de date
      2. Reguli de codificare: binara, intreaga, reala, specifica
    2. Construirea functiei de adecvare
  3. Metode de selectie
    1. Selectia dupa rang
    2. Metoda ruletei
    3. Metoda fitness-ului proportionat
    4. Selectia stochastica universala
    5. Selectia trunchiata
    6. Selectia locala
    7. Selectia de tip turneu
    8. Compararea metodelor de selectie
  4. Operatori genetici
    1. Incrucisarea
      1. Incrucisarea binara
      2. Incrucisarea reala
      3. Incrucisarea adiacenta
      4. Incrucisarea prin drumuri
      5. Incrucisarea ordinala
      6. Incrucisarea matriceala
    2. Mutatia
      1. Mutatia binara
      2. Mutatia reala
      3. Mutatia intreaga
      4. Mutatia specifica
    3. Reinsertia
      1. Reinsertia locala
      2. Reinsertia globala
  5. Functionarea algoritmilor genetici
    1. Rezolvarea problemelor de optimizare
    2. Rezolvarea problemelor NP-complete
    3. Aplicatii in algebra
  6. Scheme si blocuri
    1. Scheme: definitie, caracteristici
    2. Teorema schemei
    3. Blocuri
  7. Tipuri de algoritmi genetici
    1. Probleme de convergenta
    2. Algoritmul genetic modificat
    3. Algoritmul hillclimber
    4. Algoritmul de tip calire simulata
    5. Algoritmi cu dimensiunea variabila a populatiei
    6. Algoritmul cu constrangeri
    7. Studiul calitativ

    8. Discipline anterioare cerute:
    • Programare orientata obiect; Cod: I1203
    • Tehnici avansate de programare; Cod: I2402
    Discipline anterioare recomandate:
    • Probabilitati si statistica; Cod: I2304
    Forma de evaluare: colocviu
    1. Examenul consta in proba scrisa (si proba orala pentru cei care care doresc sa-si mareasca nota de la scris)
    2. Nota finala este media ponderata a notei de la examen si a celei de la laborator, cu ponderile 60% si respectiv 40%
    Cerinte minime pentru promovare:
    1. Cunoasterea urmatoarelor notiuni
      1. structura unui algoritm genetic
      2. codificarea reala
      3. construirea functiei de adecvare
      4. selectia prin metoda ruletei
      5. incrucisarea binara multipla
      6. incrucisarea reala intermediara
      7. mutatia binara tare si mutatia reala neuniforma
      8. un tip special de algoritm genetic
    2. Activitate la laborator
      1. prezenta la cel putin 50% din laboratoare
      2. nota de promovare la temele de laborator
      Continutul laboratorului:
      1. Tehnici de codificare a spatiului de cautare, construirea functiei de adecvare
      2. Implementarea unor metode de selectie
      3. Implementarea unor operatori de evolutie: încrucisare, mutatie
      4. Rezolvarea unei probleme de optimizare folosind algoritmi genetici
      5. Simularea reprezentarii prin scheme
      6. Utilizarea algoritmilor genetici neclasici; comparatie cu cei clasici
      7. Implementarea unui algoritm cu dimensiunea variabila a populatiei
      8. Rezolvarea unei probleme cu restrictii
      9. Compararea calitativa a doi algoritmi
      Bibliografie:
      1. I. Iancu: Algoritmi genetici, Editura SITECH, 2008
      2. Z. Michalewicz: Genetic algorithms+Data structures=Evolution programs, Springer, New York, 1996
      3. D. Dumitrescu: Algoritmi genetici si strategii evolutive. Aplicatii in inteligenta artificiala si domenii conexe. Editura Albastra, Cluj-Napoca, 2000
      4. D. Dumitrescu, B. Lazzerini, L. C. Jain, A. Dumitrescu: Evolutionary computation, CRC Press, New York, 2000
      5. H. Luchian, S. Luchian: Clasificare evolutiva, Editura Integral, Iasi, 1999
      6. F. Herrera, J. L. Verdegay (Eds.): Genetic algorithms and soft computing, Physica Verlang, Heidelberg, 1996
      7. R. Polli: Introduction to evolutionary computation, School of Computer science, Univ. of Birmingham, 1996
      8. M. Lalena: Teamwork in genetic programming, Thesis, School of Computer science and technology, Rochester Institute of Technology, 1997
      9. 5. T. Jones: Evolutionary algorithms, fitness, landscape and search, Thesis, Univ. of New Mexico, Albuquerque, 1995
      10. H. Horner: A C++ class library for genetic programming, The Vienna Univ. of Economics, 1996
      Sinteza cursului
Ultima actualizare: octombrie 2011