An automated parameter tuning method for ant colony optimization for scheduling jobs in grid environment

An automated parameter tuning method for ant colony optimization for scheduling jobs in grid environment

Автор: Ankita, Sudip Kumar Sahana

Журнал: International Journal of Intelligent Systems and Applications @ijisa

Статья в выпуске: 3 vol.11, 2019 года.

Бесплатный доступ

The grid infrastructure has evolved as the integration and collaboration of multiple computer systems, networks, different databases and other network resources. The problem of scheduling in grid environment is an NP complete problem where conventional approaches like First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin Scheduling algorithm (RR), Backfilling is not preferred because of the unexpectedly high computational cost and time in the worst case. Different algorithms, for example bio-inspired algorithms like Ant Colony Optimization (ACO), Artificial Bee Colony (ABC), Genetic Algorithm and Particle Swarm Optimization (PSO) are there which can be applied for solving NP complete problems. Among these algorithms, ACO is designed specifically to solve minimum cost problems and so it can be easily applied in grid environment to calculate the execution time of different jobs. Algorithms have different parameters and the performance of these algorithms extremely depends on the values of its parameters. In this paper, we have proposed a method to tune the parameters of ACO and discussed how parameter tuning affects the performance of ACO which in turn affects the performance of grid environment when applied for scheduling.

Еще

ACO, bio-inspired, grid, parameter values, parameter tuning, scheduling

Короткий адрес: https://sciup.org/15016577

IDR: 15016577   |   DOI: 10.5815/ijisa.2019.03.02

