MIDACO parallelization scalability on 200 minlp benchmarks

• Autorzy: Schlueter M. , Munetomo M.

Identyfikatory

DOI

10.1515/jaiscr-2017-0012

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

MINLP; optimization; MIDACO; parallelization

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2017
• Tom: Vol. 7, No. 3
• Strony: 171--181
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Schlueter M.

• Information Initiative Center, Hokkaido University Sapporo, Sapporo 060-0811, Japan

autor

Munetomo M.

• Information Initiative Center, Hokkaido University Sapporo, Sapporo 060-0811, Japan

Bibliografia

• [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.
• [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.
• [3] Costa L., Oliveira P., Evolutionary algorithms approach to the solution of mixed integer nonlinear programming problems, Comput Chem Eng, 25(23), 2001, 257-266.
• [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.
• [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.
• [6] Glover F., Parametric tabu-search for mixed integer programs, Comput Oper Res 33(9), 2006,24492494.
• [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.
• [8] Quinn J.M., Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2003.
• [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.
• [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.
• [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.
• [12] Mohamed A.W., An efficient modified differential evolution algorithm for solving constrained nonlinear integer and mixed-integer global optimization problems. Int. J. Mach. Learn. & Cyber., 2015, pp. 1–19.
• [13] Munawar A., Redesigning Evolutionary Algorithms for Many-Core Processors Ph.D. Thesis, Graduate School of Information Science and Technology, Hokkaido University, Japan, 2012.
• [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.
• [15] Powell D., Hollingsworth J., A NSGA-II, webenabled, parallel optimization framework for NLP and MINLP, Proceedings of the 9th annual conference on Genetic and evolutionary computation, 2007, pp. 2145–2150.
• [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.
• [17] Schlueter M., Egea J.A., Banga J.R., Extended antcolony optimization for non-convex mixed integer nonlinear programming, Comput. Oper. Res. 36(7), 2009, 2217–2229.
• [18] Schlueter M., Gerdts M., The Oracle Penalty Method. J. Global Optim. 47(2), 2010, 293–325.
• [19] Schlueter, M., Gerdts, M., Rueckmann J.J., A Numerical Study of MIDACO on 100 MINLP Benchmarks, Optimization 7(61), 2012, pp. 873–900.
• [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.
• [21] Schlueter M., MIDACO Software Performance on Interplanetary Trajectory Benchmarks, Advances in Space Research, 54(4), 2014, 744–754.
• [22] Schlueter M., MIDACO Solver - Global Optimization Software for Mixed Integer Nonlinear Programming, Software available at http://www.midacosolver.com, 2016.
• [23] Schlueter M., Munetomo M., Numerical Assessment of the Parallelization Scalability on 200 MINLP Benchmarks, Proc. of the IEEE-CEC2016 Conference, Vancouver, Canada, 2016.
• [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.
• [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.
• [26] K. Socha and M. Dorigo, Ant colony optimization for continuous domains, Eur. J. Oper. Res. 85, 2008, pp. 1155–1173.
• [27] Sudholt D., Parallel Evolutionary Algorithms, In Janusz Kacprzyk and Witold Pedrycz (Eds.): Handbook of Computational Intelligence, Springer, 2015.
• [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.
• [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.
• [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.
• [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.
• [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.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).