Browsing by Author "Lin, Jih-Yiing"

Now showing 1 - 4 of 4

Analysis on the Collaboration Between Global Search and Local Search in Memetic Computation
(2011-10-01)
Lin, Jih-Yiing
;
Chen, Ying-Ping
;
資訊工程學系
;
Department of Computer Science
The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergies still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. This paper aims to provide a theoretical model that can depict the collaboration between global search and local search in memetic computation on a broad class of objective functions. In the proposed model, the interaction between global search and local search creates a set of local search zones, in which the global optimal points reside, within the search space. Based on such a concept, the quasi-basin class (QBC) which categorizes problems according to the distribution of their local search zones is adopted. The subthreshold seeker, taken as a representative archetype of memetic algorithms, is analyzed on various QBCs to develop a general model for memetic algorithms. As the proposed model not only well describes the expected time for a simple memetic algorithm to find the optimal point on different QBCs but also consists with the observations made in previous studies in the literature, the proposed model may reveal important insights to the design of memetic algorithms in general.
On the Effect of Population Size and Selection Mechanism from the Viewpoint of Collaboration between Exploration and Exploitation
(2013)
Lin, Jih-Yiing
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
The synergy between exploration and exploitation has been a prominent issue in optimization. Optimization algorithms are generally required to have their parameters tuned to achieve successful exploration-exploitation synergies. Nonetheless, while many algorithms have achieved remarkable success in a wide range of applications, the key to successful exploration-exploitation synergies still remains obscure because conclusions drawn from empirical results or theoretical derivations are usually algorithm specific and/or problem dependent. In our previous studies, a theoretical model based on the concept of local search zones was proposed to provide an alternative perspective depicting the synergy between global search and local search in memetic algorithms. In the present work, we adopt the concept of local search zones to interpret and discuss the effect of population size and selection mechanism, two common design concerns in evolutionary algorithms, on the synergy between exploration and exploitation. In addition to providing interpretations to the effect of population size and selection mechanism on different problem types, this investigation also suggests that with proper mapping, the concept of local search zones is also applicable to delineate the behavior of optimization algorithms with different mechanisms.
Population sizing for inductive linkage identification
(2013)
Lin, Jih-Yiing
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Variable interdependency, referred to as linkage in genetic algorithms (GAs), has been among the most useful information in evolutionary optimisation. With the aid of linkage information, efficient evolution can be attained by GAs. Among variants of advanced GAs, linkages are either explicitly identified, as in perturbation-based methods, or implicitly extracted, as in estimation of distribution algorithms (EDAs). As linkage discovery can be considered a matter of information extraction, Shannon's entropy, a renowned metric, has been widely adopted in modern GAs. Despite the validation of theoretical bounds, which is not algorithm-specific, on evaluation complexity of linkage problems, a representative population sizing model for discrete EDAs has been developed based on the distribution of entropy measurement. On the other hand, though entropy metrics have been adopted in recent perturbation-based methods, relevant complexity analysis on these methods is still absent. In this article, we propose a population sizing model for a recently developed linkage identification method, called inductive linkage identification (ILI). The proposed model takes the entropy-based classification algorithm into account and is capable of providing an accurate estimation of population requirement. The adopted modelling approach is different than that for discrete EDAs and may give researchers insights into entropy-based linkage discovery approaches.
When and What Kind of Memetic Algorithms Perform Well
(2012)
Lin, Jih-Yiing
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to a successful exploration-exploitation synergy still remains obscure. Manifold empirical results and theoretical derivations have been proposed and provided various perspectives from different algorithm-problem complexes to this issue. In our previous work, the concept of local search zones was proposed to provide an alternative perspective depicting the general behavior of memetic algorithms on a broad range of problems. In this work, based on the local search zone concept, we further investigate how the problem landscape and the way the algorithm explores and exploits the search space affect the performance of a memetic algorithm. The collaborative behavior of several representative archetypes of memetic algorithms, which exhibit different degrees of explorability and exploitability, are illustrated empirically and analytically on problems with different landscapes. As the empirical results consist with the local search zone concept and describe the behavior of various memetic algorithms on different problems, this work may reveal some essential design principals for memetic algorithms.