Made available in DSpace on 2016-03-15T19:37:57Z (GMT). No. of bitstreams: 1 DAVILA PATRICIA FERREIRA CRUZ.pdf: 3761174 bytes, checksum: 5bdf7491a01f52fa9d31b6f66eca7c87 (MD5) Previous issue date: 2015-06-17 / With the popularization of Internet, the advancement of electronic devices and the ease of storage, the volume of data stored and available at companies has increased substantially. Therefore, it becomes necessary to use intelligent techniques to extract useful information and knowledge from these data. In this context, Data Mining has been the aim of several researches by providing a set of intelligent techniques to the exploration of large volumes of data. The present project aims to research and develop new algorithms inspired by the collective behavior of bee colonies for solving complex clustering and classification tasks. More specifically, this project proposes adaptations of an optimization algorithm inspired by the behavior of bees so that it can be applied to solve clustering problems and also for positioning centers of RBF neural networks. The proposed approaches were applied to several benchmark problems with promising results. / Com a popularização da Internet, o avanço dos dispositivos eletrônicos e a facilidade de armazenamento, o volume de dados armazenados e disponibilizados por empresas de diversos ramos tem aumentado rapidamente. Com isso, torna-se necessária a utilização de técnicas avançadas capazes de extrair desses dados informações úteis e conhecimentos que, na maioria das vezes, estão implícitos. Nesse contexto, a Mineração de Dados tem sido alvo de diversas pesquisas por prover um conjunto de técnicas inteligentes para a exploração de grandes volumes de dados. O presente projeto visa à investigação e desenvolvimento de novos algoritmos inspirados no comportamento coletivo das colônias de abelhas para aplicação em problemas complexos de classificação e agrupamentos de dados, que são importantes tarefas da Mineração de Dados. Mais especificamente, esse projeto propõe adaptações de um algoritmo de otimização inspirado no comportamento de abelhas, sua aplicação em problemas de agrupamento de dados e para o posicionamento de centros de redes neurais do tipo RBF. Os resultados experimentais em bases de dados da literatura mostraram a viabilidade e benefícios das propostas, tanto para problemas de agrupamento, quanto para problemas de classificação.

Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-21T19:17:51Z No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:10:55Z (GMT) No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:10:55Z (GMT). No. of bitstreams: 2 THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-08-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Fundo Mackenzie de Pesquisa / Combinatorial optimization problems are widely studied in the literature. On the one hand, their challenging characteristics, such as the constraints and number of potential solutions, inspire their use to test new solution techniques. On the other hand, the practical application of these problems provides support on daily tasks of people and companies. Vehicle routing problems constitute a well-known class of combinatorial optimization problems, from which the Traveling Salesman Problem (TSP) is one of the most elementary problems. Despite its simplicity, the difficulty in finding its exact solution and its direct application in practical problems in multiple areas make it one of the most studied problems in the literature. Algorithms inspired by biological phenomena are being successfully applied to optimization problems, mainly combinatorial optimization problems. Those inspired by the collective behavior of insects produce good results for solving such problems. This work proposes the VRoptBees, a framework inspired by honeybee behavior to tackle vehicle routing problems. Together with the framework, two examples of implementation are described, one to solve the TSP and the other to solve the Capacitated Vehicle Routing Problem (CVRP). Tests were conducted with benchmark instances from the literature, on which the implementation for the TSP presented the third best results in a comparison with other bee-inspired algorithms. / Problemas de otimização combinatória são largamente estudados na literatura. De um lado, suas características desafiadoras, como o número de restrições e possíveis soluções, inspiram seu uso para testar novas técnicas de solução. Por outro lado, a aplicação prática desses problemas auxilia no dia a dia de pessoas e empresas. Os problemas de roteamento de veículos constituem uma classe muito conhecida da otimização combinatória, tendo o Problema de Caixeiro Viajante (PCV) como um dos mais elementares. Apesar de sua simplicidade, a dificuldade em encontrar uma solução exata e sua direta aplicação prática em diversas áreas o faz um dos problemas mais estudados na literatura. Algoritmos inspirados em fenômenos naturais têm sido utilizados com sucesso em problemas de otimização, principalmente de natureza combinatória. Aqueles inspirados no comportamento coletivo de insetos apresentam bons resultados para esses problemas. Nesse trabalho é proposto um framework inspirado no comportamento de abelhas para a solução de problemas de roteamento de veículos, chamado de VRoptBees. Junto ao framework, dois exemplos de implementações são propostos, um para a solução do PCV e outro para o Problema de Roteamento de Veículos Capacitados (PRVC). Testes foram feitos com instâncias de benchmark comumente utilizadas na literatura, com a implementação ao PCV apresentando o terceiro melhor resultado entre os algoritmos inspirados em abelhas.

