Spelling suggestions: "subject:"algorítmos"" "subject:"algorítimos""
101 |
Análise de complexidade de códigos turbo utilizando as treliças mínima e seccionadaMoritz, Guilherme Luiz 17 February 2012 (has links)
A dissertação apresentada utiliza a representação de treliça mínima e seccionada para a decodificação de códigos turbo, analisando os impactos da aplicação desta técnica no desempenho (taxa de erro em função da relação sinal ruído) em um canal AWGN e avaliando a redução de complexidade de processamento. O processo de decodificação proposto utilizará a teoria de minimização de treliça proposta em (MCELIECE, 1996) e a teoria de seccionamento de treliça proposto em (VARDY, 1998). Decodifica-se utilizando o algoritmo max-log-MAP (VUCETIC; YUAN, 2000). Desenvolve-se uma métrica de complexidade baseada no número de operações e mostra-se técnicas para escolher-se seccionamentos que são simples e apresentam pouca ou nenhuma perda de desempenho em função da decodificação convencional. / We present a technique for reducing the turbo decoding complexity based on minimal and sectionalized trellises. A novel complexity metric is proposed and the complexity of all possible sectionalizations for some selected codes is evaluated. We use the minimal trellis representation proposed in (MCELIECE, 1996) for BCJR decoding and conclude that one can find less complex sectionalizations (when compared to the conventional trellis) which show small or none performance degradation.
|
102 |
An ecosystemic view for developing biologically plausible optimization systems / Uma visão ecossistêmica para o desenvolvimento de sistemas de otimização biologicamente plausíveisParpinelli, Rafael Stubs 19 February 2013 (has links)
A busca por ideias, modelos e paradigmas computacionais biologicamente inspirados e plausíveis sempre atraiu o interesse de cientistas da computação, especialmente na área de Computação Natural. Além disso, o conceito de otimização pode ser abstraído de vários processos naturais como, por exemplo, na evolução das espécies, no comportamento de grupos sociais, na dinâmica do sistema imunológico, nas estratégias de busca por alimento e nas relações ecológicas entre populações de animais. Com o melhor de nosso conhecimento, os ecossistemas naturais e seus conceitos ainda não foram explorados computacionalmente no contexto de otimização de funções e, portanto, eles são abordados nesta tese. Este trabalho destaca as principais propriedades de ecossistemas naturais que podem ser importantes para a construção de ferramentas computacionais para resolver problemas complexos de otimização. Também, a modelagem computacional para tais funcionalidades são introduzidas. A principal discussão apresentada nesta tese refere-se ao uso cooperativo de populações de soluções candidatas, co-evoluindo em um contexto ecossistêmico. Com esta analogia, cada população comportar-se de acordo com uma estratégia de busca específica que é empregada na evolução das soluções candidatas. Além da possibilidade de utilizar diferentes estratégias de busca cooperativamente, esta analogia abre a possibilidade de inserção de conceitos ecológicos no processo de otimização, permitindo o desenvolvimento de novos sistemas de otimização biologicamente inspirados e plausíveis. O potencial de alguns conceitos ecológicos é apresentado em um algoritmo canônico ecologicamente inspirado, chamado ECO (Ecological-inspired Optimiaztion algorithm). Alguns algoritmos baseados em população são utilizados para compor a abordagem proposta. Os problemas resolvidos nesta tese são várias funções contínuas de benckmark com um número alto de dimensões ($D = 200$) e o problema de predição de estrutura de proteínas para o modelo 2D AB. Além disso, o uso de dinâmica populacional para auto-regular o tamanho das populações; o uso de modelos heterogêneos com diferentes estratégias de busca; e o uso de agrupamento hierárquico para ajustar dinamicamente a formação de habitats e probabilisticamente definir as topologias de comunicação são alguns estudos de caso investigados. Os resultados obtidos se mostraram promissores considerando a aplicação do ecossistema computacional. Finalmente, conclusões e várias ideias para pesquisas futuras são apresentadas. / The search for plausible biologically inspired ideas, models and computational paradigms always drew the interest of computer scientists, particularly those from the Natural Computing area. Also, the concept of optimization can be abstracted from several natural processes, for instance, in the evolution of species, in the behavior of social groups, in the dynamics of the immune system, in the food search strategies and in the ecological relationships of different animal populations. To the best of our knowledge, ecosystems and their concepts have not been explored computationally in the context of function optimization and, therefore, they are addressed in this thesis. This work highlights the main properties of ecosystems that can be important for building computational tools to solve complex problems. Also, it is introduced the computational modelling for such biologically plausible functionalities (e.g., habitats, ecological relationships, ecological succession, and another). The main discussion presented in this work relates to the cooperative use of populations of candidate solutions, coevolving in an ecological context. With this ecology-based analogy, each population can behave according to a specific search strategy, employed in the evolution of candidate solutions. In addition to the possibility of using different optimization strategies cooperatively, this analogy opens the possibility of inserting ecological concepts in the optimization process, thus allowing the development of new bio-plausible hybrid systems. The potentiality of some ecological concepts is also presented in a canonical Ecology-inspired Algorithm for Optimization, named ECO. Some population-based algorithms are used to compose the ecology-based approach. The problems solved in this thesis are several continuous benchmark functions with a high number of dimensions ($D = 200$), and the protein structure prediction problem for the 2D AB model. Also, the use of population dynamics to self-regulate the size of populations during ecological successions; the use of heterogeneous models embedding different search strategies into the system; and the use of hierarchical clustering to dynamically adjust the habitats formation and probabilistically define the habitats communication are some case studies investigated. Results were promising concerning the application of the proposed computational ecosystem for optimization. Finally, concluding remarks and several ideas for future research are presented.
|
103 |
Transgenética computacional aplicada a problemas de otimização combinatória com múltiplos objetivosAlmeida, Carolina Paula de 29 February 2012 (has links)
CNPq / A Transgenética Computacional é uma metáfora para o desenvolvimento de algoritmos evolucionários com base na teoria de evolução endossimbiótica e em outras interações do fluxo intracelular. Diversos algoritmos foram desenvolvidos com base nesta metáfora para problemas de Otimização Combinatória, em sua maioria com um único objetivo, obtendo bons resultados. Uma vez que a consideração de mais de um objetivo leva, em geral, a representações mais realistas de problemas práticos complexos, neste trabalho investiga-se o desenvolvimento de Algoritmos Transgenéticos para problemas multiobjetivo. Tais algoritmos são examinados em versões que utilizam elementos de outros algoritmos evolucionários multiobjetivo sendo eles o NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) e o MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Diante disso, este trabalho propõe duas novas metodologias utilizando a Transgenética Computacional acoplada ao NSGA-II e ao MOEA/D, denominadas NSTA (Non-Dominated Sorting Transgenetic Algorithm) e MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectivamente. Para avaliar o desempenho das técnicas propostas, os algoritmos desenvolvidos foram aplicados a dois problemas de Otimização Combinatória, NP-difíceis,em versões com mais de um objetivo. O primeiro problema é o Caixeiro Comprador Biobjetivo e o segundo o Quadrático de Alocação multiobjetivo. Foram realizados experimentos com casos de teste disponíveis em bancos utilizados comumente por outros trabalhos da literatura. Os resultados dos algoritmos propostos foram comparados com os resultados obtidos com os algoritmos evolucionários multiobjetivo que os inspiraram. A análise dos dados obtidos com os experimentos computacionais mostram que a versão MOTA/D é a mais eficiente dentre os algoritmos do experimento com relação a qualidade da aproximação da fronteira de Pareto. / The Computational Transgenetic is a metaphor for the development of evolutionary algorithms based on the theory of evolution endosymbiotic and other intracellular interactions flow. Several algorithms have been developed based on this metaphor for combinatorial optimization problems, mostly with a single objective, obtaining good results. Once the account of more than one objective provides, in general, more realistic representations of complex practical problems, this work investigates the development of Transgenetic Algorithms for multiobjective problems. Such algorithms are examined in versions that use elements of other multiobjective evolutionary algorithms such as the NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) and the MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Therefore, this work proposes two new methods using Computational Transgenetic attached to NSGA-II and MOEA/D, named NSTA (Non-Dominated Sorting Transgenetic Algorithm) and MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectively. To evaluate the proposed techniques performance, the experiments consider two NP-hard combinatorial optimization problems, in versions with more than one objective. The first problem is the Traveling Purchaser Problem and the second the Quadratic Assignment Problem. Experiments were performed with test cases available in benchmarks commonly used by other studies in the literature. The proposed algorithms' results were compared with those obtained by the multiobjetive evolutionary algorithms that inspired them. The analysis of data obtained by the computational experiment shows that the version MOTA/D is among the most efficient algorithms of the experiment with respect to the quality of the Pareto front approximation.
|
104 |
Roteamento em redes tolerantes a atrasos: intensificação versus exploração no processo de busca por melhores caminhosOliveira, Jaquinei de 16 July 2015 (has links)
Voltado para Redes Tolerantes a Atrasos, o protocolo de roteamento Cultural GrAnt (CGrAnt) utiliza Otimização por Colônia de Formigas para representar o espaço populacional de um Algoritmo Cultural. O protocolo CGrAnt emprega diferentes componentes de conhecimento de modo a explorar as características da rede e melhorar o encaminhamento de mensagens: Domínio, Situacional e Histórico. O conhecimento de Domino exerce uma função central na operação do CGrAnt uma vez que ele influencia os conhecimentos Situacional e Hist ́rico, determinando se um n ́ deve explorar (através da seleção de novos encaminhadores de mensagens) ou intensificar (através da seleção de encaminhadores promissores previamente encontrados) o espaço de busca. Através do uso de uma m ́trica especıfica que analisa a dinâmica local da mobilidade dos, o conhecimento de Dom ́ determina o status da busca por caminhos (explora ̧ao ou interino ossificação). O uso dessa m ́trica pode induzir a falso-positivos ou falso-negativos quando o protocolo CGrAnt determina a qualidade de um n ́ como encaminhador de mensagens. De modo a mitigar as limitações da m ́trica original do CGrAnt, este trabalho propõe três metricas alternativas para o conhecimento de Domínio do CGrAnt. As m ́tricas propostas abordam aspectos da rede que n ̃o s ̃o contemplados pela abordagem utilizada pela métrica original. Os resultados mostram que as métricas propostas melhoram o desempenho do protocolo CGrAnt uma vez que apresentam redução na rela ̧ao de redundância de mensagens para todos os cenários de simula ̧ao utilizados e aumentam a taxa de entrega de mensagens em dois dos cenários utilizados. / Designed to Delay Tolerant Networks (DTNs), the Cultural GrAnt (CGrAnt) routing protocol uses Ant Colony Optimization metaheuristic to represent the population space of a Cultural Algorithm. The CGrAnt employs distinct components knowledge in order to explore the network characteristics and improve the message forwarding: Domain, Situational, and History. Domain knowledge plays a central role in the protocol operation as it influences the History and Situational knowledge, by determining if a node must explore (through the selection of new message forwarders) or exploit (through the selection of previously found message forwarders) the search space. By using a specific metric that analyzes the local dynamics of node mobility, the Domain knowledge can set the status of the path search (exploration or exploitation). The use of this metric can induce false- positives or false-negatives when the CGrAnt protocol evaluates the quality of a node as a message forwarder. In order to mitigate the limitations of the CGrAnt’s original metric, this work proposes three alternative metrics to the Domain knowledge of the CGrAnt. The proposed metrics cover aspects of the network which are not addressed by the original metric. Results show the new proposed metrics increase the CGrAnt performance as they achieve lower message redundancy ratio for all the scenarios considered and higher message delivery ratio for two scenarios.
|
105 |
Um algoritmo genético paralelo para o problema de dobramento de proteínas utilizando o modelo 3DHP com cadeia lateralBenítez, César Manuel Vargas 30 June 2010 (has links)
CNPq / Este trabalho apresenta um algoritmo genético paralelo (AGP) para o problema de dobramento de proteínas, utilizando o modelo 3DHP-SC. Este modelo tem sido pouco abordado devido ao elevado grau de complexidade envolvido. Foi proposta uma função de fitness baseada na energia livre e na compacidade do dobramento. Operadores genéticos especiais foram desenvolvidos, além de estratégias para auxiliar o algoritmo no processo de busca de conformações de proteínas. Vários experimentos foram realizados para ajustar todos os parâmetros do sistema, incluindo os parâmetros básicos do AG (probabilidades de mutação e crossover, e o tamanho de torneio) e os parâmetros dos operadores especiais e das estratégias. O efeito da matriz de energias para o modelo no desempenho do algoritmo também foi estudado. Uma comparação com outra abordagem de computação evolucionária também foi realizada, a fim de verificar o desempenho do método proposto. Devido a não existir, até então, benchmarks para teste deste modelo, foi proposto um conjunto de 25 sequências baseado em outro modelo mais simplificado. Os resultados obtidos mostraram que o AGP alcançou um bom nível de eficiência e obteve dobramentos biologicamente coerentes, sugerindo a adequabilidade da metodologia proposta. / This work presents a parallel genetic algorithm (PGA) for the protein folding problem, using the 3DHP-SC model. This model has been sparsely studied in the literature due to its complexity. A new fitness function was proposed, based on the free-energy and compacity of the folding. Special genetic operators were developed, besides strategies to aid the algorithm in the search of protein conformations. Many experiments were done to adjust all the parameters of the system, including the basic parameters of the GA (mutation and crossover probability, and tournament size) and parameters of the special genetic operators and strategies. The effect of the energy matrix of the model in the performance of the algorithm was also studied. Moreover, a comparison with other evolutionary computation approach was done, to verify the performance of the proposed method. Since there is no benchmark available to date, a set of 25 sequences was used, based on a simpler model. Results show that the PGA achieved a good level of efficiency and obtained biologically coherent results, suggesting its adequacy for the problem.
|
106 |
Controle PID gaussiano com otimização dos parâmetros das funções gaussianas usando algoritmo genético e PSO / Gaussian PID control with gaussian function parameters optimization using genetic algorithm and PSOPuchta, Erickson Diogo Pereira 09 December 2016 (has links)
Este trabalho propõe a utilização de uma técnica de controle PID adaptativo gaussiano (GAPID) com o objetivo de aumentar o desempenho do controle PID tradicional aplicado a um conversor Buck. A função gaussiana utilizada para definir os ganhos adaptativos tem características como: é uma função suave e com derivadas suaves, possui limites inferior e superior bem definidos e possui concavidade ajustável. Pelo fato de ser uma função suave, ajuda a evitar problemas relacionados às transições abruptas dos ganhos, comumente encontradas em outros métodos adaptativos. Entretanto, não há uma metodologia algébrica para obter os ganhos adaptativos, visto que originalmente o conjunto de parâmetros do GAPID é composto por oito elementos. Para tanto, utilizaram-se técnicas como otimização através de metaheurísticas bio-inspiradas, métricas avaliativas de desempenho, alteração no método de obtenção do tempo de acomodação, com o objetivo de aumentar o desempenho deste controlador (GAPID) e obter os ganhos adaptativos. O uso do conjunto de oito elementos na otimização gerou soluções ótimas, porém, muito especializadas, levando o controlador a não se comportar bem quando as condições de operação mudam. Desta forma, é proposto um vínculo entre os parâmetros não lineares das curvas gaussianas com os parâmetros lineares do controlador PID, que demonstrou gerar soluções quase tão boas quanto com parâmetros livres e menos especializadas, com comportamento mais homogêneo face a mudanças no ponto de operação do controlador e trazendo como principal vantagem a utilização dos mesmos requisitos de projeto do PID tradicional, o que facilitaria a migração do controlador PID para o GAPID dentro da maioria das indústrias. Os resultados obtidos, tanto na simulação quanto no protótipo foram semelhantes. Isso se deve ao cuidado com a modelagem e o rigor nos procedimentos de projeto, implementados da mesma forma no modelo e no protótipo. / This work proposes the use of a Gaussian adaptive PID control technique (GAPID) in order to increase the performance of the traditional PID control applied to a Buck converter. The Gaussian function used to define adaptive gains has characteristics such as; it is a smooth function with smooth derivatives, it has well defined lower and upper bounded and it has the adjustable concavity. Because it is a smooth function, it helps avoid problems related to abrupt gains transition, commonly found in other adaptive methods. However, there is no algebraic methodology to obtain the adaptive gains, since originally the GAPID parameter set consists of eight elements. Therefore, was used techniques such as optimization through bio-inspired metaheuristics, performance evaluation metrics, and change in the method to obtaining the settling-time, in order to increase the performance of this controller (GAPID) and obtain the adaptive gains. The use of the eight elements in the optimization generated optimized but very specialized solutions, causing the controller not to behave well when the operating conditions change. In this way, a link between the nonlinear parameters of the gaussian curves and the linear parameters of the PID controller was proposed, which demonstrated to generate solutions almost as good as with free and less specialized parameters, with a more homogeneous behavior in relation to changes in the operating point of the controller and bringing as a main advantage the use of the same traditional PID design requirements, which would facilitate the migration of PID controller to GAPID within most industries. The results obtained in both the simulation and the prototype were similar. This is due to careful modeling and rigor in design procedures, implemented in the same way in the model and the prototype.
|
107 |
Proposta de benchmark para simulações de roteamento de dados em redes veiculares ad hocSilva, Rodrigo 29 September 2015 (has links)
Nas últimas décadas, fatores como maior facilidade de crédito e aumento da renda média dos brasileiros motivaram o crescimento das vendas de veículos novos. Com isso, a quantidade de veículos em circulação também aumentou significativamente. Como consequência desse crescimento observa-se o aumento de congestionamento nas grandes cidades, maior número de acidentes de trânsito com vítimas fatais, dentre outros problemas. Neste contexto surge o Sistema de Transporte Inteligente (ITS), que oferece serviços e produtos que utilizam a comunicação de dados no intuito de melhorar o sistema de transporte. Neste sistema, os veículos, os equipamentos móveis e a infraestrutura nas proximidades das vias de tráfego podem transferir dados entre si, formando assim uma rede de comunicação de dados denominada VANET. Esta comunicação permite a implantação de uma série de serviços e soluções de segurança, informação e entretenimento no trânsito. Para gerenciar o roteamento de dados nestas redes de topologia altamente dinâmica, uma série de algoritmos baseados em ACO (Ant Colony Optmization) vem sendo criados. Estes algoritmos são baseados no comportamento das formigas ao saírem de seus ninhos em busca de alimento, as quais tendem a escolher o caminho mais curto entre ninho e alimento. No entanto, observa-se que na literatura não há um padrão para comparação de desempenho destes algoritmos heurísticos, sendo comumente comparados entre si ou com algoritmos de redes MANETs. Neste trabalho foi criado um benchmark com várias instâncias de roteamento multiobjetivo em redes VANETs que podem ser utilizadas para teste de outros algoritmos. Os simuladores de mobilidade e de rede foram configurados para que os cenários de simulação se aproximassem de redes VANETs reais. A área de simulação escolhida para cada cenário foi uma região localizada próxima ao centro da cidade de Curitiba/PR, na qual várias densidades de veículos foram distribuídas de duas formas distintas, uma aleatória e outra tendenciosa a obter maior fluxo nas grandes avenidas. Foram também aplicados o modelo de propagação three log distance sozinho e combinado com o modelo de desvanecimento de Nakagami. Em cada cenário, os veículos origem e destino foram mantidos fixos em lados opostos da área de simulação. Para cada instante da simulação foi aplicado o algoritmo Dijkstra para obter o menor caminho entre origem e destino para a transmissão de pacotes de dados. Um algoritmo de roteamento multiobjetivo baseado em ACO foi proposto e seus resultados foram comparados com o benchmark. Os caminhos encontrados pelo ACO apresentaram maiores números de saltos e, consequentemente, custos superiores aos encontrados pelo algoritmo de Dijkstra. Um benchmark com vários cenários foi criado. As simulações destes cenários mostraram a influência de diversos fatores na conectividade de uma rede VANET, como a densidade de veículos, suas localizações geográficas e modelo de propagação usado. Os resultados obtidos são promissores e apontam a importância na escolha dos modelos de simulação. Tais resultados incentivam o uso de algoritmos heurísticos para roteamento de dados em redes VANET. / In the last decades, we have witnessed an increasing sale of new cars, driven by extensive credit availability and the growth of average income. Hence, the number of vehicles on the roads has increased. Due to this high density of vehicles, the traffic jams as well as fatal accidents are increasing.
In order to reduce such factors, the Intelligent Transportation Systems (ITS) aroused, offering connected services and products related to entertainment and road safety. In this system, vehicles, mobile equipments and the infrastructure in the neighborhood of the traffic ways can transfer data to each other, thus creating a network called VANET (Vehicular Ad-hoc Network).
To optimize the packets routing in these dynamic networks, several Ant Colony Optmization (ACO) - based algorithms have been proposed. Such algorithms are inspired by the foraging behavior of ants, which are capable of finding the shortest paths from food sources to the nest.
However, there are no performance evaluation standards in the recent literature. The algorithms are often compared to each other or with MANET’s algorithms. In this dissertation, a bench-mark of several routing instances for VANETs was created. These benchmarks can be used for testing routing algorithms.
The mobility and network simulators were configured in order to create real-world VANET-like scenarios. The geographical area chosen for the scenarios was near to Curitiba downtown.
Different vehicle densities were distributed in two way: purely random and biased in such a way that avenues receive higher vehicle flows. The three log-distance path loss model was applied to each scenario, sometimes combined with the Nakagami fading model.
In each scenario the source and destination vehicles are fixed on opposite sides of the simulated area. For each simulation time step, the Dijkstra algorithm was run to find the shortest path data transmission between source and destination. A multiobjective ACO-based algorithm was proposed and compared with the Dijkstra algorithm. The paths found by ACO include higher number of hops than those found by the Dijkstra algorithm.
A benchmark with several scenarios was created. The scenario’s simulations show the importance of several factors in the VANET connectivity, such as vehicle density, geographical location and propagation models. The results are promising and indicate the importance of choosing appropriated simulation models.
|
108 |
Genius: um escalonamento baseado em algoritmos genéticos para comutadores de alto desempenhoHoffmann, José Ricardo 18 October 2013 (has links)
Um dos mais importantes elementos que compõem uma rede de telecomunicações é o roteador. Os roteadores modernos empregam sofisticados comutadores para a transmissão de pacotes. A arquitetura de comutadores com filas de entrada exige um processo de escalonamento que estabelece a transferência de pacotes das portas de entrada às portas de saída. O desempenho do sistema depende diretamente do algoritmo de escalonamento, considerando sua vazão e complexidade. Esta dissertação realiza o levantamento teórico dos algoritmos de escalonamento mais relevantes e propõe uma abordagem de escalonamento usando algoritmos genéticos. Um simulador baseado em eventos discretos foi desenvolvido para a realização de testes de desempenho dos escalonadores estudados. O algoritmo proposto, denominado GENIUS, apresentou desempenho relevante e baixa complexidade. / One of the most important components of network telecommunications is the router. Modern routers employ input-queued crossbar switches that require sophisticated scheduling techniques for packet transmission. The architecture of switches with input queues requires an scheduling process that establishes the transfer of packets from input to output ports. The performance of router depends of the scheduling algorithm, considering its throughput and complexity. In this work we survey the most relevant theoretical scheduling algorithms and propose a scheduling approach using genetic algorithms. We developed a simulator of discrete events for testing of schedulers performance. The proposed algorithm, called GENIUS, presents relevant performance and low complexity.
|
109 |
Segmentação de movimento por fluxo óticoKuiaski, José Rosa 24 August 2012 (has links)
A percepção de movimento é uma característica essencial à sobrevivência de diversas espécies. Na natureza, é através do movimento que uma presa percebe a chegada de um predador e decide em que direção deve fugir, bem como o predador detecta a presença de uma presa e decide para onde atacar. O Sistema Visual Humano é mais sensível a movimento do que a imagens estáticas, sendo capaz de separar as informações de movimento originadas pela movimentação própria das informações de movimento de objetos animados no ambiente. A Teoria Ecológica de Gibson (1979) provê uma base para o entendimento de como esse processo de percepção ocorre e estende-se com o conceito do que chamamos de campo vetorial de Fluxo Ótico, através do qual se representa computacionalmente o movimento. O objetivo principal deste trabalho é procurar reproduzir computacionalmente esse comportamento, para possíveis aplicações em navegação autônoma e processamento de vídeo com movimentação desconhecida. Para isso, vale-se das técnicas de estimação de Fluxo Ótico presentes na literatura, tais como as propostas por Lucas e Kanade (1981) e Farneback (1994). Em primeiro momento, avalia-se a possibilidade de utilização de uma técnica estatística de separação cega de fontes, a chamada Análise de Componentes Independentes, tomando como base o trabalho de Bell e Sejnowski (1997), na qual se mostra que tal análise aplicada em imagens fornece filtros de bordas. Depois, avalia-se a utilização do Foco de Expansão para movimentos translacionais. Resultados experimentais demonstram uma maior viabilidade da abordagem por Foco de Expansão. / Motion Perception is an essential feature for the survival of several species. In nature, it is through motion that a prey perceives the predator and is able to decide which direction to escape, and the predator detects the presence of a prey and decides where to attack. The Human Visual System is more sensitive to motion than to static imagery, and it is able to separate motion information due to egomotion from that due to an animated object in the environment. The Ecological Theory of Gibson (1979) provides a basis for understanding how this processes of perception occurs, and leads to the concept of what we call the vector field of Optical Flow, through which computational motion is represented. The main objective of this work is to try to reproduce computationally this behaviour, for possible applications in autonomous navigation and video processing with unknown self-motion. For this, we use some Optical Flow estimation techniques, as those proposed by Lucas and Kanade (1981) and Farneback (1994). At first, we assess the possibility of using a statistical technique of blind source separation, the so-called Independent Component Analysis, based on the work of Bell and Sejnowski (1997), which demonstrates that this technique, when applied to imagery, provides edge filters. Then, we assess the use of the Focus of Expansion to translational motion. Experimental results show the second approach, using the Focus of Expansion, is more viable than through Independent Component Analysis.
|
110 |
Mega busca harmônica: algoritmo de busca harmônica baseado em população e implementado em unidades de processamento gráficoScalabrin, Marlon Henrique 31 March 2012 (has links)
CAPES / Este trabalho propõe uma modificação da meta-heurística Busca Harmônica (HS) a partir de uma nova abordagem baseada em população, empregando, também, algumas estratégias inspiradas em outras meta-heurísticas. Este novo modelo foi implementado utilizando a arquitetura de programação paralela CUDA em uma GPU. O uso de placas de processamento gráficas (GPU) para processamento de propósito geral está crescendo, e estas têm sido utilizadas por muitos pesquisadores para processamento científico. Seu uso se mostra interessante para meta-heurísticas populacionais, podendo realizar muitas operações simultaneamente. A HS é uma meta-heurística inspirada no objetivo de um músico em buscar uma harmonia perfeita. modelo proposto incluiu-se uma população de harmonias temporárias que são geradas a cada nova iteração, permitindo a realização simultânea de diversas avaliações de função. Assim aumenta-se o grau de paralelismo da HS, possibilitando maiores ganhos de velocidade com o uso de arquiteturas paralelas. O novo modelo proposto executado em GPU foi denominado Mega Harmony Search (MHS). Na implementação em GPU cada passo do algoritmo é tratado individualmente em forma de kernels com configurações particulares para cada um. Para demonstrar a eficácia do modelo proposto foram selecionados alguns problemas de benchmark, como a otimização de estruturas de proteínas, a otimização de treliças e problemas matemáticos. Através de experimentos fatoriais foi identificado um conjunto de parâmetros padrão, o qual foi utilizado nos outros experimentos. As análises realizadas sobre resultados experimentais mostram que o MHS apresentou solução de qualidade equivalente à HS e ganhos de velocidade, com a sua execução em GPU, superiores a 60x quando comparado a implementação em CPU. Em trabalhos futuros poderão ser estudadas novas modificações ao algoritmo, como a implementação de nichos e estudos de estratégias de interação entre eles. / This work propose a new approach for the metaheuristic Harmonic Search (HS), by using a population of solutiona and other strategies inspired in another metaheuristics. This new model was implemented using a parallel architecture of a graphical processing unity (GPU). The use of GPU for general-purpose processing is growing, specially for scientific processing. Its use is particularly interesting for populational metaheuristics, where multiple operations are executed simultaneously. The HS is a metaheuristic inspired by the way jazz musicians search for a perfect harmony. In the proposed model a population of temporary harmonies was included. Such population was generated at each iteration, enabling simultaneous evaluation of the objective function being optimized, and thus, increasing the level of parallelism of HS. The new approach implemented in GPU was named Mega Harmony Search (MHS), and each step of the algorithm is handled in the form of kernels with particular configurations for each one. To show the efficiency of MHS some benchmark problems were selected for testing, including mathematical optimization problems, protein structure prediction, and truss structure optimization. Factorial experiments were done so as to find the best set of parameters for the MHS. The analyzes carried out on the experimental results show that the solutions provided by MHS have comparable quality to those of the simple Harmony Search. However, by using GPU, MHS achieved a speedup of 60x, compared with the implementation in regular CPU. Future work will focus other improvements in the algorithm, such as the use of niches and species, as well a study of the interactions between them.
|
Page generated in 0.0282 seconds