Modified Shuffled Frog Leaping Algorithm for Improved Pareto-Set Computation: Application to Product Transport in Pipeline Networks
Tóm tắt
An efficiency improvement of product transport through pipeline networks can be obtained by a better allocation of available resources. That is a hard combinatorial problem with multi-objective optimization characteristics due to different types of products to be moved and the high occupance rate of the network. This paper presents a novel modified shuffled frog leaping algorithm, named modified shuffled frog leaping Pareto approach (MSFLPA), to solve this resource allocation problem. This new algorithm combines the use of a small population and an archiving strategy with a procedure to restart the population using two auxiliary memories to store nondominated solutions (Pareto set) found during population evolution. To validate the performance and efficiency of the proposed MSFLPA in spread Pareto front, five Zitzler–Deb–Thiele functions are examined and compared against two well-known multi-objective genetic algorithms: NSGA-II and SPEA2. The numerical experiments indicate that MSFLPA yields spread solutions and converges to the true Pareto front, and it is verified to be efficient and competitive for solving multi-objective problem. After this validation, the MSFLPA is used to optimize the allocation of resources and to solve the scheduling problem of a real-world pipeline network and if compared with NSGA-II and
$$\mu \hbox {GA}$$
, MSFLPA is verified to be a new effective alternative for solving multi-objective scheduling problems with more than two objectives as it is the case of the pipeline scheduling problems.
Tài liệu tham khảo
Arruda, L., Neves-Jr, F., & Yamamoto, L. (2010). Using moga to order batches in a real world pipeline network. In N. Garca-Pedrajas, F. Herrera, C. Fyfe, J. Bentez, & M. Ali (Eds.), Trends in applied intelligent systems, Lecture Notes in Computer Science (Vol. 6098, pp. 546–555). Berlin: Springer.
Arruda, L. V. R., Swiech, M. C. S., Neves-Jr, F., & Delgado, M. R. (2008). Um método evolucionário para sintonia de controladores PI/PID em processos multivariáveis. Sba: Controle & Automação Sociedade Brasileira de Automatica, 19, 1–17.
Boschetto, S. N., Magatão, L., Brondani, W. M., Neves-Jr, F., Arruda, L. V. R., Barbosa-Póvoa, A. P. F. D., et al. (2010). An operational scheduling model to product distribution through a pipeline network. Industrial and Engineering Chemistry Research, 49(12), 5661–5682.
Coello, C. A. C. (2003). Evolutionary multiobjective optimization: Current and future challenges. In J. M. Bentez, O. Cordn, F. Hoffmann, & R. Roy (Eds.), Advances in soft computing, Lecture Notes in Computer Science (pp. 243–256). London: Springer.
Cruz, J. M., Andres-Toro, B., Herrán, A., Besada, E. P., & Blanco, P. F. (2003). Multiobjective optimization of the transport in oil pipeline networks. In IEEE international conference on emerging technologies and factory automation (pp. 566–573).
De-Ming, L., & Zhi-Ming, W. (2005). Crowding-measure based multi-objective evolutionary algorithm. Chinese Journal of Computers, 28(8), 1320–1326.
Deb, K. (1999). Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3), 205–230.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. New York, NY: Wiley.
Deb, K., & Agrawal, S. (1995). Simulated binary crossover for continuos search space. Complex Systems, 9, 115–148.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
Dreo, J., Siarry, P., Petrowski, A., & Taillard, E. (2006). Metaheuristics for hard optimization. Heidelberg: Springer.
Elbehairy, H., Elbeltagi, E., Hegazy, T., & Soudki, K. (2006). Comparison of two evolutionary algorithms for optimization of bridge deck repairs. Computer-Aided Civil and Infrastructure Engineering, 21(8), 561–572.
Elbeltagi, E., Hegazy, T., & Grierson, D. (2005). Comparison among five evolutionary-based optimization algorithm. Advanced Engineering Informatics, 19, 43–53.
Elbeltagi, E., Hegazy, T., & Grierson, D. (2007). A modified shuffled frog-leaping optimization algorithm: Applications to project management. Structure and Infrastructure Engineering, 3, 53–56.
Eusuff, M., Lansey, K. E., & Pasha, F. (2006). Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization. Engineering Optimization, 38, 129–154.
Eusuff, M. M., & Lansey, K. E. (2003). Optimization of water distribution network design using the shuffled frog leaping algorithm. Water Resources Planning Management, 129, 210–225.
Grefenstette, J. J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, 16, 122–128.
Hertz, A., & Widmer, M. (2003). Guidelines for the use of meta-heuristics in combinatorial optimization. European Journal of Operational Research, 151, 247–252.
Lamboia, F., Arruda, L. V. R., & Neves-Jr, F. (2014). A modified shuffled frog-leaping algorithm to model products transport in pipeline networks. In H. Rodrigues, J. Herskovits, C. M. Soares, J. M. Guedes, A. Araujo, J. O. Folgado, F. Moleiro, & J. F. Madeira (Eds.), Engineering Optimization IV, (pp. 885–890). London: Taylor & Francis Group.
Li, Y., Zhou, J., Zhang, Y., Qin, H., & Liu, L. (2010). Novel multiobjective shuffled frog leaping algorithm with application to reservoir flood control operation. Journal of Water Resources Planning and Management, 136(2), 217–226.
Lopes, T., Cir, A., de Souza, C., & Moura, A. (2010). A hybrid model for a multiproduct pipeline planning and scheduling problem. Constraints, 15(2), 151–189.
Magato, S. N. B., Magatão, L., Luis Polli, H., Neves, F., de Arruda, L. V. R., Relvas, S., et al. (2012). Planning and sequencing product distribution in a real-world pipeline network: An milp decomposition approach. Industrial and Engineering Chemistry Research, 51(12), 4591–4609.
Neves-Jr, F., Magatão, L., Stebel, S. L., Boschetto, S., Felizari, L. C., Czaikowski, D. I., et al. (2007). An efficient approach to the operational scheduling of a real-world pipeline network. In V. Plesu & P. S. Agachi (Eds.), 17th European symposium on computer aided process engineering, computer aided chemical engineering (Vol. 24, pp. 697–702). Amsterdam: Elsevier.
Rahimi-Vahed, A., Dangchi, M., Rafiei, H., & Salimi, E. (2009). A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 41(11–12), 1227–1239.
Rahimi-Vahed, A., & Mirzaei, A. H. (2007). A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem. Computers & Industrial Engineering, 53(4), 642–666.
Relvas, S., Matos, H. A., Barbosa-Pvoa, A. P. F. D., Fialho, J., & Pinheiro, A. S. (2006). Pipeline scheduling and inventory management of a multiproduct distribution oil system. Industrial & Engineering Chemistry Research, 45(23), 7841–7855.
Ribas, P., Yamamoto, L., Polli, H. L., Arruda, L., & Neves-Jr, F. (2013). A micro-genetic algorithm for multi-objective scheduling of a real world pipeline network. Engineering Applications of Artificial Intelligence, 26(1), 302–313.
Stebel, S. L., Magatão, S. N. B., Arruda, L. V. R., Neves, F, Jr, Povoa, A. P. F. D., & Relvas, S. (2012). Mixed integer linear programming formulation for aiding planning activities in a complex pipeline network. Industrial and Engineering Chemistry Research, 51(35), 11417–11433.
Tiwari, S., Koch, P., Fadel, G., & Deb, K. (2008). Amga: An archive-based micro genetic algorithm for multi-objective optimization. In Proceedings of genetic and evolutionary computation conference (GECCO-2008), Atlanta, USA (pp. 729–736).
Walpole, R. E., Myers, R. H., Myers, S. L., & Ye, K. (1998). Probability and statistics for engineers and scientists. Upper Saddle River, NJ: Pearson Prentice Hall.
Westphal, H., & Arruda, L. V. R. (2007). Multiobjective optimization applied to the distribution of petroleum products in pipelines networks. In Proceedings of 17th European symposium on computer aided process engineering (pp. 1–6). Amsterdam: Elsevier.
Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173–195.
Zitzler, E., Laumanns, M., & Thiele, L. (2001). Spea2: Improving the strength pareto evolutionary algorithm. Tech. Rep. 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.