Image Segmentation Using Ant System-based Clustering Algorithm

Industrial applications of computer vision sometimes require detection of atypical objects that occur as small groups of pixels in digital images. These objects are difficult to single out because they are small and randomly distributed. In this work we propose an image segmentation method using the novel Ant System-based Clustering Algorithm (ASCA). ASCA models the foraging behaviour of ants, which move through the data space searching for high data-density regions, and leave pheromone trails on their path. The pheromone map is used to identify the exact number of clusters, and assign the pixels to these clusters using the pheromone gradient. We applied ASCA to detection of microcalcifications in digital mammograms and compared its performance with state-of-the-art clustering algorithms such as 1D Self-Organizing Map, k-Means, Fuzzy c-Means and Possibilistic Fuzzy c-Means. The main advantage of ASCA is that the number of clusters needs not to be known a priori. The experimental results show that ASCA is more efficient than the other algorithms in detecting small clusters of atypical data.

A theoretical consideration of the parameters of the Max Min Ant System

In this thesis we will discuss the setting of the parameters of the Max-Min Ant System. In the literature it is possible to find theoretical and practical considerations of these parameters, nevertheless it seems that they have not been studied in a joint manner. We propose a theoretical study of the relationship between them, giving the user some further knowledge at the time of setting the algorithm's parameters and some new idea are proposed. In particular, the number of ants is studied in more detail. Then we will study the settings of the Tmax and Tmin in a way which is diferent from the most commonly used technique, taking in consideration theoretical as well as experimental problems. Finally, some experiments are shown that demonstrate the validity of our proposals.

Models for pheromone evaluation in Ant Systems for Mobile Ad-hoc networks

On a mobile ad-hoc network environment, where the resources are scarce, the knowledge about the network's link state is essential to optimize the routing procedures. This paper presents a study about different pheromone evaluation models and how they react to possible changes in traffic rate. Observing how the pheromone value on a link changes, it could be possible to identify certain patterns which can indicate the path status. For this study, the behavior of the Ant System evaluation model was compared with a Temporal Active Pheromone model (a biological approach) and a Progressive Pheromone Reduction model with and without a maximum pheromone limit.

Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

NEW METHODOLOGY FOR FEEDER RECONFIGURATION IN DISTRIBUTION NETWORKS WITH DISTRIBUTED ENERGY RESOURCES

This doctoral Thesis defines and develops a new methodology for feeder reconfiguration in distribution networks with Distributed Energy Resources (DER). The proposed methodology is based on metaheuristic Ant Colony Optimization (ACO) algorithms. The methodology is called Item Oriented Ant System (IOAS) and the doctoral Thesis also defines three variations of the original methodology, Item Oriented Ant Colony System (IOACS), Item Oriented Max-min Ant System (IOMMAS) y Item Oriented Max-min Ant Colony System (IOACS). All methodologies pursue a twofold objective, to minimize the power losses and maximize DER penetration in distribution networks. The aim of the variations is to find the algorithm that adapts better to the present optimization problem, solving it most efficiently. The main feature of the methodology lies in the fact that the heuristic information and the exploitation information (pheromone) are attached to the item not to the path. Besides, the doctoral Thesis proposes to use feeder reconfiguration in order to increase the distribution network capacity of accepting a major degree of DER. The proposed methodology and its three variations have been tested and verified in two distribution networks well documented in the existing bibliography. These networks have been modeled and used to test all proposed methodologies for different scenarios with various DER penetration degrees.

Roteamento em redes embutidas utilizando otimização por colônia de formigas.

Redes embutidas (NoC, Network-on-Chip) vêm sendo adotadas como uma solução interessante para o projeto de infraestruturas de comunicação em sistemas embutidos (SoC, System-on-Chip). Estas redes são em geral parametrizadas, podendo assim ser utilizadas em vários projetos de SoCs, cada qual com diferentes quantidades de núcleos. NoCs permitem uma escalabilidade dos sistemas, ao mesmo tempo que balanceiam a comunicação entre núcleos. Projetos baseados em NoC visam a implementação de uma aplicação específica. Neste contexto, ferramentas de auxílio de projeto são essenciais. Estas ferramentas são projetadas para, a partir de uma descrição simples da aplicação, realizar sucessivos processos de otimização que irão modelar as várias características do sistema. Estes algoritmos de otimização são necessários para que a rede atenda a um conjunto de restrições, como área, consumo de energia e tempo de execução. Dentre estas etapas, pode ser incluído o roteamento estático. As rotas através da rede por onde os núcleos irão se comunicar são otimizadas, de forma a minimizar o tempo de comunicação e os atrasos na transmissão de pacotes ocasionados por congestionamentos nas chaves que compõem a NoC. Nesta dissertação, foi utilizada a otimização por colônia de formigas no cálculo dos percursos. Esta é uma meta-heurística interessante para a solução de problemas de busca em grafos, inspirada no comportamento de formigas reais. Para os algoritmos propostos, múltiplas colônias são utilizadas, cada uma encarregada pela otimização do percurso de uma mensagem. Os diferentes testes realizados mostram o roteamento baseado no Elitist Ant System obtendo resultados superiores a outros algoritmos de roteamento.

Investigation of population genetic structure and mating system in the ant Pheidole pallidula

The origin of eusociality in haplo-diploid organisms such as Hymenoptera has been mostly explained by kin selection. However, several studies have uncovered decreased relatedness values within colonies, resulting primarily from multiple queen matings (polyandry) and/or from the presence of more than one functional queen (polygyny). Here, we report on the use of microsatellite data for the investigation of sociogenetic parameters, such as relatedness, and levels of polygyny and polyandry, in the ant Pheidole pallidula. We demonstrate, through analysis of mother-offspring combinations and the use of direct sperm typing, that each queen is inseminated by a single male. The inbreeding coefficient within colonies and the levels of relatedness between the queens and their mate are not significantly different from zero, indicating that matings occur between unrelated individuals. Analyses of worker genotypes demonstrate that 38% of the colonies are polygynous with 2-4 functional queens, and suggest the existence of reproductive skew, i.e. unequal respective contribution of queens to reproduction. Finally, our analyses indicate that colonies are genetically differentiated and form a population exhibiting significant isolation-by-distance, suggesting that some colonies originate through budding.

Ant colony system based approach to single machine scheduling problems: weighted tardiness scheduling problem

The paper introduces an approach to solve the problem of generating a sequence of jobs that minimizes the total weighted tardiness for a set of jobs to be processed in a single machine. An Ant Colony System based algorithm is validated with benchmark problems available in the OR library. The obtained results were compared with the best available results and were found to be nearer to the optimal. The obtained computational results allowed concluding on their efficiency and effectiveness.

Female reproductive system of ant species of the subfamily ponerinae: Review and new data

Literature data about the female reproductive system of some species in the subfamily Ponerinae are presented. Our project objective to compile a report containing the largest possible number of data about the reproductive system in Ponerinae for a better understanding of the reproductive biology of these Insects, was completed.

On the morphology of the digestive system of two Moomorium ant species

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

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.