Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Contemporary Heuristic Techniques

Informacje ogólne

Kod przedmiotu: 103A-TCTCM-ISA-ECOHT Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Contemporary Heuristic Techniques
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Courses in English )--eng.-EITI
( Przedmioty techniczne )---EITI
( Technical Courses )--eng.-EITI
Punkty ECTS i inne: 6.00
Język prowadzenia: angielski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

ECOHT

Numer wersji:

1

Skrócony opis: (tylko po angielsku)

Due to high computational complexity of many practical problems, there is a need to use approximate algorithms to obtain good results in resonable time. Heuristic is a technique which seeks good ( i.e. near-optimal) solutions in acceptable time. The lecture presents modern inteligent heuristics. The students learn about specific techniques that are available, thought the application of computer algorithms. Second they understand when each of these methods should and should not be used. Applications contain: Travelling Salesman Problem, Boolean Satisfiability Problem, The 0-1 Knapsack Problem, The Vehicle Routing Problem, Graph coloring.

Pełny opis: (tylko po angielsku)

Due to high computational complexity of many practical problems, there is a need to use approximate algorithms to obtain good results in resonable time. Heuristic is a technique which seeks good ( i.e. near-optimal) solutions in acceptable time. The lecture presents modern inteligent heuristics. The students learn about specific techniques that are available, thought the application of computer algorithms. Second they understand when
each of these methods should and should not be used. Applications contain: Travelling Salesman Problem, Boolean Satisfiability Problem, The 0-1 Knapsack Problem, The Vehicle Routing Problem, Graph coloring.



Lecture contents

  1. Introduction. Why some problems are difficult to solve?

  2. Computational complexity.

    • NP-complete, NP-hard problems.

  3. Local and global search

    • Approximate solutions

  4. Quality of heuristics solutions.

    • Worst case, average case

  5. Exhaustive search

    • backtracking methods

    • dynamic programming

    • branch and bound method

  6. Heuristics for some combinatorial problems (greedy, heuristics dedicated to the specific problems).

    • Travelling Salesman Problem (algorithms and bounds), applications

    • Boolean Satisfiability Problem (SAT)

    • Graph Coloring Problem,

    • String Alignment Problem

  7. Local search methods,

    • k-opt methods

    • applications TSP, SAT

  8. Simulating annealing,

    • applications.

    • Examples

    • Tuning

  9. Tabu Search.

    • Comparison with Simulating Annealing

  10. Evolutionary computation.

    • Coding

    • Genetic operators,

    • selection methods

    • Applications: TSP, SAT, design of telecommunication networks.

  11. Swarm Intelligence. Routing in Telecommunication Networks.

  12. Parastic Computing

  13. Fuzzy sets.



  14. Projects contents
    During the project students implement one the techniques described during the lecture. The obtained results are compared with simple greedy technique. Students are encouraged to propose their own problems which are suitable to the topic of the lecture.

Literatura: (tylko po angielsku)

  • Z. Michalewicz, David B. Fogel, "How To Solve It: Modern Heuristics" Springer 2000

  • Colin R. Reeves, "Modern Heuristics Techniques for Combinatorial Problems ", McGraw-Hill 1995

  • Andries P. Engelbrecht, "Computational Intelligence. An Introduction." Wiley 2002

  • J. Arabas, "Wykłady z algorytmów ewolucyjnych" WNT 2000


Zajęcia w cyklu "rok akademicki 2014/2015 - sem. letni" (zakończony)

Okres: 2015-02-23 - 2015-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2013/2014 - sem. letni" (zakończony)

Okres: 2014-02-24 - 2014-09-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. letni" (zakończony)

Okres: 2013-02-20 - 2013-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Zajęcia w cyklu "rok akademicki 2012/2013 - sem. zimowy" (zakończony)

Okres: 2012-10-01 - 2013-02-19
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 1 miejsc więcej informacji
Wykład, 30 godzin, 1 miejsc więcej informacji
Koordynatorzy: Piotr Bilski
Prowadzący grup: Piotr Bilski
Lista studentów: (nie masz dostępu)
Zaliczenie: Ocena łączna
Jednostka realizująca:

103400 - Instytut Radioelektroniki i Technik Multimedialnych

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.