research-article

Cloudde: A Heterogeneous Differential Evolution Algorithm and Its Distributed Cloud Version

Authors:

Huaxiang Zhang,

Jun ZhangAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 28, Issue 3

Pages 704 - 716

https://doi.org/10.1109/TPDS.2016.2597826

Published: 01 March 2017 Publication History

Abstract

Existing differential evolution (DE) algorithms often face two challenges. The first is that the optimization performance is significantly affected by the ad hoc configurations of operators and parameters for different problems. The second is the long runtime for real-world problems whose fitness evaluations are often expensive. Aiming at solving these two problems, this paper develops a novel double-layered heterogeneous DE algorithm and realizes it in cloud computing distributed environment. In the first layer, different populations with various parameters and/or operators run concurrently and adaptively migrate to deliver robust solutions by making the best use of performance differences among multiple populations. In the second layer, a set of cloud virtual machines run in parallel to evaluate fitness of corresponding populations, reducing computational costs as offered by cloud. Experimental results on a set of benchmark problems with different search requirements and a case study with expensive design evaluations have shown that the proposed algorithm offers generally improved performance and reduced computational time, compared with not only conventional and a number of state-of-the-art DE variants, but also a number of other distributed DE and high-performing evolutionary algorithms. The speedup is significant especially on expensive problems, offering high potential in a broad range of real-world applications.

References

[1]

M. D. Dikaiakos, G. Pallis, D. Katsaros, P. Mehra, and A. Vakali, “ Cloud computing: Distributed internet computing for IT and scientific research,” IEEE Internet Comput., vol. Volume 13, no. Issue 5, pp. 10–13, 2009.

Digital Library

[2]

S. Bera, S. Misra, and J. Rodrigues, “ Cloud computing applications for smart grid: A survey,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 26, no. Issue 5, pp. 1477–1494, 2015.

Digital Library

[3]

Z. H. Zhan, X. F. Liu, Y. J. Gong, J. Zhang, H. S. H. Chung, and Y. Li, “ Cloud computing resource scheduling and a survey of its evolutionary approaches,” ACM Comput. Surveys, vol. Volume 47, no. Issue 4, pp. 1–33, 2015, Art. no. 63.

Digital Library

[4]

Z. Zhu, G. Zhang, M. Li, and X. Liu, “ Evolutionary multi-objective workflow scheduling in cloud,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 27, no. Issue 5, pp. 1344–1357, 2016.

Digital Library

[5]

X. F. Liu, Z. H. Zhan, K. J. Du, and W. N. Chen, “ Energy aware virtual machine placement scheduling in cloud computing based on ant colony optimization approach,” in Proc. Genetic Evol. Comput. Conf., 2014, pp. 41–47.

Digital Library

[6]

H. F. Sheikh, I. Ahmad, and D. Fan, “ An evolutionary technique for performance-energy-temperature optimized scheduling of parallel tasks on multi-core processors,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 27, no. Issue 3, pp. 668–681, 2016.

Digital Library

[7]

W. Guo, J. Li, G. Chen, Y. Niu, and C. Chen, “ A PSO-optimized real-time fault-tolerant task allocation algorithm in wireless sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 26, no. Issue 12, pp. 3236–3249, 2015.

Digital Library

[8]

H. K. Hsin, E. J. Chang, and A. Y. Wu, “ Spatial-temporal enhancement of ACO-based selection schemes for adaptive routing in network-on-chip systems,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 25, no. Issue 6, pp. 1626–1637, 2014.

Digital Library

[9]

J. Zhang, et al., “ Evolutionary computation meets machine learning: A survey,” IEEE Comput. Intell. Mag., vol. Volume 6, no. Issue 4, pp. 68–75, 2011.

Digital Library

[10]

Y. J. Gong, et al., “ Distributed evolutionary algorithms and their models: A survey of the state-of-the-art,” Appl. Soft Comput., vol. Volume 34, pp. 286–300, 2015.

Digital Library

[11]

K. C. Tan, Y. J. Yang, and C. K. Goh, “ A distributed cooperative coevolutionary algorithm for multiobjective optimization,” IEEE Trans. Evol. Comput., vol. Volume 10, no. Issue 5, pp. 527–549, 2006.

