Análisis de la eficiencia de los sistemas de colonias de hormigas para problemas de accesibilidad

A pesar de los avances en materia de predicción, los desastres naturales siguen teniendo consecuencias devastadoras. Entre los principales problemas a los que se enfrentan los equipos de ayuda y rescate después de un desastre natural o provocado por el hombre se encuentra la planificación de las tareas de reparación de carreteras para conseguir la máxima ventaja de los limitados recursos económicos y humanos. En la presente Tesis Fin de Máster se intenta dar solución al problema de la accesibilidad, es decir, maximizar el número de supervivientes que consiguen alcanzar el centro regional más cercano en un tiempo mínimo mediante la planificación de qué carreteras rurales deberían ser reparadas dados unos recursos económicos y humanos limitados. Como se puede observar, es un problema combinatorio ya que el número de planes de reparación y conexiones entre las ciudades y los centros regionales crece de forma exponencial con el tamaño del problema. Para la resolución del problema se comienza analizando una adaptación básica de los sistemas de colonias de hormigas propuesta por otro autor y se proponen múltiples mejoras sobre la misma. Posteriormente, se propone una nueva adaptación más avanzada de los sistemas de colonias de hormiga al problema, el ACS con doble hormiga. Este sistema hace uso de dos tipos distintos de hormigas, la exploradora y la trabajadora, para resolver simultáneamente el problema de encontrar los caminos más rápidos desde cada ciudad a su centro regional más cercano (exploradora), y el de obtener el plan óptimo de reparación que maximice la accesibilidad de la red (trabajadora). El algoritmo propuesto se ilustra por medio de un ejemplo de gran tamaño que simula el desastre natural ocurrido en Haití, y su rendimiento es comparado con la combinación de dos metaheurísticas, GRASP y VNS.---ABSTRACT---In spite of the advances in forecasting, natural disaster continue to ocasionate devastating consequences. One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work to take maximum advantage of the limited available financial and human resources. In this Master´s Final Project we account for the accesability issue, that is, to maximize the number of survivors that reach the nearest regional center in a minimum time by planning whic rural roads should be repaired given the limited financial and human resources. This is a combinatorial problem since the number of possible repairing solutions and connections between cities and regional centers grows exponentially with the size of the problem. In order to solve the problem, we analyze the basic ant colony system adaptation proposed by another author and point out multiple improvements on it. Then, we propose a novel and more advance adaptation of the ant colony systems to the problem, the double- ant ACS. This system makes use of two diferent type of ants, the explorer and the worker, to simultaneously solve the problem of finding the shorthest paths from each city to their nearest regional center (explorer), and the problem of identifying the optimal repairing plan that maximize the network accesability (worker). The proposed algorithm is illustrated by means of a big size example that simulates the natural disaster occurred in Haiti, and its performance is compared with a combination of two metaheuristics, GRASP and VNS.

Analysing the complexity of the model-based decision making processes within the industrial management context

