PB
P.A. Bouter
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
3 records found
1
Mixed-integer optimization problems, incorporating both discrete and continuous variables, present unique challenges across various domains such as computer science, finance, logistics, and healthcare. Evolutionary Algorithms (EAs) have emerged as powerful optimization techniques capable of tackling such complex problems in either the discrete or continuous domain. Model-based EAs, integrating machine learning techniques, have further improved the efficiency and scalability of these algorithms. The first algorithm to combine discrete and continuous model-based EAs is the Mixed-Integer Hybrid Evolutionary Algorithm (MIHEA). Despite its potential, MIHEA remains relatively underutilized in research endeavours. This thesis seeks to bridge this gap in research by applying the algorithm to a novel context: structure learning of Bayesian Networks (BNs).
BNs offer a transparent framework for probabilistic reasoning, making them well-suited for various applications. However, learning the structure and discretizations of BNs from data is a challenging task. It is not uncommon for the datasets to contain values of continuous nodes as well. Assuming no normality, these nodes in the data need to be discretized, since BNs are designed for discrete data. The optimal discretizations of these nodes depend on the structure of the BN, meaning that the discretization optimization should happen simultaneously with the structure learning. MIHEA holds promise for addressing this challenge by leveraging its mixed-integer optimization capabilities.
The investigation performed in this thesis starts with a reproduction study. The description of the code for MIHEA is shown to be inconsistent with the experiment results, which prompts a reproduction study resulting in a version of the code that more accurately fits the results.
Subsequently, MIHEA is applied to the structure learning of BNs, where discrete variables represent network structure and continuous variables encode discretizations of continuous nodes. Several solution representations are explored. The experiments show that MIHEA achieves similar or better performance than the state-of-the-art DBN-GOMEA approach on the task of recreating randomly generated BNs from data, at the cost of increased execution time.
These results demonstrate the potential of model-based mixed-integer EAs, particularly MIHEA, for BN structure learning from continuous data. The findings encourage further exploration and utilization of mixed-integer EAs in solving (real-world) problems involving BNs and continuous data.
...
BNs offer a transparent framework for probabilistic reasoning, making them well-suited for various applications. However, learning the structure and discretizations of BNs from data is a challenging task. It is not uncommon for the datasets to contain values of continuous nodes as well. Assuming no normality, these nodes in the data need to be discretized, since BNs are designed for discrete data. The optimal discretizations of these nodes depend on the structure of the BN, meaning that the discretization optimization should happen simultaneously with the structure learning. MIHEA holds promise for addressing this challenge by leveraging its mixed-integer optimization capabilities.
The investigation performed in this thesis starts with a reproduction study. The description of the code for MIHEA is shown to be inconsistent with the experiment results, which prompts a reproduction study resulting in a version of the code that more accurately fits the results.
Subsequently, MIHEA is applied to the structure learning of BNs, where discrete variables represent network structure and continuous variables encode discretizations of continuous nodes. Several solution representations are explored. The experiments show that MIHEA achieves similar or better performance than the state-of-the-art DBN-GOMEA approach on the task of recreating randomly generated BNs from data, at the cost of increased execution time.
These results demonstrate the potential of model-based mixed-integer EAs, particularly MIHEA, for BN structure learning from continuous data. The findings encourage further exploration and utilization of mixed-integer EAs in solving (real-world) problems involving BNs and continuous data.
...
Mixed-integer optimization problems, incorporating both discrete and continuous variables, present unique challenges across various domains such as computer science, finance, logistics, and healthcare. Evolutionary Algorithms (EAs) have emerged as powerful optimization techniques capable of tackling such complex problems in either the discrete or continuous domain. Model-based EAs, integrating machine learning techniques, have further improved the efficiency and scalability of these algorithms. The first algorithm to combine discrete and continuous model-based EAs is the Mixed-Integer Hybrid Evolutionary Algorithm (MIHEA). Despite its potential, MIHEA remains relatively underutilized in research endeavours. This thesis seeks to bridge this gap in research by applying the algorithm to a novel context: structure learning of Bayesian Networks (BNs).
BNs offer a transparent framework for probabilistic reasoning, making them well-suited for various applications. However, learning the structure and discretizations of BNs from data is a challenging task. It is not uncommon for the datasets to contain values of continuous nodes as well. Assuming no normality, these nodes in the data need to be discretized, since BNs are designed for discrete data. The optimal discretizations of these nodes depend on the structure of the BN, meaning that the discretization optimization should happen simultaneously with the structure learning. MIHEA holds promise for addressing this challenge by leveraging its mixed-integer optimization capabilities.
The investigation performed in this thesis starts with a reproduction study. The description of the code for MIHEA is shown to be inconsistent with the experiment results, which prompts a reproduction study resulting in a version of the code that more accurately fits the results.
Subsequently, MIHEA is applied to the structure learning of BNs, where discrete variables represent network structure and continuous variables encode discretizations of continuous nodes. Several solution representations are explored. The experiments show that MIHEA achieves similar or better performance than the state-of-the-art DBN-GOMEA approach on the task of recreating randomly generated BNs from data, at the cost of increased execution time.
These results demonstrate the potential of model-based mixed-integer EAs, particularly MIHEA, for BN structure learning from continuous data. The findings encourage further exploration and utilization of mixed-integer EAs in solving (real-world) problems involving BNs and continuous data.
BNs offer a transparent framework for probabilistic reasoning, making them well-suited for various applications. However, learning the structure and discretizations of BNs from data is a challenging task. It is not uncommon for the datasets to contain values of continuous nodes as well. Assuming no normality, these nodes in the data need to be discretized, since BNs are designed for discrete data. The optimal discretizations of these nodes depend on the structure of the BN, meaning that the discretization optimization should happen simultaneously with the structure learning. MIHEA holds promise for addressing this challenge by leveraging its mixed-integer optimization capabilities.
The investigation performed in this thesis starts with a reproduction study. The description of the code for MIHEA is shown to be inconsistent with the experiment results, which prompts a reproduction study resulting in a version of the code that more accurately fits the results.
Subsequently, MIHEA is applied to the structure learning of BNs, where discrete variables represent network structure and continuous variables encode discretizations of continuous nodes. Several solution representations are explored. The experiments show that MIHEA achieves similar or better performance than the state-of-the-art DBN-GOMEA approach on the task of recreating randomly generated BNs from data, at the cost of increased execution time.
These results demonstrate the potential of model-based mixed-integer EAs, particularly MIHEA, for BN structure learning from continuous data. The findings encourage further exploration and utilization of mixed-integer EAs in solving (real-world) problems involving BNs and continuous data.
GPU-Accelerated GOMEA
Solving the max-cut problem by large-scale parallelisation of GOMEA using GPGPU
With the advances in General-Purpose computing on Graphics Processing Units (GPGPU), it is worthwhile to explore whether other areas in the field of Artificial Intelligence (AI) can reap the benefits. One such area is Evolutionary Algorithms (EAs), which—among other processes—involves the repetitive exchange of genes among individuals. This repetitive nature aligns with our intuition for parallel optimisation, precisely what GPGPU is designed for. Currently, the state-of-the-art approach in EA is known as Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA), which capitalises on the information embedded within the population by computing the linkage between genes across the entire population. However, when it comes to parallelising the exchange of complete linkage sets, particularly in the context of our specific problem of interest, the challenge becomes more intricate.
In the case of our problem, known as Max-cut, there are dependencies between genes that must be considered when constructing parallel sets of linkage sets, referred to as packages. We propose three solutions: contamination, revision, and association. Contamination fully utilises parallel capabilities but deviates from the concept of linkage sets. Revision constructs the linkage sets as described by GOMEA, but keeps the dependencies between linkage sets within a package untouched. Association on the other hand attempts to resolve the dependencies by generating a dependency graph to create the set of packages.
From our experiments, we can conclude that parallel acceleration using GPGPU is roughly on par with—and sometimes even outperforms—its non-parallelised counterpart. Out of the three solutions, it is evident that association demonstrates the most promising performance profile in terms of approaching the optimal solution. However, the performance falls significantly short of matching the capabilities exhibited by GOMEA. Furthermore, all of the solutions face a significant burden when evaluating the fitness for each exchanged linkage set. An option to consider as an extension to the current setup is known as partial evaluation, although the performance exhibited by contamination implies that simplicity could be the key to success. Further exploration of the acceleration process using widely employed parallel operators—such as those found in linear algebra—has the potential to yield valuable insights for enhancing performance. ...
In the case of our problem, known as Max-cut, there are dependencies between genes that must be considered when constructing parallel sets of linkage sets, referred to as packages. We propose three solutions: contamination, revision, and association. Contamination fully utilises parallel capabilities but deviates from the concept of linkage sets. Revision constructs the linkage sets as described by GOMEA, but keeps the dependencies between linkage sets within a package untouched. Association on the other hand attempts to resolve the dependencies by generating a dependency graph to create the set of packages.
From our experiments, we can conclude that parallel acceleration using GPGPU is roughly on par with—and sometimes even outperforms—its non-parallelised counterpart. Out of the three solutions, it is evident that association demonstrates the most promising performance profile in terms of approaching the optimal solution. However, the performance falls significantly short of matching the capabilities exhibited by GOMEA. Furthermore, all of the solutions face a significant burden when evaluating the fitness for each exchanged linkage set. An option to consider as an extension to the current setup is known as partial evaluation, although the performance exhibited by contamination implies that simplicity could be the key to success. Further exploration of the acceleration process using widely employed parallel operators—such as those found in linear algebra—has the potential to yield valuable insights for enhancing performance. ...
With the advances in General-Purpose computing on Graphics Processing Units (GPGPU), it is worthwhile to explore whether other areas in the field of Artificial Intelligence (AI) can reap the benefits. One such area is Evolutionary Algorithms (EAs), which—among other processes—involves the repetitive exchange of genes among individuals. This repetitive nature aligns with our intuition for parallel optimisation, precisely what GPGPU is designed for. Currently, the state-of-the-art approach in EA is known as Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA), which capitalises on the information embedded within the population by computing the linkage between genes across the entire population. However, when it comes to parallelising the exchange of complete linkage sets, particularly in the context of our specific problem of interest, the challenge becomes more intricate.
In the case of our problem, known as Max-cut, there are dependencies between genes that must be considered when constructing parallel sets of linkage sets, referred to as packages. We propose three solutions: contamination, revision, and association. Contamination fully utilises parallel capabilities but deviates from the concept of linkage sets. Revision constructs the linkage sets as described by GOMEA, but keeps the dependencies between linkage sets within a package untouched. Association on the other hand attempts to resolve the dependencies by generating a dependency graph to create the set of packages.
From our experiments, we can conclude that parallel acceleration using GPGPU is roughly on par with—and sometimes even outperforms—its non-parallelised counterpart. Out of the three solutions, it is evident that association demonstrates the most promising performance profile in terms of approaching the optimal solution. However, the performance falls significantly short of matching the capabilities exhibited by GOMEA. Furthermore, all of the solutions face a significant burden when evaluating the fitness for each exchanged linkage set. An option to consider as an extension to the current setup is known as partial evaluation, although the performance exhibited by contamination implies that simplicity could be the key to success. Further exploration of the acceleration process using widely employed parallel operators—such as those found in linear algebra—has the potential to yield valuable insights for enhancing performance.
In the case of our problem, known as Max-cut, there are dependencies between genes that must be considered when constructing parallel sets of linkage sets, referred to as packages. We propose three solutions: contamination, revision, and association. Contamination fully utilises parallel capabilities but deviates from the concept of linkage sets. Revision constructs the linkage sets as described by GOMEA, but keeps the dependencies between linkage sets within a package untouched. Association on the other hand attempts to resolve the dependencies by generating a dependency graph to create the set of packages.
From our experiments, we can conclude that parallel acceleration using GPGPU is roughly on par with—and sometimes even outperforms—its non-parallelised counterpart. Out of the three solutions, it is evident that association demonstrates the most promising performance profile in terms of approaching the optimal solution. However, the performance falls significantly short of matching the capabilities exhibited by GOMEA. Furthermore, all of the solutions face a significant burden when evaluating the fitness for each exchanged linkage set. An option to consider as an extension to the current setup is known as partial evaluation, although the performance exhibited by contamination implies that simplicity could be the key to success. Further exploration of the acceleration process using widely employed parallel operators—such as those found in linear algebra—has the potential to yield valuable insights for enhancing performance.
The Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) is a state-of-the-art algorithm for single-objective, real-valued optimization. As many practical applications are inherently constrained, evolutionary algorithms are equipped with constraint handling techniques to allow optimizing constrained problems. The approach currently in use with RV-GOMEA prioritizes solution feasibility over the objective value in all cases, pressuring the algorithm to find feasible solutions. However, this can be inefficient if the constrained optimum is located at the constraint boundary, as search is discouraged from exploring the search space close to infeasible solutions.
In this thesis, several well-known constraint handling techniques from literature are adapted for use with RV-GOMEA and evaluated on different benchmark problems, identifying the strengths and limitations of the various techniques. Furthermore, the inefficiency of the current technique is investigated in detail. Based on the insights gained, modifications to the existing techniques are proposed, leading to promising preliminary results. ...
In this thesis, several well-known constraint handling techniques from literature are adapted for use with RV-GOMEA and evaluated on different benchmark problems, identifying the strengths and limitations of the various techniques. Furthermore, the inefficiency of the current technique is investigated in detail. Based on the insights gained, modifications to the existing techniques are proposed, leading to promising preliminary results. ...
The Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) is a state-of-the-art algorithm for single-objective, real-valued optimization. As many practical applications are inherently constrained, evolutionary algorithms are equipped with constraint handling techniques to allow optimizing constrained problems. The approach currently in use with RV-GOMEA prioritizes solution feasibility over the objective value in all cases, pressuring the algorithm to find feasible solutions. However, this can be inefficient if the constrained optimum is located at the constraint boundary, as search is discouraged from exploring the search space close to infeasible solutions.
In this thesis, several well-known constraint handling techniques from literature are adapted for use with RV-GOMEA and evaluated on different benchmark problems, identifying the strengths and limitations of the various techniques. Furthermore, the inefficiency of the current technique is investigated in detail. Based on the insights gained, modifications to the existing techniques are proposed, leading to promising preliminary results.
In this thesis, several well-known constraint handling techniques from literature are adapted for use with RV-GOMEA and evaluated on different benchmark problems, identifying the strengths and limitations of the various techniques. Furthermore, the inefficiency of the current technique is investigated in detail. Based on the insights gained, modifications to the existing techniques are proposed, leading to promising preliminary results.