Search

Orientador: Maria Gabriela Caffarena Celani Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo Resumo: Em alguns contextos, a complexidade representa a qualidade do que é confuso, embaraçado e de difícil apreensão. No entanto, existe uma categoria de problemas científicos relacionados à complexidade organizada, nos quais ferramentas como a Estatística e a Computação Científica podem auxiliar no entendimento dessa organização. Algumas dessas ferramentas são inspiradas em teorias provenientes da Biologia, como os algoritmos evolucionários e a vida artificial. Em design computacional, os mesmos conceitos são utilizados para a geração de formas e estruturas, principalmente quando existe a intenção em simular essa complexidade. Nesse contexto, existem duas abordagens possíveis: a top-down, em que processos de otimização podem ser iniciados com uma forma complexa e estruturalmente ineficiente, para então, se buscar a eficiência por meio do refinamento progressivo da solução; a bottom-up, na qual componentes elementares (agentes) se auto organizam em um processo que subtende um nível de presciência que culmina na emergência de complexidade. Atualmente, as propostas científicas têm se valido mais dos processos de otimização da forma global do que de interação entre componentes elementares, uma vez que estes últimos são comumente padronizados e, por causa disso, recebem críticas sobre a sua limitação da liberdade formal. Partindo da hipótese de que a construção de um sistema bottom-up, com a variação paramétrica de componentes, permite chegar na mesma liberdade formal dos processos top-down, mas com as vantagens da auto-organização, esta pesquisa tem como objetivo propor um método generativo para o design de estruturas espaciais fundamentado nos conceitos de complexidade e emergência. Como método serão identificadas regras em estudos de caso e, a partir de sua síntese e implementação em rotinas de programação, será desenvolvido um algoritmo baseado no método incremental tal como descrito na computação científica. As estruturas geradas foram submetidas a métodos experimentais físicos e computacionais para a verificação de aspectos produtivos relacionados a exequibilidade. Dentre os resultados, se propôs um novo método para o design de estruturas espaciais complexas Abstract: Sometimes, complexity refers to confusion, embarrassment and difficulties of understanding. However, there's a kind of scientific problems related to organized complexity wherein statistics and computation tools can help to identify essential features of their organization. Some of these tools are inspired by theories from biology such as evolutionary algorithms and artificial life. In computational design, the same concepts are used in structural form-finding process, when it's intended to simulate this complexity. In this context, there are two design approaches: top-down, in which design process begins with a complex and structurally inefficient shape, and then, refining the solution using optimization techniques; bottom-up, in which design process begins with components (agents), and then, their self-organization results in emergent complexity. Currently, researchers have been used more global shape optimization than agents interaction, because the last ones are commonly standardized, and this is represents a limitation in form-finding process. Assuming that the use of parametric components to construct a bottom-up generative system allows the same formal freedom of top-down approach, but with the advantages of self- organization, this research aims to propose a design method for spatial structures based on concepts of emergence and complexity. In research method, we intend to identify and compile rules in case studies to develop an algorithm using computational interactive and incremental method. After that, we evaluated assembly and feasibility aspects with physical experiments and computational simulations. Among outcomes, it was proposed a new method for complex spatial structures design Doutorado Arquitetura, Tecnologia e Cidade Doutor em Arquitetura, Tecnologia e Cidade FAPESP 2012/05475-4, 2015/01228-0