Список литературы An automated parameter tuning method for ant colony optimization for scheduling jobs in grid environment

  • I. Foster, C. Kesselmen and S. Tuecke, “The anatomy of the Grid: Enabling Scalable Virtual Organisations,” International Journal of High Performance Computing Applications, vol. 15, pp. 200-222, 2001
  • I. Foster and C. Kesselmen, “The Grid: Blueprint for a future computing infrastructure,” ACM Digital Library, Morgan Kaufmann Publishers, 1999, pp. 1-593.
  • A. Yousif, SM. Nor, AH. Abdualla and MB. Bashi, “Job Scheduling algorithms on grid computing: State-of- the art,” International Journal of Grid Distribution Computing, vol. 8, pp. 125-140, 2015.
  • HB. Prajapati and VA. Shah, “Scheduling in Grid Computing Environment. Fourth International Conference on Advance Computing and Communication Technologies”, Rohtak, India, 2014.
  • MK. Mishra, YS. Patel, Y. Rout and GB. Mund, “A survey on scheduling heuristics in grid computing environment”, I.J. Modern Education and Computer Science, vol. 10, pp. 57-83, 2014.
  • X. Yu, “Introduction to Evolutionary Algorithms,” 40th International Conference on Computers & Indutrial Engineering, Awaji, Japan, 2010, pp. 1-1.
  • K. Deb, “Multi-Objective optimization using Evolutionary algorithms An Introduction,” in Wang L., Ng A., Deb K.(eds) Multi-Objective Evolutionary Optimisation using for product design and manufacturing, Springer, London, 2011, pp. 3-34.
  • SA. Ludwigand, A. Moallem, “Swarm Intelligence Approaches for Grid Load Balancing,” Journal of Grid Computing, vol. 8, pp. 279-301, 2011.
  • V. Nannen and AE. Eiben, “A method for parameter calibration and relevance estimation in evolutionary algorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, GECCO’06, Morgan Kauffman, San Francisco, 2006, pp. 183-190.
  • M. Baker, R. Buyya and D. Laforenza, “Grids and Grid technologies for wide area distributed computing,” International Journal of Software: Practice and Experience (SPE), vol. 32, pp. 1437-1466, 2002.
  • AE. Eiben, SK. Smit, “Evolutionary Algorithms and Methods to tune them,” in Hamadi Y., Monfroy E., Saubion F. (Eds) Autonomous Search, Springer, Berlin, Heidelberg, 2011, pp. 15-36.
  • KY. Wong, K. Komarudin, “Parameter tuning for ant colony optimization: A review”. International Conference on Computer and Communication Engineering, Kuala Lumpur, Malaysia, 2008, pp. 542-545.
  • T. Stutzle et al., “Parameter Adaptation in Ant Colony Optimization,” in Hamadi Y., Monfroy E., Saubion F. (eds) Autonomous Search, Springer, Berlin, Heidelberg, 2011, pp. 191-215.
  • AE. Eiben, R. Hinterding and Z. Michalewicz, “Parameter control in evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 3, pp. 124-141, 1999.
  • O. Castillo, R. Martinez-Marroquin, P. Melin, F. Valdez and J. Soria, “Comparitive study of Bio-inspired algorithms applied to the optimization of type-1 and type-2 fuzzy controllers for an autonomous mobile root,” Information Science, vol. 192, pp. 19-38, 2012.
  • R. Ugolotti, S. Cagnoni, “Analysis of Evolutionary algorithms using multi-objective parameter tuning,” Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, Canada, 2014, pp. 1343-1350.
  • SK. Sahana and PK. Mahanti, “Ant Colony Optimization for Train Scheduling” I.J. Intelligent Systems and Applications, vol. 2, pp. 29-36, 2014.
  • Yogesh and P. Singh, “Favorable Trail detection using ACO-BellMan Algorithm in VANETs”, I.J. Modern Education and Computer Science, vol. 1, pp. 33-39, 2016.
  • S.Srivastava, SK. Sahana, Nested Hybrid Evolutionary Model for traffic signal optimization”, Applied Intelligence, Springer, vol. 46, pp. 1-11, 2016.
  • AE. Eiben, SK. Smit, “Comparing parameter tuning methods for Evolutionary Algorithms,” Proceedings IEEE Congress on Evolutionary Computation, Trondheim, Norway, 2009, pp. 399-406.
  • EBM. Barbosa, ELF. Senne, “Improving the fine tuning of metaheuristics: An Approach Combining design of Experiments and Racing algorithms,” Journal of Optimization, pp. 1-7, 2017.
  • AE. Eiben, SK. Smit., “Parameter tuning for configuring and analyzing evolutionary algorithms,” Swarm and Evolutionary Computations, vol. 1, pp.19-31, 2011.
  • N. Vecek, M. Mernik, B. Filipic and M. Crepinsek, “Parameter tuning with Chess Rating System (CRS-Tuning) for meta heuristic algorithms,” Information Sciences, vol. 372, pp. 446-469, 2016.
  • M. Mobin, SM. Mousavi, M. Komaki and M. Tavana, “A hybrid desirability function approach for tuning parameters in evolutionary optimization algorithms,” Measurement, vol. 114, pp. 417- 427, 2018.
  • O. Castillo, H. Neyoy, J. Soria, P. Melin and F. Vldez “A new approach for dynamic fuzzy logic parameter tuning in Ant Colony Optimization and its application in fuzzy control of a mobile robot,” Applied Soft Computing, vol. 28, pp. 150-159, 2015.
  • T. Agasiev and A. Karpenko, “The program system for automated parameter tuning of optimization algorithms,” Procedia Computer Science, vol. 103, pp. 347-354, 2016.
  • N. Iwasaki, K. Yasuda and G. Ueno, “Dynamic parameter tuning of particle Swarm Optimization,” IEEEJ Trans. Electr. Electron. Eng, vol. 1, pp. 353-363, 2006.
  • B. Akay and D. Karaboga, Parameter tuning for the artificial bee colony algorithm. International conference on Computational Collective Intelligence, Berlin, Heidelberg, 2009, pp. 608-619.
  • SK. Smit and AE. Eiben, “Parameter Tuning of Evolutionary Algorithms: Generalist vs Specialist. in Di Chio C. et al. (eds), Applications of Evolutionary Computation. EvoApplications, Lecture Notes in Computer Science, Berlin, Heidelberg, 2010, pp. 542-551.
  • E. Montero, M-C Riff and B. Neveu, “A beginner’s guide to tuning methods,” Applied Soft Computing, vol. 17, pp.39-51, 2014.
  • B. Adenso-Diaz and M. Laguna, “Fine-tuning of algorithms using fractional experimental designs and local search,” Operational Research, vol. 54, pp. 99-114, 2006.
  • ICO. Ramos, R. Goldbarg, E. Goldbarg and A. Neto, “Logistic regression for fine tuning of an evolutionary algorithm,” Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Edinburgh, UK, 2005, pp. 1061-1068.
  • SP. Coy, BL. Golden, GC. Runger and EA.Wasil, Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics, vol. 5, pp. 77-97, 2001.
  • V. Nannen and AE. Eiben, “Efficient relevance estimation and value calibration of evolutionary algorithm parameters,” IEEE Congress on Evolutionary Computation, Singapore, 2007, pp. 103-110.
  • V. Nannen and AE. Eiben, “A method for parameter calibration and relevance estimation in evolutionary algorithms,” Proceedings of the Genetic and Evolutionary Computation Conference, GECCO’06, San Francisco, 2006. pp. 183-190.
  • SK. Smit and AE. Eiben, “Using Entropy for parameter analysis of Evolutionary algorithms,” in Bartz-Beielstein T., Chiarandini M, Paquete L., Preuss M(Eds.), Experimental Methods for the Analysis of Optimization Algorithms, Berlin, Heidelberg, 2010, pp. 287–310.
  • V. Nannen , SK. Smit and AE. Eiben, “Costs and Benefits of tuning parameters of evolutionary algorithms,” in Rudolph G., Jansen T., Lucas SM., Poloni C., Beume N. (Eds.), Parallel Problem Solving from Nature – PPSN X, Lecture Notes in Computer Science, Berlin, Heidelberg, 2008, pp. 528–538.
  • H. Neyoy, O. Castillo and J. Soria, “Fuzzy Logic for Dynamic Parameter Tuning in ACO and its applications in optimal fuzzy logic controller design,” in Castillo O., Melin P.(eds) Fuzzy Logic Augmentation of Nature-Inspired Optimization Metaheuristics. Studies in Computational Intelligence, (2014), Springer, Cham, pp. 3-28.
  • M. Dorigo, C. Blum, “Ant Colony Optimization theory: A Survey,” Theoretical Computer Science, Elsevier, vol. 344, pp. 243-278, 2005.
  • C. Blum, “Ant Colony Optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2, pp. 353-373, 2005.
  • D. Merkle, M. Mddendorf and H. Schmeck, “Ant Colony optimization for resource constrained project scheduling,” IEEE Trans. Evolutionary Computation, vol.6, pp. 333-346, 2002.
  • B. Meyer, “Convergence control in ACO,” Genetic and Evolutionary computation conference (GECCO), Seattle, WA, 2004.
  • D. Merkle and M. Middendorf, “Prospects for dynamic algorithm control: lessons from the phase structure of ant scheduling algorithms,” in R.B. Heckendorn (ed.), Proceedings of the 2000 Genetic and Evolutionary Computation Conference- Workshop Program. Workshop- The next ten years of scheduling research, Morgan Kaufmann Publishers, Las Vegas, USA, 2001, pp. 121-126.
  • Y. Nakamichi and T. Arita, “Diversity control in Ant Colony Optimization,” Proc. Inaugural Workshop on Artificial Life (AL’01), Adelaide, Australia, 2001, pp. 70-78.
  • A. Sieminski, “Ant Colony Optimization Parameter evaluation,” in Zgrzywa A., Choros K., Sieminski A. (eds) Multimedia and Internet Systems: Theory and Practice. Advances in Intelligent Systems and Computing, (Springer, Berlin, Hidelberg, 2013), pp. 143-153.
  • D. Klusacek and H. Rudova, “Alea 2- Job Scheduling Simulator,” Proceedings of the 3rd international conference on simulation tools and techniques (SIMUTools 2010), (ICST 2010).
  • R. Buyya and M. Murshed M, “GridSim: A toolkit for the modeling and simulation of Distributed Resource Management and Scheduling for grid computing” the journal of concurrency and computation: Practice and Experience (CCPE), vol. 14, pp. 1035-1593, 2002.
  • M. Murshed and R. Buyya, “Using the GridSim toolkit for Enabling Grid Computing Education,” Proceedings of the International Conference on Communication Networks and Distributed Systems Modeling and Simulation, San Antonio, Texas, USA, 2002.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp