ALGORITMOS de Estimação de Distribuição (EDAs) compõem uma frente de pesquisa em Computação Evolutiva que tem apresentado resultados promissores para lidar com problemas complexos de larga escala. Nesse contexto, destaca-se o Algoritmo de Otimização Bayesiano (BOA) que usa um modelo probabilístico multivariado (representado por uma rede Bayesiana) para gerar novas soluções a cada iteração. Baseado no BOA e na investigação de algoritmos de detecção de estrutura de comunidades (para melhorar os modelos multivariados construídos), propõe-se dois novos algoritmos denominados CD-BOA e StrOp. Mostra-se que ambos apresentam vantagens significativas em relação ao BOA. O CD-BOA mostra-se mais flexível que o BOA, ao apresentar uma maior robustez a variações dos valores de parâmetros de entrada, facilitando o tratamento de uma maior diversidade de problemas do mundo real. Diferentemente do CD-BOA e BOA, o StrOp mostra que a detecção de comunidades a partir de uma rede Bayesiana pode modelar mais adequadamente problemas decomponíveis, reestruturando-os em subproblemas mais simples, que podem ser resolvidos por uma busca gulosa, resultando em uma solução para o problema original que pode ser ótima no caso de problemas perfeitamente decomponíveis, ou uma aproximação, caso contrário. Também é proposta uma nova técnica de reamostragens para EDAs (denominada REDA). Essa técnica possibilita a obtenção de modelos probabilísticos mais representativos, aumentando significativamente o desempenho do CD-BOA e StrOp. De uma forma geral, é demonstrado que, para os casos testados, CD-BOA e StrOp necessitam de um menor tempo de execução do que o BOA. Tal comprovação é feita tanto experimentalmente quanto por análise das complexidades dos algoritmos. As características principais desses algoritmos são avaliadas para a resolução de diferentes problemas, mapeando assim suas contribuições para a área de Computação Evolutiva / ESTIMATION of Distribution Algorithms represent a research area which is showing promising results, especially in dealing with complex large scale problems. In this context, the Bayesian Optimization Algorithm (BOA) uses a multivariate model (represented by a Bayesian network) to find new solutions at each iteration. Based on BOA and in the study of community detection algorithms (to improve the constructed multivariate models), two new algorithms are proposed, named CD-BOA and StrOp. This paper indicates that both algorithms have significant advantages when compared to BOA. The CD-BOA is shown to be more flexible, being more robust when using different input parameters, what makes it easier to deal with a greater diversity of real-world problems. Unlike CD-BOA and BOA, StrOp shows that the detection of communities on a Bayesian network more adequately models decomposable problems, resulting in simpler subproblems that can be solved by a greedy search, resulting in a solution to the original problem which may be optimal in the case of perfectly decomposable problems, or a fair approximation if not. Another proposal is a new resampling technique for EDAs (called REDA). This technique results in multivariate models that are more representative, significantly improving the performance of CD-BOA and StrOp. In general, it is shown that, for the scenarios tested, CD-BOA and StrOp require lower running time than BOA. This indication is done experimentally and by the analysis of the computational complexity of the algorithms. The main features of these algorithms are evaluated for solving various problems, thus identifying their contributions to the field of Evolutionary Computation

ALGORITMOS de Estimação de Distribuição (EDAs) compõem uma frente de pesquisa em Computação Evolutiva que tem apresentado resultados promissores para lidar com problemas complexos de larga escala. Nesse contexto, destaca-se o Algoritmo de Otimização Bayesiano (BOA) que usa um modelo probabilístico multivariado (representado por uma rede Bayesiana) para gerar novas soluções a cada iteração. Baseado no BOA e na investigação de algoritmos de detecção de estrutura de comunidades (para melhorar os modelos multivariados construídos), propõe-se dois novos algoritmos denominados CD-BOA e StrOp. Mostra-se que ambos apresentam vantagens significativas em relação ao BOA. O CD-BOA mostra-se mais flexível que o BOA, ao apresentar uma maior robustez a variações dos valores de parâmetros de entrada, facilitando o tratamento de uma maior diversidade de problemas do mundo real. Diferentemente do CD-BOA e BOA, o StrOp mostra que a detecção de comunidades a partir de uma rede Bayesiana pode modelar mais adequadamente problemas decomponíveis, reestruturando-os em subproblemas mais simples, que podem ser resolvidos por uma busca gulosa, resultando em uma solução para o problema original que pode ser ótima no caso de problemas perfeitamente decomponíveis, ou uma aproximação, caso contrário. Também é proposta uma nova técnica de reamostragens para EDAs (denominada REDA). Essa técnica possibilita a obtenção de modelos probabilísticos mais representativos, aumentando significativamente o desempenho do CD-BOA e StrOp. De uma forma geral, é demonstrado que, para os casos testados, CD-BOA e StrOp necessitam de um menor tempo de execução do que o BOA. Tal comprovação é feita tanto experimentalmente quanto por análise das complexidades dos algoritmos. As características principais desses algoritmos são avaliadas para a resolução de diferentes problemas, mapeando assim suas contribuições para a área de Computação Evolutiva / ESTIMATION of Distribution Algorithms represent a research area which is showing promising results, especially in dealing with complex large scale problems. In this context, the Bayesian Optimization Algorithm (BOA) uses a multivariate model (represented by a Bayesian network) to find new solutions at each iteration. Based on BOA and in the study of community detection algorithms (to improve the constructed multivariate models), two new algorithms are proposed, named CD-BOA and StrOp. This paper indicates that both algorithms have significant advantages when compared to BOA. The CD-BOA is shown to be more flexible, being more robust when using different input parameters, what makes it easier to deal with a greater diversity of real-world problems. Unlike CD-BOA and BOA, StrOp shows that the detection of communities on a Bayesian network more adequately models decomposable problems, resulting in simpler subproblems that can be solved by a greedy search, resulting in a solution to the original problem which may be optimal in the case of perfectly decomposable problems, or a fair approximation if not. Another proposal is a new resampling technique for EDAs (called REDA). This technique results in multivariate models that are more representative, significantly improving the performance of CD-BOA and StrOp. In general, it is shown that, for the scenarios tested, CD-BOA and StrOp require lower running time than BOA. This indication is done experimentally and by the analysis of the computational complexity of the algorithms. The main features of these algorithms are evaluated for solving various problems, thus identifying their contributions to the field of Evolutionary Computation

Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. / Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

Vários problemas do mundo real podem ser modelados como problemas de otimização global, os quais são comuns em diversos campos da Engenharia e Ciência. Em geral, problemas complexos e de larga-escala não podem ser resolvidos de forma eficiente por técnicas determinísticas. Desse modo, algoritmos probabilísticos, como as metaheurísticas, têm sido amplamente empregados para otimização global. Duas das principais dificuldades nesses problemas são escapar de regiões sub-ótimas e evitar convergência prematura do algoritmo. À medida que a complexidade do problema aumenta, devido a um grande número de variáveis ou de regiões sub-ótimas, o tempo computacional torna-se grande e a possibilidade de que o algoritmo encontre o ótimo global diminui consideravelmente. Para solucionar esses problemas, propõe-se o uso de técnicas de aumento ou melhoria de eficiência. Com essas técnicas, buscase desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização global, ao invés de criar um novo algoritmo de otimização ou um algoritmo híbrido. No contexto de problemas contínuos, foram desenvolvidas técnicas para determinação de uma ou mais regiões promissoras do espaço de busca, que contenham uma grande quantidade de soluções de alta qualidade, com maior chance de conterem o ótimo global. Duas das principais técnicas propostas, o Algoritmo de Otimização de Domínio (DOA) e a arquitetura de Amostragem Inteligente (SS), foram testadas com sucesso significativo em vários problemas de otimização global utilizados para benchmark na literatura. A aplicação do DOA para metaheurísticas produziu melhoria de desempenho em 50% dos problemas testados. Por outro lado, a aplicação da SS produziu reduções de 80% da quantidade de avaliações da função objetivo, bem como aumentou a taxa de sucesso em encontrar o ótimo global. Em relação a problemas discretos (binários), foram abordados problemas nos quais existem correlações entre as variáveis, que devem ser identificadas por um modelo probabilístico. Das duas técnicas de aumento de eficiência propostas para esses problemas, a técnica denominada Gerenciamento do Tamanho da População (PSM) possibilita a construção de modelos probabilísticos mais representativos. Com o PSM foi possível atingir uma redução de cerca de 50% na quantidade de avaliações, mantendo a taxa de sucesso em 100%. Em resumo, as técnicas de aumento de eficiência propostas mostramse capazes de aumentar significativamente o desempenho de metaheurísticas, tanto para problemas contínuos quanto para discretos / Several real-world problems from various fields of Science and Engineering can be modeled as global optimization problems. In general, complex and large-scale problems can not be solved eficiently by exact techniques. In this context, Probabilistic algorithms, such as metaheuristics, have shown relevant results. Nevertheless, as the complexity of the problem increases, due to a large number of variables or several regions of the search space with sub-optimal solutions, the running time augments and the probability that the metaheuristics will find the global optimum is significantly reduced. To improve the performance of metaheuristics applied to these problems, new eficiency-enhancement techniques (EETs) are proposed in this thesis. These EETs can be applied to different types of global optimization algorithms, rather than creating a new or a hybrid optimization algorithm. For continuous problems, the proposed EETs are the Domain Optimization Algorithm (DOA) and the Smart Sampling (SS) architecture. In fact, they are pre-processing algorithms that determine one or more promising regions of the search-space, containing a large amount of high-quality solutions, with higher chance of containing the global optimum. The DOA and SS were tested with signicant success in several global optimization problems used as benchmark in the literature. The application of DOA to metaheuristics produced a performance improvement in 50% of problems tested. On the other hand, the application of SS have produced reductions of 80% of the evaluations of the objective function, as well as increased the success rate of finding the global optimum. For discrete problems (binary), we focused on metaheuristics that use probabilistic models to identify correlations among variables that are frequent in complex problems. The main EET proposed for discrete problems is called Population Size Management (PSM), which improves the probabilistic models constructed by such algorithms. The PSM produced a reduction of 50% of function evaluations maintaining the success rate of 100%. In summary, the results show that the proposed EETs can significantly increase the performance of metaheuristics for both discrete and continuous problems