Orientadores: Fernando José Von Zuben, Leandro Nunes de Castro Silva Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: Existem muitas formas de se entender e descrever a natureza, sendo que a Computação Natural parte do princípio de que sistemas naturais são processadores de informação, ou seja, realizam computação. Esta tese recorre aos mecanismos da Computação Natural para o entendimento das computações realizadas em um sistema natural específico: os ecossistemas. O primeiro passo está fundamentado na ciência da Biogeografia, que estuda os ecossistemas e seus padrões emergentes. Na Biogeografia, é possível identificar elementos, relações entre eles e processos. A principal contribuição desta tese está na formalização computacional da Biogeografia, dando origem à Computação Biogeográfica. A proposta da Computação Biogeográfica é desenvolvida em várias frentes. A primeira delas promove a formalização do metamodelo, definido como uma estrutura conceitual que busca contextualizar a existência de ecossistemas artificiais e seus processos espaço temporais. Em seguida, para ilustrar a aplicação do metamodelo, são propostas definições de computação de ecossistemas em superfícies adaptativas fenotípicas. Essas definições resultam em um conjunto de relações e processos, os quais são aplicáveis à construção de ecossistemas artificiais. Estes, por sua vez, permitem o entendimento de dinâmicas e padrões de ecossistemas e também podem contribuir para a resolução de problemas computáveis. Na etapa final da tese, será proposto um algoritmo de radiação adaptativa que exibe padrões similares aos encontrados em ecossistemas reais e que se mostra competitivo para otimização multimodal em espaços contínuos. Por fim, perspectivas futuras são apresentadas visando indicar caminhos para se consolidar a Computação Biogeográfica como um novo ramo da Computação Natural Abstract: There are several attempts to understand and describe nature, and Natural Computing is founded on the principle that natural systems are information processors, in the sense that they perform computation. This thesis makes use of Natural Computing mechanisms for the understanding of the computation taking place in a specific natural system: the ecosystems. The first step is based on the science of Biogeography, devoted to the study of ecosystems and their emerging patterns. In Biogeography, it is possible to identify elements, relations among them, and processes. The main contribution of this thesis resides in the computational formalization of Biogeography, thus establishing the research area of Biogeographic Computation. The proposal of Biogeographic Computation is introduced in several fronts. The first front promotes the metamodel formalism, which defines a conceptual framework focused on contextualizing the existence of artificial ecosystems and their spatio-temporal processes. After that, aiming at illustrating the application of the metamodel, definitions of ecosystems computing in phenotypic adaptive surfaces is proposed. These definitions proceed to a set of relations and processes directly applicable to the proposition of artificial ecosystems. These artificial ecosystems promote the understanding of natural ecosystems dynamics and patterns, and can also contribute to the resolution of computable problems. At the final stage of the thesis, it is presented an adaptive radiation algorithm exhibiting patterns which are similar to the ones found in real ecosystems, and also proving to be competitive for multimodal optimization in continuous spaces. To conclude, some perspectives for the further steps of the research are outlined with the purpose of indicating some routes to consolidate Biogeographic Computation as a new branch of Natural Computing Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Orientador: Ricardo da Silva Torres Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Vida artificial é a área de estudo que tem por objetivo reproduzir comportamentos análogos à vida em diferentes tipos de mídia. Na abordagem \emph{soft}, essa tarefa é realizada usando simulações em \emph{software}. Essa tese apresenta um arcabouço de vida artificial, chamado Evocycle, que utiliza diferentes meta-heurísticas bioinspiradas como agentes do sistema. Tais meta-heurísticas são parte do campo da Computação Evolutiva em Ciência da Computação, na qual a teoria biológica da evolução é tomada como inspiração para projetar algoritmos estocásticos de otimização. Na computação evolutiva clássica, frequentemente abordagens elitistas são utilizadas, como por exemplo usar funções de \emph{fitness} para selecionar indivíduos para novas gerações. No entanto, a seleção natural como observada na natureza não possui uma função de \emph{fitness} para avaliação. Neste trabalho, propomos um arcabouço que remove a ênfase do processo de seleção baseado apenas nos valores de {\em fitness}, e tenta uma abordagem diferente, baseada em relações ecológicas de alimentação, reprodução e predação, utilizando assim o valor de \emph{fitness} indiretamente. Nosso sistema de vida artificial forma um ecossistema no qual diferentes espécies são modeladas pela hibridização de algoritmos de inteligência coletiva e evolucionários, e a interação dessas espécies através das relações ecológicas constrói seu comportamento ao longo do tempo. Com essa abordagem, buscamos aumentar a plausibilidade biológica do sistema evolutivo em nossas simulações de vida artificial. Para validar o arcabouço proposto, nós o simulamos com implementações utilizando os algoritmos de \emph{Particle Swarm Optimization} (PSO), no qual a função de velocidade de cada partícula é definida por uma árvore de programação genética (GP), e o algoritmo de otimização \emph{Artificial Bee Colony} (ABC). Ao invés de um ciclo completo de seleção por função de \emph{fitness}, as árvores GP, que codificam cada partícula PSO, evoluem tomando como base a sobrevivência dentro da simulação, levando em conta fatores como energia interna, idade e proximidade de outros indivíduos. Este ecossistema foi estudado em \emph{benchmarks} de otimização contínua, e pela análise da variação da frequência genética de populações de interesse, nós observamos o desenvolvimento de dinâmicas ecológicas promissoras, resultado da pressão seletiva oriunda das interações ecológicas entre os agentes do sistema de vida artificial. Também avaliamos a resiliência da população de predadores no sistema utilizando estudos da teoria de catástrofes em Biologia. As principais contribuições deste trabalho consistem na proposta do sistema de vida artificial em si, o estudo da emergência do comportamento de busca dos agentes do sistema em um cenário evolutivo que buscava maior plausibilidade biológica, e a proposta de uso da análise das taxas de recuperação após perturbações na população para avaliar sua resiliência Abstract: Artificial life is the field of study that aims to reproduce life-like behavior in different types of media. In the soft approach, this task is performed using software simulations. This thesis presents an artificial life framework, named EvoCycle, which uses different bio-inspired meta-heuristics as agents of the system. Such meta-heuristics are part of the Evolutionary Computation field in Computer Science, in which the general theory of evolution is taken as inspiration to design stochastic optimization algorithms. In classic evolutionary computation, often elitist approaches are used, such as those based on fitness functions, to select individuals for new generations. However, natural selection as observed has no explicit fitness evaluation. In this work, we propose a framework that de-emphasizes the selection process based solely on fitness values, and tries a different approach based on ecological relationships of feeding, reproduction, and predation, using the fitness values indirectly. Our artificial life system composes an ecosystem where different species are modelled as a hybridization of swarm intelligence with evolutionary algorithms, and the interaction of the species through ecological relationships shapes their behaviour over time. With this approach, we seek to increase the biological plausibility of the evolution process in our artificial life simulations. To validate the proposed framework, we performed simulations with implementations based on the Particle Swarm Optimization~(PSO) algorithm, in which the velocity rule of each particle is defined by a Genetic Programming~(GP) tree and the Artificial Bee Colony~(ABC) algorithm. Instead of an explicit fitness-selection cycle, the GP trees composing individual PSO particles evolve based on surviving in the simulation, taking into account different factors, such as energy, hunger, mutation, and proximity to other individuals. This ecosystem is investigated on optimization benchmarks, and through the analysis of the variance of the gene frequency, we observed the development of promising ecological dynamics, resulting from the selective pressure coming from the ecological relationships between agents of the artificial life system. We also evaluate the resilience of a predator population in the system using biological studies of the catastrophe theory. The main contributions of the work are the proposal of the artificial life framework itself, the study of the emergence of search behavior of the agents in an evolutionary scenario that aimed to be more biologically plausible, and the proposal of using the analysis of recovery rates after perturbations to investigate the resilience of artificial populations Doutorado Ciência da Computação Doutor em Ciência da Computação CNPQ 141224/2016-9 CAPES 0

Orientadores: Francisco José Arnold, Paulo Sérgio Martins Pedro Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Atualmente o número de cerâmicas piezelétricas existentes é elevada em virtude da rápida adoção de equipamentos elétricos pela sociedade, uma vez que inúmeros dispositivos apresentam essas cerâmicas integradas em sua constituição, como por exemplo, sistemas ultrassônicos, microfones, sensores, sonares, entre outros. Devido à importância e o potencial de uso em diversos segmentos, tais como medicinal, industrial, militar e entretenimento, o estudo dos parâmetros das cerâmicas piezelétricas é primordial para assegurar e impulsionar a pesquisa e o desenvolvimento de equipamentos cada vez mais confiáveis, versáteis e inteligentes. O estudo dos parâmetros do modelo de Mason para cerâmicas piezelétricas visa modelar os parâmetros físicos para simulação e otimização. Esse processo é dependente da estimativa de constantes de material por meio de medida da impedância elétrica. A partir disso, o objetivo dessa pesquisa propõe-se a desenvolver um sistema que utilize metodologias numéricas para melhorar e facilitar o estudo dos parâmetros do modelo de Mason para cerâmicas piezelétricas. Para tanto, empregou-se diferentes Algoritmos Genéticos com Otimização Mono-Objetivo e Multiobjetivo aliados a Equações baseadas no modelo de Mason para comparar e estimar os melhores cenários. Tendo como base os cálculos e os estudos de casos realizados, utilizando diferentes tipos de cerâmicas piezelétricas com modo de vibração em espessura e transversal, em consonância com o referencial teórico e os resultados obtidos, comprovou-se que ocorreram efetivas melhoras com o emprego dos Algoritmos Genéticos, independentemente do modo de vibração, ocasionando o efetivo ajuste das curvas entre os dados estimados e os dados experimentais Abstract: Currently, the number of existing piezoelectric ceramics is significant due to the rapid adoption of electrical equipment by society, since numerous devices present these ceramics integrated in their constitution, as ultrasonic systems, microphones, sensors, sonars, among others. Due to the importance and potential of use in various segments, such as medical, industrial, military and entertainment, the study of parameters of piezoelectric ceramics is paramount to ensure and boost the research and development of devices that is increasingly reliable, versatile, and smart. The study of the parameters of the Mason model for piezoelectric ceramics aims to model the physical parameters for simulation and optimization. This process is dependent on the estimation of material constants by means of electrical impedance measurement. This process is dependent on the estimation of material constants by means of electrical impedance measurement. Because of scenario, the objective of this research is to develop a system that uses numerical methodologies to improve and facilitate the study of the parameters of the Mason model for piezoelectric ceramics. In the direction of objective, different Genetic Algorithms were used with Mono-Objective and Multi-Objective Optimization allied to Equations based on the Mason model to compare and estimate the best scenarios. Based on the calculations and the case studies performed, using different types of piezoelectric ceramics with vibration mode in thickness and transverse, in accordance with the theoretical reference and the obtained results, it was verified that there were effective improvements with the use of Algorithms Genetics, independently of the mode of vibration, causing the effective adjustment of the curves between the estimated data and the experimental data Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior This dissertation makes use of Biogeography and Biogeographic Computation concepts for the proposal of an adaptive radiation model on adaptive surfaces. The proposed model is based on a computational definition of biological isolation to detect the emergence of a new species and, thus, to promote emergent processes of sympatric speciation and extinction of species from a single ancestral species. Ecosystem patterns were investigated in static and time-varying habitats based on the model. Adaptive surfaces represent ecological habitats and opportunities and, therefore, the temporal variation of habitats is linked to the variation of the surface. In this context we have investigated how adaptive radiation patterns emerge and are favorable to the continued adaptation of species, even in cases where severe environmental changes occur. Adaptive surfaces may also be linked to optimization problems, so the results allow a discussion of how ecosystem patterns can be conducive to optimization in dynamic environments where decision surfaces vary in time. Essa dissertação faz uso de conceitos da Biogeografia e Computação Biogeográfica para a proposta de um modelo de radiação adaptativa em superfícies de adaptação. O modelo pro-posto valeu-se de uma definição computacional de isolamento biológico para detecção do surgimento de uma nova espécie e, dessa forma, promover processos emergentes de especiação simpátrica e extinção de espécies a partir de uma única espécie ancestral. Por meio do modelo foram investigados padrões de ecossistemas em habitats estáticos e variantes no tempo. Superfícies de adaptação representam habitats e oportunidades ecológicas e, portanto, a variação temporal de habitats está vinculada à variação da superfície. Neste contexto foram investigados como padrões de radiação adaptativa emergem e são favoráveis à adaptação continuada de espécies, mesmo em casos em que ocorrem mudanças ambientais severas. Superfícies de adaptação também podem estar vinculadas a problemas de otimização, sendo assim os resultados permitem uma discussão de como padrões de ecossistemas podem ser favoráveis à otimização em ambientes dinâmicos onde superfícies de decisão são variantes no tempo.

Dissertação (mestrado) — Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Mecânica, 2016. O presente trabalho propõe um modelo evolucionário para simulação da evolução da camuflagem em seres vivos virtuais na presença de seus predadores. Neste modelo contém gerente, ambiente, presas, predadores, recursos para as presas, recursos para os predadores e recursos compartilhados. Foram definidos seus atributos e comportamentos básicos incluindo as relações entre eles. A partir do modelo geral, duas aplicações específicas foram propostas: (a) o caso particular dos lebistes (Poecilia reticulata) estudado por John A. Endler. Os predadores se alimentam dos lebistes que, por sua vez, se alimentam de outros recursos. Os três elementos do modelo (predador, lebiste e os recursos dos lebistes) estão inseridos no ambiente; e (b) um cenário fictício que simula um ambiente com espécies terrestres de presas e predadores, onde as presas representam uma espécie herbívora que possue plantas como recurso alimentar ao mesmo tempo que são recursos alimentares dos predadores. Além disso, há lagos que representam recursos compartilhados por ambas as espécies. Os atributos e comportamentos dos organismos simulados foram modelados a partir de pesquisa por observação. Um software computacional de simulação foi desenvolvido com base no modelo proposto com a finalidade de validá-lo. Os resultados obtidos a partir de simulações utilizando o software mostram que o modelo proposto atinge um nível satisfatório em relação ao trabalho biológico utilizado como referência. A ferramenta de simulação pode principalmente ser utilizada por pesquisadores que precisam trabalhar com diversas variáveis para compreensão de modelos complexos de interação entre presas e predadores, podendo auxiliar na tomada de decisão sobre problemas de conservação de espécies além de possuir um carácter didático, podendo ser utilizado para demonstrar e estudar o processo de evolução dos seres vivos pela seleção natural. This paper proposes an evolutionary model for simulation of the evolution of camouflage in virtual living beings in presence of predators. In this model contains a manager, an environment, preys, predators, resources for preys, resources for predators and shared resources. Their basics attributes and behaviors were defined beyond the relations among them. From the general model, two specific applications have been proposed: (a) the particular case of guppies (Poecilia reticulata) studied by John A. Endler. The predators feed of guppies and they feed of other resources. The three elements of model (predator, guppy and resource of guppy) are inserted in the environment; and (b) a fictitious scenario that simulates an environment with terrestrial species of preys and predators, which preys represent an herbivorous specie that take plants as food resources and are food resources for predators. Furthermore, there are lakes that represent shared resources for both species. The simulated organism' attributes and behaviors were modeled from researches through observation. A computational software was developed based on proposed model in order to validate it. The results obtained by simulations using the software show that the proposed model reaches a satisfactory level in relation to the biological work used as reference. The simulation tool can mainly be used by researchers who need to work with several variables for understanding of complex interaction models between preys and predators to assist in decision-making on species conservation issues and it has a didactic character and can be used to demonstrate and study the process of evolution of living beings by natural selection as well.

Universidade Presbiteriana Mackenzie Currently, the natural sciences are taking advantage of information and computing concepts to investigate the structure of nature and the interrelationships among the various natural systems. Furthermore, scientists from various fields are arguing that nature performs computations and others argue that the basic structure of the physical world is based on informational and computational processes. Within this scenario, there is the Natural Computing, whose main premise is to assume that natural phenomena can be interpreted from a computational perspective and that these phenomena can be modeled computationally and applied in different scientific contexts. Although Natural Computing is committed with the computational interpretation of nature, there is no theoretical framework that leads to the explanation of natural systems from a computational perspective. In this context, this thesis proposes a Conceptual Framework that allows to computationally explain the structures and processes within natural systems. The Conceptual Framework is based on a set of concepts and macroconcepts and its formalization consists of two sets of tools: a conceptual map with its graphical view of macroconcepts and concepts and their relationships; and a set of UML diagrams to computationally modeling the structures, processes and subprocesses present in natural systems. Thus, the proposed Conceptual Framework brings an intuitive and visual way to understand the natural systems under a computational perspective and to guide the modeling of bioinspired algorithms. From the perspective of a bioinspired analysis of algorithms, modeling tools allow to view conceptual gaps in the algorithms. Finally, the proposed Conceptual Structure is used as a tool for the analysis and synthesis of bioinspired algorithms, more specifically to develop algorithms inspired by the behavior of bacteria. In this way, the proposed framework aims to build an analysis and synthesis tool to collaborate for the theoretical and interdisciplinary maturation of Natural Computing. Atualmente, as ciências naturais estão se valendo de conceitos de informação e computação para investigar a estrutura da natureza e as inter-relações entre os diversos sistemas naturais. Além disso, cientistas de diversas áreas estão argumentando que a natureza realiza computações e outros defendem que a estrutura básica do mundo físico está fundamentada em processos informacionais e computacionais. Dentro deste cenário, existe a Computação Natural, cuja principal premissa é assumir que os fenômenos naturais podem ser interpretados sob uma perspectiva computacional e que esses fenômenos podem ser modelados computacionalmente e aplicados em diferentes contextos científicos. Embora a Computação Natural se comprometa com a interpretação computacional da natureza não existe um corpo teórico que permita explicar os sistemas naturais sob uma perspectiva computacional. Neste contexto, esta tese propõe uma Estrutura Conceitual, que explica computacionalmente as estruturas e processos presentes nos sistemas naturais. A Estrutura Conceitual é embasada em um conjunto de conceitos e macroconceitos e sua formalização consiste em dois conjuntos de ferramentas: um mapa conceitual que representa uma visualização gráfica dos macroconceitos e conceitos e suas relações; e um conjunto de diagramas UML para modelar computacionalmente as estruturas, processos e subprocessos presentes nos sistemas naturais. Desta forma, a Estrutura Conceitual proposta traz consigo uma forma intuitiva e visual de entender os sistemas naturais sob uma perspectiva computacional e de guiar a modelagem de algoritmos bioinspirados. Da perspectiva da análise de algoritmos bioinspirados, as ferramentas de modelagem permitem visualizar lacunas conceituais na engenharia dos algoritmos estudados. Por fim, a Estrutura Conceitual proposta é utilizada como ferramenta para o projeto e desenvolvimento (síntese) de algoritmos bioinspirados, mais especificamente para o desenvolvimento de algoritmos inspirados no comportamento das bactérias. Desta forma, a Estrutura Conceitual proposta visa a construção de um ferramental de análise e síntese que colabore para o amadurecimento teórico e interdisciplinar da Computação Natural.

In this paper we discuss the problem of linear tting to experimental data using a method bio-inspired of optimization, i.e., it imitates the biological concepts attempt to nd optimal or suboptimal results. The method used is the genetic algorithm (GA), AG makes use of the theory of Darwinian evolution to nd the best route for the desired maximum point. Traditionally, the linear tting is made through the method of least squares. The method is e cient, but is di cult to justify the pre-calculus classes. Therefore, the alternative AG comes as a computationally exhaustive procedure, however easy justi cation for these classes. Thus, the purpose of this study is to compare the results of linear tting for some control scenarios using this methods and certify the quality of the adjustments obtained by the approximate method. At the end of the work it was found that the results are solid enough to justify the alternative method and the proposed use of this optimization process has the potential to spark interest in other areas of mathematics. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES Neste trabalho abordaremos o problema de ajuste linear para dados experimentais através de um método de otimização bio-inspirado, isto é, que mimetiza conceitos biológicos na tentativa de buscar resultados ótimos ou sub-ótimos. O método utilizado é o algoritmo genético (AG), AG faz uso da teoria da evolução Darwiniana para buscar a melhor rota para o ponto de máximo desejado. Tradicionalmente, o ajuste linear é feito através do método de mínimos quadrados. Tal método é e ciente, porém é de difícil justi cativa para as turmas pré-cálculo. Diante disso, a alternativa do AG vem como um procedimento exaustivo computacionalmente, entretanto de fácil justi cativa para essas turmas. Assim, a proposta do trabalho é comparar os resultados de ajuste linear para alguns cenários de controle através dos dois métodos e certi car a qualidade dos ajustes obtidos pelo método aproximado. No nal do trabalho constatou-se que os resultados encontrados sÿo sólidos o bastante para justi car o método alternativo e que a proposta da utilização desse processo de otimização tem potencial para despertar interesse em outras áreas da matemática.

O Problema da Galeria de Arte consiste em determinar o número mínimo de guardas necessários para cobrir um ambiente tal que cada ponto no espaço é coberto por, pelo menos, um observador. Neste trabalho, apresentamos uma abordagem genética que pode ser aplicada a ambientes 3D genéricos sem qualquer restrição, uma lacuna existente no estado da arte até então. A metodologia utiliza técnicas de (i) computação gráfica para gerar pontos de amostragem no ambiente, (ii) teste de interseção raio-malha para gerar um gráfico de visibilidade entre as amostras e (iii) algoritmos genéticos para encontrar e minimizar o conjunto de observadores. Os mapas do jogo Counter-Strike foram utilizados como ambientes de entrada e os motores de jogo Half-Life e Irrlicht foram usados para gerar os grafos de visibilidade. Uma série de experimentos foram realizados, e os resultados mostram que nossa metodologia é capaz de obter uma boa cobertura de espaços complexos com um pequeno número de guardas. The Art Gallery Problem consists in determining the minimum number of observers required to cover an environment such that each point of space is seen by at least one observer. This is a NP-Hard problem well known in the field of computational geometry. In the literature, several restrictions are applied to 2D and 3D environments to study and solve the problem in polynomial time, for example the use of simple polygons, orthogonal and planar environments, etc. In this work we present an approximate and polynomial solution based on metaheuristic genetic algorithms that can be applied to general 3D environments without any restriction and, therefore, applicable in shooter games and also real-world environments. The methodology uses the techniques of (i) computer graphics to generate sample points in the environment, (ii) ray-mesh intersection test to generate a graph of visibility between the samples and (iii) genetic algorithms to find and optimize the minimum set of observers. The maps of the game Counter-Strike were used to analyze the placement of small groups of observers in complex environments with obstacles. The game engines Half-Life and Irrlicht were used to apply the ray-mesh intersection test in 3D environments. A series of experiments were performed and the results show that our methodology is capable of obtaining a good coverage of complex spaces with a small number of agents observing.

