Made available in DSpace on 2015-03-04T18:51:02Z (GMT). No. of bitstreams: 1 thesis_final.pdf: 17163181 bytes, checksum: 00c96f156953680b2cfcf263393486b2 (MD5) Previous issue date: 2008-04-30 / Conselho Nacional de Desenvolvimento Cientifico e Tecnologico / The goal of ab initio protein structure prediction (PSP) methods is to predict, based on first principles, the three-dimensional structure that a given amino-acid sequence will assume. These methods have important biotechnological applications from the creation of new proteins, drug design (the receptor's structure), the refinement of theoretical models and the elucidation of structures from sparse experimental data. The prediction encompasses an optimization problem with thousands of degrees of freedom and is associated with extremely complex energy hypersurfaces. This results in a problem that is difficult to treat computationally. In this work a simplified three-dimensional protein model (hydrophobic-polar model, HP) was used in order to reduce the computational costs of the PSP problem allowing for the fast development of a robust and efficient genetic algorithms based methodology. This methodology was then adapted to an all-atoms protein model. During the development different strategies for the PSP problem were analyzed. A new crowding based approach is described for the maintenance of diversity within the population which resulted in achieving multiple solutions. The HP model's methodology was tested against all 35 major sequences from the literature and the comparative results showed that the proposed genetic algorithm is superior to other evolutionary algorithms and comparable to specialized methods. The algorithm applied to the all-atoms model was initially tested with poli-alanines and later with five other proteins. Structures with RMSDs ranging from 2.0 to 6.7 Å were found and the proposed algorithm was superior to others similar methods, in terms of computational costs. The results obtained showed that optimization strategies with multiple solutions characteristics present two advantages. The first one is the more efficient investigation of a complex hypersurface, with better chances of finding optimal solutions; the second one is increasing the probability of finding structures close to those experimentally determined, even when they are not near the global optimum of the energy hypersurface. / Métodos de predição ab initio de estrutura de proteínas (PSP) buscam prever, baseando-se em primeiros princípios, a estrutura tridimensional que uma dada seqüência de aminoácidos irá adotar no espaço. Os métodos de predição ab initio atualmente possuem aplicações biotecnológicas que envolvem desde a criação de novas proteínas, o auxílio no desenho racional de fármacos (estrutura do receptor), o refinamento de modelos teóricos e a obtenção de estruturas a partir de dados experimentais incompletos. Entretanto, a predição envolve um problema de otimização que lida com milhares de graus de liberdade e está associado à hipersuperfícies de energia extremamente complexas o que torna o problema difícil de ser tratado computacionalmente. Neste trabalho utilizamos um modelo tridimensional de proteínas simplificado (modelo hidrofóbico-polar, HP) para reduzir os custos computacionais associados ao problema de PSP de modo que uma metodologia de otimização, robusta e eficiente, baseada em algoritmos genéticos, fosse desenvolvida mais rapidamente. Em seguida a metodologia foi adaptada para um modelo com descrição atômica que utiliza um campo de forças clássico como função de energia. Durante o desenvolvimento foram implementadas e analisadas várias estratégias para o problema. Foi descrita uma nova abordagem, baseada em crowding, para a manutenção da diversidade na população que resulta na obtenção simultânea de múltiplas soluções. A metodologia para o modelo HP foi aplicada a 35 seqüências disponíveis na literatura e os resultados comparativos mostraram que o algoritmo genético desenvolvido é superior a outros algoritmos evolutivos publicados, e comparável a métodos especializados. A metodologia para o modelo atômico foi inicialmente testada em poli-alaninas e em seguida em cinco outras proteínas de maior complexidade. Foram encontradas estruturas apresentando RMSDs entre 2,0 e 6,7 Å, em relação à estrutura determinada experimentalmente. O algoritmo genético se mostrou superior a outros métodos semelhantes, em termos de custo computacional. Os resultados obtidos mostram que as estratégias de otimização envolvendo a busca por múltiplos mínimos possuem duas grandes vantagens. A primeira delas está em uma investigação mais efetiva de uma hipersuperfície complexa aumentando a probabilidade de se encontrar soluções ótimas (de mais baixa energia); a segunda delas está no aumento da probabilidade de se obter estruturas próximas daquelas determinadas experimentalmente mesmo quando estas não são o mínimo global da hipersuperfície de energia investigada.

O processo evolutivo deixa vieses no sistema nervoso de forma a optimizar nossas capacidades cognitivas para o ambiente em que evoluímos. Nosso objetivo é criar modelos de vida artificial nos quais a atenção seletiva, a tomada de decisão em sequências binárias e o tempo de reação ao aparecimento abrupto de um alvo precedido por pista emerjam como consequência da evolução. Em nossos experimentos, a atenção seletiva enviesava o processamento de estímulos de forma a dar prioridade aos mais relevantes quando eles tinham relevâncias diferentes. Nossos experimentos de tomada de decisão apóiam a teoria de que o pareamento de probabilidades, estratégia adotada por seres humanos neste tipo de experimento, é consequência da busca de padrões, que decorre da importância que isto teve durante a evolução humana. No estudo do tempo de reação, o comportamento observado em seres humanos só pôde ser modelado em populações de animais artificiais quando existia ruído e eles tinham que selecionar uma ação apropriada entre duas possíveis. / The evolutionary process leaves biases in the nervous system so as to optimize our cognitive capacities to the environment where we evolved. Our objective is to create artificial life models wherein selective attention, decision making in binary sequences and reaction time to the abrupt appearance of a target preceded by a cue emerge as a consequence of evolution. In our experiments, selective attention biased stimuli processing so as to give priority to the most relevant stimuli when they had different relevances. Our decision making experiments support the theory that probability matching, the strategy adopted by humans in this kind of experiment, is a consequence of a search for patterns, which results from the importance that finding regularities in our environment had during human evolution. In the study of reaction time, the behavior observed in humans could only be modeled in populations of artificial animal when there was noise and they had to select an appropriate action between two possible ones.

Fundação do Amparo à Pesquisa do Estado do Amazonas (FAPEAM) / Nesta dissertação de mestrado é apresentada uma proposta de um método simples de compressão de dados sem perda para Redes de Sensores sem Fio (RSSF). Este método é baseado numa codificação Huffman convencional aplicada a um conjunto de amostras de parâmetros monitorados que possuam uma forte correlação temporal, fazendo com que seja gerado um dicionário Huffman a partir dessas probabilidades e que possam ser utilizadas em outros conjuntos de parâmetros de mesma característica. Os resultados de simulação usando temperatura e umidade relativa mostram que este método supera alguns dos mais populares mecanismos de compressão projetados especificamente para RSSF. / In this masters thesis we present a lightweight lossless data compression method for wireless sensor networks(WSN). This method is based on a conventional Huffman coding applied to a sample set of monitored parameters that have a strong temporal correlation, so that a Huffman dictionary is generated from these probabilities, and which may be used in other sets of parameters with same characteristic. Simulations results using temperature and relative humidity measurements show that the proposed method outperforms popular compression mechanisms designed specifically for wireless sensor networks.

Parte da população mundial sofre com distúrbios relacionados ao controle muscular de membros superiores e inferiores que, em muitos casos, podem ter sua origem devido a interrupção da comunicação sensório-motora entre o cérebro e os grupos musculares. Estes fatores podem estar relacionados à idade, doenças neuro-degenerativas ou acidentes vasculares cerebrais (AVC). Dessa forma, devido ao gradativo envelhecimento da população, em função do aumento da expectativa de vida e consequentemente da demanda por tratamentos de reabilitação, diversos estudos da literatura utilizam equipamentos de biofeedback na reabilitação do controle muscular, não havendo, porém, uma ferramenta simples e unificada que permita a elaboração de protocolos motores para diversas patologias em uma única plataforma. Sendo assim, o objetivo deste trabalho é apresentar o desenvolvimento de uma ferramenta de biofeedback visual, baseada em plataformas de força para membros inferiores e aquisição de imagem para membros superiores. Este sistema conta com duas interfaces: a primeira, programável em alto nível, é destinada ao profissional da saúde para elaboração do treino motor conforme a necessidade do paciente; a segunda é a interface do jogo, ou serious game, com o qual o paciente interage realizando a série de atividades programadas em um jogo de exercícios, ou exergames. A proposta deste estudo é fornecer uma plataforma de reabilitação programável de acordo com a necessidade específica de cada paciente, mantendo características motivacionais e de interatividade, que proporcionem entretenimento associado às atividades, reduzindo assim a evasão dos tratamentos, que costumam ser realizados por longos períodos. Ainda, neste estudo foram apresentados alguns testes, aprovados pelo comitê de ética, com voluntários, em que é aplicado um protocolo motor a um grupo de jovens saudáveis e comparando os resultados com um grupo de voluntários idosos. Os resultados deste estudo foram obtidos a partir de duas análises: a primeira é interna à sessão, em tempo real, e diz respeito à pontuação dos voluntários no jogo; a segunda é externa à sessão, utiliza os dados armazenados ao longo de um teste estabilométrico e compara medidas posturográficas do grupo de jovens e idosos saudáveis. Ainda, para complementar a validação do equipamento desenvolvido, foi realizada uma comparação dos resultados das análises posturográficas obtidas, com os resultados obtidos a partir de um baropodômetro comercial. Os resultados demonstram que o sistema permite a obtenção da estimativa da estabilometria e atividades de serious games. / The cases of disorders related to upper and lower limbs control directly affect the population. These problems may have its origin due to interruption of sensorimotor communication between the brain and the muscle groups. These factors may be related to aging, neurodegenerative diseases or stroke. Thus, due to the gradual aging of the population, the increase in life expectancy and hence the demand for rehabilitation treatments, several studies in the literature are using biofeedback to rehabilitation of muscle control. However, there is no unified tool that allows the development of exercise protocols for several diseases in a single platform. The aim of this work is to present the development of a visual biofeedback tool, based on force platforms for lower limbs and image acquisition for upper limbs. This system has two interfaces: the first, programmable in high-level, is intended for health professionals to prepare the motor training as needed by the patient; the second is the serious game interface, with which the patient interacts performing the series of activities planned in an exercise games (exergames). The purpose of this study is to provide a programmable rehabilitation platform according to the specific needs of each patient, keeping motivational and interactive features that provide fun activities to reduce evasion of treatments, which are usually carried out for long periods. Moreover, this study shows some tests, approved by the Ethics Committee, with volunteers, applying an exercise protocol to a group of healthy young and comparing the results with a group of elderly volunteers. The results of this study are obtained from two experimental setups: the first is internal to the session in real time, and concerns the scores of volunteers in the game; the second is external to the session, uses the data stored over a stabilometry and compare posturographic data between control and study group. Furthermore, in order to complement the assessments of the developed system, the posturographic data is compared to those obtainded from a commercial baropodometer. Results show that the system is able to perform the estimative of the stabilometry and serious game activities.

A tablatura é um formato de notação musical alternativo para instrumentos de corda. Ela contém a posição exata (corda e casa) que necessita ser tocada para produzir um som desejado. A conversão da notação musical padrão (partitura) para uma tablatura de violão, também conhecida como transcrição, não é um processo simplificado. A razão é que cada nota da notação musical padrão pode ser tocada em diferentes posições no braço do violão. Desta forma este problema pode ser classificada como um problema de otimização combinatório. Neste trabalho, foi empregado um estudo comparativo de diferentes algoritmos: A*, algoritmos genéticos (AG), algoritmos genéticos com uso de subpopulações (AG-SP), otimização por colônia de formigas (ACO), e evolução diferencial (ED). Heurísticas baseadas nas buscas locais 2-opt e 3-opt para as abordagens AG, AG-SP e ED também foram inclusas. Os resultados experimentais com um conjunto de dados de 87 músicas monofônicas demonstraram que os algoritmos ACO, AG-SP 2-opt e AG 2-opt apresentaram os melhores resultados. Por fim, cada abordagem foi estatisticamente comparada utilizando o teste ANOVA em conjunto com o pós-teste de Tukey (Tukey post hoc), onde as análises demonstraram que há diferenças significativas entre os algoritmos avaliados. / A tablature is an alternative music notation format for string instruments. It contains the exact position (string and fret) witch needs to be played to produce the desired sound. The conversion of the musical staff notation (sheet music) to a guitar tablature, also known as transcription, is not a straightforward process. The reason is that each note on the music notation format can be played in different positions of the guitar fretboard. So this problem can be classified as a combinatorial optimization problem. In this work, we have employed a comparative study of different algorithms: A*, genetic algorithms (AG), genetic algorithms with use of subpopulations (AG-SP), ant colony optimization (ACO) and differential evolution (ED). I was also included heuristics based on local search 2-opt and 3-opt in the aproaches AG, AG-SP and ED. The experimental results with a dataset of 87 monophonic musics indicated that the approaches ACO, AG-SP 2-opt and AG 2-opt obtained the best results. Finally, each approach were statistically compared using the ANOVA with the Tukey post hoc, where the analysis indicated that there are significant differences between the evaluated algorithms.

Neste trabalho propomos algoritmos para resolver uma formulação primal-dual geral de ponto fixo aplicada ao problema de Ridge Regression. Estudamos a formulação primal para problemas de quadrados mínimos regularizado, em especial na norma L2, nomeados Ridge Regression e descrevemos a dualidade convexa para essa classe de problemas. Nossa estratégia foi considerar as formulações primal e dual conjuntamente, e minimizar o gap de dualidade entre elas. Estabelecemos o algoritmo de ponto fixo primal-dual, nomeado SRP e uma reformulação para esse método, contribuição principal da tese, a qual mostrou-se mais eficaz e robusta, designada por método acc-SRP, ou versão acelerada do método SRP. O estudo teórico dos algoritmos foi feito por meio da análise de propriedades espectrais das matrizes de iteração associadas. Provamos a convergência linear dos algoritmos e apresentamos alguns exemplos numéricos comparando duas variantes para cada algoritmo proposto. Mostramos também que o nosso melhor método, acc-SRP, possui excelente desempenho numérico na resolução de problemas muito mal-condicionados quando comparado ao Método de Gradientes Conjugados, o que o torna computacionalmente mais atraente. / In this work we propose algorithms for solving a fixed-point general primal-dual formulation applied to the Ridge Regression problem. We study the primal formulation for regularized least squares problems, especially L2-norm, named Ridge Regression and then describe convex duality for that class of problems. Our strategy was to consider together primal and dual formulations and minimize the duality gap between them. We established the primal-dual fixed point algorithm, named SRP and a reformulation for this method, the main contribution of the thesis, which was more efficient and robust, called acc-SRP method or accelerated version of the SRP method. The theoretical study of the algorithms was done through the analysis of the spectral properties of the associated iteration matrices. We proved the linear convergence of algorithms and some numerical examples comparing two variants for each algorithm proposed were presented. We also showed that our best method, acc-SRP, has excellent numerical performance for solving very ill-conditioned problems, when compared to the conjugate gradient method, which makes it computationally more attractive.

O projeto de filtros digitais do tipo IIR é um problema clássico da engenharia. Filtros digitais possuem diversas aplicações, e muitas variantes de comportamento. Existem vários métodos especialistas consagrados na literatura, cada um com suas peculiaridades e adequações a diferentes casos. Porém, a maior parte destes métodos não é flexível, impedindo a especificação de todos os parâmetros importantes de um filtro, pois alguns desses são um sub-produto do processo de cálculo. Por isso, este problema também é atacado na literatura através de técnicas de computação evolucionária. Diversos estudos foram encontrados com esta abordagem, mas em quase todos, o enfoque era dado no algoritmo evolucionário em vez de no filtro, utilizando este apenas como uma função de \emph{benchmark}. Além disso, a estabilidade do filtro - condição imprescindível para a utilização do mesmo - é desprezada em quase todos os trabalhos. Portanto, este trabalho propõe uma função de \emph{fitness} e uma nova codificação para este problema, de forma a possibilitar a obtenção de bons filtros, dentro das especificações, com algoritmos de Computação Evolucionária na forma canônica, isto é, sem modificações estruturais. A função de \emph{fitness} proposta busca corrigir distorções causadas pela função tradicional, que não leva em conta a obediência às especificações do filtro. A codificação mapeia o espaço de busca apenas para as soluções estáveis, sem excluir nenhuma solução válida nesta transformação. Além disso, um pós-processamento permite equalizar a resposta em fase do filtro, isto é, tornar o atraso de fase na banda de passagem linear, condição necessária para a utilização em diversos sistemas, especialmente os de telecomunicações. O desempenho das modificações é comparado com as abordagens clássicas utilizadas na literatura, e o conjunto escolhido como o mais eficiente é utilizado para comparar os dois algoritmos mais utilizados em Computação Evolucionária, o PSO e o AG. Após esse passo, experimentos extensivos de ajuste de parâmetros foram realizados, para que a versão final fosse comparada com o método especialista mais poderoso, que é o cálculo de filtros elípticos. Os resultados mostraram que o conjunto de modificações proposto fez com que excelentes filtros fossem obtidos, com uma taxa de obediência às especificações muito superior à obtida sem o mesmo. Comparando com o método especialista, o desempenho foi semelhante, com pontos a favor e contra cada um, mostrando que o projeto de filtros IIR através de Computação Evolucionária pode ser utilizado em sistemas reais. Em trabalhos futuros poderão ser estudadas novas modificações na funçao de \emph{fitness}, além do desempenho obtido com outros algoritmos evolucionários. A utilização em sistemas \emph{online} é uma aplicação promissora, e o comportamento deste método com especificações não-estacionárias, oriundas de informações de estimação de canal também deve ser investigado. / IIR digital filter design is classic problem in Electrical Engineering. Digital filter have many applications, and dozens of different behaviors. There are many specialist methods in literature, each with specific differences and characteristics. But most of these methods are not flexible, preventing one from fixing all parameters, because some of them are a sub-product of the calculation process. Therefore, this problem is also solved in literature with Evolutionary Computing techniques. Several works were found with this approach, but in almost all, the focus was in the evolutionary algorithm rather than on the filter problem, using this only as a benchmark function. Moreover, the filter stability - prerequisite for the filter application - is neglected in almost all of them. So, this work proposes a new fitness function, as well as a new codification, in order to obtain good filters, obedient to the specifications, with Evolutionary Computing algorithms in the canonic form, this is, without structural modifications. The proposed fitness function tries to correct distortions caused by the traditional one, which does not takes into account the filter gain specifications. The new coding maps the search space only to the stable solutions, not excluding any valid solution in the transformation. Moreover, a post-processing allows the filter phase equalization, this is, to make the pass band phase delay linear. This property is necessary in many types of applications, specially the telecommunication ones. The modifications performance is compared to the classic approaches found in the literature, and the most efficient set is use to compare the two most used Evolutionary Computing algorithms, GA and PSO. After this, extensive parameter tuning experiments were made, producing a final version of the method to compare with the specialist one. The chosen specialist method was the Elliptic filter, because the filter response has similarities with the one found by the proposed algorithm, and also because it is the most powerful one. Results showed excellent filters found with the proposed modifications, with a specification obedience rate well above the ones obtained with the classical approaches. Comparing with the specialist method, a similar performance was achieved, showing that IIR filter design with Evolutionary Computing can be used in real systems. Future work will address new modifications in the fitness function, and the performance of different EC algorithms in this problem. The application in online systems is promising, so the behavior of this approach with non-stationary specifications coming from channel estimation techniques should also be investigated.

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.

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.

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.