Vários problemas do mundo real podem ser modelados como problemas de otimização global, os quais são comuns em diversos campos da Engenharia e Ciência. Em geral, problemas complexos e de larga-escala não podem ser resolvidos de forma eficiente por técnicas determinísticas. Desse modo, algoritmos probabilísticos, como as metaheurísticas, têm sido amplamente empregados para otimização global. Duas das principais dificuldades nesses problemas são escapar de regiões sub-ótimas e evitar convergência prematura do algoritmo. À medida que a complexidade do problema aumenta, devido a um grande número de variáveis ou de regiões sub-ótimas, o tempo computacional torna-se grande e a possibilidade de que o algoritmo encontre o ótimo global diminui consideravelmente. Para solucionar esses problemas, propõe-se o uso de técnicas de aumento ou melhoria de eficiência. Com essas técnicas, buscase desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização global, ao invés de criar um novo algoritmo de otimização ou um algoritmo híbrido. No contexto de problemas contínuos, foram desenvolvidas técnicas para determinação de uma ou mais regiões promissoras do espaço de busca, que contenham uma grande quantidade de soluções de alta qualidade, com maior chance de conterem o ótimo global. Duas das principais técnicas propostas, o Algoritmo de Otimização de Domínio (DOA) e a arquitetura de Amostragem Inteligente (SS), foram testadas com sucesso significativo em vários problemas de otimização global utilizados para benchmark na literatura. A aplicação do DOA para metaheurísticas produziu melhoria de desempenho em 50% dos problemas testados. Por outro lado, a aplicação da SS produziu reduções de 80% da quantidade de avaliações da função objetivo, bem como aumentou a taxa de sucesso em encontrar o ótimo global. Em relação a problemas discretos (binários), foram abordados problemas nos quais existem correlações entre as variáveis, que devem ser identificadas por um modelo probabilístico. Das duas técnicas de aumento de eficiência propostas para esses problemas, a técnica denominada Gerenciamento do Tamanho da População (PSM) possibilita a construção de modelos probabilísticos mais representativos. Com o PSM foi possível atingir uma redução de cerca de 50% na quantidade de avaliações, mantendo a taxa de sucesso em 100%. Em resumo, as técnicas de aumento de eficiência propostas mostramse capazes de aumentar significativamente o desempenho de metaheurísticas, tanto para problemas contínuos quanto para discretos / Several real-world problems from various fields of Science and Engineering can be modeled as global optimization problems. In general, complex and large-scale problems can not be solved eficiently by exact techniques. In this context, Probabilistic algorithms, such as metaheuristics, have shown relevant results. Nevertheless, as the complexity of the problem increases, due to a large number of variables or several regions of the search space with sub-optimal solutions, the running time augments and the probability that the metaheuristics will find the global optimum is significantly reduced. To improve the performance of metaheuristics applied to these problems, new eficiency-enhancement techniques (EETs) are proposed in this thesis. These EETs can be applied to different types of global optimization algorithms, rather than creating a new or a hybrid optimization algorithm. For continuous problems, the proposed EETs are the Domain Optimization Algorithm (DOA) and the Smart Sampling (SS) architecture. In fact, they are pre-processing algorithms that determine one or more promising regions of the search-space, containing a large amount of high-quality solutions, with higher chance of containing the global optimum. The DOA and SS were tested with signicant success in several global optimization problems used as benchmark in the literature. The application of DOA to metaheuristics produced a performance improvement in 50% of problems tested. On the other hand, the application of SS have produced reductions of 80% of the evaluations of the objective function, as well as increased the success rate of finding the global optimum. For discrete problems (binary), we focused on metaheuristics that use probabilistic models to identify correlations among variables that are frequent in complex problems. The main EET proposed for discrete problems is called Population Size Management (PSM), which improves the probabilistic models constructed by such algorithms. The PSM produced a reduction of 50% of function evaluations maintaining the success rate of 100%. In summary, the results show that the proposed EETs can significantly increase the performance of metaheuristics for both discrete and continuous problems

Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. / Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

As proteínas são moléculas que desempenham funções essenciais para a vida. Para entender a função de uma proteína é preciso conhecer sua estrutura tridimensional. No entanto, encontrar a estrutura da proteína pode ser um processo caro e demorado, exigindo profissionais altamente qualificados. Neste sentido, métodos computacionais têm sido investigados buscando predizer a estrutura de uma proteína a partir de uma sequência de aminoácidos. Em geral, tais métodos computacionais utilizam conhecimentos de estruturas de proteínas já determinadas por métodos experimentais, para tentar predizer proteínas com estrutura desconhecida. Embora métodos computacionais como, por exemplo, o Rosetta, I-Tasser e Quark tenham apresentado sucesso em suas predições, são apenas capazes de produzir estruturas significativamente semelhantes às já determinadas experimentalmente. Com isso, por utilizarem conhecimento a priori de outras estruturas pode haver certa tendência em suas predições. Buscando elaborar um algoritmo eficiente para Predição de Estruturas de Proteínas livre de tendência foi desenvolvido um Algoritmo de Estimação de Distribuição (EDA) específico para esse problema, com modelagens full-atom e algoritmos ab initio. O fato do algoritmo proposto ser ab initio é mais interessante para aplicação envolvendo proteínas com baixa similaridade, com relação às estruturas já conhecidas. Três tipos de modelos probabilísticos foram desenvolvidos: univariado, bivariado e hierárquico. O univariado trata o aspecto de multi-modalidade de uma variável, o bivariado trata os ângulos diedrais (Φ Ψ) de um mesmo aminoácido como variáveis correlacionadas. O hierárquico divide o problema em subproblemas e tenta tratá-los separadamente. Os resultados desta pesquisa mostraram que é possível obter melhores resultados quando considerado a relação bivariada (Φ Ψ). O hierárquico também mostrou melhorias nos resultados obtidos, principalmente para proteínas com mais de 50 resíduos. Além disso, foi realiza uma comparação com algumas heurísticas da literatura, como: Busca Aleatória, Monte Carlo, Algoritmo Genético e Evolução Diferencial. Os resultados mostraram que mesmo uma metaheurística pouco eficiente, como a Busca Aleatória, pode encontrar a solução correta, porém utilizando muito conhecimento a priori (predição que pode ser tendenciosa). Por outro lado, o algoritmo proposto neste trabalho foi capaz de obter a estrutura da proteína esperada sem utilizar conhecimento a priori, caracterizando uma predição puramente ab initio (livre de tendência). / Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Φ Ψ) within an amino acid as correlated variables. The hierarchical approach splits the original problem into subproblems and attempts to treat these problems in a separated manner. The experiments show that, indeed, it is possible to achieve better results when modeling the correlation (Φ Ψ). The hierarchical model also showed that is possible to improve the quality of results, mainly for proteins above 50 residues. Besides, we compared our proposed techniques among other metaheuristics from literatures such as: Random Walk, Monte Carlo, Genetic Algorithm and Differential Evolution. The results show that even a less efficient metaheuristic such as Random Walk managed to find the correct structure, however using many prior knowledge (prediction that may be biased). On the other hand, our proposed EDA for PSP was able to find the correct structure with no prior knowledge at all, so we can call this prediction as pure ab initio (biased-free).