Orientador: Romis Ribeiro de Faissol Attux Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: Os algoritmos de otimização podem possuir características de busca local, global e multimodal. Em termos simples, os algoritmos de busca local procuram refinar uma solução inicial encontrada, promovendo a sua movimentação para o ótimo local dominante em sua vizinhança. Já os algoritmos de busca global possuem estratégias para escapar de ótimos locais, e, desta forma conseguem movimentar seus pontos de forma mais ampla pelo espaço de busca. Por fim, algoritmos multimodais procuram encontrar os vários ótimos no espaço de busca. Neste trabalho foi proposto um algoritmo de otimização multimodal, baseado em PSO, com duas inovações: o raio de repulsão com controlador de passo, e o armazenamento da região promissora. O algoritmo foi chamado de MPSO (Magnetic Particle Swarm Optimization), e possui apenas um parâmetro de configuração, o número de partículas. Ele apresentou resultados bastante interessantes nos experimentos comparativos realizados, tanto em funções benchmark quanto em uma aplicação prática. A segunda proposta foi uma metodologia de busca baseada em clusterização. Nesta metodologia, a modificação proposta translada os centroides das posições de representantes dos clusters, obtidas originalmente pelos algoritmos de clusterização clássicos, para uma região promissora no cluster, ou seja, para uma região melhor avaliada pela função objetivo, que será maximizada ou minimizada. Desta forma, a metodologia toma a forma de um operador que pode ser utilizado como pré-processador de algoritmos de otimização clássicos, sendo capaz de introduzir diversidade na população inicial, o que, como mostram os experimentos realizados, melhorou os resultados obtidos. Outras possibilidades de aplicação da ideia também são expostas e avaliadas Abstract: Optimization algorithms have local, global and multimodal search features. In simple terms, a local search algorithm refines an initial solution by moving it towards an optimal dominant place in its neighborhood. Global search algorithms have strategies to escape from local optima, and thus can move their points more broadly throughout the search space. Finally, multimodal algorithms seek to find several global optima in the search space. In this thesis, we propose a multimodal optimization algorithm based on PSO with two innovations: the repulsion radius with step controller and the storage of promising search directions. The algorithm was named MPSO (Magnetic Particle Swarm Optimization) and has only one configuration parameter, the number of particles. It led to consistent results in benchmark-based comparative experiments and in a practical application. The second proposal was a clustering-based optimization methodology. This proposal moves the centroids from a position representative of a cluster, originally obtained by classical clustering algorithms, to a promising region in terms of an objective function to be maximized or minimized . The methodology was implemented in the form of an operator used as a pre-processor to traditional optimization algorithms. It introduced diversity in the initial population, which, as shown by the experiments,led to significant performance improvements. Other possibilities of applying this new idea are also discussed in the text Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T11:51:21Z No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) Made available in DSpace on 2015-03-30T11:51:21Z (GMT). No. of bitstreams: 1 Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) Previous issue date: 2014-01-31 Nenhuma Este trabalho apresenta um algoritmo de otimização baseado na metaheurística dos Sistemas Imunológicos Artificiais, princípios de Teoria dos Jogos, Co-evolução e Paralelização. Busca-se a combinação adequada dos conceitos de Teoria dos Jogos, Co-evolução e Paralelização aplicados ao algoritmo AISO (Artificial Immune System Optimization) para resolução do Problema de Alocação de Berços (PAB). Dessa maneira, o algoritmo é formalizado a partir das técnicas citadas, formando o PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Inicialmente, foram realizados experimentos visando à sintonia dos parâmetros empregados nas diferentes versões da ferramenta desenvolvida. Com base nas melhores configurações identificadas, foram realizados experimentos de avaliação através da solução de um conjunto de instâncias do PAB. Os resultados obtidos permitiram a indicação da versão co-evolutiva associada à teoria dos jogos como a melhor para solução do problema em estudo. This paper presents an optimization algorithm based on metaheuristic of Artificial Immune Systems, principles of Game Theory, Co-evolution and parallelization. The objective is find the appropriate combination of the concepts of Game Theory, Co-evolution and Parallelization applied to AISO algorithm (Artificial Immune System Optimization) for solving the Berth Allocation Problem (BAP). Thus, the algorithm is formalized from the above mentioned techniques, forming the PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Initially, experiments aiming to tune the parameters were performed using different versions of the tool developed. Based on the identified best settings, evaluation experiments were carried out by solving a set of instances of the PAB. The results obtained allowed the appointment of co-evolutionary version associated with game theory as the best solution to the problem under study.

The educational game Calangos is based on the ecological modeling of a real case of lizards that inhabit the Dunes of the Middle São Francisco River, in the state of Bahia - Brazil. The goal of the game is to enable students to interact with an environment that promotes a proper understanding of ecological and evolutionary processes. The game should serve as a tool to support the teaching and learning of ecology and evolution to high school students. For the Calangos Game to achieve this goal, central concepts of evolution and ecology should be properly incorporated in the game. Thus, the first scientific challenge of the project, in addition to the technological challenge of developing the game itself, is related to modeling the population dynamics and evolutionary biology in the context of Calangos. To investigate these aspects independently of the game, this dissertation proposes a simulator for Calangos, as well as a genetic-evolutionary model for the lizards. Furthermore, it performs a set of experiments that examine the ecology and evolution of the lizards in the proposed simulated environment. More specifically, four experimental scenarios and three difficulty levels for each environmental scenario are proposed to carefully analyze the dynamics of populations and the influence of the evolution on the fertility and longevity of lizards populations located within the simulated environment. The results clearly show that in a balanced environment without predators it is possible to observe a dynamic equilibrium of populations in a typical Lotka-Volterra model of population dynamics. On the other hand, it is also observed that in the most hostile environments containing large numbers of predators, the capability of evolution allows the lizard species to survive in the environment, which does not occur if the lizards evolution is disabled during the simulations. In the context of the Calangos game, the results presented here serve as the initial proof of concept necessary for the modeling of the lizards to be incorporated in the game. O jogo eletrônico educativo Calangos é baseado na modelagem de um caso ecológico real relativo aos lagartos que habitam a região das Dunas do Médio São Francisco, no Estado da Bahia. O objetivo final do jogo é possibilitar ao estudante interagir com um ambiente que promova uma compreensão adequada de processos ecológicos e evolutivos da natureza. O jogo deve funcionar como ferramenta de apoio ao ensino e aprendizagem de ecologia e evolução no nível médio de escolaridade. Para que o Calangos atinja esse objetivo conceitos centrais de evolução e ecologia deverão ser incorporados adequadamente ao jogo. Nesse sentido, o primeiro desafio científico do projeto, que antecede aos desafios tecnológicos de desenvolvimento de jogos propriamente ditos, está relacionado à como modelar a dinâmica das populações e a biologia evolutiva no contexto do Calangos. Para investigar estes aspectos de forma independente do jogo, essa dissertação propõe um simulador para o Calangos, assim como uma modelagem genético-evolutiva para os lagartos e, na sequência, realiza um conjunto de experimentos que permitem analisar a ecologia e evolução dos lagartos no ambiente simulado. Mais especificamente, são propostos quatro cenários experimentais e três níveis de dificuldade ambiental para cada cenário, que permitirão analisar cuidadosamente a dinâmica das populações e influência da evolução na fecundidade e longevidade de populações de lagartos localizadas dentro do ambiente de simulação. Os resultados mostram que em um ambiente equilibrado e sem predadores é possível observar um equilíbrio dinâmico das populações, em um formato típico dos modelos clássicos de dinâmica populacional baseados nas equações de Lotka-Volterra. Por outro lado, observa-se também que em ambientes mais hostis contendo grande quantidade de predadores a capacidade de evolução dos lagartos permite a sobrevivência da espécie no ambiente, o que não ocorre caso os lagartos não possam evoluir durante as simulações. No contexto do jogo Calangos, os resultados apresentados aqui servem como a prova de conceito inicial necessária para a modelagem computacional dos lagartos a serem incorporados no jogo.

