Solution representation learning in transfer evolutionary optimization

• Main Author: Lim, Ray Chee Chuan
• Other Authors: Ong Yew Soon
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering::Computing methodologies
• Online Access: https://hdl.handle.net/10356/153156
• Institution: Nanyang Technological University

The human cognitive ability to learn with experience is a masterpiece of natural evolution that has yet to be fully duplicated in computational and artificial intelligence systems. When presented with a new task, our brain has the natural tendency to retrieve and reuse knowledge priors acquired from related experiences, thereby speeding up our problem-solving process. In the modern era of data-driven optimization, fuelled by growing amounts of data and seamless information transmission technologies, it is becoming increasingly important for machines to embody the ability to learn from experiences as well. To this end, a recent computational paradigm known as transfer evolutionary optimization (TrEO) has emerged to encompass methods that leverage knowledge priors from various source optimization tasks to boost the convergence performance in a new but related target task. Despite the potential for performance speed-up, the effectiveness of existing TrEO algorithms in actual practice could be hampered by discrepancies between the original search spaces of source and target problems – a common scenario when solving black-box optimization problems of diverse properties, where little is known about their search landscapes a priori. In particular, heterogeneous source and target dimensionalities or a lack of overlap between their optimized search distributions may give rise to unaligned solution representations that conceal useful inter-task relationships. This could in turn cause two undesired issues in TrEO, namely, the scarcity of beneficial positive transfers, or the increase of harmful negative transfers. Even though methodological advances have been made, for instance, the state-of-the-art probabilistic model-based transfer approach for curbing negative inter-task interactions, there is currently a lack of approaches capable of jointly addressing the two predominant issues in TrEO. Taking the cue, this thesis presents a novel study on solution representation learning in probabilistic model-based TrEO for inducing greater alignment (of solution representations) and hence positive transfers between distinct optimization tasks that bear discrepancies in their original search spaces, while simultaneously curbing the occurrence of negative transfers. A formalization of solution representation learning in TrEO is established. To this end, the importance and motivations of solution representation learning for uncovering useful but hidden inter-task relationships are conceived. Following from the motivations, a principled perspective of solution representation learning via search space mappings in TrEO is presented, where a streamlined definition is first given. Accordingly, the source-to-target map is proposed as a category of spatial mappings by which source tasks are mapped to a transformed and well-aligned solution representation space, such that the discrepancies between various sources and the target task are reduced – in this category, the target search space serves as the transformed (or common) solution representation space. In particular, we outline the probabilistic formulation of TrEO inclusive of a source-to-target map that flexibly allows various source-to-target spatial mapping functions to be incorporated. To complete the formalization, a novel TrEO algorithmic framework is put forward, endowed with a solution representation learning module to induce positive transfers, while synergized with a probabilistic model-based inter-task similarity capture mechanism to simultaneously mitigate the threat of negative transfers. Based on the proposed framework, novel TrEO algorithms are developed in the context of single-objective and multi-objective optimization. Under each context, case studies are presented for continuous and discrete optimization domains, in which distinct methodologies for constructing source-to-target spatial mappings are designed for learning well-aligned solution representations. A range of empirical experiments are conducted to verify the efficacy of the resultant TrEO algorithmic instantiations, using benchmark optimization problems as well as practical tasks in inventory planning, engineering design and graph-based vehicle route planning. The numerical results demonstrate superior convergence rates and solution qualities achieved by the proposed algorithms, in comparison to state-of-the-art TrEO baselines. Further analyses of the results reveal the effectiveness of the source-to-target spatial mappings, and provide insights into the synergy between learning solution representations and capturing source-target similarities. The work of this thesis subsequently sheds light on several promising future research directions for TrEO algorithms that improve their efficacy by learning from various sources of past problem-solving experiences.