Název:
Paralelní genetický algoritmus pro vícejádrové systémy
Překlad názvu:
The Parallel Genetic Algorithm for Multicore Systems
Autoři:
Vrábel, Lukáš ; Šimek, Václav (oponent) ; Jaroš, Jiří (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2010
Jazyk:
eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng][cze]
Genetický algoritmus je optimalizačná metóda zameraná na efektívne hľadanie riešení rozličných problémov. Je založená na princípe evolúcie a prirodzeného výberu najschopnejších jedincov v prírode. Keďže je táto metóda výpočtovo náročná, bolo vymyslených veľa spôsobov na jej paralelizáciu. Avšak väčšina týchto metód je z historických dôvodov založená na superpočítačoch alebo rozsiahlych počítačových systémoch. Moderný vývoj v oblasti informačných technológií prináša na trh osobných počítačov stále lacnejšie a výkonnejšie viacjadrové systémy. Táto práca sa zaoberá návrhom nových metód paralelizácie genetického algoritmu, ktoré sa snažia naplno využiť možnosti práve týchto počítačových systémov. Tieto metódy sú následne naimplementované v programovacom jazyku C za využitia knižnice OpenMP určenej na paralelizáciu. Implementácia je následne použitá na experimentálne ohodnotenie rozličných charakteristík každej z prezentovaných metód (zrýchlenie oproti sekvenčnej verzii, závislosť konvergencie výsledných hodnôt od miery paralelizácie alebo od vyťaženia procesoru, ...). V poslednej časti práce sú prezentované porovnania nameraných hodnôt a závery vyplývajúce z týchto meraní. Následne sú prediskutované možné vylepšenia daných metód vyplývajúce z týchto záverov, ako aj možnosti spracovania väčšieho množstva charakteristík na presnejšie ohodnotenie efektivity paralelizácie genetických algoritmov.
Genetic algorithm is a powerful optimization and search method successfully used in practice to solve many different problems. Underlying concept is based on the evolutionary mechanics observed in nature. As the GAs are computationaly intense applications, it is natural that there are many efficient methods for parallelization of these algorithms. However, most of these methods deal with supercomputers or large computer clusters with specialized hardware, as these were the most common parallel architectures in the past. With modern-day computers the trend in personal computer design is also moving towards parallel architectures bringing small and cheap parallel multicore processors. That's why it is imperative to have efficient methods to exploit capabilities of this system. This document presents prototypes of new methods of parallel genetic algorithms designed especially for these multiprocessor computers with shared memory.
Klíčová slova:
genetic algorithm; multicore; multiprocessor system; OpenMP; parallel; genetický algoritmus; OpenMP; paralelní; vícejádrové systémy; víceprocesorové systémy
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/54379