Universidade Presbiteriana Mackenzie With the constant growth in the quantity of websites, and consequently the increase in content availability throughout the Internet, the development of search mechanisms that enable access to reliable information has become a complex activity. In this sense, this work presents a revision on the behavior of search mechanisms, as well as the manner through which they map information, including the study of ontologies and knowledge bases, as well as forms of knowledge representation on the Internet. These models integrate the Semantic Web, which constitutes a proposal for the organization of information. Based on these elements, a search mechanism was developed for a specific domain: videogames. This mechanism is based on the classification of electronic games by specialized review websites, where one may extract information about select titles. As such, this work is divided in four stages. Firstly, data is extracted from the aforementioned websites for previously selected titles through the use of a webcrawler. Secondly, an analysis is performed on the obtained data on two fronts, utilizing natural computing as well as power-law concepts. Next, an ontology for videogames is constructed, with its subsequent publication in a knowledge base accessible to the software. Lastly, the implementation of the actual mechanism, which will make use of the knowledge base and bring the user suggestions pertaining to his search, such as titles or related characteristics intrinsic to games that may be evaluated relating to the search. This work also hopes to present itself as a useful model that may be utilized in different domains, such as movies, travel destinations, electronic appliances and software, among others. Com o crescimento da quantidade de websites e, consequentemente, o aumento de conteúdo disponível na Internet, desenvolver sistemas de busca que possibilitem o acesso à informação confiável tornou-se uma atividade complexa. Desta forma, este trabalho apresenta uma revisão do funcionamento dos mecanismos de busca e das formas pelas quais a informação é mapeada, o que inclui o estudo de ontologias e bases de conhecimento, bem como de formas de representação de informação na Internet. Estes modelos integram a Web Semântica, que constitui uma proposta de organização de informação. Com base nestes elementos foi desenvolvido um sistema de busca de conteúdo em um domínio específico: jogos eletrônicos. Este pauta-se na classificação de websites especializados, de onde pode-se extrair informações das resenhas disponíveis sobre os títulos escolhidos. Para tanto, a proposta divide-se em quatro fases. A primeira relaciona-se à coleta de dados dos websites mencionados por meio da implementação de um webcrawler que realiza a extração de informações de uma lista de jogos pré-determinada. Em seguida é feito o tratamento e a análise dos dados por meio de duas abordagens, que utilizam-se de computação natural e conceitos de lei de potência. Além disso, foi feita a construção de uma ontologia para estes jogos e publicação destes dados em uma base de conhecimento acessível ao software. Por último, foi implementado um mecanismo de busca que faz uso da base de conhecimento e apresenta como resultado, ao usuário, sugestões pertinentes à sua busca, como títulos ou características relacionadas. Este trabalho ainda apresenta um modelo que pode ser utilizado em outros domínios, tais como filmes, destinos de viagens, eletrodomésticos, softwares, dentre outros.

Fundo Mackenzie de Pesquisa Molecular replication was introduced as a possible theory to explain the origin of life. Since their proposal they have been extensively studied from a biochemical perspective. This work proposes a taxonomy for the main properties of replicators that are important for building computational tools to solve complex problems as well as introduces two computational models for these entities in order to observe and analyze the behavior of these models in light of the natural properties of replicators introduced. A replicação molecular foi introduzida como uma possível teoria para explicar a origem da vida. Desde sua proposição, ela vem sendo estudada extensivamente a partir de uma perspectiva bioquímica. Baseado na literatura de replicadores moleculares, esta dissertação organiza e propõe uma taxonomia para as principais propriedades dos replicadores que sejam interessantes para a construção de ferramentas computacionais voltadas para a solução de problemas complexos na engenharia e na computação, bem como introduz dois modelos computacionais baseado nessas entidades a fim de observar e analisar o comportamento destes modelos sob a luz das propriedades dos replicadores naturais discutidas nesta dissertação.

Fundo Mackenzie de Pesquisa This dissertation discusses the use of bio-inspired algorithms for data clustering, with emphasis on a model of emergent collective behavior of agents and a new clustering algorithm called cBoids is presented. The cBoids algorithm is a variation of the classic Boids model. In this new algorithm, each Boid represents an object from the data base and the three original rules from the Boids model were modified so that the objects of the database have influence on the behaviour of the Boids. Two new rules have also been proposed, responsible for the creation and destruction of centroids, which represent the formed clusters. In the experiments conducted in this work the algorithm was successfully tested on four databases. Esta dissertação aborda o uso de algoritmos bioinspirados para a tarefa de agrupamento de dados , com ênfase nos modelos de comportamentos emergentes coletivos de agentes e um novo algoritmo de agrupamento de dados chamado cBoids é apresentado. O algoritmo cBoids é uma variação do clássico modelo Boids. Neste novo algoritmo, cada Boid representa um objeto da base de dados e as três regras originais do modelo Boids foram alteradas para que os objetos da base de dados influenciem o comportamento dos Boids. Duas novas regras também foram propostas, responsáveis pela criação e destruição de centróides, que representam os clusters formados. Nos experimentos realizados nesta dissertação o algoritmo foi testado com sucesso em quatro bases de dados.

