ANTS-CLUSTERING ALGORITHM FOR BEST MEMORY UTILIZATION

Manjula S1, Shivamurthaiah M2
1, 2 Department of Studies in Computer Science, Davangere University,
Shivagangothri, Davangere, (India)

ABSTRACT

The Artificial Intelligence is playing vital role in the area of Swarm Intelligence, which is a study of bio inspired behaviour of insects, with the help of SI we are trying to make the implementation biological behaviour in computational area, such as Swarm intelligence in optimization, swarm robotics, routing protocols for next generation network, evolution of self organization, dynamic optimization problem. An agent based approach to self organized production and organic computing. This paper is mainly concentrating on one of the features of organic computing that is ants clustering techniques. This organic computing systems should possess self – x properties have a decentralized control and adaptive to changing requirements to their user. This clustering technique is implemented based on random selection or initialization of basic objects and fixing their threshold values and clustering will be worked with the help of similarities and dissimilarity behaviour of an item.

Keywords: Ants Colony, Clustering, Swarm Intelligence.

  1. INTRODUCTION

Swarm Intelligence is an interesting area of research which has interlinked with Artificial Intelligence discipline. The Artificial Intelligence is nothing but requiring human intelligence, to implant knowledge to machine, so that work/problem to be solved. Swarm Intelligence emerged out social insect collective behaviour shows many interesting properties such as flexibility, robustness, decentralization and self organization. This is implemented based on natural support or by inspiration from natural insects such as ants, bees and swarm, the life style or living behaviour of these insects made the researchers to implement this technique in the area of computation. The functions performed by these insects are based on team or group work. The representation of group is technically termed as “Clustering”. This clustering aims at representing large datasets by fever number of prototypes or clusters. This technique is one of the key tasks of data mining. It is also a current area of research. Clustering can be defined as the act of partitioning an unlabeled data set into groups of similar objects/items. This similar property of group is known as cluster. The dissimilarity of object is represented as different group. Hence dissimilarity is usually represented between the clusters. This cluster analysis has played a central role in the field of engineering, computer science, life and medical science, earth science and social science.

  1. SWARM INTELLIGENCE

This Swarm intelligence is a relatively new interdisciplinary field of research, which has gained huge population in today‟s research area. The implementation of Swarm Intelligence is as same as Artificial Intelligence that means through the design of algorithm. This improves several computational requirements on the relevant clustering techniques. A family of bio inspired algorithm has recently emerged that meets these requirements and has successfully been applied to a real world clustering problem. The behaviour of the natural swarms has influenced the design of algorithms and systems in computer science as following features:

  1. Collective transport of ants has inspired the design of controllers of robot for performing work coordination
  2. Brood sorting behaviour of ants motivated several clustering and sorting algorithm.
  3. The path finding and orientation skills of the ants are mainly used for implementation of ant colonial optimization.

The swarm intelligence algorithm mainly focuses on particle swarm optimization (PSO), Artificial Bees Colony (ABC) and Ants Colony System (ACS).

In this paper we are mainly focusing on swarm controlled emergence based on ant base clustering technique and this can be implemented with the help of Ants Colonial Optimization.

III. ANT COLONICAL OPTIMIZATION FOR CLUSTERING

Ant clustering refers to the behaviour of ants to cluster their brood (producing new ant) within the nest centre, or to cluster dead corpses (dead body) so that they transform so called cemeteries [1]. Both the phenomena can be seen as emergent behaviour which has been inspired biological insects. This living behaviour can be implemented in the area of computation based on ant clustering technique; this can be done with the help of distribution of items in two dimensional or n dimensional arrays.


It can be seen that many small clusters have been formed after 100000 simulation type steps with growing number of clusters becomes smaller and the size of the cluster increases [2]. The top left group represents less ants but more groups, right top group represents little bit less number of groups but number of ants in each group is more compare to left group. Down group represents number of clustering group is very small but number of ants in each cluster group is more compare to both the above groups Considering an ant as an agent walk randomly within the cell array/memory location and picks up an item that it finds with certain probability, carries it around, and drops it with a certain probability [3]. The mathematical implementation of picking up of an item can be represented as Pp = (k1/ (k1 + f)) 2

