Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-09T01:35:05.987Z Has data issue: false hasContentIssue false
  • English
  • Français

Direct Gravitational Search Algorithm for Global Optimisation Problems

Part of: Algorithms - Computer Science Optimality conditions

Published online by Cambridge University Press:  20 July 2016

Ahmed F. Ali  and
Mohamed A. Tawhid
Ahmed F. Ali*
Affiliation:
Department of Computer Science, Faculty of Computers & Informatics, Suez Canal University, Ismailia, Egypt Department of Mathematics and Statistics, Faculty of Science, Thompson Rivers University, Kamloops, BC, CanadaV2C 0C8
Mohamed A. Tawhid*
Affiliation:
Department of Mathematics and Statistics, Faculty of Science, Thompson Rivers University, Kamloops, BC, CanadaV2C 0C8 Department of Mathematics and Computer Science, Faculty of Science, Alexandria University, Moharam Bey 21511, Alexandria, Egypt
*
*Corresponding author. Email addresses:[email protected] (A. F. Ali), [email protected] (M. A. Tawhid)
*Corresponding author. Email addresses:[email protected] (A. F. Ali), [email protected] (M. A. Tawhid)
Get access

Abstract

A gravitational search algorithm (GSA) is a meta-heuristic development that is modelled on the Newtonian law of gravity and mass interaction. Here we propose a new hybrid algorithm called the Direct Gravitational Search Algorithm (DGSA), which combines a GSA that can perform a wide exploration and deep exploitation with the Nelder-Mead method, as a promising direct method capable of an intensification search. The main drawback of a meta-heuristic algorithm is slow convergence, but in our DGSA the standard GSA is run for a number of iterations before the best solution obtained is passed to the Nelder-Mead method to refine it and avoid running iterations that provide negligible further improvement. We test the DGSA on 7 benchmark integer functions and 10 benchmark minimax functions to compare the performance against 9 other algorithms, and the numerical results show the optimal or near optimal solution is obtained faster.

Keywords

Gravitational search algorithmdirect search methodsNelder-Mead methodinteger programming problemsminimax problems

MSC classification