PURPOSE The decision-making process plays a key role in organizations. Every decision-making process produces a final choice that may or may not prompt action. Recurrently, decision makers find themselves in the dichotomous question of following a traditional sequence decision-making process where the output of a decision is used as the input of the next stage of the decision, or following a joint decision-making approach where several decisions are taken simultaneously. The implication of the decision-making process will impact different players of the organization. The choice of the decision- making approach becomes difficult to find, even with the current literature and practitioners’ knowledge. The pursuit of better ways for making decisions has been a common goal for academics and practitioners. Management scientists use different techniques and approaches to improve different types of decisions. The purpose of this decision is to use the available resources as well as possible (data and techniques) to achieve the objectives of the organization. The developing and applying of models and concepts may be helpful to solve managerial problems faced every day in different companies. As a result of this research different decision models are presented to contribute to the body of knowledge of management science. The first models are focused on the manufacturing industry and the second part of the models on the health care industry. Despite these models being case specific, they serve the purpose of exemplifying that different approaches to the problems and could provide interesting results. Unfortunately, there is no universal recipe that could be applied to all the problems. Furthermore, the same model could deliver good results with certain data and bad results for other data. A framework to analyse the data before selecting the model to be used is presented and tested in the models developed to exemplify the ideas. METHODOLOGY As the first step of the research a systematic literature review on the joint decision is presented, as are the different opinions and suggestions of different scholars. For the next stage of the thesis, the decision-making process of more than 50 companies was analysed in companies from different sectors in the production planning area at the Job Shop level. The data was obtained using surveys and face-to-face interviews. The following part of the research into the decision-making process was held in two application fields that are highly relevant for our society; manufacturing and health care. The first step was to study the interactions and develop a mathematical model for the replenishment of the car assembly where the problem of “Vehicle routing problem and Inventory” were combined. The next step was to add the scheduling or car production (car sequencing) decision and use some metaheuristics such as ant colony and genetic algorithms to measure if the behaviour is kept up with different case size problems. A similar approach is presented in a production of semiconductors and aviation parts, where a hoist has to change from one station to another to deal with the work, and a jobs schedule has to be done. However, for this problem simulation was used for experimentation. In parallel, the scheduling of operating rooms was studied. Surgeries were allocated to surgeons and the scheduling of operating rooms was analysed. The first part of the research was done in a Teaching hospital, and for the second part the interaction of uncertainty was added. Once the previous problem had been analysed a general framework to characterize the instance was built. In the final chapter a general conclusion is presented. FINDINGS AND PRACTICAL IMPLICATIONS The first part of the contributions is an update of the decision-making literature review. Also an analysis of the possible savings resulting from a change in the decision process is made. Then, the results of the survey, which present a lack of consistency between what the managers believe and the reality of the integration of their decisions. In the next stage of the thesis, a contribution to the body of knowledge of the operation research, with the joint solution of the replenishment, sequencing and inventory problem in the assembly line is made, together with a parallel work with the operating rooms scheduling where different solutions approaches are presented. In addition to the contribution of the solving methods, with the use of different techniques, the main contribution is the framework that is proposed to pre-evaluate the problem before thinking of the techniques to solve it. However, there is no straightforward answer as to whether it is better to have joint or sequential solutions. Following the proposed framework with the evaluation of factors such as the flexibility of the answer, the number of actors, and the tightness of the data, give us important hints as to the most suitable direction to take to tackle the problem. RESEARCH LIMITATIONS AND AVENUES FOR FUTURE RESEARCH In the first part of the work it was really complicated to calculate the possible savings of different projects, since in many papers these quantities are not reported or the impact is based on non-quantifiable benefits. The other issue is the confidentiality of many projects where the data cannot be presented. For the car assembly line problem more computational power would allow us to solve bigger instances. For the operation research problem there was a lack of historical data to perform a parallel analysis in the teaching hospital. In order to keep testing the decision framework it is necessary to keep applying more case studies in order to generalize the results and make them more evident and less ambiguous. The health care field offers great opportunities since despite the recent awareness of the need to improve the decision-making process there are many opportunities to improve. Another big difference with the automotive industry is that the last improvements are not spread among all the actors. Therefore, in the future this research will focus more on the collaboration between academia and the health care sector.

A socio-economic approach to online vision graph generation and handover in distributed smart camera networks

In this paper we propose an approach based on self-interested autonomous cameras, which exchange responsibility for tracking objects in a market mechanism, in order to maximise their own utility. A novel ant-colony inspired mechanism is used to grow the vision graph during runtime, which may then be used to optimise communication between cameras. The key benefits of our completely decentralised approach are on the one hand generating the vision graph online which permits the addition and removal cameras to the network during runtime and on the other hand relying only on local information, increasing the robustness of the system. Since our market-based approach does not rely on a priori topology information, the need for any multi-camera calibration can be avoided. © 2011 IEEE.

Socio-economic vision graph generation and handover in distributed smart camera networks

In this article we present an approach to object tracking handover in a network of smart cameras, based on self-interested autonomous agents, which exchange responsibility for tracking objects in a market mechanism, in order to maximise their own utility. A novel ant-colony inspired mechanism is used to learn the vision graph, that is, the camera neighbourhood relations, during runtime, which may then be used to optimise communication between cameras. The key benefits of our completely decentralised approach are on the one hand generating the vision graph online, enabling efficient deployment in unknown scenarios and camera network topologies, and on the other hand relying only on local information, increasing the robustness of the system. Since our market-based approach does not rely on a priori topology information, the need for any multicamera calibration can be avoided. We have evaluated our approach both in a simulation study and in network of real distributed smart cameras.

Improved adaptivity and robustness in decentralised multi-camera networks

In this paper we present increased adaptivity and robustness in distributed object tracking by multi-camera networks using a socio-economic mechanism for learning the vision graph. To build-up the vision graph autonomously within a distributed smart-camera network, we use an ant-colony inspired mechanism, which exchanges responsibility for tracking objects using Vickrey auctions. Employing the learnt vision graph allows the system to optimise its communication continuously. Since distributed smart camera networks are prone to uncertainties in individual cameras, such as failures or changes in extrinsic parameters, the vision graph should be sufficiently robust and adaptable during runtime to enable seamless tracking and optimised communication. To better reflect real smart-camera platforms and networks, we consider that communication and handover are not instantaneous, and that cameras may be added, removed or their properties changed during runtime. Using our dynamic socio-economic approach, the network is able to continue tracking objects well, despite all these uncertainties, and in some cases even with improved performance. This demonstrates the adaptivity and robustness of our approach.

'Artificial Immune Systems: A new Decision Making Paradigm for Operational Research'

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here

A New Paradigm for Heuristic Decision Making, Invited Keynote Talk

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here.

Artificial Bee Colony (ABC) for multi-objective design optimization of composite structures

In this paper, we present a generic method/model for multi-objective design optimization of laminated composite components, based on Vector Evaluated Artificial Bee Colony (VEABC) algorithm. VEABC is a parallel vector evaluated type, swarm intelligence multi-objective variant of the Artificial Bee Colony algorithm (ABC). In the current work a modified version of VEABC algorithm for discrete variables has been developed and implemented successfully for the multi-objective design optimization of composites. The problem is formulated with multiple objectives of minimizing weight and the total cost of the composite component to achieve a specified strength. The primary optimization variables are the number of layers, its stacking sequence (the orientation of the layers) and thickness of each layer. The classical lamination theory is utilized to determine the stresses in the component and the design is evaluated based on three failure criteria: failure mechanism based failure criteria, maximum stress failure criteria and the tsai-wu failure criteria. The optimization method is validated for a number of different loading configurations-uniaxial, biaxial and bending loads. The design optimization has been carried for both variable stacking sequences, as well fixed standard stacking schemes and a comparative study of the different design configurations evolved has been presented. Finally the performance is evaluated in comparison with other nature inspired techniques which includes Particle Swarm Optimization (PSO), Artificial Immune System (AIS) and Genetic Algorithm (GA). The performance of ABC is at par with that of PSO, AIS and GA for all the loading configurations. (C) 2009 Elsevier B.V. All rights reserved.

Colony sex ratios vary with breeding structure but not relatedness asymmetry in the facultatively polygynous ant Pheidole pallidula

We investigated sex allocation in a Mediterranean population of the facultatively polygynous (multiple queen per colony) ant Pheidole pallidula. This species shows a strong split sex ratio, with most colonies producing almost exclusively a single-sex brood. Our genetic (microsatellite) analyses reveal that P. pallidula has an unusual breeding system, with colonies being headed by a single or a few unrelated queens. As expected in such a breeding system, our results show no variation in relatedness asymmetry between monogynous (single queen per colony) and polygynous colonies. Nevertheless, sex allocation was tightly associated with the breeding structure, with monogynous colonies producing a male-biased brood and polygynous colonies almost only females. In addition, sex allocation was closely correlated with colony total sexual productivity. Overall, our data show that when colonies become more productive (and presumably larger) they shift from monogyny to polygyny and from male production to female production, a pattern that has never been reported in social insects.

Covariation between colony social structure and immune defences of workers in the ant Formica selysi

Several ant species vary in the number of queens per colony, yet the causes and consequences of this variation remain poorly understood. In previous experiments, we found that Formica selysi workers originating from multiple-queen (=polygyne) colonies had a lower resistance to a fungal pathogen than workers originating from single-queen (=monogyne) colonies. In contrast, group diversity improved disease resistance in experimental colonies. This discrepancy between field and experimental colonies suggested that variation in social structure in the field had antagonistic effects on worker resistance, possibly through a down-regulation of the immune system balancing the positive effect of genetic diversity. Here, we examined if workers originating from field colonies with alternative social structure differed in three major components of their immune system. We found that workers from polygyne colonies had a lower bacterial growth inhibitory activity than workers from monogyne colonies. In contrast, workers from the two types of colonies did not differ significantly in bacterial cell wall lytic activity and prophenoloxidase activity. Overall, the presence of multiple queens in a colony correlated with a slight reduction in one inducible component of the immune system of individual workers. This reduced level of immune defence might explain the lower resistance of workers originating from polygyne colonies despite the positive effect of genetic diversity. More generally, these results indicate that social changes at the group level can modulate individual immune defences.

Colony dehydration and water collection by specialized caste in the leaf-cutting ant Atta sexdens rubropilosa

Social organization enables leaf-cutting ants to keep appropriate micro-ecological nest conditions for the fungus garden (their main food), eggs, larvae and adults. To maintain stability while facing changing conditions, individual ants must perceive destabilising factors and produce a proper behavioral response. We investigated behavioral responses to experimental dehydration in leaf-cutting ants to verify if task specialization exists, and to quantify the ability of ant sub-colonies for water management. Our setup consisted of fourteen sub-colonies, ten of which were randomly assigned to different levels of experimental dehydration with silica gel, whereas the remaining four were controls. The ten experimental sub-colonies were split into two groups, so that five of them had access to water. Diverse ant morphs searched for water in dehydrated colonies, but mainly a caste of small ants collected water after sources had been discovered. Size specialization for water collection was replicable in shorter experiments with three additional colonies. Ants of dehydrated colonies accumulated leaf-fragments on the nest entrance, and covering the fungus garden. Behaviors that may enhance humidity within the nests were common to all dehydration treatments. Water availability increased the life span of dehydrated colonies.

Digging effort in leaf-cutting ant queens (Atta sexdens rubropilosa) and its effects on survival and colony growth during the claustral phase

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

SPATIAL-ORGANIZATION OF FORAGING ACTIVITY AND COLONIZATION BY COLONY EMIGRATION IN THE PHARAOH ANT, MONOMORIUM-PHARAONIS

Using food bait stations and colony trap nests, the spatial relation between the foraging activity of established colonies of the polygynous and unicolonial exotic pharaoh's ant, Monomorium pharaonis, and colonization by colony fragments was studied over an 8 month period in a large institutional setting in Brazil. Both foraging activity and colonizations demonstrated significant spatial clumping. However, colonizations were significantly negatively clumped spatially with respect to foraging activity. This suggests that the colonization strategy of this species under the studied conditions was that of complete habitat domination.

Causes and consequences of inbreeding in the ant Formica exsecta

Human actions cause destruction and fragmentation of natural habitats, predisposing populations to loss of genetic diversity and inbreeding, which may further decrease their fitness and survival. Understanding these processes is a main concern in conservation genetics. Yet data from natural populations is scarce, particularly on invertebrates, owing to difficulties in measuring both fitness and inbreeding in the wild. Ants are social insects, and a prime example of an ecologically important group for which the effects of inbreeding remain largely unstudied. Social insects serve key roles in all terrestrial ecosystems, and the division of labor between the females in the colonies queens reproduce, workers tend to the developing brood probably is central to their ecological success. Sociality also has important implications for the effects of inbreeding. Despite their relative abundance, the effective population sizes of social insects tend to be small, owing to the low numbers of reproductive individuals relative to the numbers of sterile workers. This may subject social insects to loss of genetic diversity and subsequent inbreeding depression. Moreover, both the workers and queens can be inbred, with different and possibly multiplicative consequences. The aim of this study was to investigate causes and consequences of inbreeding in a natural population of ants. I used a combination of long-term field and genetic data from colonies of the narrow-headed ant Formica exsecta to examine dispersal, mating behavior and the occurrence of inbreeding, and its consequences on individual and colony traits. Mating in this species takes place in nuptial flights that have been assumed to be population-wide and panmictic. My results, however, show that dispersal is local, with queens establishing new colonies as close as 60 meters from their natal colony. Even though actual sib-mating was rare, individuals from different but related colonies pair, which causes the population to be inbred. Furthermore, multiple mates of queens were related to each other, which also indicates localized mating flights. Hence, known mechanisms of inbreeding avoidance, dispersal and multiple mating, were not effective in this population, as neither reduced inbreeding level of the future colony. Inbreeding had negative consequences both at the individual and colony level. A queen that has mated with a related male produces inbred workers, which impairs the colony s reproductive success. The inbred colonies were less productive and, specifically, produced fewer new queens, possibly owing to effects of inbreeding on the caste determination of female larvae. A striking finding was that males raised in colonies with inbred workers were smaller, which reflects an effect of the social environment as males, being haploid, cannot be inbred themselves. The queens produced in the inbred colonies, in contrast, were not smaller, but their immune response was up-regulated. Inbreeding had no effect on queen dispersal, but inbred queens had a lower probability of successfully founding a new colony. Ultimately, queens that survived through the colony founding phase had a shorter lifespan. This supports the idea that inbreeding imposes a genetic stress, leading to inbreeding depression on both the queen and the colony level. My results show that inbreeding can have profound consequences on insects in the wild, and that in social species the effects of inbreeding may be multiplicative and mediated through the diversity of the social environment, as well as the genetic makeup of the individuals themselves. This emphasizes the need to take into account all levels of organization when assessing the effects of genetic diversity in social animals.