Digital Library

[12]

E. Dilettoso, S. A. Rizzo, and N. Salerno, “ A parallel version of the self-adaptive low-high evaluation evolutionary-algorithm for electromagnetic device optimization,” IEEE Trans. Magn., vol. Volume 50, no. Issue 2, pp. 1–4, 2014.

[13]

R. Storn and K. Price, “ Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces,” J. Global Optimization, vol. Volume 11, no. Issue 4, pp. 341–359, 1997.

Digital Library

[14]

R. Storn, “ On the usage of differential evolution for function optimization,” in Proc. North Amer. Fuzzy Inf. Process. Soc. Conf., 1996, pp. 519–523.

[15]

E. Mezura-Montes, J. Velázquez-Reyes, and C. A. C. Coello, “ A comparative study of differential evolution variants for global optimization,” in Proc. Genetic Evol. Comput. Conf., 2006, pp. 485–492.

Digital Library

[16]

A. Salman, A. P. Engelbrecht, and M. G. H. Omran, “ Empirical analysis of self-adaptive differential evolution,” Eur. J. Oper. Res., vol. Volume 183, no. Issue 2, pp. 785–804, 2007.

[17]

J. Brest, S. Greiner, B. Boskovic, M. Mernik, and V. Zumer, “ Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems,” IEEE Trans. Evol. Comput., vol. Volume 10, no. Issue 6, pp. 646–657, 2006.

Digital Library

[18]

A. K. Qin, V. L. Huang, and P. N. Suganthan, “ Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Trans. Evol. Comput., vol. Volume 13, no. Issue 2, pp. 398–417, 2009.

Digital Library

[19]

J. Q. Zhang and A. C. Sanderson, “ JADE: Adaptive differential evolution with optional external archive,” IEEE Trans. Evol. Comput., vol. Volume 13, no. Issue 5, pp. 945–958, 2009.

Digital Library

[20]

Z. H. Zhan and J. Zhang, “ Self-adaptive differential evolution based on PSO learning strategy,” in Proc. Genetic Evol. Comput. Conf., 2010, pp. 39–46.

Digital Library

[21]

Q. Liu, W. Wei, H. Yuan, Z. H. Zhan, and Y. Li, “ Topology selection for particle swarm optimization,” Inf. Sci., vol. Volume 363, no. Issue 1, pp. 154–173, 2016.

Digital Library

[22]

Y. H. Li, Z. H. Zhan, S. J. Lin, J. Zhang, and X. N. Luo, “ Competitive and cooperative particle swarm optimization with information sharing mechanism for global optimization problems,” Inf. Sci., vol. Volume 293, no. Issue 1, pp. 370–382, 2015.

[23]

W. J. Yu et al., “ Differential evolution with two-level parameter adaptation,” IEEE Trans. Cybern., vol. Volume 44, no. Issue 7, pp. 1080–1099, 2014.

[24]

Y. Wang, Z. X. Cai, and Q. F. Zhang, “ Differential evolution with composite trial vector generation strategies and control parameters,” IEEE Trans. Evol. Comput., vol. Volume 15, no. Issue 1, pp. 55–66, 2011.

Digital Library

[25]

X. F. Liu, Z. H. Zhan, and J. Zhang, “ Dichotomy guided based parameter adaptation for differential evolution,” in Proc. Genetic Evol. Comput. Conf., 2015, pp. 289–296.

Digital Library

[26]

S. M. Islam, S. Das, S. Ghosh, S. Roy, and P. N. Suganthan, “ An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization,” IEEE Trans. Syst. Man Cybern. B, vol. Volume 42, no. Issue 2, pp. 482–500, 2012.

Digital Library

[27]

S. M. Elsayed, R. A. Sarker, and D. L. Essam, “ An improved self-adaptive differential evolution algorithm for optimization problems,” IEEE Trans. Ind. Informat., vol. Volume 9, no. Issue 1, pp. 89–99, 2013.

[28]

B. Dorronsoro and P. Bouvry, “ Improving classical and decentralized differential evolution with new mutation operator and population topologies,” IEEE Trans. Evol. Comput., vol. Volume 15, no. Issue 1, pp. 67–98, 2011.

Digital Library

[29]

