|
Rastlantısal (ing: stochastic) karmaşık birleşimsel eniyileme (ing: combinatorial optimisation) problemlerini çözmek, yalnızca gerekirci (ing: deterministic) yöntemler ile değil, aynı zamanda bazı sezgisel-tabanlı yöntemler ile de layıkıyla ele alınamayan mühim araştırma zorluklarından biri olmaya devam etmektedir. Mühendislikten nörogörüntülemeye kadar geniş bir uygulama alanına sahip gerçek hayat problemleri, doğası gereği oldukça karmaşık, değişen, belirsiz ve gürültülü bir yapıya sahiptir. Bu tarz problemler, yüksek doğrusal olmayan (ing: high non-linearities), yüksek çoklu şekilli (ing: high multi-modality), büyük ölçekli, gürültülü uygunluk yüzeyi (ing: noisy fitness landscape), hesaplama maliyeti yüksek amaç işlevi (ing: computationally expensive objective functions) gibi bazı özellikleri nedeniyle makul bir zamanda çözülemezler. Geleneksel gerekirci yöntemlerin kullanımı, genel olarak eniyileme araması hakkında yeterli önsel bilgiye sahip olmadığından, çözümü garanti edemez ve bundan dolayı akılcı hesaplamalı eniyileme yöntemleri kaçınılmaz hale gelir. Bu, sezgi-üstü (ing: metaheuristics) yöntemler olarak adlandırılan, arama uzayında daha etkin ve verimli bir şekilde inceleme yapabilecek, yüksek düzeyde, problemden bağımsız kavramsal bir çerçeve sunan yeni tür yaklaştırım (ing: approximate) Harezmi yollarına (ing: algorithms) önayak olmuştur. Sezgi-üstü-tabanlı yaklaştırımların çoğu, biyobilişim (ing: bioinformatics), beyin görüntüleme (nörogörüntüleme), sosyal ağlar, lojistik&ulaşım, ve bunun gibi bir çok gerçek yaşamdaki uygulama alanlarında en gelişmiş yöntemlerinin temelini oluşturmaya başlamıştır. Bu nedenle, karmaşık birleşimsel eniyileme problemlerinin çözümünde sezgi-üstü yaklaşımların kullanılması son on yılda daha fazla ilgi görmüştür.
Eniyileme Harezmi yolları açısından bakıldığında, çevresel değişimler ve belirsizlikler: uygunluk işlevindeki gürültüden; uygunluk işlevinin yaklaşıklık hatalarından; tasarım değişkenlerinden bir veya birkaçında meydana gelen değişimlerden; zaman içinde uygunluk işlevindeki değişimlerden bir veya birkaçında tekil veya eşzamanlı değişimlerden kaynaklanıyor olabilir. Bunun yanında, farklı tür problemlerde bu değişimler de farklılık gösterebilmektedir. Bu özellikler genelde değişimlerin şiddetine, sıklığına, periyodik olup olmamasına göre sınıflandırılır. Ayrıca ortamın değişim örüntüsü ve özellikleri de zaman içinde değişebilir. Bu durumda başta seçilen yaklaşım, eniyilemenin ilerleyen aşamalarında başarılı olmayabilir. Ortamdaki değişimin özelliklerine göre farklı durumlarda farklı sezgi-üstü-tabanlı yöntemler başarı sağlayabilir. Bu ise eniyileme yaklaşımını seçerken ortamdaki değişimlerin örüntüsünün bilinmesi gerektiği anlamına gelir. Halbuki gerçek hayatta bu her zaman mümkün olmayabilir. Bu değişim örüntüsünü de göz önüne alarak çalışan bir eniyileme yaklaşımından beklenen, değişime hem hızlı hem de etkin bir şekilde uyum sağlarken gürültü ve oynaklık (ing: volatility) gibi belirsizlikler ile başa çıkabilmesidir.
Bu bağlamda günümüz bilimsel yazınlarında, zaman içinde farklı örüntü özelliklerine sahip problemlerin değişimini ve belirsizliğini ele alan farklı sezgi-üstü Harezmi yolları geliştirilmiş olmasına karşın, bu tür yaklaşımların hala birçok eksikleri vardır ve değişim olduğu anda bu değişimleri takip edip hızla uyum sağlayabilmesi konusundaki zorlukları devam etmektedir. Bu konudaki en belirgin eksiklik, sezgi-üstü-tabanlı yaklaşımlarda, iki karşıt ölçütlerden olan sömürme (ing: exploitation) ve keşfetme (ing: exploration) arasındaki dengeyi sağlarken, aynı zamanda var olan çok sayıda değiştirgelerin (ing: parameter) belirlenmesi ve ayarlanması da gerekmektedir. Bu kapsamda tasarımı yapılacak yaklaşımların öz-uyumlu (ing: self-adaptation) bir yapıda olmaları önem arz etmektedir. Birleşimsel eniyileme Harezmi yollarındaki öğrenme yöntemleri de bağlamında gerekli hale gelmiştir. Bu bakışla değişen ortamlarda sıklıkla ya çevrimiçi ve/veya çevrimdışı öğrenme teknikleri kullanılmaktadır. Çevrimiçi öğrenme yönteminde, problem örneği çözülürken, eniyileme araması süresince geri bildirim ve güdüm (ing: guidance) alınır. Diğer taraftan, çevrimdışı öğrenme gerçeklenirken, henüz karşılaşılmayan örneklerin çözümü için, bir dizi test örneklerinin kullanıldığı eğitim aşamasından yararlanır. Ne yazık ki, tüm bu öngörülemeyen değişimleri ve belirsizliklerin tamamını tek seferde ele alabilen öz-uyumlu genel bir yaklaşımdan bahsetmek pek mümkün olmamaktadır.
Olasılıksal çizgesel biçeleri, gerçek dünyadaki büyük-ölçekli uygulama alanlarının karmaşık yapısındaki belirsizliklerin ve rassal değişkenler arasındaki bağımsızlık kısıtlarının birlikte ifade edilmesine olanak sağlayan istatistiksel tabanlı çizgesel biçelerdir. Olasılıksal çizgesel biçelerinin düğümleri rassal değişkenlere karşılık gelir ve ayrıtlar değişkenler arasındaki olasılıksal ilişkileri (koşullu bağımlılık/bağımsızlıkları) betimlemektedir. Bu yapılar bize, bir yandan olasılık kuramı kullanarak belirsizlikleri ele alan, diğer taraftan karmaşıklık ile baş edebilmek için rassal değişkenler arasındaki koşullu bağımsızlıkları kullanan çok yönlü bir dil sunar. Bu özellikleri, olasılıksal çizgesel biçelerinin, sezgi-üstü yaklaşımlarının daha da gelişmesine önayak olmuştur, bu yaklaşımlar olasılıksal çizgesel biçeleri-tabanlı sezgi-üstleri olarak adlandırılabilir. Bu iki yaklaşımın birlikteliği, bu yöntemlere, belirsizlikleri ele alabilen ve beklenmeyen değişimlere karşı hızlı uyum sağlayabilen, öz-uyumsal bir yapı sağlar. Dağılım tahmini Harezmi yolları (ing: estimation of distribution algorithms) gibi olasılıksal çizgesel biçeleri-tabanlı sezgi-üstleri oldukça uyarlanabilir yaklaşımlar olarak kabul edilir ve böylece farklı değişim türlerini ele alabilme kabiliyetine sahiptirler.
Diğer bir olasılıksal çizgesel biçeleri-tabanlı sezgi-üstü yaklaşımı, ortak değişinti dizeyi uyarlamalı evrimsel izlem (ing: covariance matrix adaptation evolution strategy) Harezmi yoludur. Bu Harezmi yolu, bilimsel yazınlarda en gelişmiş sürekli rassal arama yöntemi olarak kabul görmüştür. Özellikle eniyileme yaklaşımları açısından, ayrışmayan (ing: non-separable), kötü koşullandırılmış (ing: ill-conditioned) ve engebeli/çetin (ing: rugged) işlevlerin arama yöntemi olarak kabul edilir. Ortak değişinti dizeyi uyarlamalı evrimsel izlem Harezmi yolu ve türevleri, örneğin artan toplumlu ortak değişinti dizeyi uyarlamalı evrimsel izlem yöntemi sağlam, türevlenmeyen, sürekli eniyileme problemleri için doğrusal olmayan ve dışbükey olmayan eniyileme Harezmi yollarıdır. Ayrıca bu yaklaştırım, belirsizlikler ile baş edebilen çok yönlü öz-uyumlu bir yöntem olarak kabul görmüştür. Bu özellikler, ortak değişinti dizeyi uyarlamalı evrimsel izlemi yaklaşımını sadece durağan değil aynı zamanda durağan olmayan (değişen) ortamlarda da cazip hale getirmiştir.
Son yıllarda, arama yöntembilimlerinin (ing: methodologies) yarı-otomatik tasarımı olan üst-sezgisel yaklaşımlarına artan bir ilgi vardır. Sezgisel ve birçok sezgi-üstü yaklaşımlar, doğrudan çözüm uzayında çalışır ve problem özgü bilgiyi kullanırken, üst-sezgiseller hesaplaması zor olan problemler ile baş edebilmek için alt-sezgisel takımlarından oluşan uzay üzerinde, aday çözümleri bozarak (ing: perturb) ve kurarak (ing: construct) arama yapan genel yöntembilimlerdir. Bu nedenle, üst-sezgisel yaklaşımlarından beklenen, değişen ortamlarda öz-uyumsal kararları alabilen en münasip alt-sezgiselleri seçmesidir. Sezgiselleri üreten ve sezgiselleri seçen üst-sezgiseller olmak üzeri iki yöntembilim mevcuttur. Bununla beraber, deneysel kanıtlar, sezgiselleri seçen üst-sezgisellerin, herhangi bir dış müdahale gerektirmeden değişim örüntülerine çok çabuk uyum sağladığını ve etkin çözümler sunduğunu göstermiştir.
Öngörülemeyen belirsizliklerin ve değişimlerin yoğun olduğu problemlerin çözümüne ilişkin olasılıksal çizgesel biçeleri-tabanlı sezgi-üstlerin türevleri üzerine yapılmış birçok etkin araştırma olmasının yanında, makine öğrenmesi-tabanlı eniyileme Harezmi yolları ile de yapılmış birçok önemli araştırma mevcuttur. Bu yöntemler arasındaki en gözde, yaygın ve etkili yaklaşımlardan biri beklenti-en büyükleme (ing: expectation-maximization) Harezmi yoludur. Beklenti-en büyükleme Harezmi yolu, en büyük olabilirlik (ing: likelihood) işlevinin, gizli (ing: latent) değişkenlerin varlığında eniyilemesinde yaygın olarak kullanılan bir yöntemdir. Beklenti-en büyükleme Harezmi yolu, arama uzayında küresel en büyük (ing: global maximum) noktayı bulmayı amaçlayan bir tepe-tırmanışı (ing: hill-climbing) yaklaşımıdır.
Mühendislik uygulamalarından biri olan ünite yüklenme (ing: unit commitment) problemi, NP-zor/karmaşık (NP-hard/complex), kısıtlı değişen birleşimsel eniyileme problemidir. Ünite yüklenme problemi, belirlenen zaman aralığında güç ünitelerinin devreye alma ve devreden çıkarma ortak maliyetlerini en küçültürken (ing: minimisation), güç üreten kaynakların açma/kapama çizelgelenmesinin tasarlandığı, dışbükey olmayan, sürekli, kısıtlı değişen bir problemdir. Diğer bir problem, nörogörüntüleme uygulama alanlarından biri olan etkin bağlantısallık (ing: effective connectivity) çözümlemesidir. Etkin bağlantısallık çıkarsamasının (ing: inferring) en etkili yaklaştırımı değişen nedensel biçelendirim (ing: dynamic causal modeling). Değişen nedensel biçelendirim, işlevsel manyetik rezonans görüntüleme (ing: functional magnetic resonance imaging [fMRI]) ve elektrofizyolojik (örneğin, manyetoensefalografi veya elektroensefalografi [MEG/EEG]) nörogörüntüleme verilerini kullanarak etkin bağlantısallığın çözümlemesine (yani, belirlenen beyin bölgeleri arasında yönlü nedensel etkiler) ve bu biçenin biyofiziksel değiştirgelerini kestirmeye olanak sağlayan bir çerçeve sunar. Bu gibi problemlerin çözümüne yönelik geliştirilen yaklaşımlardan beklenen, makul bir sürede yerel en büyükten etkin bir şekilde kurtulup küresel en büyük noktaya yakınsaması beklenmektedir.
Her ne kadar, olasılıksal çizgesel biçeleri-tabanlı sezgi-üstler, makine öğrenmesi ve bunların türevleri ile ilgili yapılmış birçok çalışma mevcut olsa da, henüz her türlü öngörülemeyen değişimin ve belirsizliğin daimi olarak ve tutarlı bir şekilde üstesinden gelebilecek tek bir yaklaştırım (yöntem) mevcut değildir. Bu bağlamda, bu tür zorlukların üstesinden gelebilecek, sezgi-üstü ve olasılıksal veya istatistiksel makine öğrenmesi yaklaşımlarındaki üstünlüklerini birlikte kullanılabilmek için melezleştirilmesi kaçınılmaz olacaktır.
Melezleştirme yaklaştırımlarının arkasındaki temel güdüleme, farklı Harezmi yolların güçlü yanlarından yararlanmak ve zayıflıklarını azaltmak için tamamlayıcı yöntemlerin görevdaş (ing: synergy) bir bağdaşımını (ing: combination) kullanmaktır. Diğer bir deyişle, melez çerçevelerin görevdaşlık etkisinden faydalanması beklenmektedir. Melez yaklaştırımlarının tasarımı ve geliştirilmesi, değişimi ve belirsizliği ele alma kabiliyetlerinden dolayı umut verici olduğu düşünülmektedir ve bu nedenle, son yıllarda artan ilgi sezgi-üstleri ve melezleştirilmesine odaklanmıştır.
Melezleştirme fikri, "henüz, her türlü değişim ve belirsizlikle başa edebilmek için diğer tüm yaklaşımlara karşı sürekli ve tutarlı olarak en iyi başarımı gösterebilen tek bir Harezmi yolu (ne sezgi-üstü ne de makine öğrenmesi) mevcut değildir" genel kanısına karşı ortaya çıkması muhtemeldir. Sezgisel olarak, böyle bir yaklaşımın arkasındaki ana fikrin "bedava öğle yemeği yok kuramı (ing: no free lunch theorem)" bakış açısının iki temel kuramına dayandığını varsayabiliriz: biri denetimli makine öğrenmesi (ing: supervised machine learning) için ve diğeri arama/eniyileme (search/optimisation) için.
Bu tez kapsamında, önerilen her bir melez çerçeve (Harezmi yolu mimarisi) ilgili "bedava öğle yemeği yok kuramı" bakış açısı üzerine inşa edilmiştir. Melezleştirme yaklaşımının ana fikri, "birlikten kuvvet doğar (ing: there is strength in numbers)" ifadesinin kuramsal bir karşılığı olarak görülebilir, ve bu nedenle böylesi bir Harezmi yolu mimarisinin güdülenmesi, sezgi-üstler (özellikle olasılıksal çizgesel biçeleri-tabanlı sezgi-üstleri) ve makine öğrenmesi (özellikle olasılıksal çizgesel biçeleri) arasında bir görevdaşlık oluşturmak olacaktır. Önerilen çerçeveler, biçe-tabanlı sezgisel seçen üst-sezgiseller ve olasılıksal çizgesel biçeleri-tabanlı sezgi-üstleri tamamlayıcı yönlerini kullanırlar ve şu şekilde sınıflandırılabilirler:
I- "Bedava öğle yemeği yok kuramı"nın arama/eniyileme durumu için: Üst-sezgisel-tabanlı iki toplumlu dağılım tahmini Harezmi yolu (ing: hyper-heuristic-based, dual population estimation of distribution algorithm [HH-EDA2]) olarak adlandırdığımız melez bir çerçeve önerilmiştir.
Bu çerçeve, üst-sezgiseller ve olasılıksal çizgesel biçeleri-tabanlı sezgi-üstlerinin yararlarını birlikte kullanır. Burada, olasılıksal biçe-tabalı sezgisel seçen üst-sezgisel yöntemleri (makine öğrenmesi yöntemleri olarak), dağılım tahmini Harezmi yolunu (olasılıksal çizgesel biçeleri-tabanlı sezgi-üstler) iyileştirmek için kullanılmıştır. Bu çerçevenin en belirgin niteliği, herhangi bir çoklu-toplumlu dağılım tahmini Harezmi yolu ile herhangi bir olasılıksal biçe-tabanlı sezgisel seçen üst-sezgiselleri önerilen melez yaklaşıma entegre (dahil) edilebilmesidir. HH-EDA2 genel olarak, değişimin örüntüsünden (doğasından) bağımsız olarak, kendini değişen ortamlara uyarlayabilme yeteneğine sahiptir. HH-EDA2 melez çerçevesi, karmaşık değişen birleşimsel eniyileme problemlerini çözmek için, çevrimiçi ve çevrimdışı öğrenme izlemlerini kullanan iki-aşamalı melez yaklaşım biçimidir. Eğitim aşaması sırasında gerçekleşen çevrimdışı öğrenme kapsamında, bir dizi farklı türde ortam (yani değişimin örüntüsü) öğrenilir ve çevrimiçi öğrenme sırasında kullanılmak üzere saklanır. Çevrimiçi öğrenme kapsamında, bu öğrenilen ortamlar, üst-sezgiseller tarafından kullanılmak üzere alt-sezgisel olarak görev yapar. HH-EDA2'nin, bilimsel yazınlarda önerilen diğer yaklaşımlar ile başarımı ve farklı sezgisel seçen üst-sezgisellerin çerçeveye etkileri, iyi bilinen denektaşı (ing: benchmark) üreteci tarafından oluşturulan bir dizi değişen ortamların yanı sıra gerçek hayattaki vaka çalışması olarak, NP-zor kısıtlı olarak bilinen ünite yüklenme problem üzerinde incelenmiştir.
II- "Bedava öğle yemeği yok kuramı"nın makine öğrenmesi durumu için: Bayesçi-güdümlü artan toplumlu ortak değişinti dizeyi uyarlamalı evrimsel izlem (ing: Bayesian-driven covariance matrix adaptation evolution strategy with increasing population [B-Ipop-CMA-ES]) melez çerçevesi önerilmiştir.
Bu çerçeve, ortak değişinti dizeyi uyarlamalı evrimsel izlem Harezmi yolu (olasılıksal biçeler-tabanlı sezgi-üstler olarak), beklenti-en büyükleme Harezmi yolunu (olasılıksal çizgesel biçeleri teknikleri olarak) iyileştirmek için kullanılmıştır. Bu melez çerçeve, sinir hücresi topluluğunun (nöronal) değişen davranışlarını betimlemeye ve daha iyi anlamaya olanak sağlayan etkin bağlantısallığın (ing: effective connectivity) biyofiziksel değiştirgelerinin tahmin edilmesine olanak sağlar. Hali hazırda, beklenti-en büyükleme Harezmi yolu Statistical Parametric Mapping (SPM) yazılım paketine bütünleşmiş (entegre edilmiş) değişen nedensel biçelendirim yaklaşımının nöronal ve hemodinamik değiştirgelerini tahmin etmek için kullanılıyor olsa da, mevcut gerçeklemenin bazı kısıtları mevcuttur. Beklenti-en büyükleme-tabanlı yaklaşımın en önemli kısıtları şunlardır: Harezmi yolu her bir biyofiziksel değiştirgeler için önsel bilgiye ihtiyaç duyar; Beklenti-en büyükleme yaklaşımı yerel en küçüğe takılma eğilimindedir; Bu yaklaşım hesaplama karmaşıklığı yoğundur ve bu nedenle ele alınan beyin bölgeleri sınırdır. Önerilen melez çerçeve bu tür kısıtların üstesinden gelebilmektedir. B-Ipop-CMA-ES çerçevesinin arkasındaki ana ilgi, başlangıç olarak biyofiziksel değiştirgelerin önsel bilgilerine gereksinim duymadan, hesaplama açısından en makul zamanda, küresel en iyi çözüme yakınsarken (yerel en iyiden kaçabilme yeteneği) işlevsel (fizyolojik) (ing: physiologically) olarak en gerçekçi biçeyi oluşturmasıdır. Bu bakış açısı ile, öz-uyumlu türevden bağımsız B-Ipop-CMA-ES çerçevesi bahsi geçen sorunların üstesinden gelebilmek için dikkate değer katkılar sunmuştur. B-Ipop-CMA-ES melez çerçevesi, hem yapay hem de deneysel işlevsel manyetik rezonans görüntüleme veri setleri üzerinde başarımı test edilmiştir. Deneysel sonuçlar önerilen çerçevenin başarımının, mevcut dayanak yaklaşımı (beklenti-en büyükleme/Gauss Newton: EM/GN) ve önerilen diğer rakip yaklaşımlardan daha iyi olduğunu göstermiştir.
Bu tez kapsamında ele alınan özgün katkılar şu şekilde özetlenebilir: (i) Farklı karmaşık yapı sergileyen değişim ve belirsizliklerin üstesinden gelebilen iki farklı genel melez çerçeve önerilmiştir; (ii) Bu tez araştırmasının başlıca odak noktası yalnızca melez çerçeveler önermek değil, aynı zamanda biçe değerlendirmesi ve bu biçelerin gerçek dünya problemlerinde süreklilik arz eden bu zorluklarının üstesinden nasıl gelinebildiğinin anlaşılmasıdır; (iii) Tezin diğer önemli dikkati, önerilen melez çerçevelerinin etkinlilerinin faklı uygulama alanlarındaki (mühendislik ve nörogörüntüleme) zamanla değişen ve belirsizliklerin olduğu karmaşık yapıdaki birleşimsel eniyileme problemlerinde sınanması ve başarı elde edilmesidir; (iv) Aynı zamanda bu tez, geniş bir yelpazede yer alan yaklaşımlar üzerine kuramsal bir araştırma ve inceleme sunmuştur.
|
|
Solving 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. |