Orientador: Jefferson Nascimento de Oliveira / Resumo: Os direitos da natureza são indispensáveis para a harmonia nos espaços de atuação e desenvolvimento da vida, onde o uso e a ocupação do solo impactam diretamente na disponibilidade e qualidade de recursos fundamentais como a água e outros bens comuns. Com a observação de iniciativas transnacionais, governamentais, laboratórios de ciência aberta, empresas e ONGs, esta pesquisa exploratória consolida cenários sobre intensos fluxos de multidões à deriva de projeções e sobre a capacidade adaptativa de aglomerados no Antropoceno. São elementos onde a Internet e os paradigmas do serviço total incitam plataformas digitais para novos produtos e serviços, adequadas à realidade dos jogos sociais contemporâneos. Com bases e referenciais em governança eletrônica para as águas, os resultados das explorações resultam na descoberta das organizações associativas cibernéticas (cyorgs) e as características fundamentais dos Escritórios da Resiliência Hídrica. Amparados por espaços antropológicos, de interação e implementações estratégicas de inovação em sustentabilidade, os produtos constroém a plataforma ÁguasML - Bem Comum em Mídia Livre, implementada digitalmente com código aberto via portais de notícias, ambientes de aprendizagem, automatizações e aplicativos para coleta e distribuição de dados. Apontam também alguns dos componentes das plataformas hidrotecnológicas nos Escritórios da Resiliência Hídrica, assim como os conteúdos, as experiências e as características de tecnologias resilient... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The rights of nature are indispensable for harmony in the spaces of participation and development of life, where the use and occupation of the lands directly affect the availability and quality of water and other commons. Observing transnational initiatives, governments, open science laboratories, corporations and NGOs, this exploratory research consolidates scenarios of intense flows of crowds drifting from projections and adaptive capacity in the Anthropocene. They are elements in which the internet and the paradigms of the total service incite digital platforms for new products and services, adapted to the mechanized reality of contemporary social games. With these baselines and benchmarks in electronic governance for water, the results of explorations are the discovery of cybernetic associative organizations (cyorgs) and the fundamental characteristics of Water Resilience Office´s. Based on anthropological spaces, spaces of interaction and strategic implementations of innovation in water sustainability, the work build the ÁguasML - Commons in Open Media platform, digitally implemented with open source through news portals, e-learning environments, automations and applications for collection and data distribution. They also show some of the components of hydrotechnology platforms at the offices for water resilience, as well as the contents, experiences and characteristics of resilient technologies in situations of water scarcity and vulnerability of rights. This office gen... (Complete abstract click electronic access below) / Mestre

