1. bookVolume 7 (2017): Issue 3 (July 2017)
Zeitschriftendaten
License
Format
Zeitschrift
Erstveröffentlichung
30 Dec 2014
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
access type Open Access

MIDACO Parallelization Scalability on 200 MINLP Benchmarks

Online veröffentlicht: 20 Mar 2017
Seitenbereich: 171 - 181
Eingereicht: 16 Sep 2016
Akzeptiert: 15 Nov 2016
Zeitschriftendaten
License
Format
Zeitschrift
Erstveröffentlichung
30 Dec 2014
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch

This contribution presents a numerical evaluation of the impact of parallelization on the performance of an evolutionary algorithm for mixed-integer nonlinear programming (MINLP). On a set of 200 MINLP benchmarks the performance of the MIDACO solver is assessed with gradually increasing parallelization factor from one to three hundred. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to CPU-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.

[1] Babu B., Angira A., A differential evolution approach for global optimisation of minlp problems, In: Proceedings of the Fourth Asia Pacific Conference on Simulated Evolution and Learning (SEAL 2002), Singapore, 2002, pp. 880–884.Search in Google Scholar

[2] Cardoso M.F., Salcedo R.L., Azevedo S.F., Barbosa D., A simulated annealing approach to the solution of MINLP problems, Computers Chem. Engng. 12(21), 1997, pp. 1349–1364.Search in Google Scholar

[3] Costa L., Oliveira P., Evolutionary algorithms approach to the solution of mixed integer non-linear programming problems, Comput Chem Eng, 25(23), 2001, 257-266.Search in Google Scholar

[4] Deep K., Krishna P.S., Kansal M.L., Mohan C., A real coded genetic algorithm for solving integer and mixed integer optimization problems. Appl. Math. Comput., 212(2), 2009, pp. 505–518.Search in Google Scholar

[5] European Space Agency (ESA) and Advanced Concepts Team (ACT), Gtop database - global optimisation trajectory problems and solutions, Software available at http://www.esa.int/gsp/ACT/inf/op/globopt.htm, 2011.Search in Google Scholar

[6] Glover F., Parametric tabu-search for mixed integer programs, Comput Oper Res 33(9), 2006, 24492494.Search in Google Scholar

[7] Gupta S., Tan G., A scalable parallel implementation of evolutionary algorithms for multi-objective optimization on GPUs, Evolutionary Computation (CEC), IEEE Congress on, Sendai, 2015, pp. 1567–1574.Search in Google Scholar

[8] Quinn J.M., Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2003.Search in Google Scholar

[9] GAMS MINLPlib - A collection of Mixed Integer Nonlinear Programming models. Washington, DC, USA; software available at http://www.gamsworld.org/minlp/minlplib.htm, 2016.Search in Google Scholar

[10] Laessig J., Sudholt D., General upper bounds on the runtime of parallel evolutionary algorithms, Evolutionary Computation, vol. 22, no. 3, 2014, pp. 405-437.Search in Google Scholar

[11] Liang B., Wang J., Jiang Y., Huang D., Improved Hybrid Differential Evolution-Estimation of Distribution Algorithm with Feasibility Rules for NLP/MINLP, Engineering Optimization Problems, Chin. J. Chem. Eng. 20(6), 2012, pp. 1074–1080.Search in Google Scholar

[12] Mohamed A.W., An efficient modified differential evolution algorithm for solving constrained non-linear integer and mixed-integer global optimization problems. Int. J. Mach. Learn. & Cyber., 2015, pp. 1–19.Search in Google Scholar

[13] Munawar A., Redesigning Evolutionary Algorithms for Many-Core Processors Ph.D. Thesis, Graduate School of Information Science and Technology, Hokkaido University, Japan, 2012.Search in Google Scholar

[14] Du X., Ni Y., Yao Z., Xiao R., High performance parallel evolutionary algorithm model based on MapReduce framework, Int. J. Computer Applications in Technology, Vol. 46, No. 3, 2013, pp. 290–296.Search in Google Scholar