The dropping of an item is represented as Pd = (f/ (k1 + f)) 2.

Where f- is a fraction of cells in the neighbourhood of the agent and it can be compute the fraction of time stamp where agent moved across cells that are occupied by an item.

K1 & K2 – The threshold value of probability of picking up & dropping of an item.

The process of ant based clustering kind of algorithm can be generalized in different steps:

  1. Projection plane: All objects and ants are randomly projected, that means selected randomly and projected onto two dimensional planes which includes the speed of an ant, projected area or space and accuracy of the ants colony optimization.
  2. The randomly selected ants are clustered based on calculating the similarities of ant‟s behaviour or items.
  3. The dissimilarity of ant cluster is usually happens with neighbouring cluster ants where has dissimilarity will occur only between two different groups.
  4. Calculating the object picking up and dropping value based on number of time required to move across the cells „f‟ and with threshold value of probability.
  5. The direction of ant‟s movements along two dimensional representations, which represents the speed of an ant which can be chosen uniformly. It affects the likelihood of picking up and dropping objects.
  6. Repeat the steps from 2 to 5.

These steps mainly help in the creation of cluster and fixing values in memory position.

  1. ALGORITHM FOR ANT BASED CLUSTERING TECHNIQUE

Step1: Initialization of ant‟s population size, ant‟s movement speed, radius of projection plane and memory capacity.

Step2: Randomly place the object or items on the area/space and item will be fixed in one of the cells of the space.

Step3: The object is dropped along their location that is memory. The number of object/item is placing in the memory will check the size of memory.

Step4: Whenever the ant picks up a new item, it checks its memory to make comparison of items based on the similarity of an object, if any item is already present in memory with same property then it jumps to that particular location, & this prevent dropping object in unvisited place, this forms cluster. This cluster reduces the number of memory usage.

Step 5: The pickup of item will be separated until all the items are completely fixed in the location.

Step6: For dropping an item first we need to generate random Maximum dropping number G.

Step7: If the probability value of dropping is more compare to G. (Pg >G) then drop (I, 0) this represents „I‟ item will be dropping at 0 positions.

Step8: Once items are dropped then memory will be allocated and it will be represented with object name, location and maximum memory size.

Step 9: Once memory is allocated, before placing an object it will compare present object with already existed object in the memory if it finds any item which is similar as present object then it will jump to that location and fixes the object in that location only.

Step 10: If any items present in memory is not similar with the current object then it moves to a new site or location where this location is not occupied by any other ants. This algorithm represents the best utilization of memory by implementing clustering technique, where data which is stored through this technique is very huge compare to data which is stored individual at every memory location.

  1. ANTS SLEEPING MODEL

An artificial Ants Sleeping Model (ASM) and adaptive artificial ants clustering algorithm are presented to resolve the clustering problem in data mining by simulating the behaviour of gregarious ant colonies. This paper reports a study of light/dark periods on workers activity as well as sleep locations, posture and wake/sleep cycle of fire ant workers and queens located in an artificial nest chamber. Workers slept in one of three locations: on the ceiling against the chamber wall or in the centre of the chamber floor, workers on the ceiling or against the chamber wall slept for longer periods than those at the center of the chamber floor where most grooming and feeding activity occurred. Sleep posture of an ant is distinctly different that wake posture. During deep sleep, queens and workers fold their antenna and were non- responsive to contact by other ants. Another indicator of deep sleep was Rapid Antennal Movement (RAM) sleep. The sleep episodes were polyphasic for queens averaged approximately 92 sleep episodes/day, each episodes has approximately 6min/episodes, for 92 episodes X 6 min/episode = 552 min/day that is 9.4 hrs/day[4]. For worker average sleep is 4.8 hrs/day. The worker were hypervigilant with an average of 80% of the labour force completing grooming, feeding or excavation tasks at any given time.

Research into the neural mechanisms of sleep in one species can enlighten us on the neural mechanisms of sleep in other species; studies of sleep among caste members in the social insects can extend our understanding of intra and inter specific variability of sleep/wake cycle day to day and over evolutionary time. This paper reports a study of the affect of light on worker activity level. The success of ants worldwide is largely a result of the ability of workers to quickly switch back and forth from individual to group tasks based on need. Since fire ants are subterranean dwellers and thus irregularly exposed to photoperiods, we hypothesized that inactivity in individuals would be polyphasic and asynchronous. Sampling for our study on sleep cycle of fire ant workers and queens, a single colony was selected from laboratory maintained colonies. This colony contained a large ratio of brood relative to workers, indicating the presence of healthy queens. To simulate the small grouping of fire ants found in field nest changers, 3 queens, 30 workers, 30 large larvae were placed in one artificial chamber. A glass cover slip was placed over the chamber and tunnel. Queen sleep data on the activity/inactivity of the three queens was collected from video record for the computation purpose a single queen is selected one at a time, for its behavioural analysis, active and inactive duration were recorded in seconds along with the time of change in behaviour, from this analysis data, frequency duration and synchrony of each queens active and inactive periods were analyzed with this posture and location of queens was noted every hour over this observation periods.

The queen activity/inactivity indicators of wake active episodes in queens took three forms: antennal movement, head movement or body movement in the form of walking. When walking or moving their heads, queen extended their antenna with the scape forward of the eyes, scape and funicular at an obtuse angle to each other (ant a). The mandibles and glossae (tongue) were partially extended [5]. Queens that ingested fluids from a worker or from a larva‟s and slit held their antennae with the scape and funiculate at acute angle and with the scape extended in front of the eyes, the tips of the antennae packed and folded, the mandibles teeth tips are touching but not overlapping and the glossae were partially extended(ant b). Queen that regurgitates food to a worker or another queen extended their antennae with the scape in front of the eyes, forming a right angle with the funiculate, mandibles were open and glossae fully extended (ant c).


The sleep mode episodes took two forms: deep-sleep and dozing. During deep-sleep, antennae where completely retracted as were glossae and mandibles, queens were unresponsive to contact by workers, during periods of deep-sleep, the folded antennae of queens quivered in a rapid antennal movement (ant d). Where as in dozing is different from deep-sleep, in that antennal were partially extended, with the scape and funicular at right angle to each other in this mandibles were partially open such that the tips of the teeth were touching but not overlapping. Dozing queens were more likely to respond to contact by worker with antennal movements.

  1. CONCLUSIONS

This paper provides the way to best utilization of Memory by Clustering Technique, As we know that Homogenous Cluster will save Memory with same attributers it is implemented with the help of ant colonial optimization technique which represents less number of clustering group of ant will have more ants compare to individual present in the projection. where clustering produce best utilization of memory with similar attributes.

REFERENCES

  • Zahra Sadeghi 1, Mohammad Teshnehlab 2, Mir Mohsen Pedram 3 “K-ANTS CLUSTERING- A NEW

STRATEGY BASED ON ANT CLUSTERING”.

  • Salima Ouadfel and Mohamed Batouche2. “AN EFFICIENT ANT ALGORITHM FOR SWARM-BASED IMAGE CLUSTERING”.
  • G¨udemann1,  F.  Nafz2,  F.  Ortmeier3,  H.  Seebach4   and  W.  Reif5.  “A  SPECIFICATION  AND

CONSTRUCTION PARADIGM FOR ORGANIC COMPUTING SYSTEMS”.

  • Chi-Ho Tsang1 and Sam Kwong2, “ANT COLONY CLUSTERING AND FEATURE EXTRACTION FOR ANOMALY INTRUSION DETECTION”.
  • Shu-Chuan Chu1,  Hsiang-Cheh  Huang2,  John    Roddick3,  and  Jeng-Shyang  Pan4,  “OVERVIEW  OF

ALGORITHMS FOR SWARM INTELLIGENCE”.

  • Wafa‟a Omar1, Amr Badr2 and Abd El-Fattah Hegazy3, “HYBRID ANT-BASED CLUSTERING ALGORITHM WITH CLUSTER ANALYSIS TECHNIQUES”.
  • Share :