Uma das premissas fundamentais em redes fotônicas baseadas na tecnologia de multiplexação por comprimento de onda (WDM) é o controle dos caminhos ópticos. Um caminho óptico, ou caminho de luz, é uma conexão puramente óptica estabelecida entre dois nós da rede, que pode atravessar diversos nós intermediários. Para dar suporte eficiente à demanda exigida de uma rede WDM sobre a qual executam aplicações de alto desempenho, os caminhos ópticos devem ser estabelecidos e encerrados dinamicamente, de tal forma que as rotas e os comprimentos de onda escolhidos minimizem a probabilidade de ocorrência de bloqueios de conexão por falta de recursos disponíveis. O elemento central de uma rede WDM é o sistema que controla os comutadores ópticos, determina as rotas, aloca os comprimentos de onda, e estabelece, mantém e encerra as conexões ópticas entre os nós da rede. O objetivo deste trabalho é apresentar estratégias de roteamento e de atribuição de comprimentos de onda para redes fotônicas usando heurísticas baseadas em inteligência de enxame. Os resultados demonstram que as estratégias desenvolvidas apresentam baixa probabilidade de bloqueio de requisições e buscam, sempre que possível, os caminhos de menor custo. As estratégias desenvolvidas levam em conta o dinamismo da rede, sendo as decisões de caminho baseadas em dados atualizados em cada nó da rede em tempo real, sem a necessidade do conhecimento global do estado da rede em cada nó. / A fundamental aspect of photonic networks based on wavelength division multiplexing (WDM) technology is the control of optical paths. An optical path, or lightpath, is a purely optical connection established between two network nodes, which can pass through several intermediate nodes. To efficiently support the demands required from a WDM network that runs high performance applications, the optical paths should be established and finished dynamically, in such a way that the selected routes and wavelengths tend to minimize the blocking probability due to the lack of available resources. The central element of a WDM network is the system that controls the optical switches, determines routes, allocates the wavelengths, and establishes, maintains and finishes connections between optical network nodes. The purpose is to present strategies for routing and wavelength assignment over photonic networks using heuristics based on swarm intelligence. Results show that the developed strategies exhibit low blocking probability of requests and find the paths of minimum cost whenever possible. The strategies developed take into account the dynamics of the network, and decisions are based on updated data at each network node in real time without the need of a complete knowledge of network state at each node.

Uma das premissas fundamentais em redes fotônicas baseadas na tecnologia de multiplexação por comprimento de onda (WDM) é o controle dos caminhos ópticos. Um caminho óptico, ou caminho de luz, é uma conexão puramente óptica estabelecida entre dois nós da rede, que pode atravessar diversos nós intermediários. Para dar suporte eficiente à demanda exigida de uma rede WDM sobre a qual executam aplicações de alto desempenho, os caminhos ópticos devem ser estabelecidos e encerrados dinamicamente, de tal forma que as rotas e os comprimentos de onda escolhidos minimizem a probabilidade de ocorrência de bloqueios de conexão por falta de recursos disponíveis. O elemento central de uma rede WDM é o sistema que controla os comutadores ópticos, determina as rotas, aloca os comprimentos de onda, e estabelece, mantém e encerra as conexões ópticas entre os nós da rede. O objetivo deste trabalho é apresentar estratégias de roteamento e de atribuição de comprimentos de onda para redes fotônicas usando heurísticas baseadas em inteligência de enxame. Os resultados demonstram que as estratégias desenvolvidas apresentam baixa probabilidade de bloqueio de requisições e buscam, sempre que possível, os caminhos de menor custo. As estratégias desenvolvidas levam em conta o dinamismo da rede, sendo as decisões de caminho baseadas em dados atualizados em cada nó da rede em tempo real, sem a necessidade do conhecimento global do estado da rede em cada nó. / A fundamental aspect of photonic networks based on wavelength division multiplexing (WDM) technology is the control of optical paths. An optical path, or lightpath, is a purely optical connection established between two network nodes, which can pass through several intermediate nodes. To efficiently support the demands required from a WDM network that runs high performance applications, the optical paths should be established and finished dynamically, in such a way that the selected routes and wavelengths tend to minimize the blocking probability due to the lack of available resources. The central element of a WDM network is the system that controls the optical switches, determines routes, allocates the wavelengths, and establishes, maintains and finishes connections between optical network nodes. The purpose is to present strategies for routing and wavelength assignment over photonic networks using heuristics based on swarm intelligence. Results show that the developed strategies exhibit low blocking probability of requests and find the paths of minimum cost whenever possible. The strategies developed take into account the dynamics of the network, and decisions are based on updated data at each network node in real time without the need of a complete knowledge of network state at each node.

