Grid Implementation Of Artificial Bee Colony Inspired Algorithm Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Artificial Bee Colony algorithm is an optimization algorithm based on the intelligent behavior of honey bee swarm. In this work, ABC algorithm is used to optimize the equilibrium of confined plasma in a nuclear fusion device. Plasma confinement is an interesting problem and has turned out to be much more difficult than anyone could have guessed. This problem need a large computing capacity to be solved so that traditional computation cannot give the solution hence environment like grid computing has to be used, thus the first step is to adapt and extend the ABC algorithm to use the grid capabilities. In this work we present a modification of the original ABC algorithm its adaption to a grid computing environment and the application of this algorithm to the equilibrium optimization process.

Keywords- Artificial Bee Colony, Grid Computing, Equilibrium, Nuclear Fusion.


. Nuclear fusion is the next generation of energy it can be thought of as the best alternative to conventional energy sources but to make use of fusion as a practical energy source, it is imperative to learn how to confine hot plasmas with magnetic fields. Plasma confinement is an interesting problem and has turned out to be much more difficult than anyone could have guessed. This problem need a large computing capacity to be solved so that traditional computation cannot give the solution hence environment like grid computing has to be used. In this work artificial bee colony algorithm is used to optimize the equilibrium of confined plasma in a nuclear fusion device thus original ABC algorithm is extended to use grid computing capabilities and then it is applied to fusion research problem. With grid computing we have the computational resources and with artificial bee colony algorithm we can look for an approximate result without exploring all the solution space.

Artificial bee colony (ABC) algorithm is one of the most recently proposed swarm intelligence algorithms for global optimization. It is a distributed asynchronous process where different bees (computational resources) are looking for flowers (approximated solutions) and every time a good flower is found, more bees are allocated for similar flowers. That means more computational resources are allocated to explore solutions close to an approximated solution found after the dancing of the bees in the colony, dancing is the process where bees exchange information. While it mimics the behavior of swarms of honey bees, the algorithm uses concepts of swarm intelligence. Basic philosophy of Swarm Intelligence is to observe the behaviour of social animals and try to mimic their problem solving abilities on computer systems.In the case of grid computing, the computational resources are Working Node (WN) - in the terminology of gLite - and the waggle dance - sharing of information about the direction and distance to paths of flowers - is performed in the User Interface (UI), where the colony is. And, as long as we plan to improve the equilibrium of a nuclear fusion device, a flower is a configuration of the device; a good flower will be an approximated configuration of the fusion device where the equilibrium is better than the existing in current devices.

In the case of optimization problems related to many scientific areas, the required time to get a fitness value is so long that traditional computation cannot be used to perform an exploration of the entire solution space. Modern paradigms, like grid computing, offer the computational resources and capabilities to carry out these optimization problems. Grid computing is the act of sharing tasks over multiple computers, tasks can range from data storage to complex calculations and can be spread over large geographical distances. It combines computer resources from multiple administrative domains to reach common goal. Grid computing can be thought of as distributed and large-scale cluster computing and as a form of network-distributed parallel processing, but they are not easy to use. Until now, many investigations have been carried out in order to use parallel architectures and GAs (Genetic Algorithms), but the coupling of grid capabilities and complex metaheuristics is still in an immature state. Furthermore, the use of swarm intelligence has not been yet deeply used in grid environments. The grid has created a way that could potentially lead to an increase in the performance of these types of algorithms In terms of execution time and problem size. Nevertheless, a high level of expertise is required to develop and execute grid applications because many problems can arise due to the specifics of the grid infrastructure. Our goal consists of improving the equilibrium of plasma in a nuclear fusion device by means of the ABC algorithm and grid computing.

The rest of this paper is organized as follows: Chapter 2, describe problem and gives overview of previous efforts done while Chapter 3, introduces some basic concepts of the ABC algorithm, Chapter 4, describes how ABC algorithm is adapted to the grid computing environment. Finally Chapter 5, conclude the paper and summaries a variety of perspectives.

nuclear fusion

Nuclear fusion is the process by which multiple atomic particles join together to form a heavier nucleus. It is accompanied by the release or absorption of energy. The fusion of two light nuclei generally release energy while the fusion of heavy nuclei absorb energy among the different reactions the most promising one is shown in equation (1) most of the current nuclear devices work with this elements to obtain fusion reaction. In equation (1), D denotes a deuterium, T denotes a tritium, 4He is an isotope of helium being aparticle, n is a neutron and MeV is megaelectron-volt.

