Spelling suggestions: "subject:" evolutionary computational"" "subject:" mvolutionary computational""
181 |
Projeto de filtros digitais IIR com técnicas de computação evolucionáriaOliveira, Daniel Rossato de 06 December 2012 (has links)
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.
|
182 |
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.
|
183 |
Adaptive behaviour in evolving robotsTyska Carvalho, Jônata January 2017 (has links)
In this thesis, the evolution of adaptive behaviour in artificial agents is studied. More specifically, two types of adaptive behaviours are studied: articulated and cognitive ones. Chapter 1 presents a general introduction together with a brief presentation of the research area of this thesis, its main goals and a brief overview of the experimental studies done, the results and conclusions obtained. On chapter 2, I briefly present some promising methods that automatically generate robot controllers and/or body plans and potentially could help in the development of adaptive robots. Among these methods I present in details evolutionary robotics, a method inspired on natural evolution, and the biological background regarding adaptive behaviours in biological organisms, which provided inspiration for the studies presented in this thesis. On chapter 3, I present a detailed study regarding the evolution of articulated behaviours, i.e., behaviours that are organized in functional sub-parts, and that are combined and used in a sequential and context-dependent way, regardless if there is a structural division in the robot controller or not. The experiments performed with a single goal task, a cleaning task, showed that it is possible to evolve articulated behaviours even in this condition and without structural division of the robot controller. Also the analysis of the results showed that this type of integrated modular behaviours brought performance advantages compared to structural divided controllers. Analysis of robots' behaviours helped to clarify that the evolution of this type of behaviour depended on the characteristics of the neural network controllers and the robot's sensorimotor capacities, that in turn defined the capacity of the robot to generate opportunity for actions, which in psychological literature is often called affordances. In chapter 4, a study seeking to understand the role of reactive strategies in the evolution of cognitive solutions, i.e. those capable of integrating information over time encoding it on internal states that will regulate the robot's behaviour in the future, is presented. More specifically I tried to understand whether the existence of sub-optimal reactive strategies prevent the development of cognitive solutions, or they can promote the evolution of solutions capable of combining reactive strategies and the use of internal information for solving a response delayed task, the double t-maze. The results obtained showed that reactive strategies capable of offloading cognitive work to the agent/environmental relation can promote, rather than prevent the evolution of solutions relying on internal information. The analysis of these results clarified how these two mechanisms interact producing a hybrid superior and robust solution for the delayed response task.
|
184 |
[en] NONCONVEX FUNCTIONS OPTIMIZATION USING AN ESTIMATION OF DISTRIBUTION ALGORITHM BASED ON MULTIVARIATE COPULAS / [pt] OTIMIZAÇÃO DE FUNÇÕES NÃO CONVEXAS UTILIZANDO UM ALGORITMO DE ESTIMAÇÃO DE DISTRIBUIÇÃO BASEADO EM CÓPULAS MULTIVARIADASHAROLD DIAS DE MELLO JUNIOR 12 January 2016 (has links)
[pt] Algoritmos de estimação de distribuição (EDAs – Estimation of Distribution Algorithms) são uma classe de algoritmos evolutivos capazes de extrair e utilizar conhecimento ao longo do processo de busca. O passo mais importante e um gargalo, que estabelece diferenciação entre esses algoritmos, é a estimação da distribuição de probabilidade conjunta das soluções mais promissoras determinadas pela função de avaliação. Recentemente, uma nova abordagem baseada em teoria das cópulas foi desenvolvida. Este trabalho apresenta um algoritmo de estimação baseado em cópulas para problemas de otimização numérica. Este modelo implementa um EDA através da expansão multivariada de cópulas (EDA-MEC – Estimation of Distribution Algorithm based on Multivariate Extension of Copulas) para estimar a distribuição de probabilidade da qual é gerada uma população de indivíduos. O EDA-MEC difere de outros EDAs baseados em cópulas em alguns aspectos: o parâmetro de cópula é estimado de forma dinâmica, através de medidas de dependência; utiliza uma variação da distribuição de probabilidade aprendida para gerar indivíduos que ajudam a evitar a convergência prematura; e utiliza uma heurística para reinicializar a população ao longo da evolução elitista como uma técnica adicional para tentar preservar a diversidade de soluções. Após um conjunto de testes de parâmetros, inclusive das distribuições marginais, este trabalho mostra que estas abordagens melhoram o desempenho global da otimização comparativamente a outros EDAs baseados em cópulas, com a perspectiva promissora de ser um algoritmo competitivo frente a outras heurísticas comprovadamente eficientes, tais como a Estratégia Evolutiva com Adaptação da Matriz de Covariância (CMA-ES - Covariance Matrix Adaptation Evolution Strategy). / [en] Estimation of distribution algorithms constitute a class of evolutionary algorithms that can extract and use knowledge acquired throughout the search process. Its most important step that differs most among EDAs, and also a bottleneck, is the estimation of the joint probability distribution associated with the variables from the most promising solutions determined by the evaluation function. Recently, a new approach to EDAs has been developed that is based on copula theory. This work presents a copula-based estimation of distribution algorithm for numeric optimization problems. This model implements an estimation of distribution algorithm using a Multivariate Extension of Copulas (EDA-MEC) to estimate the probability distribution for generating a population of individuals. EDA-MEC differs from other copula-based EDAs in some aspects: the copula parameter is estimated dynamically, using dependency measures; it uses a variation of the learned probability distribution to generate individuals that help to avoid premature convergence; and it uses a heuristic to reinitialize the population throughout an elitist evolution as an additional technique to try to preserve the diversity of solutions. After a set of parametric tests, including marginal distributions, this work shows that these approaches improve the overall performance of the optimization compared to other copula-based EDAs and promises to be a competitive algorithm compared to other efficient heuristics, such as Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
|
185 |
[en] DEVELOPMENT OF UNIMODAL AND MULTIMODAL OPTIMIZATION ALGORITHMS BASED ON MULTI-GENE GENETIC PROGRAMMING / [pt] DESENVOLVIMENTO DE ALGORITMOS DE OTIMIZAÇÃO UNIMODAL E MULTIMODAL COM BASE EM PROGRAMAÇÃO GENÉTICA MULTIGÊNICAROGERIO CORTEZ BRITO LEITE POVOA 29 August 2018 (has links)
[pt] As técnicas de programação genética permitem flexibilidade no processo de otimização, possibilitando sua aplicação em diferentes áreas do conhecimento e fornecendo novas maneiras para que especialistas avancem em suas áreas com mais rapidez. Parameter mapping approach é um método de otimização
numérica que utiliza a programação genética para mapear valores iniciais em parâmetros ótimos para um sistema. Embora esta abordagem produza bons resultados para problemas com soluções triviais, o uso de grandes equações/árvores pode ser necessário para tornar este mapeamento apropriado em sistemas mais complexos.A fim de aumentar a flexibilidade e aplicabilidade do método a sistemas de diferentes níveis de complexidade, este trabalho introduz uma generalização utilizando a programação genética multigênica, para realizar um mapeamento multivariado, evitando grandes estruturas complexas. Foram considerados três conjuntos de funções de benchmark, variando em complexidade e dimensionalidade. Análises estatísticas foram realizadas, sugerindo que este novo método é mais flexível e mais eficiente (em média), considerando funções de benchmark complexas e de grande dimensionalidade. Esta tese também apresenta uma abordagem do novo algoritmo para otimização numérica multimodal.Este segundo algoritmo utiliza algumas técnicas de niching, baseadas no procedimento chamado de clearing, para manter a diversidade da população. Um conjunto benchmark de funções multimodais, com diferentes características e níveis de dificuldade,foi utilizado para avaliar esse novo algoritmo. A análise estatística sugeriu que esse novo método multimodal, que também utiliza programação genética multigênica,pode ser aplicado para problemas que requerem mais do que uma única solução. Como forma de testar esses métodos em problemas do mundo real, uma aplicação em nanotecnologia é proposta nesta tese: ao timização estrutural de fotodetectores de infravermelho de poços quânticos a partir de uma energia desejada. Os resultados apresentam novas estruturas melhores do que as conhecidas na literatura (melhoria de 59,09 por cento). / [en] Genetic programming techniques allow flexibility in the optimization process, making it possible to use them in different areas of knowledge and providing new ways for specialists to advance in their areas more quickly and more accurately.Parameter mapping approach is a numerical optimization method that uses genetic programming to find an appropriate mapping scheme among initial guesses to optimal parameters for a system. Although this approach yields good results for problems with trivial solutions, the use of
large equations/trees may be required to make this mapping appropriate for more complex systems.In order to increase the flexibility and applicability of the method to systems of different levels of complexity, this thesis introduces a generalization by thus using multi-gene genetic programming to perform a multivariate mapping, avoiding large complex structures.Three sets of benchmark functions, varying in complexity and dimensionality, were considered. Statistical analyses carried out suggest that this new method is more flexible and performs better on average, considering challenging benchmark functions of increasing dimensionality.This thesis also presents an improvement of this new method for multimodal numerical optimization.This second algorithm uses some niching techniques based on the clearing procedure to maintain the population diversity. A multimodal benchmark set with different characteristics and difficulty levels to evaluate this new algorithm is used. Statistical analysis suggested that this new multimodal method using multi-gene genetic programming can be used for problems that requires more than a single solution. As a way of testing real-world problems for these methods, one application in nanotechnology is proposed in this thesis: the structural optimization of quantum well infrared photodetector from a desired energy.The results present new structures better than those known in the literature with improvement of 59.09 percent.
|
186 |
Especificação e implementação de um sistema evolutivo de apoio à análise de demonstrações contábeis SEADC para fins de tomada de decisão / Specification and implementation of a evolutionary system to support financial statement analysis - ESAAS for decision makingNeves, Cleonábula Maria Maranhão 03 July 2012 (has links)
This paper describes the specification and implementation of a computational system entitled Evolutionary Support System for the Analysis of Accounting Statements (ESAAS), which aims to optimize decision making, and uses variations of the genetic algorithm from Holland. In its specification, there is a population formed by chromosomes that are vectors over a ternary alphabet with size corresponding to the number of account statements contained in the type of analysis chosen by the user. The ESAAS diagnoses the financial and economic situation of commercial, industrial companies or service providers, whether they are classified as micro, small, average, average-large or large companies. The diagnosis done by ESAAS was based on the analyzes of liquidity, debt profitability, added value, average terms, vertical and horizontal analyzes; and in the diagnosis of the analytical combination of liquidity, profitability and debt with the vertical analysis, showing as a justification, the influence of each of the accounts or group of financial accounts involved. The system receives as input a set of indexes, total values of the accounts or groups of accounts of financial accounting standards of the company that will be considered in a determinted period, consisting of consecutive years, being considered the minimum of three years. To validate the ESAAS, tests were performed with data obtained from the financial statements from companies in the years 2008, 2009 and 2010. The system was implemented in the eclipse compiler, using the JAVA programming language. The results achieved in the calculation of the quotients obtained in all the seven types of analyzes performed achieved 100% of correctness. Therefore concluding that the ESAAS infers knowledge to decision-making, through diagnostic reports generated. / Este trabalho descreve a especificação e a implementação de um sistema computacional, intitulado de Sistema Evolutivo de Apoio à Análise de Demonstrações Contábeis (SEADC), que visa otimizar a tomada de decisão, e utiliza variações do algoritmo genético de Holland. Possui em sua especificação uma população formada por cromossomos que são vetores sobre um alfabeto ternário, com tamanho correspondente ao número de contas contábeis contidas no tipo de análise escolhida pelo usuário. O SEADC faz o diagnóstico da situação financeira e econômica de empresas comerciais, industriais ou prestadoras de serviço, sejam elas classificadas como micro, pequena, média, média-grande ou grande empresa. O diagnóstico realizado pelo SEADC foi baseado nas análises de liquidez, endividamento, rentabilidade, valor adicionado, prazos médios, análises vertical e horizontal; e no diagnóstico da combinação das análises de liquidez, rentabilidade e endividamento com a análise vertical, mostrando, como justificativa, a influência de cada uma das contas ou grupo de contas contábeis envolvidos. O sistema recebe como entrada um conjunto de índices, valores dos saldos das contas ou grupos de contas contábeis de demonstrações padronizadas da empresa que será analisada, em um determinado período, composto por anos consecutivos, sendo considerado o mínimo de três anos. Para validar o SEADC foram realizados testes com dados obtidos de demonstrações contábeis de empresas nos anos de 2008, 2009 e 2010. O sistema foi implementado no compilador eclipse, usando-se linguagem de programação JAVA. Os resultados alcançados no cálculo dos quocientes obtidos em todos os sete tipos de análises realizadas alcançaram 100% de corretude. Conclui-se, portanto, que o SEADC infere conhecimento à tomada de decisão, através dos relatórios de diagnósticos gerados.
|
187 |
[en] QUANTUM-INSPIRED EVOLUCIONARY ALGORITHM WITH MIXED REPRESENTATION APPLIED TO NEURO-EVOLUTION / [pt] ALGORITMO EVOLUCIONÁRIO COM INSPIRAÇÃO QUÂNTICA E REPRESENTAÇÃO MISTA APLICADO A NEUROEVOLUÇÃOANDERSON GUIMARAES DE PINHO 06 April 2011 (has links)
[pt] Esta dissertação objetivará a unificação de duas metodologias de algoritmos
evolutivos consagradas para tratamento de problemas ou do tipo combinatórios,
ou do tipo numéricos, num único algoritmo com representação mista. Trata-se de
um algoritmo evolutivo inspirado na física quântica com representação mista
binário-real do espaço de soluções, o AEIQ-BR. Este algoritmo trata-se de uma
extensão do modelo com representação binária de Jang, Han e Kin, o AEIQ-B
para otimizações combinatoriais, e o de representação real de Abs da Cruz, o
AEIQ-R para otimizações numéricas. Com fins de exemplificação do novo
algoritmo proposto, o discutiremos no contexto de neuroevolução, com o
propósito de configurar completamente uma rede neural com alimentação adiante
em termos: seleção de variáveis de entrada; números de neurônios na camada
escondida; todos os pesos existentes; e tipos de funções de ativação de cada
neurônio. Esta finalidade em se aplicar o algoritmo AEIQ-BR à neuroevolução – e
também, numa analogia ao modelo NEIQ-R de Abs da Cruz – receberá a
denominação NEIQ-BR. N de neuroevolução, E de evolutivo, IQ de inspiração
quântica, e BR de binário-real. Para avaliar o desempenho do NEIQ-BR, utilizarse-
á um total de seis casos benchmark de classificação, e outros dois casos reais,
em campos da ciência como: finanças, biologia e química. Resultados serão
comparados com algoritmos de outros pesquisadores e a modelagem manual de
redes neurais, através de medidas de desempenho. Através de testes estatísticos
concluiremos que o algoritmo NEIQ-BR apresentará um desempenho
significativo na obtenção de previsões de classificação por neuroevolução. / [en] This work aimed to unify two methodologies of evolutionary algorithms to
treat problems with or combinatorial characteristics, or numeric, on a unique
algorithm with mix representation. It is an evolutionary algorithm inspired in
quantum physics with mixed representation of the solutions space, called QIEABR.
This algorithm is an extension of the model with binary representation of the
chromosome from Jang, Han e Kin, the QIEA-B for combinatorial optimization,
and numeric representation from Abs da Cruz, the QIEA-R for numerical
optimizations. For purposes of exemplification of the new algorithm, we will
introduce the algorithm in the context of neuro-evolution, in order to completely
configure a feed forward neural network in terms of: selection of input variables;
numbers of neurons in the hidden layer; all existing synaptic weights; and types of
activation functions of each neuron. This purpose when applying the algorithm
QIEA-BR to neuro-evolution receive the designation of QIEN-BR. QI for
quantum-inspired, E for evolutive, N for neuro-evolution, and BR for binary-real
representation. To evaluate the performance of QIEN-BR, we will use a total of
six benchmark cases of classification, and two real cases in fields of science such
as finance, biology and chemistry. Results will be compared with algorithms of
other researchers and manual modeling of neural networks through performance
measures. Statistical tests will be provided to elucidate the significance of results,
and what we can conclude is that the algorithm QIEN-BR better performance
others researchers in terms of classification prediction.
|
188 |
Algoritmo de evolução diferencial paralelo aplicado ao problema da predição da estrutura de proteínas utilizando o modelo AB em 2D e 3DKalegari, Diego Humberto 18 October 2010 (has links)
O problema da predição da estrutura de proteínas (PPEP) é bastante conhecido na bioinformática. A identificação da conformação nativa de uma proteína permite predizer a sua função no organismo. Este conhecimento também é útil no desenvolvimento de novos fármacos ou na compreensão do mecanismo de várias doenças. Várias técnicas tem sido propostas para resolver este problema. Porém, o alto custo envolvido levou ao surgimento de vários modelos que simplificam, em parte, as estruturas protéicas. No entanto, mesmo com os modelos mais simplificados, a complexidade do problema traz inúmeros desafios computacionais na busca da sua conformação nativa. Este trabalho utiliza o algoritmo evolucionário denominado Evolução Diferenciada (ED) para solucionar o PPEP, representando as proteínas com o modelo AB (toy model), em duas e três dimensões (2D e 3D). O trabalho apresenta a implementação de duas versões da ED, paralelizadas num ambiente de processo em cluster, com Message Passing Interface e arquitetura mestre-escravo. Para a configuração dos operadores do algoritmo de ED, foram realizados vários estudos com diferentes configurações para ambos os modelos, e análises estatísticas determinaram quais os melhores valores. Além disso, foram criados dois operadores especiais: dizimação e mutação espelhada. O primeiro poder ser considerado um operador genérico, que pode ser utilizado em qualquer problema; o segundo é específico para o problema em questão. Além do algoritmo de ED básico, também foi proposta uma versão auto-adaptável, em que alguns de seus parâmetros são atualizados no decorrer da evolução. Os experimentos realizados utilizaram 4 sequências de aminoácidos de benchmark geradas a partir da sequência de Fibonacci, contendo entre 13 e 55 aminoácidos. Os resultados dos algoritmos de ED paralelos foram comparados com os resultados obtidos em outros trabalhos. O algoritmo de ED é capaz de obter resultados excelentes, competitivos com os métodos especializados, apesar de não atingir o ótimo conhecido em algumas instâncias. Os resultados promissores obtidos nesse trabalho mostram que o algoritmo de ED é adequado para o problema. Em trabalhos futuros poderão ser estudados novos operadores especiais ou outras técnicas de inspiração biológica, buscando melhorar os resultados. / Protein structure prediction is a well-known problem in bioinformactis. Identifying protein native conformation makes it possible to predict its function within the organism. Knowing this also helps in the development of new medicines and in comprehending how some illnesses work and act. During the past year some techniques have been proposed to solve this problem, but its high cost made it necessary to build models that simplify the protein structures. However, even with the simplicity of these models identifying the protein native conformation remains a highly complex, computationally challenging problem. This paper uses an evolutionary algorithm known as Differential Evolution (DE) to solve the protein structure prediction problem. The model used to represent the protein structure is the Toy Model (also known as the AB Model) in both 2D and 3D. This work implements two versions of the ED algorithm using a parallel architecture (master-slave) based on Message Passing interface in a cluster. A large number of tests were executed to define the final configuration of the DE operators for both models. A new set of special operators were developed: explosion and mirror mutation. We can consider the first as generic, because it can be used in any problem. The second one is more specific because it requires previous knowledge of the problem. Of the two DE algorithm implemented, one is a basic DE algorithm and the second is a self-adaptive DE. All tests executed in this work used four benchmark amino acid sequences generated from the Fibonacci sequence. Each sequence has 13 to 55 amino acids. The results for both parallel DE algorithms using both 2D and 3D models were compared with other works. The DE algorithm achieved excellent results. It did not achieve the optimal known values for some sequences, but it was competitive with other specialized methods. Overall results encourage further research toward the use of knowledge-based operators and biologically inspired techniques to improve DE algorithm performance.
|
189 |
Programação matemática e evolução diferencial para a otimização de redes de dutosKrause, Jonas 16 December 2013 (has links)
A otimização de uma rede de transporte de derivados de petróleo é um problema complexo e abordado na literatura atual. A modelagem matemática deste problema proposta neste trabalho cria um problema de otimização combinatorial. Métodos de resolução deste problema através da programação linear inteira mista e de algoritmos heurísticos de evolução diferencial (Evolução Diferencial Binária e Evolução Diferencial Discretizada) são propostos utilizando variáveis binárias. Os resultados encontrados com a programação linear apresentam valores ótimos para os benchmarks com pequenos espaços de busca e valores sub-ótimos para grandes. Resultados utilizando a evolução diferencial também são apresentados como uma alternativa de baixo esforço computacional. A aplicação destes métodos proporciona alternativas para o transporte de diferentes produtos em um horizonte de tempo definido e compara os métodos heurísticos com codificações binárias e contínuas. Tais resultados incentivam a utilização de algoritmos heurísticos com codificação contínua e apontam os métodos de discretização como alternativas eficazes para a resolução de problemas discretos. / The optimization of an pipeline network is a complex problem and addressed in the current literature. The mathematical modeling of this problem proposed in this paper creates a problem of combinatorial optimization. Methods for solving this problem using linear mixed integer programming and heuristic algorithms of differential evolution (Binary Differential Evolution and Discretized Differential Evolution) are proposed using binary variables. The results obtained with the linear programming have optimal values for the benchmarks with small search spaces and sub-optimal for large values. Results using the differential evolution are also presented as an alternative low computational effort. The application of these methods provides alternatives for transporting different products in a defined time horizon and compare heuristic methods with continuous and binary encodings. Such results encourage the use of heuristic algorithms with continuous coding and the point discretization methods as effective for solving problems discrete alternatives.
|
190 |
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.
|
Page generated in 0.1103 seconds