A Inteligência de Enxame foi proposta a partir da observação do comportamento social de espécies de insetos, pássaros e peixes. A ideia central deste comportamento coletivo é executar uma tarefa complexa decompondo-a em tarefas simples, que são facilmente executadas pelos indivíduos do enxame. A realização coordenada destas tarefas simples, respeitando uma proporção pré-definida de execução, permite a realização da tarefa complexa. O problema de alocação de tarefas surge da necessidade de alocar as tarefas aos indivíduos de modo coordenado, permitindo o gerenciamento do enxame. A alocação de tarefas é um processo dinâmico pois precisa ser continuamente ajustado em resposta a alterações no ambiente, na configuração do enxame e/ou no desempenho do mesmo. A robótica de enxame surge deste contexto de cooperação coletiva, ampliada à robôs reais. Nesta abordagem, problemas complexos são resolvidos pela realização de tarefas complexas por enxames de robôs simples, com capacidade de processamento e comunicação limitada. Objetivando obter flexibilidade e confiabilidade, a alocação deve emergir como resultado de um processo distribuído. Com a descentralização do problema e o aumento do número de robôs no enxame, o processo de alocação adquire uma elevada complexidade. Desta forma, o problema de alocação de tarefas pode ser caracterizado como um processo de otimização que aloca as tarefas aos robôs, de modo que a proporção desejada seja atendida no momento em que o processo de otimização encontre a solução desejada. Nesta dissertação, são propostos dois algoritmos que seguem abordagens distintas ao problema de alocação dinâmica de tarefas, sendo uma local e a outra global. O algoritmo para alocação dinâmica de tarefas com abordagem local (ADTL) atualiza a alocação de tarefa de cada robô a partir de uma avaliação determinística do conhecimento atual que este possui sobre as tarefas alocadas aos demais robôs do enxame. O algoritmo para alocação dinâmica de tarefas com abordagem global (ADTG) atualiza a alocação de tarefas do enxame com base no algoritmo de otimização PSO (Particle swarm optimization). No ADTG, cada robô possui uma possível solução para a alocação do enxame que é continuamente atualizada através da troca de informação entre os robôs. As alocações são avaliadas quanto a sua aptidão em atender à proporção-objetivo. Quando é identificada a alocação de maior aptidão no enxame, todos os robôs do enxame são alocados para as tarefas definidas por esta alocação. Os algoritmos propostos foram implementados em enxames com diferentes arranjos de robôs reais demonstrando sua eficiência e eficácia, atestados pelos resultados obtidos. / Swarm Intelligence has been proposed based on the observation of social behavior of insect species, birds and fishes. The main idea of this collective behavior is to perform a complex task decomposing it into many simple tasks, that can be easily performed by individuals of the swarm. Coordinated realization of these simple tasks while adhering to a pre-defined distribution of execution, allows for the achievement of the original complex task. The problem of task allocation arises from the need of assigning tasks to individuals in a coordinated fashion, allowing a good management of the swarm. Task allocation is a dynamic process because it requires a continuous adjustment in response to changes in the environment, the swarm configuration and/or the performance of the swarm. Swarm robotics emerges from this context of collective cooperation applied to swarms of real robots. In this approach, complex problems are solved by performing complex tasks using swarms of simple robots, with a limited processing and communication capabilities. Aiming at achieving flexibility and reliability, the allocation should emerge as a result of a distributed process. With the decentralization of the problem and the increasing number of robots in the swarm, the allocation process acquires a high complexity. Thus, the problem of task allocation can be characterized as an optimization process that assigns tasks to robots, so that the desired proportion is met at the end of the optimization process, find the desired solution. In this dissertation, we propose two algorithms that follow different to the problem of dynamic task allocation approaches: one is local and the other global. The algorithm for dynamic allocation of tasks with a local approach (ADTL) updates the task assignment of each robot based on a deterministic assessment of the current knowledge it has so far about the tasks allocated to the other robots of the swarm. The algorithm for dynamic task allocation with a global approach (ADTG) updates the allocation of tasks based on a swarm optimization process, inspired by PSO (Particle swarm optimization). In ADTG, each robot has a possible solution to the swarm allocation, which is continuously updated through the exchange of information between the robots. The allocations are evaluated for their fitness in meeting the goal proportion. When the allocation of highest fitness in the swarm is identified, all robots of the swarm are allocated to the tasks defined by this allocation. The proposed algorithms were implemented on swarms of different arrangements of real robots demonstrating their efficacy, robustness and efficiency, certified by obtained the results.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Os Sistemas Multi-Robôs proporcionam vantagens sobre um robô individual, quando da realização de uma tarefa com maiores velocidade, precisão e tolerância a falhas. Os estudos dos comportamentos sociais na natureza têm permitido desenvolver algoritmos bio-inspirados úteis na área da robótica de enxame. Seguindo instruções simples e repetitivas, grupos de robôs, fisicamente limitados, conseguem solucionar problemas complexos. Quando existem duas ou mais tarefas a serem realizadas e o conjunto de robôs é heterogêneo, é possível agrupá-los de acordo com as funcionalidades neles disponíveis. No caso em que o conjunto de robôs é homogêneo, o agrupamento pode ser realizado considerando a posição relativa do robô em relação a uma tarefa ou acrescentando alguma característica distintiva. Nesta dissertação, é proposta uma técnica de clusterização espacial baseada simplesmente na comunicação local de robôs. Por meio de troca de mensagens entre os robôs vizinhos, esta técnica permite formar grupos de robôs espacialmente próximos sem precisar movimentar os robôs. Baseando-se nos métodos de clusterização de fichas, a técnica proposta emprega a noção de fichas virtuais, que são chamadas de cargas, sendo que uma carga pode ser estática ou dinâmica. Se uma carga é estática permite determinar a classe à qual um robô pertence. Dependendo da quantidade e do peso das cargas disponíveis no sistema, os robôs intercambiam informações até alcançar uma disposição homogênea de cargas. Quando as cargas se tornam estacionárias, é calculada uma densidade que permite guiar aquelas que estão ainda em movimento. Durante as experiências, foi observado visualmente que as cargas com maior peso acabam se agrupando primeiro enquanto aquelas com menor peso continuam se deslocando no enxame, até que estas cargas formem faixas de densidades diferenciadas para cada classe, alcançando assim o objetivo final que é a clusterização dos robôs. / Multi-Robots Systems provide advantages over a single robot when performing a task, achieving a greater speed, higher accuracy and better fault tolerance. The studies of social behavior in nature have allowed to develop bio-inspired algorithms useful in swarm robotics. Following simple and repetitive rules, groups of robots can provide solutions to complex problems. When two or more tasks to be executed by a set of heterogeneous robots, it is possible to cluster the robots according to their intrinsic features. When homogeneous robots are used, the clustering may be achieved by considering the robot relative position regarding the location where the task has to be performed or adding some other distinct feature. In this dissertation, a technique for spatial clustering simply based on local communication between robots is proposed. Through the message exchange between neighboring robots, this technique allows cluster formation without robot movement. Based on the token clustering methods, the proposed technique employs a virtual token, which is called a load. The load allows identifying the class to which a robot belongs. Depending on the amount and weight of the loads available in the system, the robots interchange information to achieve uniform load distribution. When the loads become stationaries, a density is calculated as to guide the remaining loads that are still in motion. As a consequence, the loads of higher weight cluster first and the those of lower weight continue shifting through the swarm, until they start forming different density ranges for each class, thereby achieving the final aim which is robot clustering.

