Tese (Doutorado em Engenharia Elétrica) - Centro Universitário FEI, São Bernardo do Campo, 2016

Made available in DSpace on 2014-06-12T15:59:53Z (GMT). No. of bitstreams: 2 arquivo5703_1.pdf: 1286025 bytes, checksum: a3ca835042abe1baa9c679ac998a2987 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Atualmente, existe um grande interesse pelo estudo dos sistemas imunológicos naturais motivados para combater doenças infecciosas como a AIDS, doenças auto-imunes como esclerose múltipla, e outros problemas de saúde. A ciência da computação tem contribuído nestes estudos através da especificação e simulação de modelos de sistema imunológico que geram novos conhecimentos à área de imunologia, bem como investigam a aplicação de sistemas imunológicos artificiais na solução de problemas computacionais. Esta dissertação investiga o paradigma de Sistemas Imunológicos Artificiais (AIS) através das especificidades de seus modelos e suas aplicações em problemas computacionais de reconhecimento de padrões. O estudo desenvolvido baseia-se no modelo CLONALG [Castro & Timmis, 2002] para propor e investigar uma nova extensão do paradigma que incorpora teoria da rede imunológica para melhorar o desempenho da abordagem de AIS aplicadas em problemas de reconhecimento de padrões. Visando a investigação da adequação do modelo de AIS em problemas de reconhecimento, o modelo CLONALG+ foi implementado e comparado com as abordagens de MLP-%DFNSURSDJDWLRQ e k-NN para reconhecimento de padrões. A base de padrões de dígitos manuscritos da OPTDIGITS [UCI, 1998] foi selecionada para o estudo comparativo, onde os padrões são representados através de um vetor de característica de tamanho 64 (quantidade de SL[HOV ativos da imagem). O conjunto total é composto por 5620 padrões de dígitos, sendo que em torno de 70% é destinado ao conjunto de treinamento e o restante ao conjunto de teste. Os principais resultados demonstram que é possível reconhecer padrões com a nova abordagem de AIS semelhante aos paradigmas tradicionais de reconhecimento de padrões com a vantagem de apresentar um menor desvio padrão médio entre os resultados dos experimentos. Adicionalmente, considerando que AIS aplicada em Reconhecimento de Padrões é uma área recente, espera-se que modelos mais elaborados sejam desenvolvidos e a abordagem seja mais aplicada a problemas do mundo real

Made available in DSpace on 2014-06-12T16:00:14Z (GMT). No. of bitstreams: 2 arquivo6095_1.pdf: 962733 bytes, checksum: cd84cd8cc40e4c53ea64a83ca746aa93 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Pesquisas sobre o funcionamento da fisiologia do corpo humano têm contribuído para a evolução dos Sistemas Imunológicos Artificiais. Este trabalho procura investigar uma arquitetura de reconhecimento a partir de observações do comportamento imunológico natural. Algumas funcionalidades foram observadas e estudadas no ambiente biológico para modelar esta abordagem imunológica. As principais são a organização e o agrupamento de anticorpos (Ab) semelhantes durante todo o processo. Acredita-se que estas funcionalidades poderiam melhorar a capacidade de reconhecimento dos algoritmos imunológicos artificiais. Esta tecnologia procura modelar características e funcionalidades do mecanismo de defesa dos seres vivos. Este mecanismo permite que o organismo possa defender-se da invasão de substâncias estranhas. O Sistema Imunológico Natural procura armazenar em uma memória genética os melhores anticorpos encontrados. Futuramente eles são usados para identificar os antígenos já apresentados ao organismo e obter uma resposta mais rápida e eficaz. Para analisar o desempenho deste novo modelo, ele foi comparado com outras técnicas conhecidas. Foram utilizados a MLP (Multi-Layer Perceptron), o k-NN (k-Nearest Neighbour) e o Clonalg (Clonal Selection Algorithm). Assim foi possível estimar a contribuição deste novo modelo na pesquisa de Sistemas Imunológicos Artificiais para o problema de reconhecimento de padrões

Vários problemas do mundo real podem ser analisados como problemas de otimização. Na bioinformática, em especial, como exemplos podem ser citados o alinhamento múltiplo de sequências, a filogenia, a predição de estruturas de proteínas e RNA, entre outros. As Meta-heurísticas Populacionais (MhP) são técnicas baseadas em interações de conjuntos de soluções candidatas, como elementos de uma população, utilizadas na otimização de funções. Seu uso é especialmente interessante na otimização de problemas onde há conhecimento parcial ou nenhum do espaço de busca. O objetivo deste trabalho é investigar o uso de auto-organização da população de um sistema imunológico artificial (AIS) a fim de aplicá-lo no problema de docking, que pode ser visto como um problema de otimização multimodal complexo. O AIS é um tipo de MhP inspirado na microevolução do sistema imunológico adaptativo de organismos complexos. Neste, as soluções candidatas representam células do sistema imunológico que busca se adaptar para a eliminação de um patógeno. O desenvolvimento do algoritmo foi baseado no opt-aiNet, que utiliza dos princípios das teorias de seleção clonal e maturação de afinidade para realizar a otimização de funções. Adicionalmente, o opt-aiNet, inspirado na teoria de redes imunológicas, realiza uma etapa de supressão, que busca eliminar soluções semelhantes, aumentando assim a diversidade populacional. Esta etapa é computacionalmente custosa, dado que é feito o cálculo da distância entre todos os possíveis pares de células (soluções) afim de eliminar aquelas próximas de acordo com um dado critério. A proposta deste trabalho é o desenvolvimento de um algoritmo de supressão auto-organizável, inspirado no fenômeno da criticalidade auto-organizada, buscando diminuir a influência da seleção de parâmetros e a complexidade da etapa de supressão. O algoritmo proposto foi testado em um conjunto de funções contínuas conhecidas e comumente utilizadas pela comunidade de computação evolutiva. Os resultados obtidos foram comparados com aqueles de uma implementação do opt-aiNet. Em adição, foi proposta a utilização de operadores de mutação com distribuição q-gaussiana nos AISs desenvolvidos. O algoritmo foi também aplicado no problema de docking rígido baseado em complementaridade de superfícies e minimização de colisões, especificamente no docking de proteínas. Os resultados foram comparados com aqueles de um algoritmo genético, resultando em um melhor desempenho obtido pelo algoritmo proposto. / Many real world problems can be described as optimization problems. In bioinformatics in special, there is multiple sequence alignment, filogeny and RNA and Protein structure prediction, among others. Population based metaheuristics are techniques based in the interaction of a set of candidate solutions as elements of a population. Its use is specially interesting in optimization problems where there is little or no knowledge of the search space. The objective of this work is to study the use of self-organization of population in an artificial imune system for use in the docking problem, considered a complex multimodal optimization problem. The artificial imunme system is a type of population based methaheuristics inspired in the microevolution of the adaptive immune system of complex organisms. Candidate solutions represent cells of the immune system adapting its antibodies to eliminate a pathogen. The development of the algorithm was based in the opt-aiNet, based in the principles of clonal selection and affinity maturation for function optimization. Additionally, the opt-aiNet, inspired in theories of immune network, makes a suppression stage to eliminate similiar solutions and control diversity. This stage is computationally expensive as it calculates the distance between every possible pair of cells (solutions) eliminating those closer than a threshold. This work proposes a self-organized suppression algorithm inspired in the self-organized criticality, looking to minimize the influence of parameter selection and complexity of the suppression stage in opt-aiNet. The proposed algorithm was tested in a set of well-known functions in the evolutionary computation community. The results were compared to those of an implementation of the opt-aiNet. In addition, we proposed a mutation operator with q-Gaussian distribution for the artificial immune systems. The algorithm was then applied in the rigid protein docking problem based in surface complementarity and colision avoidance. The results were compared with a genetic algorithm and achieved a better performance.

Submitted by SIMONE SILVA FRUTUOSO DE SOUZA null (simone_mat@hotmail.com) on 2017-03-29T13:28:59Z No. of bitstreams: 1 Tese Doutorado - Final.pdf: 4108375 bytes, checksum: d0138f5bfaaf0248f430b27319d3c9e2 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-30T17:35:45Z (GMT) No. of bitstreams: 1 souza_ssf_dr_ilha.pdf: 4108375 bytes, checksum: d0138f5bfaaf0248f430b27319d3c9e2 (MD5) / Made available in DSpace on 2017-03-30T17:35:45Z (GMT). No. of bitstreams: 1 souza_ssf_dr_ilha.pdf: 4108375 bytes, checksum: d0138f5bfaaf0248f430b27319d3c9e2 (MD5) Previous issue date: 2017-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho são apresentados três algoritmos imunológicos artificiais para resolver o problema de reconfiguração de sistemas de distribuição de energia elétrica considerando demanda fixa e também demandas variáveis. Para resolver este problema foram utilizados os algoritmos CLONALG (Clonal Selection Algorithm), Copt-aiNet (Artificial Immune Network for Combinatorial Optimization) e Opt-aiNet (Artificial Immune Network for Optimization). O problema de reconfiguração considerando demandas variáveis é um problema complexo e de natureza combinatória, que tem por objetivo identificar a melhor topologia radial para um sistema de distribuição de energia elétrica, de modo a minimizar os custos das perdas de energia ao longo de um período de operação. Para avaliar a factibilidade em relação às restrições de operação dos sistemas de energia elétrica, e calcular as perdas ativas para cada demanda foi utilizado o algoritmo de fluxo de carga radial de varredura. Os algoritmos foram escritos na linguagem C++. Para avaliar os algoritmos propostos foram realizados testes com os sistemas elétricos de 33, 84, 136, 417 e 10477 barras. Os resultados foram comparados com os existentes na literatura, de modo a verificar a eficiência e robustez dos algoritmos. / This work presents three artificial immune algorithms to solve the reconfiguration problem of electrical distribution systems (EDSs) with fixed demand and variable demands. To solve this problem were used the algorithms CLONALG (Clonal Selection Algorithm), Copt-aiNet (Artificial Immune Network for Combinatorial Optimization) and Opt-aiNet (Artificial Immune Network for Optimization). The reconfiguration problem with variable demands is a complex problem having combinatorial nature and aiming at identifying the best radial topology for an EDS, in order to minimize the cost of the energy losses in a given operation period. To evaluate the feasibility of the topology regarding the operating constraints of the EDS and to calculate the active power losses for each demand level it was used a specialized sweep load flow for radial systems. The mentioned algorithms were implemented in C++. To evaluate the proposed algorithms were performed testing using test systems with 33, 84, 136, 417 and 10477 nodes. The results were compared with the ones in the literature in order to validate the efficiency and robustness of the algorithms.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Neste trabalho são apresentados três algoritmos imunológicos artificiais para resolver o problema de reconfiguração de sistemas de distribuição de energia elétrica considerando demanda fixa e também demandas variáveis. Para resolver este problema foram utilizados os algoritmos CLONALG (Clonal Selection Algorithm), Copt-aiNet (Artificial Immune Network for Combinatorial Optimization) e Opt-aiNet (Artificial Immune Network for Optimization). O problema de reconfiguração considerando demandas variáveis é um problema complexo e de natureza combinatória, que tem por objetivo identificar a melhor topologia radial para um sistema de distribuição de energia elétrica, de modo a minimizar os custos das perdas de energia ao longo de um período de operação. Para avaliar a factibilidade em relação às restrições de operação dos sistemas de energia elétrica, e calcular as perdas ativas para cada demanda foi utilizado o algoritmo de fluxo de carga radial de varredura. Os algoritmos foram escritos na linguagem C++. Para avaliar os algoritmos propostos foram realizados testes com os sistemas elétricos de 33, 84, 136, 417 e 10477 barras. Os resultados foram comparados com os existentes na literatura, de modo a verificar a eficiência e robustez dos algoritmos. / Abstract: This work presents three artificial immune algorithms to solve the reconfiguration problem of electrical distribution systems (EDSs) with fixed demand and variable demands. To solve this problem were used the algorithms CLONALG (Clonal Selection Algorithm), Copt-aiNet (Artificial Immune Network for Combinatorial Optimization) and Opt-aiNet (Artificial Immune Network for Optimization). The reconfiguration problem with variable demands is a complex problem having combinatorial nature and aiming at identifying the best radial topology for an EDS, in order to minimize the cost of the energy losses in a given operation period. To evaluate the feasibility of the topology regarding the operating constraints of the EDS and to calculate the active power losses for each demand level it was used a specialized sweep load flow for radial systems. The mentioned algorithms were implemented in C++. To evaluate the proposed algorithms were performed testing using test systems with 33, 84, 136, 417 and 10477 nodes. The results were compared with the ones in the literature in order to validate the efficiency and robustness of the algorithms. / Doutor

Vários problemas do mundo real podem ser analisados como problemas de otimização. Na bioinformática, em especial, como exemplos podem ser citados o alinhamento múltiplo de sequências, a filogenia, a predição de estruturas de proteínas e RNA, entre outros. As Meta-heurísticas Populacionais (MhP) são técnicas baseadas em interações de conjuntos de soluções candidatas, como elementos de uma população, utilizadas na otimização de funções. Seu uso é especialmente interessante na otimização de problemas onde há conhecimento parcial ou nenhum do espaço de busca. O objetivo deste trabalho é investigar o uso de auto-organização da população de um sistema imunológico artificial (AIS) a fim de aplicá-lo no problema de docking, que pode ser visto como um problema de otimização multimodal complexo. O AIS é um tipo de MhP inspirado na microevolução do sistema imunológico adaptativo de organismos complexos. Neste, as soluções candidatas representam células do sistema imunológico que busca se adaptar para a eliminação de um patógeno. O desenvolvimento do algoritmo foi baseado no opt-aiNet, que utiliza dos princípios das teorias de seleção clonal e maturação de afinidade para realizar a otimização de funções. Adicionalmente, o opt-aiNet, inspirado na teoria de redes imunológicas, realiza uma etapa de supressão, que busca eliminar soluções semelhantes, aumentando assim a diversidade populacional. Esta etapa é computacionalmente custosa, dado que é feito o cálculo da distância entre todos os possíveis pares de células (soluções) afim de eliminar aquelas próximas de acordo com um dado critério. A proposta deste trabalho é o desenvolvimento de um algoritmo de supressão auto-organizável, inspirado no fenômeno da criticalidade auto-organizada, buscando diminuir a influência da seleção de parâmetros e a complexidade da etapa de supressão. O algoritmo proposto foi testado em um conjunto de funções contínuas conhecidas e comumente utilizadas pela comunidade de computação evolutiva. Os resultados obtidos foram comparados com aqueles de uma implementação do opt-aiNet. Em adição, foi proposta a utilização de operadores de mutação com distribuição q-gaussiana nos AISs desenvolvidos. O algoritmo foi também aplicado no problema de docking rígido baseado em complementaridade de superfícies e minimização de colisões, especificamente no docking de proteínas. Os resultados foram comparados com aqueles de um algoritmo genético, resultando em um melhor desempenho obtido pelo algoritmo proposto. / Many real world problems can be described as optimization problems. In bioinformatics in special, there is multiple sequence alignment, filogeny and RNA and Protein structure prediction, among others. Population based metaheuristics are techniques based in the interaction of a set of candidate solutions as elements of a population. Its use is specially interesting in optimization problems where there is little or no knowledge of the search space. The objective of this work is to study the use of self-organization of population in an artificial imune system for use in the docking problem, considered a complex multimodal optimization problem. The artificial imunme system is a type of population based methaheuristics inspired in the microevolution of the adaptive immune system of complex organisms. Candidate solutions represent cells of the immune system adapting its antibodies to eliminate a pathogen. The development of the algorithm was based in the opt-aiNet, based in the principles of clonal selection and affinity maturation for function optimization. Additionally, the opt-aiNet, inspired in theories of immune network, makes a suppression stage to eliminate similiar solutions and control diversity. This stage is computationally expensive as it calculates the distance between every possible pair of cells (solutions) eliminating those closer than a threshold. This work proposes a self-organized suppression algorithm inspired in the self-organized criticality, looking to minimize the influence of parameter selection and complexity of the suppression stage in opt-aiNet. The proposed algorithm was tested in a set of well-known functions in the evolutionary computation community. The results were compared to those of an implementation of the opt-aiNet. In addition, we proposed a mutation operator with q-Gaussian distribution for the artificial immune systems. The algorithm was then applied in the rigid protein docking problem based in surface complementarity and colision avoidance. The results were compared with a genetic algorithm and achieved a better performance.

A geração de grades horárias de qualidade é um fator crítico em qualquer instituição de ensino, tanto em escolas de ensino fundamental/médio como em universidades. Este problema é considerado complexo, pois devem ser relacionados e otimizados diversos recursos, tais como horários, disciplinas, professores e alunos. Em grande parte das instituições de ensino, a geração de grades horárias é realizada manualmente, o que vem a tornar este processo custoso e sujeito a falhas. Diversas abordagens são também encontradas na literatura para resolução deste problema, nas quais foram aplicados métodos de busca estocástica, devido à sua inerente complexidade. As estratégias de busca formuladas e comparadas no presente trabalho foram baseadas no uso de algoritmos genéticos e de sistemas imunológicos artificiais. Tais técnicas foram capazes de fornecer soluções de qualidade para o problema de geração automática de grades horárias. Neste trabalho foram desenvolvidos dois sistemas de apoio à decisão, nos quais foram combinadas técnicas heurísticas aos algoritmos genéticos e ao algoritmo de seleção clonal. O propósito desta investigação é realizar uma análise comparativa entre as duas técnicas a fim de verificar qual delas apresenta resultados mais promissores para a resolução do problema de geração automática de grades horárias. / The generation of timetables with good quality is a critical factor in any educational institution. This is considered a complex problem because it involves several types of information, such as schedules, course subjects, teachers and students. Several search strategies have been applied to solve timetabling problems, whose constraints may vary from one educational institution to another. Most educational institutions still prepare their timetables manually, which is a highly time-consuming process and subjected to errors. Several approaches to solve this problem are also found in technical studies, which use stochastic search methods due to the problems complexity. The search optimization methods used in this work to solve the timetabling problem are genetic algorithms and the clonal selection algorithm, whose satisfactory results when applied to optimization problems are reported in the literature. Two decision support systems were developed in this work, combining heuristic techniques with the genetic algorithms and the clonal selection algorithm. The purpose of this research is to make a comparative analysis of these two techniques in order to determine which one offers the most promising results for solving the timetabling problem.

A geração de grades horárias de qualidade é um fator crítico em qualquer instituição de ensino, tanto em escolas de ensino fundamental/médio como em universidades. Este problema é considerado complexo, pois devem ser relacionados e otimizados diversos recursos, tais como horários, disciplinas, professores e alunos. Em grande parte das instituições de ensino, a geração de grades horárias é realizada manualmente, o que vem a tornar este processo custoso e sujeito a falhas. Diversas abordagens são também encontradas na literatura para resolução deste problema, nas quais foram aplicados métodos de busca estocástica, devido à sua inerente complexidade. As estratégias de busca formuladas e comparadas no presente trabalho foram baseadas no uso de algoritmos genéticos e de sistemas imunológicos artificiais. Tais técnicas foram capazes de fornecer soluções de qualidade para o problema de geração automática de grades horárias. Neste trabalho foram desenvolvidos dois sistemas de apoio à decisão, nos quais foram combinadas técnicas heurísticas aos algoritmos genéticos e ao algoritmo de seleção clonal. O propósito desta investigação é realizar uma análise comparativa entre as duas técnicas a fim de verificar qual delas apresenta resultados mais promissores para a resolução do problema de geração automática de grades horárias. / The generation of timetables with good quality is a critical factor in any educational institution. This is considered a complex problem because it involves several types of information, such as schedules, course subjects, teachers and students. Several search strategies have been applied to solve timetabling problems, whose constraints may vary from one educational institution to another. Most educational institutions still prepare their timetables manually, which is a highly time-consuming process and subjected to errors. Several approaches to solve this problem are also found in technical studies, which use stochastic search methods due to the problems complexity. The search optimization methods used in this work to solve the timetabling problem are genetic algorithms and the clonal selection algorithm, whose satisfactory results when applied to optimization problems are reported in the literature. Two decision support systems were developed in this work, combining heuristic techniques with the genetic algorithms and the clonal selection algorithm. The purpose of this research is to make a comparative analysis of these two techniques in order to determine which one offers the most promising results for solving the timetabling problem.

O presente trabalho investiga um método de detecção de anomalias baseado em sistemas imunológicos artificiais, especificamente em uma técnica de reconhecimento próprio/não-próprio chamada algoritmo de seleção negativa (NSA). Foi utilizado um esquema de representação baseado em hiperesferas com centros e raios variáveis e um modelo capaz de gerar detectores, com esta representação, de forma eficiente. Tal modelo utiliza algoritmos genéticos onde cada gene do cromossomo contém um índice para um ponto de uma distribuição quasi-aleatória que servirá como centro do detector e uma função decodificadora responsável por determinar os raios apropriados. A aptidão do cromossomo é dada por uma estimativa do volume coberto através uma integral de Monte Carlo. Este algoritmo teve seu desempenho verificado em diferentes dimensões e suas limitações levantadas. Com isso, pode-se focar as melhorias no algoritmo, feitas através da implementação de operadores genéticos mais adequados para a representação utilizada, de técnicas de redução do número de pontos do conjunto próprio e de um método de pré-processamento baseado em bitmaps de séries temporais. Avaliações com dados sintéticos e experimentos com dados reais demonstram o bom desempenho do algoritmo proposto e a diminuição do tempo de execução. / This work investigates a novel detection method based on Artificial Immune Systems, specifically on a self/non-self recognition technique called negative selection algorithm (NSA). A representation scheme based on hyperspheres with variable center and radius and a model that is able to generate detectors, based on that representation scheme, have been used. This model employs Genetic Algorithms where each chromosome gene represents an index to a point in a quasi-random distribution, which serves as a detector center, and a decoder function that determines the appropriate radius. The chromosome fitness is given by an estimation of the covered volume, which is calculated through a Monte Carlo integral. This algorithm had its performance evaluated for different dimensions, and more suitable genetic operators for the used representation, techniques of reducing self-points number and a preprocessing method based on bitmap time series have been therefore implemented. Evaluations with synthetic data and experiments with real data demonstrate the performance of the proposed algorithm and the decrease in execution time.