[15] Powell D., Hollingsworth J., A NSGA-II, web-enabled, parallel optimization framework for NLP and MINLP, Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, pp. 2145–2150.Search in Google Scholar

[16] Sakuray Pais M., Yamanaka K., Rodrigues Pinto E., Rigorous Experimental Performance Analysis of Parallel Evolutionary Algorithms on Multicore Platforms, In IEEE Latin America Transactions, vol. 12, no. 4, 2014, pp. 805–811.Search in Google Scholar

[17] Schlueter M., Egea J.A., Banga J.R., Extended ant-colony optimization for non-convex mixed integer nonlinear programming, Comput. Oper. Res. 36(7), 2009, 2217–2229.Search in Google Scholar

[18] Schlueter M., Gerdts M., The Oracle Penalty Method. J. Global Optim. 47(2), 2010, 293–325.Search in Google Scholar

[19] Schlueter, M., Gerdts, M., Rueckmann J.J., A Numerical Study of MIDACO on 100 MINLP Benchmarks, Optimization 7(61), 2012, pp. 873–900.Search in Google Scholar

[20] Schlueter M., Erb S., Gerdts M., Kemble S., Rueckmann J.J., MIDACO on MINLP Space Applications, Advances in Space Research, 51(7), 2013, 1116–1131.Search in Google Scholar

[21] Schlueter M., MIDACO Software Performance on Interplanetary Trajectory Benchmarks, Advances in Space Research, 54(4), 2014, 744–754.Search in Google Scholar

[22] Schlueter M., MIDACO Solver - Global Optimization Software for Mixed Integer Nonlinear Programming, Software available at http://www.midaco-solver.com, 2016.Search in Google Scholar

[23] Schlueter M., Munetomo M., Numerical Assessment of the Parallelization Scalability on 200 MINLP Benchmarks, Proc. of the IEEE-CEC2016 Conference, Vancouver, Canada, 2016.Search in Google Scholar

[24] K. Schittkowski, A Collection of 200 Test Problems for Nonlinear Mixed-Integer Programming in Fortran (User Guide), Report, Department of Computer Science, University of Bayreuth, Bayreuth, 2012.Search in Google Scholar

[25] K. Schittkowski, NLPQLP - A Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line search (User Guide), Report, Department of Computer Science, University of Bayreuth, Bayreuth, 2009.Search in Google Scholar

[26] K. Socha and M. Dorigo, Ant colony optimization for continuous domains, Eur. J. Oper. Res. 85, 2008, pp. 1155–1173.Search in Google Scholar

[27] Sudholt D., Parallel Evolutionary Algorithms, In Janusz Kacprzyk and Witold Pedrycz (Eds.): Handbook of Computational Intelligence, Springer, 2015.Search in Google Scholar

[28] Wasanapradit T., Mukdasanit N., Chaiyaratana N., Srinophakun T., Solving mixed-integer nonlinear programming problems using improved genetic algorithms, Korean J. Chem. Eng. 28(1), 2011, 32–40.Search in Google Scholar

[29] Yiqing L., Xigang Y., Yongjian L., An improved PSO algorithm for solving non-convex NLP/MINLP problems with equality constraints, Comp. Chem. Eng. 3(31), 2007, 153–162.Search in Google Scholar

[30] Young C.T., Zheng Y., Yeh C.W., Jang S.S., Information-guided genetic algorithm approach to the solution of MINLP problems, Ind. Eng. Chem. Res. 46, 2007, pp. 1527–1537.Search in Google Scholar

[31] Yingyong Z., Yongde Z., Qinghua L., Jingang J., Guangbin Y., Improved Multi-objective Genetic Algorithm Based on Parallel Hybrid Evolutionary Theory, International Journal of Hybrid Information Technology Vol.8, No.1, 2015, pp. 133–140.Search in Google Scholar

[32] Yue T., Guan-Zheng T., Shu-Guang D., Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems. J. Central South Univ., 2014, 21:2731–2742.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo