Abstract
In traditional, single objective, optimisation local optima may be found by gradient search. With the recently introduced hypervolume indicator (HVI) gradient search, this is now also possible for multi-objective optimisation, by steering the whole Pareto front approximation (PFA) in the direction of maximal improvement. However, so far it has only been evaluated on simple test problems. In this work the HVI gradient is used for the real world problem of building spatial design, where the shape and layout of a building are optimised. This real world problem comes with a number of constraints that may hamper the effectiveness of the HVI gradient. Specifically, box constraints, and an equality constraint which is satisfied by rescaling. Moreover, like with regular gradient search, the HVI gradient may overstep an optimum. Therefore, step size control is also investigated. Since the building spatial designs are encoded in mixed-integer form, the use of gradient search alone is not sufficient. To navigate both discrete and continuous space, an evolutionary multi-objective algorithm (EMOA) and the HVI gradient are used in hybrid, forming a so-called memetic algorithm. Finally, the effectiveness of the memetic algorithm using the HVI gradient is evaluated empirically, by comparing it to an EMOA without a local search method. It is found that the HVI gradient method is effective in improving the PFA for this real world problem. However, due to the many discrete subspaces, the EMOA is able to find better solutions than the memetic approach, albeit only marginally.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahnert, K., Mulansky, M.: Odeint - solving ordinary differential equations in C++. AIP Conference Proceedings vol. 1389, no. 1, pp. 1586–1589 (2011). https://doi.org/10.1063/1.3637934
van der Blom, K., Boonstra, S., Hofmeyer, H., Bäck, T., Emmerich, M.T.M.: Configuring advanced evolutionary algorithms for multicriteria building spatial design optimisation. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1803–1810. IEEE (2017). https://doi.org/10.1109/CEC.2017.7969520
van der Blom, K., Boonstra, S., Hofmeyer, H., Emmerich, M.T.M.: Multicriteria building spatial design with mixed integer evolutionary algorithms. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.): Parallel Problem Solving from Nature – PPSN XIV, Lecture Notes in Computer Science, vol. 9921, pp. 453–462. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_42
van der Blom, K., Boonstra, S., Hofmeyer, H., Emmerich, M.T.M.: A super-structure based optimisation approach for building spatial designs. In: Papadrakakis, M., Papadopoulos, V., Stefanou, G., Plevris, V. (eds.): VII European Congress on Computational Methods in Applied Sciences and Engineering – ECCOMAS VII, vol. 2, pp. 3409–3422. National Technical University of Athens (2016). https://doi.org/10.7712/100016.2044.10063
Boonstra, S., van der Blom, K., Hofmeyer, H., Emmerich, M.T.: Combined super-structured and super-structure free optimisation of building spatial designs. In: Koch, C., Tizani, W., Ninić, J. (eds.): 24nd International Workshop of the European Group for Intelligent Computing in Engineering, pp. 23–34. University of Nottingham (2017)
Boonstra, S., van der Blom, K., Hofmeyer, H., Emmerich, M.T., van Schijndel, J., de Wilde, P.: Toolbox for super-structured and super-structure free multi-disciplinary building spatial design optimisation. Adv. Eng. Inf. 36, 86–100 (2018). https://doi.org/10.1016/j.aei.2018.01.003
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002). https://doi.org/10.1109/4235.996017
Dellnitz, M., Schütze, O., Hestermeyer, T.: Covering pareto sets by multilevel subdivision techniques. J. Optim. Theory Appl. 124(1), 113–136 (2005). https://doi.org/10.1007/s10957-004-6468-7
Ehrgott, M.: Multicriteria Optimization, vol. 491. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-27659-9
Emmerich, M., Beume, N., Naujoks, B.: An emo algorithm using the hypervolume measure as selection criterion. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.): Evolutionary Multi-Criterion Optimization, pp. 62–76. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_5
Emmerich, M., Deutz, A.: Time complexity and zeros of the hypervolume indicator gradient field. In: Schuetze, O., Coello Coello, C.A., Tantar, A.A., Tantar, E., Bouvry, P., Moral, P.D., Legrand, P. (eds.): EVOLVE - A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation III, pp. 169–193. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-01460-9_8
Emmerich, M., Deutz, A., Beume, N.: Gradient-based/evolutionary relay hybrid for computing pareto front approximations maximizing the s-metric. In: Bartz-Beielstein, T., Blesa Aguilera, M.J., Blum, C., Naujoks, B., Roli, A., Rudolph, G., Sampels, M. (eds.): Hybrid Metaheuristics, pp. 140–156. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75514-2_11
Fliege, J., Svaiter, B.F.: Steepest descent methods for multicriteria optimization. Math. Methods Oper. Res. 51(3), 479–494 (2000). https://doi.org/10.1007/s001860000043
Fonseca, C.M., Grunert da Fonseca, V., Paquete, L.: Exploring the performance of stochastic multiobjective optimisers with the second-order attainment function. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.): Evolutionary Multi-Criterion Optimization, pp. 250–264. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_18
Guennebaud, G., Jacob, B., et al.: Eigen v3: A C++ linear algebra library (2010). http://eigen.tuxfamily.org. Accessed 7 May 2018
Koningklijk Nederlands Metereologisch Instituut: Measured weather data in the Netherlands (2018). http://www.knmi.nl/nederland-nu/klimatologie/daggegevens. Accessed 7 May 2018
Kramer, R., van Schijndel, J., Schellen, H.: Simplified thermal and hygric building models: a literature review. Front. Archit. Res. 1(4), 318–325 (2012). https://doi.org/10.1016/j.foar.2012.09.001
Lara, A., Sanchez, G., Coello, C.A.C., Schütze, O.: Hcs: A new local search strategy for memetic multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 14(1), 112–132 (2010). https://doi.org/10.1109/TEVC.2009.2024143
Li, R., Emmerich, M.T.M., Eggermont, J., Bovenkamp, E.G.P., Bäck, T., Dijkstra, J., Reiber, J.H.C.: Metamodel-assisted mixed integer evolution strategies and their application to intravascular ultrasound image analysis. In: IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 2764–2771 (2008). https://doi.org/10.1109/CEC.2008.4631169
Martín, A., Schütze, O.: Pareto tracer: a predictorcorrector method for multi-objective optimization problems. Eng. Optim. 50(3), 516–536 (2018). https://doi.org/10.1080/0305215X.2017.1327579
Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program 158-79, Technical Report, pp. 1–68 (1989)
Schäffler, S., Schultz, R., Weinzierl, K.: Stochastic method for the solution of unconstrained vector optimization problems. J. Optim. Theory Appl. 114(1), 209–222 (2002). https://doi.org/10.1023/A:1015472306888
Schütze, O., Coello, C.A.C., Mostaghim, S., Talbi, E.G., Dellnitz, M.: Hybridizing evolutionary strategies with continuation methods for solving multi-objective problems. Eng. Optim. 40(5), 383–402 (2008). https://doi.org/10.1080/03052150701821328
Schütze, O., Hernández, V.A.S., Trautmann, H., Rudolph, G.: The hypervolume based directed search method for multi-objective optimization problems. J. Heuristics 22(3), 273–300 (2016). https://doi.org/10.1007/s10732-016-9310-0
Sosa Hernández, V.A., Schütze, O., Emmerich, M.: Hypervolume maximization via set based newton’s method. In: Tantar, A.A., Tantar, E., Sun, J.Q., Zhang, W., Ding, Q., Schütze, O., Emmerich, M., Legrand, P., Del Moral, P., Coello Coello, C.A. (eds.): EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V, pp. 15–28. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07494-8_2
Wang, H., Deutz, A., Bäck, T., Emmerich, M.: Hypervolume indicator gradient ascent multi-objective optimization. In: Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M., Jin, Y., Grimme, C. (eds.) Evolutionary Multi-Criterion Optimization, pp. 654–669. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-54157-0_44
Wang, H., Ren, Y., Deutz, A., Emmerich, M.: On steering dominated points in hypervolume indicator gradient ascent for bi-objective optimization. In: Schütze, O., Trujillo, L., Legrand, P., Maldonado, Y. (eds.): NEO 2015: Results of the Numerical and Evolutionary Optimization Workshop NEO 2015 held at September 23–25 2015 in Tijuana, Mexico, pp. 175–203. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-44003-3_8
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms – a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature – PPSN V, pp. 292–301. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0056872
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003). https://doi.org/10.1109/TEVC.2003.810758
Acknowledgements
This work is part of the TTW-Open Technology Programme with project number 13596, which is (partly) financed by the Netherlands Organisation for Scientific Research (NWO). The authors express their gratitude to the reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
van der Blom, K., Boonstra, S., Wang, H., Hofmeyer, H., Emmerich, M.T.M. (2019). Evaluating Memetic Building Spatial Design Optimisation Using Hypervolume Indicator Gradient Ascent. In: Trujillo, L., Schütze, O., Maldonado, Y., Valle, P. (eds) Numerical and Evolutionary Optimization – NEO 2017. NEO 2017. Studies in Computational Intelligence, vol 785. Springer, Cham. https://doi.org/10.1007/978-3-319-96104-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-96104-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-96103-3
Online ISBN: 978-3-319-96104-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)