The design and implementation of today's most advanced VLSI circuits and multi-layer printed circuit boards would not be possible without automated design tools that assist with the placement of components and the routing of connections between these components. In this work, we investigate how placement and routing can be implemented and accelerated using cloud computing resources. A parallel genetic algorithm approach is used to optimize component placement and the routing order supplied to a Lee's algorithm maze router. A study of mutation rate, dominance rate, and population size is presented to suggest favorable parameter values for arbitrary-sized printed circuit board problems. The algorithm is then used to successfully design a Microchip PIC18 breakout board and Micrel Ethernet Switch. Performance results demonstrate that a 50X runtime performance improvement over a serial approach is achievable using 64 cloud computing cores. The results further suggest that significantly greater performance could be achieved by requesting additional cloud computing resources for additional cost. It is our hope that this work will serve as a framework for future efforts to improve parallel placement and routing algorithms using cloud computing resources.

Ensembles methods such as AdaBoost, Bagging and Random Forest have attracted much attention in the statistical learning community in the last 15 years. Zhu and Chipman (2006) proposed the idea of using ensembles for variable selection. Their implementation used a parallel genetic algorithm (PGA). In this thesis, I propose a stochastic stepwise ensemble for variable selection, which improves upon PGA. Traditional stepwise regression (Efroymson 1960) combines forward and backward selection. One step of forward selection is followed by one step of backward selection. In the forward step, each variable other than those already included is added to the current model, one at a time, and the one that can best improve the objective function is retained. In the backward step, each variable already included is deleted from the current model, one at a time, and the one that can best improve the objective function is discarded. The algorithm continues until no improvement can be made by either the forward or the backward step. Instead of adding or deleting one variable at a time, Stochastic Stepwise Algorithm (STST) adds or deletes a group of variables at a time, where the group size is randomly decided. In traditional stepwise, the group size is one and each candidate variable is assessed. When the group size is larger than one, as is often the case for STST, the total number of variable groups can be quite large. Instead of evaluating all possible groups, only a few randomly selected groups are assessed and the best one is chosen. From a methodological point of view, the improvement of STST ensemble over PGA is due to the use of a more structured way to construct the ensemble; this allows us to better control over the strength-diversity tradeoff established by Breiman (2001). In fact, there is no mechanism to control this fundamental tradeoff in PGA. Empirically, the improvement is most prominent when a true variable in the model has a relatively small coefficient (relative to other true variables). I show empirically that PGA has a much higher probability of missing that variable.

Ensembles methods such as AdaBoost, Bagging and Random Forest have attracted much attention in the statistical learning community in the last 15 years. Zhu and Chipman (2006) proposed the idea of using ensembles for variable selection. Their implementation used a parallel genetic algorithm (PGA). In this thesis, I propose a stochastic stepwise ensemble for variable selection, which improves upon PGA. Traditional stepwise regression (Efroymson 1960) combines forward and backward selection. One step of forward selection is followed by one step of backward selection. In the forward step, each variable other than those already included is added to the current model, one at a time, and the one that can best improve the objective function is retained. In the backward step, each variable already included is deleted from the current model, one at a time, and the one that can best improve the objective function is discarded. The algorithm continues until no improvement can be made by either the forward or the backward step. Instead of adding or deleting one variable at a time, Stochastic Stepwise Algorithm (STST) adds or deletes a group of variables at a time, where the group size is randomly decided. In traditional stepwise, the group size is one and each candidate variable is assessed. When the group size is larger than one, as is often the case for STST, the total number of variable groups can be quite large. Instead of evaluating all possible groups, only a few randomly selected groups are assessed and the best one is chosen. From a methodological point of view, the improvement of STST ensemble over PGA is due to the use of a more structured way to construct the ensemble; this allows us to better control over the strength-diversity tradeoff established by Breiman (2001). In fact, there is no mechanism to control this fundamental tradeoff in PGA. Empirically, the improvement is most prominent when a true variable in the model has a relatively small coefficient (relative to other true variables). I show empirically that PGA has a much higher probability of missing that variable.

Tato práce se zabývá možností paralelizace Genetického Algoritmu a jeho ná-sledné evaluace pomocí testovacích účelových funkcí. První část je teoretická a shrnuje základní poznatky z oblasti Genetických Algoritmů, paralelních archi-tektur, paralelních výpočtů a optimalizace. A dále je tato část doplněna o mož-nosti paralelizace Genetického Algoritmu. V následující praktické části je rozebrán algoritmus paralelního Genetického Algoritmu, jenž je použitý při experimentu a také je diskutována struktura a účel zvoleného experimentu. Následně jsou diskutovány výsledky získané z běhu experimentu na Eridani Clusteru z pohledu zrychlení výpočtu, kvality nalezeného řešení a závislosti kvality řešení na migračním schématu.

