×

Linear programming-based directed local search for expensive multi-objective optimization problems: application to drinking water production plants. (English) Zbl 1403.90598

Summary: Local search (LS) is an essential module of most hybrid meta-heuristic evolutionary algorithms which are a major approach aimed to solve efficiently multi-objective optimization (MOO) problems. Furthermore, LS is specifically useful in many real-world applications where there is a need only to improve a current state of a system locally with limited computational budget and/or relying on computationally expensive process simulators. In these contexts, this paper proposes a new neighborhood-based iterative LS method, relying on first derivatives approximation and linear programming (LP), aiming to steer the search along any desired direction in the objectives space. The paper also leverages the directed local search (DS) method to constrained MOO problems. These methods are applied to the bi-objective (cost versus life cycle assessment-based environmental impact) optimization of drinking water production plants. The results obtained show that the proposed method constitutes a promising local search method which clearly outperforms the directed search approach.

MSC:

90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi, A.; Tiruta-Barna, L., A process modelling - life cycle assessment - multiobjective optimization (PM-LCA-MOO) tool for the eco-design of conventional treatment processes of potable water, Journal of Cleaner Production, 100, 1, 116-125 (2015)
[2] Amaran, S.; Sahinidis, N. V.; Sharda, B.; Bury, S. J., Simulation optimization: A review of algorithms and applications, 4OR, 12, 4, 301-333 (2014) · Zbl 1317.90002
[3] Azapagic, A.; Clift, R., The application of life cycle assessment to process optimization, Computers & Chemical Engineering, 10, 1509-1526 (1999)
[4] Binois, M.; Ginsbourger, D.; Roustant, O., Quantifying uncertainty on pareto fronts with Gaussian process conditional simulations, European Journal of Operational Research, 243, 2, 386-394 (2015) · Zbl 1346.90730
[5] Bleuler, S.; Laumanns, M.; Thiele, L.; Zitzler, E., PISA - A platform and programming language independent interface for search algorithms, Evolutionary multi-criterion optimization, 494-508 (2003), Springer · Zbl 1037.68743
[6] Blum, C.; Puchinger, J.; Raidl, G. R.; Roli, A., Hybrid metaheuristics in combinatorial optimization: A survey, Applied Soft Computing, 11, 6, 4135-4151 (2011)
[7] Blum, C.; Raidl, G., Hybrid metaheuristics: Powerful tools for optimization (2016), Springer
[8] Capitanescu, F.; Ahmadi, A.; Benetto, E.; Marvuglia, A.; Tiruta-Barna, L., Some efficient approaches for multi-objective constrained optimization of computationally expensive black-box model problems, Computers & Chemical Engineering, 82, 228-239 (2015)
[9] Capitanescu, F.; Igos, E.; Marvuglia, A.; Benetto, E., Coupling multi-objective constrained optimization, life cycle assessment, and detailed process simulation for potable water treatment chains, Journal of Environmental Accounting and Management, Special issue on computational algorithms for sustainability assessment, 3, 3, 213-224 (2015)
[10] Dächert, K.; Klamroth, K.; Lacour, R.; Vanderpooten, D., Efficient computation of the search region in multi-objective optimization, European Journal of Operational Research, 260, 3, 841-855 (2017) · Zbl 1403.90602
[11] Deb, K., Multi-objective optimization, Search methodologies, 403-449 (2014), Springer
[13] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[14] Emmerich, M.; Giotis, A.; Özdemir, M.; Bäck, T.; Giannakoglou, K., Metamodel-assisted evolution strategies, Proceedings of international conference on parallel problem solving from nature, 361-370 (2002), Springer
[15] Emmerich, M.; Naujoks, B., Metamodel assisted multiobjective optimisation strategies and their application in airfoil design, Adaptive computing in design and manufacture vi, 249-260 (2004), Springer
[16] Emmerich, M. T.; Giannakoglou, K. C.; Naujoks, B., Single-and multiobjective evolutionary optimization assisted by Gaussian random field metamodels, IEEE Transactions on Evolutionary Computation, 10, 4, 421-439 (2006)
[17] Gebreslassie, B. H.; Guillén-Gosálbez, G.; Jiménez, L.; Boer, D., Design of environmentally conscious absorption cooling systems via multi-objective optimization and life cycle assessment, Applied Energy, 86, 9, 1712-1722 (2009)
[19] Goel, T.; Vaidyanathan, R.; Haftka, R. T.; Shyy, W.; Queipo, N. V.; Tucker, K., Response surface approximation of pareto optimal front in multi-objective optimization, Computer Methods in Applied Mechanics and Engineering, 196, 4, 879-893 (2007) · Zbl 1120.76358
[20] Guillén-Gosálbez, G.; Grossmann, I., A global optimization strategy for the environmentally conscious design of chemical supply chains under uncertainty in the damage assessment model, Computers & Chemical Engineering, 34, 1, 42-58 (2010)
[21] Harada, K.; Sakuma, J.; Kobayashi, S., Local search for multiobjective function optimization: Pareto descent method, Proceedings of the 8th annual conference on genetic and evolutionary computation, 659-666 (2006), ACM
[22] Hernández, V. A.S.; Schütze, O.; Rudolph, G.; Trautmann, H., The directed search method for pareto front approximations with maximum dominated hypervolume, Evolve-a bridge between probability, set oriented numerics, and evolutionary computation iv, 189-205 (2013), Springer · Zbl 1322.90090
[23] Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evolutionary Computation, 15, 1, 1-28 (2007)
[24] Ikeda, K.-i.; Kita, H.; Kobayashi, S., Failure of Pareto-based MOEAs: Does non-dominated really mean near to optimal?, Proceedings of the 2001 congress on evolutionary computation, 2, 957-962 (2001), IEEE
[25] Ishibuchi, H.; Murata, T., Multi-objective genetic local search algorithm, Proceedings of IEEE international conference on evolutionary computation, 119-124 (1996), IEEE
[26] Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 28, 3, 392-403 (1998)
[27] Ishibuchi, H.; Yoshida, T.; Murata, T., Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling, IEEE Transactions on Evolutionary Computation, 7, 2, 204-223 (2003)
[28] Jacquemin, L.; Pontalier, P.-Y.; Sablayrolles, C., Life cycle assessment (LCA) applied to the process industry: A review, The International Journal of Life Cycle Assessment, 17, 8, 1028-1041 (2012)
[29] Jaeggi, D.; Parks, G. T.; Kipouros, T.; Clarkson, P. J., The development of a multi-objective tabu search algorithm for continuous optimisation problems, European Journal of Operational Research, 185, 3, 1192-1212 (2008) · Zbl 1175.90354
[30] Jones, D. R.; Schonlau, M.; Welch, W. J., Efficient global optimization of expensive black-box functions, Journal of Global Optimization, 13, 4, 455-492 (1998) · Zbl 0917.90270
[31] Kim, H.; Liou, M.-S., Adaptive directional local search strategy for hybrid evolutionary multiobjective optimization, Applied Soft Computing, 19, 290-311 (2014)
[32] Kleijnen, J. P., Regression and Kriging metamodels with their experimental designs in simulation: A review, European Journal of Operational Research, 256, 1, 1-16 (2017) · Zbl 1394.90004
[33] Knowles, J., ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE Transactions on Evolutionary Computation, 10, 1, 50-66 (2006)
[34] Knowles, J.; Corne, D., Memetic algorithms for multiobjective optimization: issues, methods and prospects, Recent advances in memetic algorithms, 313-352 (2005), Springer
[35] Knowles, J. D.; Corne, D. W., M-PAES: A memetic algorithm for multiobjective optimization, Proceedings of the 2000 congress on evolutionary computation, 1, 325-332 (2000), IEEE
[36] Lara, A.; Alvarado, S.; Salomon, S.; Avigad, G.; Coello, C. A.C.; Schütze, O., The gradient free directed search method as local search within multi-objective evolutionary algorithms, Evolve-a bridge between probability, set oriented numerics, and evolutionary computation ii, 153-168 (2013), Springer
[37] Lara, A.; Sanchez, G.; Coello, C. A.C.; Schütze, O., HCS: A new local search strategy for memetic multiobjective evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 14, 1, 112-132 (2010)
[38] Lim, D.; Jin, Y.; Ong, Y.-S.; Sendhoff, B., Generalizing surrogate-assisted evolutionary computation, IEEE Transactions on Evolutionary Computation, 14, 3, 329-355 (2010)
[39] Lin, Q.; Li, J.; Du, Z.; Chen, J.; Ming, Z., A novel multi-objective particle swarm optimization with multiple search strategies, European Journal of Operational Research, 247, 3, 732-744 (2015) · Zbl 1346.90742
[41] Mejía, E.; Schütze, O., A predictor corrector method for the computation of boundary points of a multi-objective optimization problem, Poceedings of the 2010 7th international conference on electrical engineering computing science and automatic control (CCE), 395-399 (2010), IEEE
[42] Méry, Y.; Tiruta-Barna, L.; Benetto, E.; Baudin, I., An integrated “process modelling-life cycle assessment” tool for the assessment and design of water treatment processes, The International Journal of Life Cycle Assessment, 18, 5, 1062-1070 (2013)
[43] Mlakar, M.; Petelin, D.; Tušar, T.; Filipič, B., Gp-demo: Differential evolution for multiobjective optimization based on Gaussian process models, European Journal of Operational Research, 243, 2, 347-361 (2015) · Zbl 1346.90747
[44] Moscato, P., On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms (1989)
[45] Parkhurst, D. L.; Appelo, C., Description of input and examples for phreeqc version 3 a computer program for speciation, batch-reaction, one-dimensional transport, and inverse geochemical calculations, US geological survey techniques and methods, 6, 497 (2013)
[46] Raidl, G. R., A unified view on hybrid metaheuristics, Proceedings of third international workshop on hybrid metaheuristics, HM, 1-12 (2006), Springer
[47] Regis, R. G., Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions, IEEE Transactions on Evolutionary Computation, 18, 3, 326-347 (2014)
[48] Santana-Quintero, L.; Montano, A.; Coello Coello, C., A review of techniques for handling expensive functions in evolutionary multi-objective optimization, Computational intelligence in expensive optimization problems, 29-59 (2010), Springer
[49] Schütze, O.; Hernández, V. A.S.; Trautmann, H.; Rudolph, G., The hypervolume based directed search method for multi-objective optimization problems, Journal of Heuristics, 22, 3, 273-300 (2016)
[50] Schütze, O.; Lara, A.; Coello Coello, C., The directed search method for unconstrained multi-objective optimization problems (2010)
[51] SEQEau, Water quality evaluation system in France (version 2), Technical Report (2003)
[52] Serafini, P., Simulated annealing for multi objective optimization problems, Multiple criteria decision making, 283-292 (1994), Springer · Zbl 0818.90102
[53] Sindhya, K.; Miettinen, K.; Deb, K., A hybrid framework for evolutionary multi-objective optimization, IEEE Transactions on Evolutionary Computation, 17, 4, 495-511 (2013)
[54] Talbi, E.-G., A taxonomy of hybrid metaheuristics, Journal of Heuristics, 8, 5, 541-564 (2002)
[55] Wanner, E. F.; Guimares, F. G.; Takahashi, R. H.; Lowther, D. A.; Ramirez, J. A., Multiobjective memetic algorithms with quadratic approximation-based local search for expensive optimization in electromagnetics, IEEE Transactions on Magnetics, 44, 6, 1126-1129 (2008)
[56] Weidema, B. P.; Bauer, C.; Hischier, R.; Mutel, C.; Nemecek, T.; Reinhard, J.; Wernet, G., Overview and methodology: Data quality guideline for the ecoinvent database version 3, Technical Report (2013)
[57] You, F.; Tao, L.; Graziano, D. J.; Snyder, S. W., Optimal design of sustainable cellulosic biofuel supply chains: Multiobjective optimization coupled with life cycle assessment and input-output analysis, AIChE Journal, 58, 4, 1157-1180 (2012)
[58] Yue, D.; Kim, M. A.; You, F., Design of sustainable product systems and supply chains with life cycle optimization based on functional unit: General modeling framework, mixed-integer nonlinear programming algorithms and case study on hydrocarbon biofuels, ACS Sustainable Chemistry & Engineering, 1, 8, 1003-1014 (2013)
[59] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11, 6, 712-731 (2007)
[60] Zhang, Q.; Liu, W.; Tsang, E.; Virginas, B., Expensive multiobjective optimization by MOEA/D with Gaussian process model, IEEE Transactions on Evolutionary Computation, 14, 3, 456-474 (2010)
[61] Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: A survey of the state of the art, Swarm and Evolutionary Computation, 1, 1, 32-49 (2011)
[62] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary Computation, 8, 2, 173-195 (2000)
[63] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization, Evolutionary Methods for Design, Optimization, and Control, 95-100 (2002), Tik-report
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.