Figure.1 Nuclear fusion reaction

The nuclei of deuterium and tritium do not fuse spontaneously. Because they both have a positive charge, the repelling Coulomb force prevents the reaction. A sufficiently high kinetic energy of the nuclei is needed to overcome the Coulomb force. This high kinetic energy is achieved in a gas that has a temperature T of about 100 million degrees centigrade. At this kind of temperature gasses are ionized. We do no longer call them a gas, but call them as plasma.

Artificial Bee Colony Algorithm

Artificial Bee Colony Algorithm (ABC) is an optimization algorithm based on the intelligent foraging behavior of honey bee swarm, proposed by Karaboga in 2005.In ABC model, the colony consists of three groups of bees: employed bees, onlookers and scouts. It is assumed that there is only one artificial employed bee for each food source. Employed bees go to their food source and come back to hive and dance on this area. The employed bee whose food source has been abandoned becomes a scout and starts to search for finding a new food source. Onlookers watch the dances of employed bees and choose food sources depending on dances.

Figure 2. Honey bee extracting nectar

The main steps of the algorithm are given below:

Initial food sources are produced for all employed bees


Each employed bee goes to a food source in her memory and determines a neighbor source, then evaluates its nectar amount and dances in the hive

Each onlooker watches the dance of employed bees and chooses one of their sources depending on the dances, and then goes to that source. After choosing a neighbor around that, she evaluates its nectar amount.

Abandoned food sources are determined and are replaced with the new food sources discovered by scouts.

The best food source found so far is registered.

UNTIL (requirements are met)

3.1 Components of Original Algorithm

According to the original implementation, and following the behavior of a bee colony, there are three different bees in the algorithm:

1) Employed: Each employed bee goes to a food source and determines a neighbor source, then evaluates its nectar amount and dances in the hive these bees evaluate an approximated configuration. They are useful to maintain certain levels of convergence in the system.

2) Scouts: The employed bee whose food source has been abandoned becomes a scout and starts to search for finding a new food source they explore the solution space. There are different techniques to explore the solution space. They introduce the dispersion component into the system.

3) Onlookers: these bees evaluate the results obtained by employed and scouts bees and choose next configurations to evaluate. They are the master elements of the system. The communication between the different bees - waggle dance according to the behavior of bees in nature - is performed in the master process.

3.2 Extensions of Original algorithm

Taking into account the grid paradigm, the number of computational resources and the access to these resources, the original ABC algorithm is extended by adding:

Two levels of employed:

Elites: perform a wide search using an approximated configuration. This approximated configuration has been previously found by a scout.

Workers (associated to an elite bee): by using a local search procedure, they explore deeply the best configuration found by elite bees.

Two levels of scouts:

Rovers: they use diversification methods to explore the solution space.

Cubs (associated to a rover bee): random exploration changing configuration parameter based on good solution, in terms of dispersion, found by a rover.

Grid Implementation

Problems that are present in current nuclear fusion devices can be solved by means of modeling tools. These tools are extremely demanding in terms of computational resources and they also use a large number of parameters to represent the behavior of nuclear fusion devices. These applications require high computational costs to perform their operations; the use of the grid is an ideal environment to carry out these tests. The distributed paradigm of the grid represents an excellent alternative to execute these tools.

Figure 3. Grid Computing

A. Interaction with the Middleware

Middleware is computer software that connects software components or some people and their applications. The software consists of a set of services that allows multiple processes running on one or more machines to interact. This technology evolved to provide interoperability in support of the move to coherent distributed architectures, which are most often used to support and simplify complex distributed applications. Middleware is sometimes called plumbing because it connects two applications and passes data between them. Middleware allows data contained in one database to be accessed through another. This definition would fit enterprise application integration and data integration software.To get a non-supervised system we have developed a set of wrappers around the command line interface that interact with the metascheduler and the proxy to manage all the required processes in a proper way. Though the grid middleware is under active development with some bugs, we are adopting it because bugs encompasses in grid middleware usually affect the API (Application Programming Interface) and not the command line interface. The final algorithm is a distributed and asynchronous algorithm, where every time a solution improving the previous best solution found is obtained, new resources are allocated to look for more solutions performing a local search. Its objective is optimization of solution space

Figure 4. Interaction of controller and user node with middleware

1) Setting up the Environment

In the process of setting an environment XML configuration file is used to indicate the configuration of the algorithm. In these files the user can indicate several features of the grid environment like the virtual organization, hosts for different elements in the infrastructure, the metascheduler used or any special requirement that the user could want to include. The system will read this configuration file and will perform the required actions. If the user does not supply any data for this file, a generic configuration is used. Furthermore, the user can specify the number of chromosomes to be used, the extreme values for these chromosomes or the maximum number of evaluations to be performed among a large number of customizable characteristics. Furthermore, the maximum number of employed and scout is indicated in a file, in terms of percentage of resources of the grid environment or an absolute number of computational resources. The master process will continuously check if there are fewer processes submitted than this maximum number in order to submit new jobs to the grid.

B. Types of Jobs

In bee colony there are different bees with different functionalities. Considering that heterogeneity, grid also encompasses different tasks.

•Onlookers: This is the system running in the user interface.

•Elites and Rovers: These are jobs running in the WNs.

The main idea behind these jobs is to achieve a deep use of grid capabilities, trying to minimize the time waiting in queues compared to the execution time that they are going to require. These jobs will try to run for the longest time possible. Hence, the way to proceed is:

1) We send an empty job to the grid.

2) Once this job starts, it looks for input data in the SE.

3) When the job has processed all the input data, it tries to get new data from the SE.

•Workers and Cubs: These jobs process some input data and finishes their execution.

C .Communication Worker Nodes - User Interface

There are two different jobs or bees that need some level of communication with the master node. Furthermore, the simple jobs taking all the input information in the job wrapper have to store their results in the SE(storage element) and indicate the new result to the master element of the system.

The communication is done by means of the SE and it consists of different points:

When the system starts, it generates the folder structure in the Logical File Catalog (LFC) that will store all the information of the different bees. Besides, some files to store data such as number of jobs, evolution of the best solution found or execution time, are uploaded to the SE. These files will be modified by the different jobs submitted to the grid. To avoid that two different jobs could modify the same file at the same time, we have developed a barrier based synchronization process as stated bellow:

When a job wants to have access to a file in the SE, looks whether the file is locked or not.

If the file is locked, the process waits until the process owning the file ends.

If the file is unlocked, the process locks the file copies the file locally, modifies the content and uploads the file to the SE. When the file has bee successfully uploaded, the process unlocks the file.

When a job finishes, it stores the result in its folder in the LFC. It also updates a file, using the barrier system, to indicate the master process that new results have arrived.

When the termination condition of the system is reached, the master process indicates this fact to all the different jobs in the system. The processes will detect the condition, finishing their evaluations.

This design helps to create a checkpoint system for the different jobs that will store their information in the SE so they can resume the execution from the last checkpoint in case of failure occurrence.

the system, it can resubmit a job that will resume the execution in the last checkpoint generated by the previous version of the job.

Data management: the master process will continuously check the smooth running of the system. The master process will generate replicas of the files in the different SE of the grid environment.

V. Conclusion

This paper has presented a grid implementation of the ABC algorithm and its application to plasma physics research by improving the equilibrium of an existing device. The implementation proposed uses a barrier system to communicate the different elements in the system (different bees, that is, different computational resources) and coordinate the distributed execution of the system. This implementation is generic and can be used to optimize any other scientific problem by changing the configuration of a set of XML files and the job to be submitted to the grid. The next step will be to increase the use of the grid infrastructure by means of increasing the number of bees in the system as well as considering a longer period of time to collect the results

VI. References

Antonio G´omez-Iglesias,Miguel A. Vega-Rodr´Ä±guez†, Francisco Castej´on-, Miguel C´ardenas-Montes‡ and Enrique Morales-Ramos ,Artificial Bee Colony Inspired Algorithm Applied to Fusion Research in a Grid Computing Environment

.I. Foster and C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann.

A. G´omez-Iglesias, MA. Vega-Rodr´Ä±guez, M. C´ardenas-Montes,

E. Morales-Ramos and F.. Castej´on. Grid-Oriented Scatter Search Algorithm. ICANNGA 2009, LNCS 2009; 5495(1):193-202.

D. Karaboga. An Idea Based on Honey Bee Swarm for Numerical

Optimization. Technical Report, Erciyes University, Engineering Faculty,Computer Engineering Department, 2005.

PM. Bellan. Fundamentals of Plasma Physics. Cambridge University Press, 2006.

J. Freidberg. Plasma Physics and Fusion Energy. Cambridge University Press, 2007.

Adil Baykaso, Lale -zbakır2 and Pınar Tapkan2 . Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem. Technical report, University of Gaziantep, Department of Industrial Engineering Erciyes University, Department of Industrial Engineering Turkey