A tomografia por sensoriamento elétrico representa uma técnica de grande potencial para a otimização de processos normalmente associados às indústrias do petróleo e química. Entretanto, o emprego de técnicas tomográficas em processos industriais envolvendo fluidos multifásicos ainda carece de métodos robustos e computacionalmente eficientes. Nesse contexto, o principal objetivo deste trabalho é contribuir para o desenvolvimento de métodos para a solução do problema tomográfico com base em algoritmos genéticos específicos para a fenomenologia do problema abordado (interação do campo elétrico com o campo hidrodinâmico), bem como a adaptação do algoritmo para processamento em paralelo. A idéia básica consiste em partir de imagens qualitativas, fornecidas por uma sonda de visualização direta, para formar um modelo da distribuição interna do contraste elétrico e refiná-lo iterativamente até que variáveis de controle resultantes do modelo numérico se igualem às suas homólogas, determinadas experimentalmente. Isso pode ser feito usando um funcional de erro, que quantifique a diferença entre as medidas externas não intrusivas (fluxo de corrente elétrica real) e as medidas calculadas no modelo numérico (fluxo de corrente elétrica aproximado). De acordo com a abordagem funcional adotada, pode-se modelar a reconstrução numérica do contraste elétrico como um problema de minimização global, cuja função objetivo corresponde ao funcional de erro convenientemente definido e o mínimo global representa a imagem procurada. A grande dificuldade está no fato do problema ser não linear e mal-posto, o que reflete na topologia da superfície de minimização, demandando um método especializado de otimização para escapar de mínimos locais, pontos de sela, mínimos de fronteira e regiões praticamente planas. Métodos de otimização poderosos, como os algoritmos genéticos, embora apresentem elevado esforço computacional na obtenção da imagem procurada, são melhor adaptáveis ao problema em questão. Desse modo, optou-se pelo uso de algoritmos genéticos paralelos nas arquiteturas mestre-escravo, ilha, celular e híbrida (combinando ilha e celular). O desempenho computacional dos algoritmos desenvolvidos foi testado em um problema de reconstrução da imagem tomográfica de um escoamento vertical a bolhas. De acordo com os resultados, a arquitetura híbrida é capaz de obter a imagem desejada com um desempenho computacional melhor, quando comparado ao desempenho das arquiteturas mestre-escravo, ilha e celular. Além disso, estratégias para melhorar a eficiência do algoritmo foram propostas, como a introdução de informações a priori, derivadas de conhecimento físico do problema tomográfico (fração de vazio e coeficiente de simetria do escoamento), a inserção de uma tabela hash para evitar o cálculo de soluções já encontradas, o uso de operadores de predação e de busca local. De acordo com os resultados, pode-se concluir que a arquitetura híbrida é um método apropriado para solução do problema de tomografia por impedância elétrica de escoamentos multifásicos. / Tomography by electrical sensing represents a technique of great potential for the optimization of processes usually associated with petroleum and chemical industries. However, the employment of tomographic techniques in industrial processes involving multiphase flows still lacks robust and computationally efficient methods. In this context, the main objective of this thesis is to contribute to the development of solution methods based on specific genetic algorithms for the phenomenology of the tomographic problem (interaction between electric and hydrodynamic fields), as well as the adaptation of the algorithm to parallel processing. From qualitative images provided by a direct imaging probe, the basic idea is to generate a model of electric contrast internal distribution and refine it repeatedly until control variables resulting from the numerical model equalize their counterparts, determined experimentally. It can be performed by using an error functional to quantify the difference between non-intrusive external measurements (actual electric current flow) and measurements calculated in a numerical model (approximate electric current flow). According to the functional approach, the numerical reconstruction of the electrical contrast can be treated as a global minimization problem in which the fitness function is an error functional conveniently defined and the global minimum corresponds to the sought image. The major difficulty lies in the nonlinear and ill-posed nature of the problem, which reflects on the topology of the minimization surface, demanding a specialized optimization method to escape from local minima, saddle points, boundary minima and almost plane regions. Although powerful optimization methods, such as genetic algorithms, require high computational effort to obtain the sought image, they are best adapted to the problem in question, therefore parallel genetic algorithms were employed in master-slave, island, cellular and hybrid models (combining island and cellular). The computational performance of the developed algorithms was tested in a tomographic image reconstruction problem of vertical bubble flow. According to the results, the hybrid model can obtain the sought image with a better computational performance, when compared with the other models. Besides, strategies to improve the algorithm efficiency, such as the introduction of a priori information derived from the physical knowledge of the tomographic problem (void fraction and symmetry coefficient of the flow), the insertion of a hash table to avoid the calculation of solutions already found, the use of predation and local search operators were proposed. According to the results, it is possible to conclude that the hybrid model is an appropriate method for solving the electrical impedance tomography problem of multiphase flows.

A tomografia por sensoriamento elétrico representa uma técnica de grande potencial para a otimização de processos normalmente associados às indústrias do petróleo e química. Entretanto, o emprego de técnicas tomográficas em processos industriais envolvendo fluidos multifásicos ainda carece de métodos robustos e computacionalmente eficientes. Nesse contexto, o principal objetivo deste trabalho é contribuir para o desenvolvimento de métodos para a solução do problema tomográfico com base em algoritmos genéticos específicos para a fenomenologia do problema abordado (interação do campo elétrico com o campo hidrodinâmico), bem como a adaptação do algoritmo para processamento em paralelo. A idéia básica consiste em partir de imagens qualitativas, fornecidas por uma sonda de visualização direta, para formar um modelo da distribuição interna do contraste elétrico e refiná-lo iterativamente até que variáveis de controle resultantes do modelo numérico se igualem às suas homólogas, determinadas experimentalmente. Isso pode ser feito usando um funcional de erro, que quantifique a diferença entre as medidas externas não intrusivas (fluxo de corrente elétrica real) e as medidas calculadas no modelo numérico (fluxo de corrente elétrica aproximado). De acordo com a abordagem funcional adotada, pode-se modelar a reconstrução numérica do contraste elétrico como um problema de minimização global, cuja função objetivo corresponde ao funcional de erro convenientemente definido e o mínimo global representa a imagem procurada. A grande dificuldade está no fato do problema ser não linear e mal-posto, o que reflete na topologia da superfície de minimização, demandando um método especializado de otimização para escapar de mínimos locais, pontos de sela, mínimos de fronteira e regiões praticamente planas. Métodos de otimização poderosos, como os algoritmos genéticos, embora apresentem elevado esforço computacional na obtenção da imagem procurada, são melhor adaptáveis ao problema em questão. Desse modo, optou-se pelo uso de algoritmos genéticos paralelos nas arquiteturas mestre-escravo, ilha, celular e híbrida (combinando ilha e celular). O desempenho computacional dos algoritmos desenvolvidos foi testado em um problema de reconstrução da imagem tomográfica de um escoamento vertical a bolhas. De acordo com os resultados, a arquitetura híbrida é capaz de obter a imagem desejada com um desempenho computacional melhor, quando comparado ao desempenho das arquiteturas mestre-escravo, ilha e celular. Além disso, estratégias para melhorar a eficiência do algoritmo foram propostas, como a introdução de informações a priori, derivadas de conhecimento físico do problema tomográfico (fração de vazio e coeficiente de simetria do escoamento), a inserção de uma tabela hash para evitar o cálculo de soluções já encontradas, o uso de operadores de predação e de busca local. De acordo com os resultados, pode-se concluir que a arquitetura híbrida é um método apropriado para solução do problema de tomografia por impedância elétrica de escoamentos multifásicos. / Tomography by electrical sensing represents a technique of great potential for the optimization of processes usually associated with petroleum and chemical industries. However, the employment of tomographic techniques in industrial processes involving multiphase flows still lacks robust and computationally efficient methods. In this context, the main objective of this thesis is to contribute to the development of solution methods based on specific genetic algorithms for the phenomenology of the tomographic problem (interaction between electric and hydrodynamic fields), as well as the adaptation of the algorithm to parallel processing. From qualitative images provided by a direct imaging probe, the basic idea is to generate a model of electric contrast internal distribution and refine it repeatedly until control variables resulting from the numerical model equalize their counterparts, determined experimentally. It can be performed by using an error functional to quantify the difference between non-intrusive external measurements (actual electric current flow) and measurements calculated in a numerical model (approximate electric current flow). According to the functional approach, the numerical reconstruction of the electrical contrast can be treated as a global minimization problem in which the fitness function is an error functional conveniently defined and the global minimum corresponds to the sought image. The major difficulty lies in the nonlinear and ill-posed nature of the problem, which reflects on the topology of the minimization surface, demanding a specialized optimization method to escape from local minima, saddle points, boundary minima and almost plane regions. Although powerful optimization methods, such as genetic algorithms, require high computational effort to obtain the sought image, they are best adapted to the problem in question, therefore parallel genetic algorithms were employed in master-slave, island, cellular and hybrid models (combining island and cellular). The computational performance of the developed algorithms was tested in a tomographic image reconstruction problem of vertical bubble flow. According to the results, the hybrid model can obtain the sought image with a better computational performance, when compared with the other models. Besides, strategies to improve the algorithm efficiency, such as the introduction of a priori information derived from the physical knowledge of the tomographic problem (void fraction and symmetry coefficient of the flow), the insertion of a hash table to avoid the calculation of solutions already found, the use of predation and local search operators were proposed. According to the results, it is possible to conclude that the hybrid model is an appropriate method for solving the electrical impedance tomography problem of multiphase flows.

Finding optimal configuration of power distribution systems topology is an NP-hard combinatorial optimization problem. It becomes more complex when time varying nature of loads in large-scale distribution systems is taken into account. In the second chapter of this dissertation, a systematic approach is proposed to tackle the computational burden of the procedure. To solve the optimization problem, a novel adaptive fuzzy based parallel genetic algorithm (GA) is proposed that employs the concept of parallel computing in identifying the optimal configuration of the network. The integration of fuzzy logic into GA enhances the efficiency of the parallel GA by adaptively modifying the migration rates between different processors during the optimization process. A computationally efficient graph encoding method based on Dandelion coding strategy is developed which automatically generates radial topologies and prevents the construction of infeasible radial networks during the optimization process. The main shortcoming of the proposed algorithm in Chapter 2 is that it identifies only one single solution. It means that the system operator will not have any option but relying on the found solution. That is why a novel hybrid optimization algorithm is proposed in the third chapter of this dissertation that determines Pareto frontiers, as candidate solutions, for multi-objective distribution network reconfiguration problem. Implementing this model, the system operator will have more flexibility in choosing the best configuration among the alternative solutions. The proposed hybrid optimization algorithm combines the concept of fuzzy Pareto dominance (FPD) with shuffled frog leaping algorithm (SFLA) to recognize non-dominated suboptimal solutions identified by SFLA. The local search step of SFLA is also customized for power systems applications so that it automatically creates and analyzes only the feasible and radial configurations in its optimization procedure which significantly increases the convergence speed of the algorithm. In the fourth chapter, the problem of optimal network reconfiguration is solved for the case in which the system operator is going to employ an optimization algorithm that is automatically modifying its parameters during the optimization process. Defining three fuzzy functions, the probability of crossover and mutation will be adaptively tuned as the algorithm proceeds and the premature convergence will be avoided while the convergence speed of identifying the optimal configuration will not decrease. This modified genetic algorithm is considered a step towards making the parallel GA, presented in the second chapter of this dissertation, more robust in avoiding from getting stuck in local optimums. In the fifth chapter, the concentration will be on finding a potential smart grid solution to more high-quality suboptimal configurations of distribution networks. This chapter is considered an improvement for the third chapter of this dissertation for two reasons: (1) A fuzzy logic is used in the partitioning step of SFLA to improve the proposed optimization algorithm and to yield more accurate classification of frogs. (2) The problem of system reconfiguration is solved considering the presence of distributed generation (DG) units in the network. In order to study the new paradigm of integrating smart grids into power systems, it will be analyzed how the quality of suboptimal solutions can be affected when DG units are continuously added to the distribution network. The heuristic optimization algorithm which is proposed in Chapter 3 and is improved in Chapter 5 is implemented on a smaller case study in Chapter 6 to demonstrate that the identified solution through the optimization process is the same with the optimal solution found by an exhaustive search.

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í.

This thesis represents master's thesis focused on acceleration of Genetic algorithms using GPU. First chapter deeply analyses Genetic algorithms and corresponding topics like population, chromosome, crossover, mutation and selection. Next part of the thesis shows GPU abilities for unified computing using both DirectX/OpenGL with Cg and specialized GPGPU libraries like CUDA. The fourth chapter focuses on design of GPU implementation using CUDA, coarse-grained and fine-grained GAs are discussed, and completed by sorting and random number generation task accelerated by GPU. Next chapter covers implementation details -- migration, crossover and selection schemes mapped on CUDA software model. All GA elements and quality of GPU results are described in the last chapter.