A solução clássica para o problema de estimação dos ângulos de chegada (DOA) de sinais incidindo em um arranjo de sensores é a aplicação do método de máxima verossimilhança. Este método leva ao problema de otimização de uma função custo não-linear, não-quadrática, multimodal e variante com a relação sinal-ruído (SNR). Os métodos propostos para tal tarefa, presentes na literatura, falham em uma ampla gama de valores de SNR. Este trabalho apresenta os resultados de um estudo sobre a aplicação de ferramentas pertencentes à computação natural ao problema de estimação DOA. Simulações demonstram que quatro dos algoritmos analisados alcançam o ótimo global para uma ampla faixa de valores de SNR, com esforços computacionais inferiores àquele exigido por uma busca exaustiva. The classical solution to the problem of estimating the direction of arrival (DOA) of plane waves impinging on a sensor array is based on the application of the maximum likelihood method. This approach leads to the problem of optimizing a cost function which is non-linear, non-quadratic, multimodal and variant with respect to the signal-noise ratio (SNR). The methods proposed in the literature to solve this problem fail for a wide set of SNR values. This work presents the results obtained from a study on the application of natural computing algorithms to the DOA estimation problem. Computational simulations show that four of the analyzed algorithms find the global optimum for a broad range of SNR values with computational efforts lower than that associated with an exaustive search.

Submitted by Guilherme Lemeszenski (guilherme@nead.unesp.br) on 2013-08-22T18:58:37Z No. of bitstreams: 1 S0103-17592009000300002.pdf: 323496 bytes, checksum: c5f950e4d1b0ab979d6eb4763e967d8c (MD5) Made available in DSpace on 2013-08-22T18:58:37Z (GMT). No. of bitstreams: 1 S0103-17592009000300002.pdf: 323496 bytes, checksum: c5f950e4d1b0ab979d6eb4763e967d8c (MD5) Previous issue date: 2009-09-01 Made available in DSpace on 2013-09-30T19:54:30Z (GMT). No. of bitstreams: 2 S0103-17592009000300002.pdf: 323496 bytes, checksum: c5f950e4d1b0ab979d6eb4763e967d8c (MD5) S0103-17592009000300002.pdf.txt: 152859 bytes, checksum: 543b4c32384326467e96344dcf8cffcf (MD5) Previous issue date: 2009-09-01 Submitted by Vitor Silverio Rodrigues (vitorsrodrigues@reitoria.unesp.br) on 2014-05-20T15:14:10Z No. of bitstreams: 2 S0103-17592009000300002.pdf: 323496 bytes, checksum: c5f950e4d1b0ab979d6eb4763e967d8c (MD5) S0103-17592009000300002.pdf.txt: 152859 bytes, checksum: 543b4c32384326467e96344dcf8cffcf (MD5) Made available in DSpace on 2014-05-20T15:14:10Z (GMT). No. of bitstreams: 2 S0103-17592009000300002.pdf: 323496 bytes, checksum: c5f950e4d1b0ab979d6eb4763e967d8c (MD5) S0103-17592009000300002.pdf.txt: 152859 bytes, checksum: 543b4c32384326467e96344dcf8cffcf (MD5) Previous issue date: 2009-09-01 Este artigo apresenta uma breve revisão de alguns dos mais recentes métodos bioinspirados baseados no comportamento de populações para o desenvolvimento de técnicas de solução de problemas. As metaheurísticas tratadas aqui correspondem às estratégias de otimização por colônia de formigas, otimização por enxame de partículas, algoritmo shuffled frog-leaping, coleta de alimentos por bactérias e colônia de abelhas. Os princípios biológicos que motivaram o desenvolvimento de cada uma dessas estratégias, assim como seus respectivos algoritmos computacionais, são introduzidos. Duas aplicações diferentes foram conduzidas para exemplificar o desempenho de tais algoritmos. A finalidade é enfatizar perspectivas de aplicação destas abordagens em diferentes problemas da área de engenharia. This paper presents an overview of some most recent bioinspired methods based on swarm behaviors for the development of problem-solving techniques. The metaheuristics provided here are ant colony optimization, particle swarm optimization, shuffled frog-leaping algorithm, bacterial foraging optimization and bee colony. The basic biological principles that have motivated the development of each strategy, as well as their computational algorithms, are introduced. Two different applications were carried out in order to clarify the performance of such algorithms. The goal is to emphasize perspectives of applications of these approaches in different engineering problems. UNESP IGCE DEMAC UNESP IGCE DEMAC

Image segmentation is one of the image processing problems that deserves special attention from the scientific community. This work studies unsupervised methods to clustering and pattern recognition applicable to medical image segmentation. Natural Computing based methods have shown very attractive in such tasks and are studied here as a way to verify it's applicability in medical image segmentation. This work treats to implement the following methods: GKA (Genetic K-means Algorithm), GFCMA (Genetic FCM Algorithm), PSOKA (PSO and K-means based Clustering Algorithm) and PSOFCM (PSO and FCM based Clustering Algorithm). Besides, as a way to evaluate the results given by the algorithms, clustering validity indexes are used as quantitative measure. Visual and qualitative evaluations are realized also, mainly using data given by the BrainWeb brain simulator as ground truth Segmentação de imagens é um dos problemas de processamento de imagens que merece especial interesse da comunidade científica. Neste trabalho, são estudado métodos não-supervisionados para detecção de algomerados (clustering) e reconhecimento de padrões (pattern recognition) em segmentação de imagens médicas Métodos baseados em técnicas de computação natural têm se mostrado bastante atrativos nestas tarefas e são estudados aqui como uma forma de verificar a sua aplicabilidade em segmentação de imagens médicas. Este trabalho trata de implementa os métodos GKA (Genetic K-means Algorithm), GFCMA (Genetic FCM Algorithm) PSOKA (Algoritmo de clustering baseado em PSO (Particle Swarm Optimization) e K means) e PSOFCM (Algoritmo de clustering baseado em PSO e FCM (Fuzzy C Means)). Além disso, como forma de avaliar os resultados fornecidos pelos algoritmos são utilizados índices de validação de clustering como forma de medida quantitativa Avaliações visuais e qualitativas também são realizadas, principalmente utilizando dados do sistema BrainWeb, um gerador de imagens do cérebro, como ground truth