M. G. Epitropakis, D. K. Tasoulis, N. G. Pavlidis, V. P. Plagianakos, and M. N. Vrahatis, “ Enhancing differential evolution utilizing proximity-based mutation operators,” IEEE Trans. Evol. Comput., vol. Volume 15, no. Issue 1, pp. 99–119, 2011.

Digital Library

[30]

S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “ Opposition-based differential evolution,” IEEE Trans. Evol. Comput., vol. Volume 12, no. Issue 1, pp. 64–79, 2008.

Digital Library

[31]

N. Noman and H. Iba, “ Accelerating differential evolution using an adaptive local search,” IEEE Trans. Evol. Comput., vol. Volume 12, no. Issue 1, pp. 107–125, 2008.

Digital Library

[32]

U. K. Chakraborty, S. Das, and A. Konar, “ Differential evolution with local neighborhood,” in Proc. IEEE Congr. Evol. Comput., 2006, pp. 2042–2049.

[33]

Y. L. Li, Z. H. Zhan, Y. J. Gong, W. N. Chen, J. Zhang, and Y. Li, “ Differential evolution with an evolution path: A DEEP evolutionary algorithm,” IEEE Trans. Cybern., vol. Volume 45, no. Issue 9, pp. 1798–1810, 2015.

[34]

Z. H. Zhan and J. Zhang, “ Enhance differential evolution with random walk,” in Proc. Genetic Evol. Comput. Conf., 2012, pp. 1513–1514.

Digital Library

[35]

M. Vasile, E. Minisci, and M. Locatelli, “ An inflationary differential evolution algorithm for space trajectory optimization,” IEEE Trans. Evol. Comput., vol. Volume 15, no. Issue 2, pp. 267–281, 2011.

Digital Library

[36]

A. Basak, S. Das, and K. C. Tan, “ Multimodal optimization using a biobjective differential evolution algorithm enhanced with mean distance-based selection,” IEEE Trans. Evol. Comput., vol. Volume 17, no. Issue 6, pp. 666–685, 2013.

Digital Library

[37]

R. L. Becerra and C. A. C. Coello, “ Cultured differential evolution for constrained optimization,” Comput. Methods Appl. Mechanics Eng., vol. Volume 195, pp. 4303–4322, 2006.

[38]

A. Biswas, S. Dasgupta, S. Das, and A. Abraham, “ A synergy of differential evolution and bacterial foraging algorithm for global optimization,” Neural Netw. World, vol. Volume 17, no. Issue 6, pp. 607–626, 2007.

[39]

R. Storn, “ System design by constraint adaptation and differential evolution,” IEEE Trans. Evol. Comput., vol. Volume 3, no. Issue 1, pp. 22–34, 1999.

Digital Library

[40]

J. H. Zhong, M. Shen, J. Zhang, H. Chung, Y. H. Shi, and Y. Li, “ A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem,” IEEE Trans. Evol. Comput., vol. Volume 17, no. Issue 4, pp. 512–527, 2013.

Digital Library

[41]

F. Neri and E. Mininno, “ Memetic compact differential evolution for Cartesian robot control,” IEEE Comput. Intell. Mag., vol. Volume 5, no. Issue 2, pp. 54–65, 2010.

Digital Library

[42]

N. Noman and H. Iba, “ Inferring gene regulatory networks using differential evolution with local search heuristics,” IEEE/ACM Trans. Comput. Biol. Bioinform., vol. Volume 4, no. Issue 4, pp. 634–647, 2007.

Digital Library

[43]

B. V. Babu and R. Angira, “ Modified differential evolution (MDE) for optimization of non-linear chemical processes,” Comput. Chem. Eng., vol. Volume 30, no. Issue 6/7, pp. 989–1002, 2006.

[44]

G. Chen, A. Sarrafzadeh, and S. Pang, “ Service provision control in federated service providing systems,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 24, no. Issue 3, pp. 587–600, 2013.

Digital Library

[45]

Y. L. Li, Z. H. Zhan, Y. J. Gong, J. Zhang, Y. Li, and Q. Li, “ Fast micro-differential evolution for topological active net optimization,” IEEE Trans. Cybern., vol. Volume 46, no. Issue 6, pp. 1411–1423, 2016.

[46]

Z. H. Zhan and J. Zhang, “ Differential evolution for power electronic circuit optimization,” in Proc. Conf. Technol. Appl. Artificial Intell., 2015, pp. 158–163.

[47]

D. K. Tasoulis, N. G. Pavlidis, V. P. Plagianakos, and M. N. Vrahatis, “ Parallel differential evolution,” in Proc. IEEE Congr. Evol. Comput., 2004, pp. 2023–2029.

[48]

W. Kwedlo and K. Bandurski, “ A parallel differential evolution algorithm,” in Proc. IEEE Int. Symp. Parallel Comput. Electr. Eng., 2006, pp. 319–324.

Digital Library

[49]

K. N. Kozlov and A. M. Samsonov, “ New migration scheme for parallel differential evolution,” in Proc. Int. Conf. Bioinfor. Genome Regulation Structure, 2006, pp. 141–144.

[50]

J. Apolloni, G. Leguizamón, J. García-Nieto, and E. Alba, “ Island based distributed differential evolution: An experimental study on hybrid testbeds,” in Proc. IEEE Int. Conf. Hybrid Intell. Syst., 2008, pp. 696–701.

Digital Library

[51]

M. Weber, F. Neri, and V. Tirronen, “ A study on scale factor in distributed differential evolution,” Inf. Sci., vol. Volume 181, pp. 2488–2311, 2011.

Digital Library

[52]

M. Weber, F. Neri, and V. Tirronen, “ A study on scale factor/crossover interaction in distributed differential evolution,” Artificial Intell. Rev., vol. Volume 39, no. Issue 3, pp. 195–224, 2013.

Digital Library

[53]

M. Salomon, G. R. Perrin, F. Heitz, and J. P. Armspach, “ Parallel differential evolution: Application to 3-D medical image registration,” Differential Evolution . Berlin, Germany: Springer, 2005, pp.353–411.

[54]

I. De Falco, A. Della Cioppa, D. Maisto, U. Scafuri, and E. Tarantino, “ Satellite image registration by distributed differential evolution,” Applications of Evolutionary Computing . Berlin, Germany: Springer, 2007, pp. 251–260.

Digital Library

[55]

W. J. Yu and J. Zhang, “ Multi-population differential evolution with adaptive parameter control for global optimization,” in Proc. Genetic Evol. Comput. Conf., 2011, pp. 1093–1098.

Digital Library

[56]

R. Mallipeddi, P. N. Suganthan, Q. K. Pan, and M. F. Tasgetiren, “ Differential evolution algorithm with ensemble of parameters and mutation strategies,” Appl. Soft Comput., vol. Volume 11, no. Issue 2, pp. 1679–1696, 2011.

Digital Library

[57]

T. Ishimizu and K. Tagawa, “ Experiment study of a structured differential evolution with mixed strategies,” in Proc. 2nd World Congr. Nature Biologically Inspired Comput., 2010, pp. 591–596.

[58]

W. Gropp, E. Lusk, N. Doss, and A. Skjellum, “ A high-performance, portable implementation of the MPI message passing interface standard,” Parallel Comput., vol. Volume 22, no. Issue 6, pp. 789–828, 1996.

Digital Library

[59]

Z. H. Zhan, J. Zhang, Y. Li, and Y. H. Shi, “ Orthogonal learning particle swarm optimization,” IEEE Trans. Evol. Comput., vol. Volume 15, no. Issue 6, pp. 832–847, 2011.

[60]

Z. H. Zhan and J. Zhang, “ Orthogonal learning particle swarm optimization for power electronic circuit optimization with free search range,” in Proc. IEEE Congr. Evol. Comput., 2011, pp. 2563–2570.

[61]

X. F. Liu, Z. H. Zhan, J. H. Lin, and J. Zhang, “ Parallel differential evolution on distributed computational resources for power electronic circuit optimization,” in Proc. Genetic Evol. Comput. Conf., 2016, pp. 117–118.

Digital Library

[62]

Z. H. Zhan, J. Zhang, Y. Li, and H. Chung, “ Adaptive particle swarm optimization,” IEEE Trans. Syst. Man Cybern. B, vol. Volume 39, no. Issue 6, pp. 1362–1381, 2009.

Digital Library

[63]

A. Auger and N. Hansen, “ Performance evaluation of an advanced local search evolutionary algorithm,” in Proc. IEEE Congr. Evol. Comput., 2005, pp. 1777–1784.

[64]

Z. H. Zhan, J. J. Li, J. N. Cao, J. Zhang, H. Chung, and Y. H. Shi, “ Multiple populations for multiple objectives: A coevolutionary technique for solving multiobjective optimization problems,” IEEE Trans. Cybern., vol. Volume 43, no. Issue 2, pp. 445–463, 2013.

Cited By

Bu XZhang QGao HZhang H(2024)Multi-strategy differential evolution algorithm based on adaptive hash clustering and its application in wireless sensor networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123214246:COnline publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123214
Lin ZLi JLi Y(2024)A cloud computing approach to superscale colored traveling salesman problemsThe Journal of Supercomputing10.1007/s11227-024-06433-x80:19(27340-27369)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11227-024-06433-x
Xin Sui Zhu LSong XSheng GLiu D(2023)The Green Scheduling Architecture for the Virtual Resource SupplyAutomatic Control and Computer Sciences10.3103/S014641162301010857:1(14-26)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.3103/S0146411623010108
Show More Cited By

Recommendations

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

The proposed constrained differential evolution framework uses nondominated sorting mutation operator based on fitness and diversity information for constrained optimization. This study proposes a new constraint differential evolution framework.Parents ...
Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformatics

This paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...
Comparison of cauchy EDA and BIPOP-CMA-ES algorithms on the BBOB noiseless testbed
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

Estimation-of-distribution algorithm using Cauchy sampling distribution is compared with the bi-population CMA evolutionary strategy which was one of the best contenders in the black-box optimization benchmarking workshop in 2009. The results clearly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 28, Issue 3

March 2017

313 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Press

Publication History

Published: 01 March 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bu XZhang QGao HZhang H(2024)Multi-strategy differential evolution algorithm based on adaptive hash clustering and its application in wireless sensor networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123214246:COnline publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123214
Lin ZLi JLi Y(2024)A cloud computing approach to superscale colored traveling salesman problemsThe Journal of Supercomputing10.1007/s11227-024-06433-x80:19(27340-27369)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s11227-024-06433-x
Xin Sui Zhu LSong XSheng GLiu D(2023)The Green Scheduling Architecture for the Virtual Resource SupplyAutomatic Control and Computer Sciences10.3103/S014641162301010857:1(14-26)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.3103/S0146411623010108
Zhan ZLi JKwong SZhang J(2023)Learning-Aided Evolution for OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.323277627:6(1794-1808)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3232776
Jiang YZhan ZTan KZhang J(2023)A Bi-Objective Knowledge Transfer Framework for Evolutionary Many-Task OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321078327:5(1514-1528)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3210783
Wang ZJian JZhan ZLi YKwong SZhang J(2023)Gene Targeting Differential Evolution: A Simple and Efficient Method for Large-Scale OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.318566527:4(964-979)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3185665
Zhao HTang LLi JLiu J(2023)Strengthening evolution-based differential evolution with prediction strategy for multimodal optimization and its application in multi-robot task allocationApplied Soft Computing10.1016/j.asoc.2023.110218139:COnline publication date: 10-May-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110218
Wang ZCao ZDu ZJia HHan BTian FLiu F(2022)Differential Evolution with Autonomous Selection of Mutation Strategies and Control Parameters and Its ApplicationComplexity10.1155/2022/72750882022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/7275088
Wang YLi JChen CZhang JZhan Z(2022)Scale adaptive fitness evaluation‐based particle swarm optimisation for hyperparameter and architecture optimisation in neural networks and deep learningCAAI Transactions on Intelligence Technology10.1049/cit2.121068:3(849-862)Online publication date: 2-Jun-2022
https://dl.acm.org/doi/10.1049/cit2.12106
Zhan ZLi JZhang J(2022)Evolutionary deep learningNeurocomputing10.1016/j.neucom.2022.01.099483:C(42-58)Online publication date: 28-Apr-2022
https://dl.acm.org/doi/10.1016/j.neucom.2022.01.099
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents