Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

Tato práce se zabývá problematikou urychlování genetických algoritmů a hned v úvodu nastiňuje možnosti využití genetických algoritmů v praxi. V první kapitole je detailně rozebrán princip fungování genetického algoritmu. Tato kapitola se dále zabývá možnostmi zákódování problému, který je použit pro běh genetického algoritmu. Konkrétně je vzpomenuto binární zakódování jedince, celočíselné zakódování jedince, neceločíselné zakódování jedince a permutační zakódování jedince. Pro každý typ zakódování jsou dále představeny genetické operátory mutace, křížení a selekce. Důraz je kladen na permutační genetické operátory OX a PMX. Další kapitola se zabývá možnostmi paralelizace genetického algoritmu. Další kapitola představuje nový standard jménem OpenCL, který umožňuje snadnou paralelizaci výpočtú s využitím různých typů procesorů v ten samý čas. OpenCL taktéž zjednodušuje programování pro grafické karty. Další kapitola navrhuje možnost, jak urychlit výpočet genetického algoritmu s využitím grafické karty a jazyka OpenCL. Pro urychlení byl zvolen permutační genetický algoritmus "problém N-dam", který je náročný na paměť grafické karty. Tato kapitola rozebírá technické specifikace grafické karty, které jsou nevyhnutelné k určení maximální velikosti šachovnice. V kapitole je analyzována správná práce s pamětí grafické karty, která je nevyhnutelná k dosažení urychlení zvoleného genetického algoritmu. Jsou zde taky nastíněny dva generátory náhodných čísel, které jsou součástí testů. Následující kapitola detailně popisuje fungování navržené paralelizace genetického algoritmu. Jsou zde porovnány dvě metody evaluace jedince a je popsán způsob testování a vyhodnocování výsledků. Předposlední kapitola porovnává časovou náročnost generátorů náhodných čísel. Bylo zjištěno, že generátor HybridTaus je o 20 rychlejší o proti generátoru XORshift na GPU. Na CPU byl naopak rychlejší generátor XORshift. Generátor XORshift je na GPU 20 krát rychlejší a generátor HybridTaus je dokonce až 80 krát rychlejší. Dále byly porovnány evaluační funkce. Bylo zjištěno, že GPU běh je 800 krát rychlejší oproti běhu na CPU. Paměťově náročná evaluační metoda byla schopná dosáhnout jenom dvojnásobné zrychlení. Kapitola dále porovnává funkce křížení. PMX dosáhlo zrychlení maximálně o 100 a i to v případech, které nejsou atraktivní pro řešení problému N-dam (N>20). V případe OX je možné dosáhnout zrychlení až o 1100. Také v tomto případě jsou atraktivní hodnoty pouze do 500. Testy, které vyhodnocují běh celého GA, ukázaly, že GPU verze je zhruba dvojnásobně rychlejší. Malé zrychlení bylo způsobeno operátorem selekce a funkcí křížení.