Secondary: 49K35: Minimax problems 90C10: Integer programming 68U20: Simulation 68W05: Nonnumerical algorithms
Type
Research Article
Information
East Asian Journal on Applied Mathematics , Volume 6 , Issue 3 , August 2016 , pp. 290 - 313
Copyright
Copyright © Global-Science Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bacanin, N. and Tuba, M., Artificial bee colony (ABC) algorithm for constrained optimization improved with genetic operators, Studies in Informatics Control 21, 137–146 (2012).CrossRefGoogle Scholar
[2]Bandler, J.W. and Charalambous, C., Nonlinear programming using minimax techniques, J. Optimization Theory Appl. 13, 607–619 (1974).Google Scholar
[3]Bacanin, N., Brajevic, I. and Tuba, M., Firefly Algorithm applied to integer programming problems, in Proc. 7th Int. Conf. on Applied Mathematics, Simulation, Modelling (ASM’13), Cambridge, Mass., USA, pp. 143–148, WSEAS Press (2013).Google Scholar
[4]Borchers, B. and Mitchell, J.E., Using an interior point method in a branch and bound algorithm for integer programming, Technical Rep., Rensselaer Polytechnic Institute, (1992).Google Scholar
[5]Borchers, B. and Mitchell, J.E., An improved branch and bound algorithm for mixed integer non-linear programs, Computers Op. Res. 21, 359–367 (1994).CrossRefGoogle Scholar
[6]Chu, S.A., Tsai, P.W. and Pan, J.S., Cat swarm optimization, Lecture Notes Comp. Sc. (subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4099 LNAI, pp. 854–858 (2006).Google Scholar
[7]Dorigo, M., Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, Italy (1992).Google Scholar
[8]Du, D.Z. and Pardalose, P.M., Minimax and Applications, Kluwer (1995).Google Scholar
[9]Fletcher, R., Practical Method of Optimization, Vols. 1 & 2, Wiley (1980).Google Scholar
[10]Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).Google Scholar
[11]Gill, P.E., Murray, W. and Wright, M.H., Practical Optimzization, Academic Press, London (1981).Google Scholar
[12]Glankwahmdee, A., Liebman, J.S. and Hogg, G.L., Unconstrained discrete nonlinear programming, Eng. Optimization 4, 95–107 (1979).Google Scholar
[13]Isabel, A.C.P., Santo, E. and Fernandes, E., Heuristics pattern search for bound constrained minimax problems, Comp. Sc. Appl. 6784, 174–184, ICCSA (2011).Google Scholar
[14]Jovanovic, R. and Tuba, M., An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem, Appl. Soft Computing 11, 5360–5366 (2011).Google Scholar
[15]Jovanovic, R. and Tuba, M., Ant colony optimization Aagorithm with pheromone correction strategy for minimum connected dominating set problem, Comp. Sc. Inf. Systems 10, 133–149 (2013).Google Scholar
[16]Karaboga, D. and Basturk, B., A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, J. Global Optimization 39, 459–471 (2007).CrossRefGoogle Scholar
[17]Kennedy, J. and Eberhart, R.C., Particle swarm optimization, in Proc. IEEE Int. Conf. Neural Networks 4, pp. 1942–1948 (1995).Google Scholar
[18]Laskari, E.C., Parsopoulos, K.E. and Vrahatis, M.N., Particle swarm optimization for integer programming, in Proc. IEEE 2002 Congress on Evolutionary Computation, Honolulu, pp. 1582–1587 (2002).Google Scholar
[19]Lawler, E.L. and Wood, D.W., Branch and bound methods: A survey, Operations Res. 14, 699–719 (1966).Google Scholar
[20]Li, X.L., Shao, Z.J. and Qian, J.X.. Optimizing method based on autonomous animals: Fish-swarm algorithm, Xitong Gongcheng Lilun yu Shijian/System Eng. Theory and Practice 22, 32–38 (2002).Google Scholar
[21]Liuzzi, G., Lucidi, S. and Sciandrone, M., A derivative-free algorithm for linearly constrained finite minimax problems, SIAM J. Optimization 16, 1054–1075 (2006).CrossRefGoogle Scholar
[22]Lukšan, L. and Vlcek, J., Test problems for nonsmooth unconstrained and linearly constrained optimization, Technical Rep. 798, Institute Comp. Sc., Academy of Sciences of the Czech Republic, Prague (2000).Google Scholar
[23]Manquinho, V.M., Marques Silva, J.P., Oliveira, A.L. and Sakallah, K.A., Branch and bound algorithms for highly constrained integer programs, Technical Rep., Cadence European Laboratories, Portugal (1997).Google Scholar
[24]Nelder, J.A. and Mead, R., A simplex methods for function minimization, Computer J. 7, 308–313 (1965).Google Scholar
[25]Nemhauser, G.L., Rinnooy Kan, A.H.G. and Todd, M.J., Handbooks in OR & MS, Vol. 1, Elsevier (1989).Google Scholar
[26]Nemhauser, G. and Wolsey, L., Integer and Combinatorial Optimization, Wiley (1988).CrossRefGoogle Scholar
[27]Parsopoulos, K.E. and Vrahatis, M.N., Unified particle swarm optimization for tackling operations research problems, in Proc. IEEE 2005 Swarm Intelligence Symposium, Pasadena, USA, pp. 53–59 (2005).CrossRefGoogle Scholar
[28]Passino, M.K., Biomimicry of bacterial foraging for distributed optimization and control, Control Systems, IEEE 22, 52–67 (2002).Google Scholar
[29]Petalas, Y.G., Parsopoulos, K.E. and Vrahatis, M.N., Memetic particle swarm optimization, Ann. Op. Res. 156, 99–127 (2007).CrossRefGoogle Scholar
[30]Polak, E., Royset, J.O. and Womersley, R.S., Algorithms with adaptive smoothing for finite minimax problems, J. Optimization Theory Applic. 119, 459–484 (2003).Google Scholar
[31]Rao, S.S., Engineering Optimization-Theory and Practice, Wiley (1994).Google Scholar
[32]Rashedi, E., Nezamabadi-pour, H., and Saryazdi, S., GSA: A gravitational search algorithm, Inf. Sc. 179, 2232–2248 (2009).Google Scholar
[33]Rudolph, G., An evolutionary algorithm for integer programming, in Parallel Problem Solving from Nature 3, Davidor, Y., Schwefel, H.P. and Männer, R. (Eds), pp. 139–148 (1994).Google Scholar
[34]Schwefel, H.P., Evolution and Optimum Seeking, Wiley (1995).Google Scholar
[35]Tang, R., Fong, S., Yang, X.S. and Deb, S., Wolf search algorithm with ephemeral memory, in Digital Information Management, 2012 Seventh Int. Conf. Digital Inf. Management (ICDIM), pp. 165–172 (2012).Google Scholar
[36]Teodorovic, D. and DellOrco, M., Bee colony optimizationa cooperative learning approach to complex tranportation problems, in Advanced OR and AI Methods in Transportation: Proceedings of 16th MiniEURO Conference and 10th Meeting of EWGT (13-16 September 2005), Poznan: Publishing House of the Polish Operational and System Research, pp. 51–60 (2005).Google Scholar
[37]Tuba, M., Bacanin, N. and Stanarevic, N., Adjusted artificial bee colony (ABC) algorithm for engineering problems, WSEAS Trans. Computers 11, 111–120 (2012).Google Scholar
[38]Tuba, M., Subotic, M. and Stanarevic, N., Performance of a modified cuckoo search algorithm for unconstrained optimization problems, WSEAS Trans. Systems 11, 62–74 (2012).Google Scholar
[39]Wilson, B., A Simplicial Algorithm for Concave Programming, Ph.D. Thesis, Harvard University (1963).Google Scholar
[40]Xu, S., Smoothing method for minimax problems, Comp. Optimization Appl. 20, 267–279 (2001).Google Scholar
[41]Yang, X.S., Firefly algorithm, stochastic test functions and design optimization, Int. J. Bio-Inspired Comp. 2, 78–84 (2010).Google Scholar
[42]Yang, X.S., A new meta-heuristic bat-inspired algorithm, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74 (2010).Google Scholar
[43]Zuhe, S., Neumaier, A. and Eiermann, M.C., Solving minimax problems by interval methods, BIT 30, 742–751 (1990).Google Scholar