Social and temporal organization in an ant colony

Ant colonies are known for their complex and efficient social organization that com-pletely lacks hierarchical structure. However, due to methodological difficulties in follow¬ing all ants of a colony, it was until now impossible to investigate the social and temporal organization of colonies. We developed a tracking system that allows tracking the posi¬tions and orientations of several hundred individually labeled ants continuously, providing for the first time quantitative long term data on all individuals of a colony. These data permit reconstructing trajectories, activity patterns and social networks of all ants in a colony and enable us to investigate ant behavior quantitatively in previously unpreceded ways. By analyzing the spatial positions and social interactions of all ants in six colonies for 41 days we show that ant colonies are organized in groups of nurses, nest patrollers and foragers. Workers of each group were highly interconnected and occupied similar spa¬tial locations in the nest. Groups strongly segregated spatially, and were characterized by unique behavioral signatures. Nurses spent most of their time on the brood. Nest patrollers frequently visited the rubbish pile, and foragers frequently visited the forag¬ing arena. In addition nurses were on average younger than nest patrollers who were, in turn, younger than foragers. We further show that workers had a preferred behav¬ioral trajectory and moved from nursing to nest patrolling, and from nest patrolling to foraging. By analyzing the activity patterns of all ants we show that only a third of all workers in a colony exhibit circadian rhythms and that these rhythms shortened by on av¬erage 42 minutes in constant darkness, thereby demonstrating the presence of a functional endogenous clock. Most rhythmic workers were foragers suggesting that rhythmicity is tightly associated with task. Nurses and nest patrollers were arrhythmic which most likely reflects plasticity of the circadian clock, as isolated workers in many species exhibit circadian rhythmicity. Altogether our results emphasize that ant colonies, despite their chaotic appearance, repose on a strong underlying social and temporal organization. - Les colonies de fourmis sont connues pour leur organisation sociale complexe et effi-cace, charactérisée par un manque absolu de structure hiérarchique. Cependant, puisqu'il est techniquement très difficile de suivre toutes les fourmis d'une colonie, il a été jusqu'à maintenant impossible d'étudier l'organisation sociale et temporelle des colonies de four-mis. Nous avons développé un système qui permet d'extraire en temps réel à partir d'images vidéo les positions et orientations de plusieurs centaines de fourmis marquées individuellement. Nous avons pu ainsi générer pour la première fois des données quanti-tatives et longitudinales relatives à des fourmis appartenant à une colonie. Ces données nous ont permis de reconstruire la trajectoire et l'activité de chaque fourmi ainsi que ses réseaux sociaux. Ceci nous a permis d'étudier de manière exhaustive et objective le com-portement de tous les individus d'une colonie. En analysant les données spatiales et les interactions sociales de toutes les fourmis de six colonies qui ont été filmées pendant 41 jours, nous montrons que les fourmis d'une même colonie se répartissent en trois groupes: nourrices, patrouilleuses et approvisionneuses. Les fourmis d'un même groupe interagis-sent fréquemment et occupent le même espace à l'intérieur du nid. L'espace propre à un groupe se recoupe très peu avec celui des autres. Chaque groupe est caractérisé par un comportement typique. Les nourrices s'affairent surtout autour du couvain. Les pa-trouilleuses font de fréquents déplacements vers le tas d'ordures, et les approvisionneuses sortent souvent du nid. Les nourrices sont en moyenne plus jeunes que les patrouilleuses qui, à leur tour, sont plus jeunes que les approvisionneuses. De plus, nous montrons que les ouvrières changent de tâche au cours de leur vie, passant de nourrice à patrouilleuse puis à approvisionneuse. En analysant l'activité de chaque fourmi, nous montrons que seulement un tiers des ouvrières d'une colonie présente des rythmes circadiens et que ces rythmes diminuent en moyenne de 42 minutes lorsqu'il y a obscurité constante, ce qui démontre ainsi la présence d'une horloge endogène. De plus, la plupart des approvi¬sionneuses ont une activité rythmique alors que les nourrices et patrouilleuses présentent une activité arythmique, ce qui suggère que la rythmicité est étroitement associée à la tâche. L'arythmie des nourrices et patrouilleuses repose probablement sur une plasticité de l'horloge endogène car des ouvrières de nombreuses espèces font preuve d'une ryth¬micité circadienne lorsqu'elles sont isolées de la colonie. Dans l'ensemble nos résultats révèlent qu'une colonie de fourmis se fonde sur une solide organisation sociale et tem¬porelle malgré son apparence chaotique.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

Architecture for peer-to-peer databases with routing queries using ant colony algorithm and semantic support

In a peer-to-peer network, the nodes interact with each other by sharing resources, services and information. Many applications have been developed using such networks, being a class of such applications are peer-to-peer databases. The peer-to-peer databases systems allow the sharing of unstructured data, being able to integrate data from several sources, without the need of large investments, because they are used existing repositories. However, the high flexibility and dynamicity of networks the network, as well as the absence of a centralized management of information, becomes complex the process of locating information among various participants in the network. In this context, this paper presents original contributions by a proposed architecture for a routing system that uses the Ant Colony algorithm to optimize the search for desired information supported by ontologies to add semantics to shared data, enabling integration among heterogeneous databases and the while seeking to reduce the message traffic on the network without causing losses in the amount of responses, confirmed by the improve of 22.5% in this amount. © 2011 IEEE.

Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony

Pós-graduação em Ciência da Computação - IBILCE

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

Ottimizzazione mediante ant colonies del tempo di evacuazione dei passeggeri dagli aerei da trasporto

Sviluppo di un modello di ottimizzazione dei tempi di evacuazione da aerei da trasporto mediante disposizione intelligente dei passeggeri effettuata con un algoritmo basato sulla Ant Colony Optimization.

An Ant Colony System adaptation to deal with accessibility issues after a disaster

One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work tasks to take maximum advantage of the limited available financial and human resources. Previous research focused on speeding up repair work or on selecting the location of health centers to minimize transport times for injured citizens. In spite of the good results, this research does not take into account another key factor: survivor accessibility to resources. In this paper we account for the accessibility issue, that is, we maximize the number of survivors that reach the nearest regional center (cities where economic and social activity is concentrated) in a minimum time by planning which rural roads should be repaired given the available financial and human resources. This is a combinatorial problem since the number of connections between cities and regional centers grows exponentially with the problem size, and exact methods are no good for achieving an optimum solution. In order to solve the problem we propose using an Ant Colony System adaptation, which is based on ants? foraging behavior. Ants stochastically build minimal paths to regional centers and decide if damaged roads are repaired on the basis of pheromone levels, accessibility heuristic information and the available budget. The proposed algorithm is illustrated by means of an example regarding the 2010 Haiti earthquake, and its performance is compared with another metaheuristic, GRASP.

Estado da Arte da Computação Evolutiva Aplicada à Eletrónica

A Computação Evolutiva enquadra-se na área da Inteligência Artificial e é um ramo das ciências da computação que tem vindo a ser aplicado na resolução de problemas em diversas áreas da Engenharia. Este trabalho apresenta o estado da arte da Computação Evolutiva, assim como algumas das suas aplicações no ramo da eletrónica, denominada Eletrónica Evolutiva (ou Hardware Evolutivo), enfatizando a síntese de circuitos digitais combinatórios. Em primeiro lugar apresenta-se a Inteligência Artificial, passando à Computação Evolutiva, nas suas principais vertentes: os Algoritmos Evolutivos baseados no processo da evolução das espécies de Charles Darwin e a Inteligência dos Enxames baseada no comportamento coletivo de alguns animais. No que diz respeito aos Algoritmos Evolutivos, descrevem-se as estratégias evolutivas, a programação genética, a programação evolutiva e com maior ênfase, os Algoritmos Genéticos. Em relação à Inteligência dos Enxames, descreve-se a otimização por colônia de formigas e a otimização por enxame de partículas. Em simultâneo realizou-se também um estudo da Eletrónica Evolutiva, explicando sucintamente algumas das áreas de aplicação, entre elas: a robótica, as FPGA, o roteamento de placas de circuito impresso, a síntese de circuitos digitais e analógicos, as telecomunicações e os controladores. A título de concretizar o estudo efetuado, apresenta-se um caso de estudo da aplicação dos algoritmos genéticos na síntese de circuitos digitais combinatórios, com base na análise e comparação de três referências de autores distintos. Com este estudo foi possível comparar, não só os resultados obtidos por cada um dos autores, mas também a forma como os algoritmos genéticos foram implementados, nomeadamente no que diz respeito aos parâmetros, operadores genéticos utilizados, função de avaliação, implementação em hardware e tipo de codificação do circuito.

Incorporating waiting time in competitive location models: formulations and heuristics

In this paper we propose a metaheuristic to solve a new version of the Maximum Capture Problem. In the original MCP, market capture is obtained by lower traveling distances or lower traveling time, in this new version not only the traveling time but also the waiting time will affect the market share. This problem is hard to solve using standard optimization techniques. Metaheuristics are shown to offer accurate results within acceptable computing times.

Incorporating waiting time in competitive location models: Formulations and heuristics

In this paper we propose a metaheuristic to solve a new version of the Maximum CaptureProblem. In the original MCP, market capture is obtained by lower traveling distances or lowertraveling time, in this new version not only the traveling time but also the waiting time willaffect the market share. This problem is hard to solve using standard optimization techniques.Metaheuristics are shown to offer accurate results within acceptable computing times.

Optimización del sistema de transporte en el colegio The English School

La optimización de sistemas y modelos se ha convertido en uno de los factores más importantes a la hora de buscar la mayor eficiencia de un proceso. Este concepto no es ajeno al transporte escolar, ambiente que cambia constantemente al ritmo de las necesidades de sus clientes, y que responde ante una fuerte responsabilidad frente a sus usuarios, los niños que hacen uso del servicio, en cuanto al cumplimiento de tiempos y seguridad, mientras busca constantemente la reducción de costos. Este proyecto expone las problemáticas presentadas en The English School en esta área y propone un modelo de optimización simple que permitirá notables mejoras en términos de tiempos y costos, de tal forma que genere beneficios para la institución en términos financieros y de satisfacción al cliente. Por medio de la implementación de este modelo será posible identificar errores comunes del proceso, se identificarán soluciones prácticas de fácil aplicación en el manejo del transporte y se presentarán los resultados obtenidos en la muestra utilizada para desarrollar el proyecto.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

Fundamentos de otimização por inteligência de enxames: uma visão geral

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.

Contributions to underwater glider path planning

[ES] La Planificación de Rutas o Caminos es un disciplina de Robótica que trata la búsqueda de caminos factibles u óptimos. Para la mayoría de vehículos y entornos, no es un problema trivial y por tanto nos encontramos con un gran diversidad de algoritmos para resolverlo, no sólo en Robótica e Inteligencia Artificial, sino también como parte de la literatura de Optimización, con Métodos Numéricos y Algoritmos Bio-inspirados, como Algoritmos Genéticos y el Algoritmo de la Colonia de Hormigas. El caso particular de escenarios de costes variables es considerablemente difícil de abordar porque el entorno en el que se mueve el vehículo cambia con el tiempo. El presente trabajo de tesis estudia este problema y propone varias soluciones prácticas para aplicaciones de Robótica Submarina.