A Hybrid Genetic Algorithm and Gravitational Search Algorithm for Global Optimization

Aizu Zhang, Genyun Sun, Zhenjie Wang, Yanjuan Yao

Abstract


The laws of gravity and mass interactions inspire the gravitational search algorithm (GSA), which nds optimal regions of complex search spaces through the interaction of individuals in a population of particles. Although GSA has proven effective in both science and engineering, it is still easy to suffer from premature convergence especially facing complex problems. In this paper, we pro- posed a new hybrid algorithm by integrating genetic algorithm (GA) and GSA (GA-GSA) to avoid premature convergence and to improve the search ability of GSA. In GA-GSA, crossover and mutation operators are introduced from GA to GSA for jumping out of the local optima. To demonstrate the search ability of the proposed GA-GSA, 23 complex benchmark test functions were employed, including unimodal and multimodal high-dimensional test functions as well as multimodal test functions with xed dimensions. Wilcoxon signed-rank tests were also utilized to execute statistical analysis of the results obtained by PSO, GSA, and GA-GSA. Experimental results demonstrated that the proposed algorithm is both efficient and effective.

Keywords


heuristic algorithms; genetic algorithms; gravitational search algorithm; optimization

Full Text:

PDF

References


ANGELINE P.J. Using selection to improve particle swarm optimization. In: Proceedings

of the IEEE International Conference on Evolutionary Computation, Anchorage, Alaska.

IEEE, 1998, pp. 84-89, doi: 10.1109/ICEC.1998.699327.

CHELOUAH R., SIARRY P. Genetic and nelder-mead algorithms hybridized for a more

accurate global optimization of continuous multiminima functions. European Journal of Op-

erational Research. 2003, 148(2), pp. 335-348, doi: 10.1016/S0377-2217(02)00401-0.

CIVICIOGLU P. Transforming geocentric cartesian coordinates to geodetic coordinates by

using differential search algorithm. Computers & Geosciences. 2012, 46, pp. 229-247, doi:

1016/j.cageo.2011.12.011.

CIVICIOGLU P. Backtracking search optimization algorithm for numerical optimization

problems. Applied Mathematics and Computation. 2013, 219(15), pp. 8121-8144, doi:

1016/j.amc.2013.02.017.

CIVICIOGLU P. Artificial cooperative search algorithm for numerical optimization prob-

lems. Information Sciences. 2013, 229, pp. 58-76, doi: 10.1016/j.ins.2012.11.013.

CLERC M., KENNEDY J. The particle swarm-explosion, stability, and convergence in a

multidimensional complex space. IEEE Transactions on Evolutionary Computation. 2002,

(1), pp. 58-73, doi: 10.1109/4235.985692.

CUEVAS E., GONZALEZ M., ZALDIVAR D. An algorithm for global optimization inspired

by collective animal behavior. Discrete Dynamics in Nature and Society. 2012(2012), pp.24,

doi: 10.1155/2012/638275.

DERRAC J., et al. A practical tutorial on the use of nonparametric statistical tests as

a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and

Evolutionary Computation. 2011, 1(1), pp. 3-18, doi: 10.1016/j.swevo.2011.02.002.

DORIGO M., MANIEZZO V., COLORNI A. Ant system: optimization by a colony of coop-

erating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics.

, 26(1), pp. 29-41, doi: 10.1109/3477.484436.

DU W.L., LI B. Multi-strategy ensemble particle swarm optimization for dynamic optimiza-

tion. Information Sciences. 2008, 178(15), pp. 3096-3109, doi: 10.1016/j.ins.2008.01.020.

Neural Network World 1/15, 53-73

FAN S.F., ZAHARA E. Hybrid simplex search and particle swarm optimization for uncon-

strained optimization problems. European Journal of Operational Research. 2007, 181(2),

pp. 527-548, doi: 10.1016/j.ejor.2006.06.034.

GAO S., et al. Solving traveling salesman problem by hybrid particle swarm optimiza-

tion algorithm. Control and Decision. 2004, 19(11), pp. 1286-1289, doi: 10.3321/j.issn:1001.

2004.11.020.

GARC ´ IA S., et al. A study on the use of non-parametric tests for analyzing the evolutionary

algorithms’ behaviour: a case study on the cec’2005 special session on real parameter opti-

mization. Journal of Heuristics. 2009, 15(6), pp. 617-644, doi: 10.1007/s10732-008-9080-4.

GLOVER F., KOCHENBERGER G.A. Handbook of meta-heuristics. New York: Springer,

HOLLAND J.H. Adaptation in natural and artificial systems. Ann Arbor, MA, USA: The

University of Michigan Press, 1975.

JI Z., LIAO H.L., WU Q.H. PSO algorithm and its application. Beijing, China: Science

Press, 2009.

JUANG C.F. A hybrid of genetic algorithm and particle swarm optimization for recurrent

network design. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics.

, 34(2), pp. 997-1006, doi: 10.1109/TSMCB.2003.818557.

KENNEDY J., EBERHART R. Particle swarm optimization. In: Proceedings of the IEEE

International on Neural Networks, Perth, Australia. IEEE, 1995, pp. 1942-1948, doi:

1109/ICNN.1995.488968.

KIRKPATRICK S., GELATTO C.D., VECCHI M.P. Optimization by simulated annealing.

Science. 1983, 220(4598), pp. 671-680, doi: 10.1126/science.220.4598.671.

LAWLER E.L., WOOD D.E. Branch-and-bound methods: a survey. Operations Research.

, 14(4), pp. 699-719, doi: 10.1287/opre.14.4.699.

LI X.T., YIN M.H., MA Z.Q. Hybrid differential evolution and gravitation search algorithm

for unconstrained optimization. International Journal of the Physical Sciences. 2011, 6(25),

pp. 5961-5981, doi: 10.5897/IJPS11.029.

LIANG J.J., QIN A.K., SUGANTHAN P.N. Comprehensive learning particle swarm opti-

mizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary

Computation. 2006, 10(3), pp. 281-295, doi: 10.1109/TEVC.2005.857610.

LIU H.B., ABRAHAM A., ZHANG W.S. A fuzzy adaptive turbulent particle swarm opti-

mization. International Journal of Innovative Computing and Applications. 2007, 1(1), pp.

-47, doi: 10.1109/ICHIS.2005.49.

MANSOURI R., et al. Effective time variation of g in a model universe with variable space

dimension. Physics Letters. 1999, 259(3), pp. 194-200, doi: 10.1016/S0375-9601(99)00449-1.

LI R.J. New hybrid particle swarm optimization. Application Research of Computers. 2009,

(05), pp. 1700-1702, doi: 10.3969/j.issn.1001-3695.2009.05.028.

RASHEDI E., NEZAMABADI-POUR H., SARYAZDI S. GSA: a gravitational search algo-

rithm. Information Sciences. 2009, 179(13), pp. 2232-2248, doi: 10.1016/j.ins.2009.03.004.

RASHEDI E. Gravitational search algorithm. Iran, 2007. M.Sc. Thesis, Shahid Bahonar

University of Kerman.

RASHEDI E., et al. Allocation of static var compensator using gravitational search algo-

rithm. World. 2007, 1, pp. 10.

SARAFRAZI S., NEZAMABADI-POUR H., SARYAZDI S. Disruption: a new opera-

tor in gravitational search algorithm. Scientia Iranica. 2011, 18(3), pp. 539-548, doi:

1016/j.scient.2011.04.003.

SATHYA P.D., KAYALVIZHI R. PSO-based Tsallis thresholding selection procedure for

image segmentation. International Journal of Computer Applications. 2010, 5(4), pp. 39-46,

doi: 10.5120/903-1279.

Zhang A., et al.: A hybrid genetic algorithm and gravitational search. . .

SHAW B., MUKHERJEE V., GHOSHAL S.P. A novel opposition-based gravitational search

algorithm for combined economic and emission dispatch problems of power systems. In-

ternational Journal of Electrical Power and Energy Systems. 2012, 35(1), pp. 21-33, doi:

1016/j.ijepes.2011.08.012.

SHEN L.C., HUO X.H., NIU Y.F. Survey of discrete particle swarm optimization algorithm.

Systems Engineering and Electronics. 2008, 30(10), pp. 1986-1994, doi: 10.3321/j.issn:1001.

X.2008.10.039.

SHI F., et al. MATLAB intelligence algorithm: the 30 cases. Beijing, China: Beijing Uni-

versity of Aeronautics and Astronautics Press, 2011.

SNYMAN J.A. Practical mathematical optimization: an introduction to basic optimization

theory and classical and new gradient-based algorithms. New York: Springer, 2005.

SRIDHARA R.G., SASTRY V.V., VENKATA R.P. Comparison of nonlinear programming

techniques for the optimal design of transformers. In: Proceedings of the Institute Electrical

Engineers. IET Digital Library, 1977, 124(12), pp. 1225-1226, doi: 10.1049/piee.1977.0255.

SUMAN B. Study of simulated annealing based algorithms for multiobjective optimization

of a constrained problem. Computers & Chemical Engineering. 2004, 28(9), pp. 1849-1871,

doi: 10.1016/j.compchemeng.2004.02.037.

TANG K.S., et al. Genetic algorithms and their applications. IEEE Signal Processing Mag-

azine. 1996, 13(6), pp. 22-37, doi: 10.1109/79.543973.

VAN DEN BERGH F., ENGELBRECHT A.P. A study of particle swarm optimization particle trajectories. Information Sciences. 2006, 176(8), pp. 937-971, doi:

1016/j.ins.2005.02.003.

WANG Y.L., WANG Y.P. Based on mix GA-PSO nerve network algorithm. Computer Engineering and Applications. 2007, 43(2), pp. 38-40, doi: 10.3321/j.issn:1002-8331.2007.02.010.

WILCOXON F. Individual comparisons by ranking methods. Biometrics. 1945, 1(6), pp. 80-83, doi: 10.2307/3001968.

YAO X., LIU Y., LIN G. Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation. 1999, 3(2), pp. 82-102, doi: 10.1109/4235.771163.

YEN J., et al. A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cy-

bernetics. 1998, 28(2), pp. 173-191, doi: 10.1109/TPWRS.2005.860945.

ZARATE L.A., et al. Fast computation of voltage stability security margins using nonlinear programming techniques. IEEE Transactions on Power Systems. 2006, 21(1), pp. 19-27, doi: 10.1109/TPWRS.2005.860945.

ZHAO H.L., PANG X.H., WU Z.M. A building block coded parallel genetic algorithm and its application in TSP. Journal of Shanghai Jiaotong University. 2004, 38(S1), pp. 213-217,

doi: 10.3321/j.issn:1006-2467.2004.z1.051.

ZHOU Y., CHEN J.L. Review of genetic algorithms. Guangxi Journal of Light Industry. 2008, 1, pp. 84-85, doi: 10.3969/j.issn.1003-2673.2008.01.040.




DOI: http://dx.doi.org/10.14311/NNW.2015.25.003

Refbacks

  • There are currently no refbacks.


Should you encounter an error (non-functional link, missing or misleading information, application crash), please let us know at nnw.ojs@fd.cvut.cz.
Please, do not use the above address for non-OJS-related queries (manuscript status, etc.).
For your convenience we maintain a list of frequently asked questions here. General queries to items not covered by this FAQ shall be directed to the journal editoral office at nnw@fd.cvut.cz.