A Inteligência de Enxame foi proposta a partir da observação do comportamento social de espécies de insetos, pássaros e peixes. A ideia central deste comportamento coletivo é executar uma tarefa complexa decompondo-a em tarefas simples, que são facilmente executadas pelos indivíduos do enxame. A realização coordenada destas tarefas simples, respeitando uma proporção pré-definida de execução, permite a realização da tarefa complexa. O problema de alocação de tarefas surge da necessidade de alocar as tarefas aos indivíduos de modo coordenado, permitindo o gerenciamento do enxame. A alocação de tarefas é um processo dinâmico pois precisa ser continuamente ajustado em resposta a alterações no ambiente, na configuração do enxame e/ou no desempenho do mesmo. A robótica de enxame surge deste contexto de cooperação coletiva, ampliada à robôs reais. Nesta abordagem, problemas complexos são resolvidos pela realização de tarefas complexas por enxames de robôs simples, com capacidade de processamento e comunicação limitada. Objetivando obter flexibilidade e confiabilidade, a alocação deve emergir como resultado de um processo distribuído. Com a descentralização do problema e o aumento do número de robôs no enxame, o processo de alocação adquire uma elevada complexidade. Desta forma, o problema de alocação de tarefas pode ser caracterizado como um processo de otimização que aloca as tarefas aos robôs, de modo que a proporção desejada seja atendida no momento em que o processo de otimização encontre a solução desejada. Nesta dissertação, são propostos dois algoritmos que seguem abordagens distintas ao problema de alocação dinâmica de tarefas, sendo uma local e a outra global. O algoritmo para alocação dinâmica de tarefas com abordagem local (ADTL) atualiza a alocação de tarefa de cada robô a partir de uma avaliação determinística do conhecimento atual que este possui sobre as tarefas alocadas aos demais robôs do enxame. O algoritmo para alocação dinâmica de tarefas com abordagem global (ADTG) atualiza a alocação de tarefas do enxame com base no algoritmo de otimização PSO (Particle swarm optimization). No ADTG, cada robô possui uma possível solução para a alocação do enxame que é continuamente atualizada através da troca de informação entre os robôs. As alocações são avaliadas quanto a sua aptidão em atender à proporção-objetivo. Quando é identificada a alocação de maior aptidão no enxame, todos os robôs do enxame são alocados para as tarefas definidas por esta alocação. Os algoritmos propostos foram implementados em enxames com diferentes arranjos de robôs reais demonstrando sua eficiência e eficácia, atestados pelos resultados obtidos. / Swarm Intelligence has been proposed based on the observation of social behavior of insect species, birds and fishes. The main idea of this collective behavior is to perform a complex task decomposing it into many simple tasks, that can be easily performed by individuals of the swarm. Coordinated realization of these simple tasks while adhering to a pre-defined distribution of execution, allows for the achievement of the original complex task. The problem of task allocation arises from the need of assigning tasks to individuals in a coordinated fashion, allowing a good management of the swarm. Task allocation is a dynamic process because it requires a continuous adjustment in response to changes in the environment, the swarm configuration and/or the performance of the swarm. Swarm robotics emerges from this context of collective cooperation applied to swarms of real robots. In this approach, complex problems are solved by performing complex tasks using swarms of simple robots, with a limited processing and communication capabilities. Aiming at achieving flexibility and reliability, the allocation should emerge as a result of a distributed process. With the decentralization of the problem and the increasing number of robots in the swarm, the allocation process acquires a high complexity. Thus, the problem of task allocation can be characterized as an optimization process that assigns tasks to robots, so that the desired proportion is met at the end of the optimization process, find the desired solution. In this dissertation, we propose two algorithms that follow different to the problem of dynamic task allocation approaches: one is local and the other global. The algorithm for dynamic allocation of tasks with a local approach (ADTL) updates the task assignment of each robot based on a deterministic assessment of the current knowledge it has so far about the tasks allocated to the other robots of the swarm. The algorithm for dynamic task allocation with a global approach (ADTG) updates the allocation of tasks based on a swarm optimization process, inspired by PSO (Particle swarm optimization). In ADTG, each robot has a possible solution to the swarm allocation, which is continuously updated through the exchange of information between the robots. The allocations are evaluated for their fitness in meeting the goal proportion. When the allocation of highest fitness in the swarm is identified, all robots of the swarm are allocated to the tasks defined by this allocation. The proposed algorithms were implemented on swarms of different arrangements of real robots demonstrating their efficacy, robustness and efficiency, certified by obtained the results.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Os Sistemas Multi-Robôs proporcionam vantagens sobre um robô individual, quando da realização de uma tarefa com maiores velocidade, precisão e tolerância a falhas. Os estudos dos comportamentos sociais na natureza têm permitido desenvolver algoritmos bio-inspirados úteis na área da robótica de enxame. Seguindo instruções simples e repetitivas, grupos de robôs, fisicamente limitados, conseguem solucionar problemas complexos. Quando existem duas ou mais tarefas a serem realizadas e o conjunto de robôs é heterogêneo, é possível agrupá-los de acordo com as funcionalidades neles disponíveis. No caso em que o conjunto de robôs é homogêneo, o agrupamento pode ser realizado considerando a posição relativa do robô em relação a uma tarefa ou acrescentando alguma característica distintiva. Nesta dissertação, é proposta uma técnica de clusterização espacial baseada simplesmente na comunicação local de robôs. Por meio de troca de mensagens entre os robôs vizinhos, esta técnica permite formar grupos de robôs espacialmente próximos sem precisar movimentar os robôs. Baseando-se nos métodos de clusterização de fichas, a técnica proposta emprega a noção de fichas virtuais, que são chamadas de cargas, sendo que uma carga pode ser estática ou dinâmica. Se uma carga é estática permite determinar a classe à qual um robô pertence. Dependendo da quantidade e do peso das cargas disponíveis no sistema, os robôs intercambiam informações até alcançar uma disposição homogênea de cargas. Quando as cargas se tornam estacionárias, é calculada uma densidade que permite guiar aquelas que estão ainda em movimento. Durante as experiências, foi observado visualmente que as cargas com maior peso acabam se agrupando primeiro enquanto aquelas com menor peso continuam se deslocando no enxame, até que estas cargas formem faixas de densidades diferenciadas para cada classe, alcançando assim o objetivo final que é a clusterização dos robôs. / Multi-Robots Systems provide advantages over a single robot when performing a task, achieving a greater speed, higher accuracy and better fault tolerance. The studies of social behavior in nature have allowed to develop bio-inspired algorithms useful in swarm robotics. Following simple and repetitive rules, groups of robots can provide solutions to complex problems. When two or more tasks to be executed by a set of heterogeneous robots, it is possible to cluster the robots according to their intrinsic features. When homogeneous robots are used, the clustering may be achieved by considering the robot relative position regarding the location where the task has to be performed or adding some other distinct feature. In this dissertation, a technique for spatial clustering simply based on local communication between robots is proposed. Through the message exchange between neighboring robots, this technique allows cluster formation without robot movement. Based on the token clustering methods, the proposed technique employs a virtual token, which is called a load. The load allows identifying the class to which a robot belongs. Depending on the amount and weight of the loads available in the system, the robots interchange information to achieve uniform load distribution. When the loads become stationaries, a density is calculated as to guide the remaining loads that are still in motion. As a consequence, the loads of higher weight cluster first and the those of lower weight continue shifting through the swarm, until they start forming different density ranges for each class, thereby achieving the final aim which is robot clustering.

Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-10-17T18:58:21Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese-ldsp-cin-ufpe.pdf: 2057113 bytes, checksum: 40e1baebc2bc4840cd9803fdc16d952f (MD5) / Made available in DSpace on 2016-10-17T18:58:21Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese-ldsp-cin-ufpe.pdf: 2057113 bytes, checksum: 40e1baebc2bc4840cd9803fdc16d952f (MD5) Previous issue date: 2016-08-26 / CNPQ / A Análise de Agrupamentos, também conhecida por Aprendizagem Não-Supervisionada, é uma técnica importante para a análise exploratória de dados, tendo sido largamente empregada em diversas aplicações, tais como mineração de dados, segmentação de imagens, bioinformática, dentre outras. A análise de agrupamentos visa a distribuição de um conjunto de dados em grupos, de modo que indivíduos em um mesmo grupo estejam mais proximamente relacionados (mais similares) entre si, enquanto indivíduos pertencentes a grupos diferentes tenham um alto grau de dissimilaridade entre si. Do ponto de vista de otimização, a análise de agrupamentos é considerada como um caso particular de problema de NP-Difícil, pertencendo à categoria da otimização combinatória. Técnicas tradicionais de agrupamento (como o algoritmo K-Means) podem sofrer algumas limitações na realização da tarefa de agrupamento, como a sensibilidade à inicialização do algoritmo, ou ainda a falta de mecanismos que auxiliem tais métodos a escaparem de pontos ótimos locais. Meta-heurísticas como Algoritmos Evolucionários (EAs) e métodos de Inteligência de Enxames (SI) são técnicas de busca global inspirados na natureza que têm tido crescente aplicação na solução de uma grande variedade de problemas difíceis, dada a capacidade de tais métodos em executar buscas minuciosas pelo espaço do problema, tentando evitar pontos de ótimos locais. Nas últimas décadas, EAs e SI têm sido aplicadas com sucesso ao problema de agrupamento de dados. Nesse contexto, a meta-heurística conhecida por Otimização por Busca em Grupo (GSO) vem sendo aplicada com sucesso na solução de problemas difíceis de otimização, obtendo desempenhos superiores a técnicas evolucionárias tradicionais, como os Algoritmos Genéticos (GA) e a Otimização por Enxame de Partículas (PSO). No contexto de análise de agrupamentos, EAs e SIs são capazes de oferecer boas soluções globais ao problema, porém, por sua natureza estocástica, essas abordagens podem ter taxas de convergência mais lentas quando comparadas a outros métodos de agrupamento. Nesta tese, o GSO é adaptado ao contexto de análise de agrupamentos particional. Modelos híbridos entre o GSO e o K-Means são apresentados, de modo a agregar o potencial de exploração oferecido pelas buscas globais do GSO à velocidade de exploitação de regiões locais oferecida pelo K-Means, fazendo com que os sistemas híbridos formados sejam capazes de oferecerem boas soluções aos problemas de agrupamento tratados. O trabalho apresenta um estudo da influência do K-Means quando usado como operador de busca local para a inicialização populacional do GSO, assim como operador para refinamento da melhor solução encontrada pela população do GSO durante o processo geracional desenvolvido por esta técnica. Uma versão cooperativa coevolucionária do modelo GSO também foi adaptada ao contexto da análise de agrupamentos particional, resultando em um método com grande potencial para o paralelismo, assim como para uso em aplicações de agrupamentos distribuídos. Os resultados experimentais, realizados tanto com bases de dados reais, quanto com o uso de conjuntos de dados sintéticos, apontam o potencial dos modelos alternativos de inicialização da população propostos para o GSO, assim como de sua versão cooperativa coevolucionária, ao lidar com problemas tradicionais de agrupamento de dados, como a sobreposição entre as classes do problema, classes desbalanceadas, dentre outros, quando em comparação com métodos de agrupamento existentes na literatura. / Cluster analysis, also known as unsupervised learning, is an important technique for exploratory data analysis, and it has being widely employed in many applications such as data mining, image segmentation, bioinformatics, and so on. Clustering aims to distribute a data set in groups, in such a way that individuals from the same group are more closely related (more similar) among each other, while individuals from different groups have a high degree of dissimilarity among each other. From an optimization perspective, clustering is considered as a particular kind of NP-hard problem, belonging in the combinatorial optimization category. Traditional clustering techniques (like K-Means algorithm) may suffer some limitations when dealing with clustering task, such as the sensibility to the algorithm initialization, or the lack of mechanisms to help these methods to escape from local minima points. Meta-heuristics such as EAs and SI methods are nature-inspired global search techniques which have been increasingly applied to solve a great variety of difficult problems, given their capability to perform thorough searches through a problem space, attempting to avoid local optimum points. From the past few decades, EAs and SI approaches have been successfully applied to tackle clustering problems. In this context, Group Search Optimization (GSO) meta-heuristic has been successfully applied to solve hard optimization problems, obtaining better performances than traditional evolutionary techniques, such as Genetic Algorithms (GA) and Particle Swarm Optimization (PSO). In clustering context, EAs an SIs are able to obtain good global solutions to the problem at hand, however, according to their stochastic nature, these approaches may have slow convergence rates in comparison to other clustering methods. In this thesis, GSO is adapted to the context of partitional clustering analysis. Hybrid models of GSO and K-Means are presented, in such a way that the exploration offered by GSO global searches are combined with fast exploitation of local regions provided by K-Means, generating new hybrid systems capable of obtaining good solutions to the clustering problems at hands. The work also presents a study on the influence of K-Means when adopted as a local search operator for GSO population initialization, just like its application as an refinement operator for the best solution found by GSO population during GSO generative process. A cooperative coevolutionary variant of GSO model is adapted to the context of partitional clustering, resulting in a method with great potential to parallelism, as much as for the use in distributed clustering applications. Experimental results, performed as with the use of real data sets, as with the use of synthetic data sets, showed the potential of proposed alternative population initialization models and the potential of GSO cooperative coevolutionary variant when dealing with classic clustering problems, such as data overlapping, data unbalancing, and so on, in comparison to other clustering algorithms from literature.