In robotic rehabilitation therapies, knowledge of human joint torques is important for patient safety, to provide a reliable data for clinical assessment and to increase control performance of the device, nevertheless, its measurement can be complex or have a highcost implementation. The most of techniques for torque estimation have been developed for upper limb robotic rehabilitation devices, in addition, they typically require detailed anthropometric and musculoskeletal models. In this dissertation is presented the ankle torque estimation for the Anklebot robot, the estimation uses an ankle/Anklebot dynamic model that consider the ankle joint angular displacement and velocity measurement, its mechanical impedance parameters are obtained through a second-order modeled mechanical impedance of the ankle and an identification of frictional and gravitational torques. Three approaches for the ankle torque estimation were proposed to be implemented in the Anklebot robot, the Generalized Momentum, the Kalman filter and finally a combination of both the above mentioned approaches. The validation of such approaches was developed first on a physical mockup configured to reproduce the human ankle joint movement, by assessing its performances, the Kalman filter approach was selected to be implemented on a voluntary subject. A set of experiments were performed considering the physical activity that the subject may realize when interacting with the Anklebot, the developed ankle torque estimation proved to be successful for passive torque and in most of the proposed scenarios where active torque is performed. / Em terapias de reabilitação robótica, o conhecimento dos torques da articulação humana é importante para a segurança do paciente, para fornecer dados confiáveis na avaliação clínica e aumentar o desempenho de controle do dispositivo, no entanto, sua medição pode ser complexa ou costoso de implementar. A maioria das técnicas de estimativa de torque tem sido desenvolvidas para dispositivos de reabilitação robótica de membros superiores, além disso, eles normalmente requerem modelos antropométricos e musculoesqueléticos detalhados. Nesta dissertação é apresentada a estimativa do torque do tornozelo no robô Anklebot, a estimação utiliza um modelo dinâmico tornozelo + Anklebot o qual considera a medição da posição e velocidade angular do tornozelo, os parametros de impedancia mecânica do tornozelo são obtidos por meio de um modelo simples de segunda ordem e são identificados os torques gravitacionais e de atrito. Três abordagens para a estimativa de torque de tornozelo foram propostas para serem implementadas, o momento generalizado, o filtro de Kalman e, finalmente, uma abordagem que combina tanto o momento generalizado e o filtro de Kalman. A validação de tais abordagens foi desenvolvida primeiro em um mock-up físico configurado para reproduzir o movimento articular do tornozelo humano, avaliando seus desempenhos. A segunda abordagem proposta foi selecionada para ser implementada em um usuário voluntário. Um conjunto de experimentos foi realizado considerando a atividade física que o sujeito pode realizar ao interagir com o Anklebot, a estimativa desenvolvida de torque de tornozelo demostrou ser bem sucedida para o torque passivo e na maioria dos cenários propostos onde o torque ativo é realizado.

In robotic rehabilitation therapies, knowledge of human joint torques is important for patient safety, to provide a reliable data for clinical assessment and to increase control performance of the device, nevertheless, its measurement can be complex or have a highcost implementation. The most of techniques for torque estimation have been developed for upper limb robotic rehabilitation devices, in addition, they typically require detailed anthropometric and musculoskeletal models. In this dissertation is presented the ankle torque estimation for the Anklebot robot, the estimation uses an ankle/Anklebot dynamic model that consider the ankle joint angular displacement and velocity measurement, its mechanical impedance parameters are obtained through a second-order modeled mechanical impedance of the ankle and an identification of frictional and gravitational torques. Three approaches for the ankle torque estimation were proposed to be implemented in the Anklebot robot, the Generalized Momentum, the Kalman filter and finally a combination of both the above mentioned approaches. The validation of such approaches was developed first on a physical mockup configured to reproduce the human ankle joint movement, by assessing its performances, the Kalman filter approach was selected to be implemented on a voluntary subject. A set of experiments were performed considering the physical activity that the subject may realize when interacting with the Anklebot, the developed ankle torque estimation proved to be successful for passive torque and in most of the proposed scenarios where active torque is performed. / Em terapias de reabilitação robótica, o conhecimento dos torques da articulação humana é importante para a segurança do paciente, para fornecer dados confiáveis na avaliação clínica e aumentar o desempenho de controle do dispositivo, no entanto, sua medição pode ser complexa ou costoso de implementar. A maioria das técnicas de estimativa de torque tem sido desenvolvidas para dispositivos de reabilitação robótica de membros superiores, além disso, eles normalmente requerem modelos antropométricos e musculoesqueléticos detalhados. Nesta dissertação é apresentada a estimativa do torque do tornozelo no robô Anklebot, a estimação utiliza um modelo dinâmico tornozelo + Anklebot o qual considera a medição da posição e velocidade angular do tornozelo, os parametros de impedancia mecânica do tornozelo são obtidos por meio de um modelo simples de segunda ordem e são identificados os torques gravitacionais e de atrito. Três abordagens para a estimativa de torque de tornozelo foram propostas para serem implementadas, o momento generalizado, o filtro de Kalman e, finalmente, uma abordagem que combina tanto o momento generalizado e o filtro de Kalman. A validação de tais abordagens foi desenvolvida primeiro em um mock-up físico configurado para reproduzir o movimento articular do tornozelo humano, avaliando seus desempenhos. A segunda abordagem proposta foi selecionada para ser implementada em um usuário voluntário. Um conjunto de experimentos foi realizado considerando a atividade física que o sujeito pode realizar ao interagir com o Anklebot, a estimativa desenvolvida de torque de tornozelo demostrou ser bem sucedida para o torque passivo e na maioria dos cenários propostos onde o torque ativo é realizado.

As proteínas são moléculas que desempenham funções essenciais para a vida. Para entender a função de uma proteína é preciso conhecer sua estrutura tridimensional. No entanto, encontrar a estrutura da proteína pode ser um processo caro e demorado, exigindo profissionais altamente qualificados. Neste sentido, métodos computacionais têm sido investigados buscando predizer a estrutura de uma proteína a partir de uma sequência de aminoácidos. Em geral, tais métodos computacionais utilizam conhecimentos de estruturas de proteínas já determinadas por métodos experimentais, para tentar predizer proteínas com estrutura desconhecida. Embora métodos computacionais como, por exemplo, o Rosetta, I-Tasser e Quark tenham apresentado sucesso em suas predições, são apenas capazes de produzir estruturas significativamente semelhantes às já determinadas experimentalmente. Com isso, por utilizarem conhecimento a priori de outras estruturas pode haver certa tendência em suas predições. Buscando elaborar um algoritmo eficiente para Predição de Estruturas de Proteínas livre de tendência foi desenvolvido um Algoritmo de Estimação de Distribuição (EDA) específico para esse problema, com modelagens full-atom e algoritmos ab initio. O fato do algoritmo proposto ser ab initio é mais interessante para aplicação envolvendo proteínas com baixa similaridade, com relação às estruturas já conhecidas. Três tipos de modelos probabilísticos foram desenvolvidos: univariado, bivariado e hierárquico. O univariado trata o aspecto de multi-modalidade de uma variável, o bivariado trata os ângulos diedrais (Φ Ψ) de um mesmo aminoácido como variáveis correlacionadas. O hierárquico divide o problema em subproblemas e tenta tratá-los separadamente. Os resultados desta pesquisa mostraram que é possível obter melhores resultados quando considerado a relação bivariada (Φ Ψ). O hierárquico também mostrou melhorias nos resultados obtidos, principalmente para proteínas com mais de 50 resíduos. Além disso, foi realiza uma comparação com algumas heurísticas da literatura, como: Busca Aleatória, Monte Carlo, Algoritmo Genético e Evolução Diferencial. Os resultados mostraram que mesmo uma metaheurística pouco eficiente, como a Busca Aleatória, pode encontrar a solução correta, porém utilizando muito conhecimento a priori (predição que pode ser tendenciosa). Por outro lado, o algoritmo proposto neste trabalho foi capaz de obter a estrutura da proteína esperada sem utilizar conhecimento a priori, caracterizando uma predição puramente ab initio (livre de tendência). / Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Φ Ψ) within an amino acid as correlated variables. The hierarchical approach splits the original problem into subproblems and attempts to treat these problems in a separated manner. The experiments show that, indeed, it is possible to achieve better results when modeling the correlation (Φ Ψ). The hierarchical model also showed that is possible to improve the quality of results, mainly for proteins above 50 residues. Besides, we compared our proposed techniques among other metaheuristics from literatures such as: Random Walk, Monte Carlo, Genetic Algorithm and Differential Evolution. The results show that even a less efficient metaheuristic such as Random Walk managed to find the correct structure, however using many prior knowledge (prediction that may be biased). On the other hand, our proposed EDA for PSP was able to find the correct structure with no prior knowledge at all, so we can call this prediction as pure ab initio (biased-free).