LEE- Bilgisayar Mühendisliği Lisansüstü Programı
Bu topluluk için Kalıcı Uri
Gözat
Konu "bayes ağ" ile LEE- Bilgisayar Mühendisliği Lisansüstü Programı'a göz atma
Sayfa başına sonuç
Sıralama Seçenekleri
-
ÖgeHybridization of probabilistic graphical models and metaheuristics for handling dynamism and uncertainty(Graduate School, 2021-06-30) Uludağ, Gönül ; Etaner Uyar, Ayşe Şima ; 504072510 ; Computer EngineeringSolving stochastic complex combinatorial optimisation problems remains one of the most significant research challenges that cannot be adequately addressed not only by deterministic methods but also by some metaheuristics. Today's real-life problems in a broad range of application domains from engineering to neuroimaging are highly complex, dynamic, uncertain, and noisy by nature. Such problems cannot be solved in a reasonable time because of some properties including noisy fitness landscape, high non-linearities, large scale, high multi-modality, computationally expensive objectives functions. The environmental variabilities and uncertainties may be occurred in the problem instance, the objective functions, the design variables, the environmental parameters, and the constraints. Thus, the variations and uncertainties may be due to a change in one or more of these components over time. It is commonly informed that the environmental dynamism is classified based upon the change frequency, predictability, and severity as well as whether it is periodic or not. Different types of variations and uncertainties may arise over time due to the dynamic nature of the combinatorial optimisation problem, and hence an approach chosen at the start of the optimisation may become inappropriate later on. It is expected that such search methodologies for the time-variant problems would be capable of adapting to the change not only efficiently but also quickly, as well as handling the uncertainty such as noise and volatility. On the other hand, it is crucial to identify and adjust the values of numerous parameters of the metaheuristic algorithm while balancing two contradictory criteria: exploitation (i.e., intensification) and exploration (i.e., diversification). Therefore, the self-adaptation is a critical parameter control strategy in metaheuristics for time-variant optimisation. There exists lots of study concerning time-variant problem to handle dynamism and uncertainty, yet a comprehensive approach to address different variations at once still seems to be a task to accomplish. The ideal strategies should take into consideration both environmental dynamism and uncertainties, whereas conventional approaches; however, problems are postulated as time-invariant and disregard this variability and uncertainties. Meanwhile, each real-world problem exhibits different types of changes and uncertainties. Thus, solving such complex problems remains extremely challenging due to the variations, dependencies, and uncertainties during the optimisation process. Probabilistic graphical models are the principal probabilistic model for which a graph expresses the conditional dependence structure to represent complex, real-world phenomena in a compact fashion. Hence, they provide an elegant language to handle complexity and uncertainty. Such properties of probabilistic graphical models have led to further developments in metaheuristics that can be termed probabilistic graphical models-based metaheuristic algorithms. Probabilistic graphical model-based metaheuristic algorithms are acknowledged as highly self-adaptive, and thus able to handle different types of variations. There is a range of probabilistic graphical model-based metaheuristic approaches, e.g., variants of estimation of distribution algorithms suggested in the literature to address dynamism and uncertainty. One of the remarkable state-of-the-art continuous stochastic probabilistic graphical model-based metaheuristic approaches is the covariance matrix adaptation evolution strategy. The covariance matrix adaptation evolution strategy approach and its variants (e.g. covariance matrix adaptation evolution strategy with the increasing population; Ipop-CMA-ES) have become a sophisticated adaptive uncertainty handling scheme. The characteristics of these approaches make them more plausible for handling uncertainty and rapidly changing variations. In recent years, the concept of semi-automatic search methodologies called hyper-heuristics has become increasingly important. Many metaheuristics operate directly on the solution space and utilize problem domain-specific information. However, hyper-heuristics are general methodologies that explore over the space formed by a set of low-level heuristics that perturb or construct a (set of) candidate solution(s) to make self-adaptive decisions for dynamic environments to deal with computationally difficult problems. Besides several impressive research studies that have been carried out on variants of probabilistic graphical model-based metaheuristic algorithms, there also exist many extensive research studies that have been working on machine learning-based optimisation approaches. One of the most popular such methods is the expectation-maximization algorithm, which is a widely used scheme for the optimisation of likelihood functions in the presence of latent (i.e., hidden) variables models. Expectation-maximization is a hill-climbing approach to finding a global maximum of a likelihood function that required achieving convergence to global optima in a reasonable time. One of the extremely challenging dynamic combinatorial optimisation problems is the unit commitment problem, which in the engineering application domain. The unit commitment problem is considered as an NP-hard, non-convex, continuous, constrained dynamic combinatorial optimisation problem in which turn-on/off scheduling of power generating resources is utilized over a given time horizon to minimize the joint cost of committing and de-committing. Another such problem is effective connectivity analysis, which is one of the neuroimaging application areas. The predominant scheme of inferring (i.e., estimating) effective connectivity is dynamic causal modelling, provides a framework for the analysis of effective connectivity (i.e., the directed causal influences between brain areas) and estimating their biophysical parameters from the measured blood oxygen level-dependent functional magnetic resonance responses. However, although, different kinds of metaheuristic- or machine learning-based algorithms have become more satisfying within different types of dynamic environments, neither metaheuristic- nor machine learning-based algorithms are capable of consistently handle the environmental dynamism and uncertainty. In this sense, it is indispensable to hybridize metaheuristics with probabilistic or statistical machine learning to utilize the advantages of both approaches for coping with such challenges. The main motivation of hybridization is to exploit the complementary aspect of different methods. In other words, hybrid frameworks are expected to benefit from the synergy effect. The design and development of hybrid approaches are considered to be promising due to their success in handling variations and uncertainties, and hence, increased attention in recent years has been focused on the fields of metaheuristics and their hybridization. Intuitively, the central idea behind such an approach is based on the two principal theories of the "no free lunch theorem" perspectives: one for supervised machine learning, and one for search/optimisation. Within the context of no free lunch theorem perspective, the following hybrid frameworks are addressed: (i) In the case of no free lunch theorem for search/optimisation, utilize machine learning approaches to enhance metaheuristics; (ii) In the case of no free lunch theorem for machine learning, utilize metaheuristics to improve the performance of machine learning algorithms. Within the scope of this dissertation, each proposed hybrid framework is built on the corresponding "no free lunch theorem" perspective. The first introduced hybrid framework is designed on the no free lunch theorem for search/optimisation concept, referred to as hyper-heuristic-based, dual population estimation of distribution algorithm (HH-EDA2). Within this notion, especially probabilistic model-based schemes are employed to enhance probabilistic graphical model-based metaheuristics that utilize the synergy of selection hyper-heuristic schemes and dual population estimation of distribution algorithm. HH-EDA2 is the form of a two-phase hybrid approach that performs offline and online learning schemes to handle uncertainties and unexpected variations of combinatorial optimisation problems regardless of their dynamic nature. The important characteristic feature of this framework is to integrate any multi-population estimation of distribution algorithms with any probabilistic model-based approach selection hyper-heuristic into the proposed approach. The performance of the hybrid HH-EDA2 along with the influence of different heuristic selection methods was investigated over a range of dynamic environments produced by a well-known benchmark generator as well as over unit commitment problem, which is known as NP-hard constrained combinatorial optimisation problem as a real-life case study. The empirical results show that the proposed approach outperforms some of the best-known approaches in the literature on the non-stationary environment problems dealt with. The second proposed hybrid framework is designed on the no free lunch theorem for machine learning, referred to as Bayesian-driven covariance matrix adaptation evolution strategy with an increasing population (B-Ipop-CMA-ES). Within this notion, especially probabilistic model-based metaheuristics are employed to enhance probabilistic graphical models that utilize the synergy of covariance matrix adaptation evolution strategy algorithm and expectation-maximization schemes. This hybrid framework performs the estimation of biophysical parameters of effective connectivity (i.e., dynamic causal modelling) that enable one to characterize and better understand the dynamic behaviour of the neuronal population. The main attestation of the B-Ipop-CMA-ES is to get rid of crucial issues of dynamic causal modelling, including prior knowledge dependence, computational complexity, and a tendency of getting stuck on local optima. B-Ipop-CMA-ES is capable of performing physiologically plausible models while converging to the global solution in computationally feasible time without relying on initial prior knowledge of biophysical parameters. The performance of the B-Ipop-CMA-ES framework was investigated on both synthetic and empirical functional magnetic resonance imaging datasets. Experimental results demonstrate that B-Ipop-CMA-ES framework outperformed the reference (expectation-maximization/Gauss-Newton) and other competing methods.