Abstract
This paper introduces a multi-level (m-lev) mechanism into Evolution Strategies (ESs) in order to address a class of global optimization problems that could benefit from fine discretization of their decision variables. Such problems arise in engineering and scientific applications, which possess a multi-resolution control nature, and thus may be formulated either by means of low-resolution variants (providing coarser approximations with presumably lower accuracy for the general problem) or by high-resolution controls. A particular scientific application concerns practical Quantum Control (QC) problems, whose targeted optimal controls may be discretized to increasingly higher resolution, which in turn carries the potential to obtain better control yields. However, state-of-the-art derivative-free optimization heuristics for high-resolution formulations nominally call for an impractically large number of objective function calls. Therefore, an effective algorithmic treatment for such problems is needed. We introduce a framework with an automated scheme to facilitate guided-search over increasingly finer levels of control resolution for the optimization problem, whose on-the-fly learned parameters require careful adaptation. We instantiate the proposed m-lev self-adaptive ES framework by two specific strategies, namely the classical elitist single-child (1+1)-ES and the non-elitist multi-child derandomized \((\mu _W,\lambda )\)-sep-CMA-ES. We first show that the approach is suitable by simulation-based optimization of QC systems which were heretofore viewed as too complex to address. We also present a laboratory proof-of-concept for the proposed approach on a basic experimental QC system objective.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Arnold, D.V., Beyer, H.G.: Local performance of the \((\mu /\mu _I, \lambda )\)-ES in a noisy environment. In: Martin, W., Spears, W. (eds.) Foundations of Genetic Algorithms, 6, pp. 127–141. Morgan Kaufmann, San Francisco (2001)
Arnold, D.V., MacLeod, A.: Hierarchically organised evolution strategies on the parabolic ridge. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO ’06, pp. 437–444. ACM, New York, NY, USA (2006). https://doi.org/10.1145/1143997.1144080
Asbury, S., Holloway, J.P.: Multi-grid genetic algorithms for space shield design. In: Proceedings of the International Conference on Mathematics, Computational Methods and Reactor Physics (2009)
Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York (1996)
Bäck, T., Foussette, C., Krause, P.: Contemporary Evolution Strategies. Natural Computing Series. Springer, Berlin (2013)
Barth, T., Chan, T., Haimes, R.: Multiscale and Multiresolution Methods: Theory and Applications, Lecture Notes in Computational Science and Engineering. Springer, Berlin (2002)
Bellman, R.E.: Adaptive Control Processes: A Guided Tour. Princeton University Press, Princteton (1961)
Beyer, H.G.: Toward a theory of evolution strategies: some asymptotical results from the \((1\stackrel{+}{,}\lambda )\)-theory. Evol. Comput. 1(2), 165–188 (1993)
Beyer, H.G.: An alternative explanation for the manner in which genetic algorithms operate. BioSystems 41(1), 1–15 (1997)
Beyer, H.G.: The Theory of Evolution Strategies. Springer, Heidelberg (2001)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)
Brandt, A., Ron, D.: Multigrid solvers and multilevel optimization strategies. In: Cong, J., Shinnerl, J.R. (eds.) Multilevel Optimization in VLSICAD, Combinatorial Optimization, vol. 14, pp. 1–69. Springer US (2003). https://doi.org/10.1007/978-1-4757-3748-6_1
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, Norwell (2001)
Briggs, W.L., Henson, V.E., McCormick, S.F.: A Multigrid Tutorial, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960). https://doi.org/10.1287/opre.8.1.101
Emmerich, M., Shir, O.M., Wang, H.: Handbook of Heuristics, chap. Evolution Strategies, pp. 1–31. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-07153-4_13-1
Giannakoglou, K.C., Kampolis, I.C.: Computational Intelligence in Expensive Optimization Problems, chap. Multilevel optimization algorithms based on metamodel- and fitness inheritance-assisted evolutionary algorithms, pp. 61–84. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-10701-6_3
Hackbusch, W.: Multi-Grid Methods and Applications. Springer Series in Computational Mathematics. Springer (1985)
Hansen, N., Arnold, D.V., Auger, A.: Springer Handbook of Computational Intelligence, chap. Evolution Strategies, pp. 871–898. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-43505-2_44
Harvey, I.: Species Adaptation Genetic Algorithms: A Basis for a Continuing Saga. In: Proceedings of the First European Conference on Artificial Life, pp. 346–354. MIT Press/Bradford Books (1992)
He, J., Kang, L.: A mixed strategy of combining evolutionary algorithms with multigrid methods. Int. J. Comput. Math. 86(5), 837–849 (2009). https://doi.org/10.1080/00207160701713581
Koza, J.R.: Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. technical Report. Stanford University, Stanford, CA, USA (1990)
Laforge, F., Roslund, J., Shir, O.M., Rabitz, H.: Multiobjective adaptive feedback control of two-photon absorption coupled with propagation through a dispersive medium. Phys. Rev. A 84, 013401 (2011). https://doi.org/10.1103/PhysRevA.84.013401
Lindauer, M., Eggensperger, K., Feurer, M., Falkner, S., Biedenkapp, A., Hutter, F.: Smac v3: Algorithm Configuration in python (2017). https://github.com/automl/SMAC3
Liu, B., Koziel, S., Zhang, Q.: A multi-fidelity surrogate-model-assisted evolutionary algorithm for computationally expensive optimization problems. J. Comput. Sci. 12, 28–37 (2016). https://doi.org/10.1016/j.jocs.2015.11.004
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002
Loshchilov, I.: A computationally efficient limited memory cma-es for large scale optimization. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO ’14, pp. 397–404. Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2576768.2598294
March, A., Willcox, K.: Provably convergent multifidelity optimization algorithm not requiring high-fidelity derivatives. AIAA J. 50(5), 1079–1089 (2012). https://doi.org/10.2514/1.J051125
Mathew, R., Hall, K.C.: Tailoring the ultrafast control of quantum dot excitons using optical pulse shaping. Phys. Status Solidi C Curr. Top. 13, 67–72 (2016). https://doi.org/10.1002/pssc.201510152
Nuernberger, P., Vogt, G., Brixner, T., Gerber, G.: Femtosecond quantum control of molecular dynamics in the condensed phase. Phys. Chem. Chem. Phys. 9(20), 2470–2497 (2007)
Powell, W., Ryzhov, I.: Optimal Learning. Wiley Series in Probability and Statistics. Wiley (2013)
Press, W., Teukolsky, S., Vetterling, W., Flannery, B.: Numerical Recipes in C, 2nd edn. Cambridge University Press, Cambridge (1992)
Rabitz, H., de Vivie-Riedle, R., Motzkus, M., Kompa, K.: Whither the future of controlling quantum phenomena? Science 288, 824–828 (2000)
Rechenberg, I.: Evolutionsstrategies: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart (1973)
Ros, R., Hansen, N.: A simple modification in CMA-ES achieving linear time and space complexity. In: Parallel Problem Solving from Nature—PPSN X, Lecture Notes in Computer Science, vol. 5199, pp. 296–305. Springer (2008)
Rosca-Pruna, F., Vrakking, M.J.: Revival structures in picosecond laser-induced alignment of i2 molecules. J. Chem. Phys. 116(15), 6579–6588 (2002)
Roslund, J., Shir, O.M., Bäck, T., Rabitz, H.: Accelerated optimization and automated discovery with covariance matrix adaptation for experimental quantum control. Phys. Rev. A (At. Mol. Opt. Phys.) 80(4), 043415 (2009). https://doi.org/10.1103/PhysRevA.80.043415
Roth, M.: Optimal Dynamic Discrimination in the Laboratory. Ph.D. thesis, Princeton University (2007)
Salimans, T., Ho, J., Chen, X., Sutskever, I.: Evolution strategies as a scalable alternative to reinforcement learning. CoRR abs/1703.03864 (2017). http://arxiv.org/abs/1703.03864
Shir, O.M., Bäck, T.: The second harmonic generation case study as a gateway for ES to quantum control problems. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2007, pp. 713–721. ACM Press, New York, NY, USA (2007)
Shir, O.M., Bäck, T.: Sequential experimentation by evolutionary algorithms. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, GECCO ’20, p. 957-974. Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3377929.3389877
Shir, O.M., Beltrani, V., Bäck, T., Rabitz, H., Vrakking, M.J.: On the diversity of multiple optimal controls for quantum systems. J. Phys. B At. Mol. Opt. Phys. 41(7), 074021 (2008a). https://doi.org/10.1088/0953-4075/41/7/074021
Shir, O.M., Roslund, J., Bäck, T., Rabitz, H.: Performance analysis of derandomized evolution strategies in quantum control experiments. In: Proceedings of the 10th Genetic and Evolutionary Computation Conference, GECCO-2008, pp. 519–526. ACM Press, New York, NY, USA (2008b)
Shir, O.M., Roslund, J., Leghtas, Z., Rabitz, H.: Quantum control experiments as a testbed for evolutionary multi-objective algorithms. Genet. Program. Evol. Mach. 13, 445–491 (2012). https://doi.org/10.1007/s10710-012-9164-7
Tilahun, S.L., Kassa, S.M., Ong, H.C.: PRICAI 2012: Trends in Artificial Intelligence: 12th Pacific Rim International Conference on Artificial Intelligence, Kuching, Malaysia, September 3-7, 2012. Proceedings, chap. A New Algorithm for Multilevel Optimization Problems Using Evolutionary Strategy, Inspired by Natural Adaptation, pp. 577–588. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32695-0_51
Warren, W.S., Rabitz, H., Dahleh, M.: Coherent control of quantum dynamics: the dream is alive. Science 259, 1581–1589 (1993)
Watanabe, K., Campelo, F., Igarashi, H.: Topology optimization based on immune algorithm and multi grid method. IEEE Trans. Magn. 43(4) (2007)
Weiner, A.M.: Femtosecond pulse shaping using spatial light modulators. Rev. Sci. Instrum. 71(5), 1929–1960 (2000). https://doi.org/10.1063/1.1150614
Acknowledgements
The authors have very much appreciated the detailed comments of the anonymous reviewers of this paper, which have helped to improve it. The author O.M.S. is grateful to Jonathan Roslund, Naor Alaluf and Soli Vishkautsan for their contributions in various stages of this research thread. The author H.R. acknowledges support from the Department of Energy (DE-FG02-02ER15344) and X.X. acknowledges support from the National Science Foundation (CHE-1763198).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
The pixelation effect
The time modulation of these step-functions is attained by their inverse Fourier transform,
where the width of \(\text {sinc}(\tau )=\frac{\sin (\tau )}{\tau }\) is inversely proportional to the pixel width. Explicitly, the resulting temporal electric field in this pixelation can be described by
with \(\tilde{e}(t)\) as the desired electric field, and where \(\tau = \frac{1}{\varDelta \nu }\) is the inverse frequency spacing per pixel. Figure 11 provides an illustration of the pixelation effect (Roth 2007).
Illustration of the pixelation effect occurring in pulse shapers during typical QC experiments; shaping is carried out with 32 pixels in the domain \([-\pi ,\pi ]\). Panel a presents replica pulses with a moderate linear phase, with the envelope of the replicas in a dashed curve. Panel b shows a steeper phase, with more pronounced replica pulses (Roth 2007). Figure courtesy of Matthias Roth and Jonathan Roslund
Laboratory setup
A commercial Ti:Sapphire femtosecond laser system consisting of an oscillator and a multi-pass amplifier (KMlab, Dragon) is used to produce pulses with \(\sim 25\text {fs}\) pulse width centered at \(\sim 790\text {nm}\). The laser pulses are shaped with a dual-mask liquid crystal SLM (CRI, SLM-640), capable of simultaneous phase and amplitude modulation. A small fraction of the shaped laser pulse is spit and focused into a GaP photodiode (Thorlab), which generates only the TPA signal from the \(790\text {nm}\) incident light. The laser power was adjusted with neutral density filters before entering the photodiode to make sure that the TPA signal does not saturate. The SLM contains \(N_f=640\) pixels, and the shaper is configured at a resolution of \(\sim 0.2\text {nm/pixel}\). We utilize phase-only modulation in the experiment, with all the amplitudes fixed at 1. Adjacent SLM pixels are sequentially tied together in groups of \(g_{\ell }~\left( g_{\ell }=32,~16,~8,~4,~2 \right) \) to reduce the 640-dimensional space of spectral phases to the desired grid levels \(n_{\ell }~\left( n_{\ell }=20,~40,~80,~160,~320 \right) \), respectively. The QC objective function is the experimental equivalence of Eq. 10, that is, to experimentally maximize the TPA signal by obtaining the optimal phase mask on the shaper. Ideally, the optimal phase should be a flat phase or a linear phase, but in laboratory practice, it contains higher order nonlinear terms to compensate for or correct those inherent in the laser system.
Figure 12 schematically illustrates an experimental QC learning loop (Nuernberger et al. 2007).
The experimental quantum control learning loop. An unshaped laser pulse, approximated well by a Gaussian, is shaped by a pixel-based modulator and applied to a molecular sample. The control variables addressed in the laboratory by the evolution strategy are the individual pixels that determine the pulse shape. The measured signal reflecting the molecular response constitutes the feedback for optimization by the ES
Rights and permissions
About this article
Cite this article
Shir, O.M., Xing, X. & Rabitz, H. Multi-level evolution strategies for high-resolution black-box control. J Heuristics 27, 1021–1055 (2021). https://doi.org/10.1007/s10732-021-09483-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-021-09483-z