1,720,952 research outputs found
Designing the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm and Applying it to Substantially Improve the Efficiency of Multi-Objective Deformable Image Registration
No full textThe recently introduced Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) for discrete variables has been shown to be able to efficiently and effectively exploit the decomposability of optimization problems, especially in a grey-box setting, in which a solution can be efficiently updated after a modification of a subset of its variables. GOMEA is considered to be state of the art, but currently no version of GOMEA for real-valued variables exists. In this thesis, we design a real-valued version of GOMEA, for both single-objective and multi-objective optimization. Our novel GOMEA variant is then applied to the Deformable Image Registration (DIR) problem, which was adapted to allow for efficient partial evaluations. DIR concerns the calculation of a deformation that transforms one image to another, and is of great importance for many medical applications. Experiments are performed to assess GOMEA’s performance in black-box and grey-box settings on a range of single-objective and multi-objective benchmark problems, including comparisons with it to the state-of-the-art real-valued optimization algorithm AMaLGaM. From the results of these experiments, we find that GOMEA performs substantially better on all considered single-objective and multi-objective benchmark problems in a grey-box setting, in terms of required time and number of evaluations. Moreover, the improvement becomes larger as problem dimensionality increases. In a black-box setting, GOMEA still performed better than AMaLGaM in terms of time, and comparable in terms of the number of evaluations. On DIR problems, GOMEA achieved solutions of similar quality while achieving a speed-up of up to a factor of 1600.Electrical Engineering, Mathematics and Computer ScienceSoftware TechnologyAlgorithmic
Optimal Mixing Evolutionary Algorithms for Large-Scale Real-Valued Optimization: Including Real-World Medical Applications
Get PDFIn recent years, the use of Artificial Intelligence (AI) has become prevalent in a large number of societally relevant, real-world problems, e.g., in the domains of engineering and health care. The field of Evolutionary Computation (EC) can be considered to be a sub-field of AI, concerning optimization using Evolutionary Algorithms (EAs), which are population-based (meta-)heuristics that employ the Darwinian principles of evolution, i.e., variation and selection. Such EAs are historically mainly considered for the optimization of difficult, non-linear problems in a Black-Box Optimization (BBO) setting, because EAs can effectively optimize such problems even when very little is known about the optimization problem and its structure. This is in contrast to optimization methods that are specifically designed for certain problems of which the definition and structure are known, i.e., a White-Box Optimization (WBO) setting
GPU-Accelerated GOMEA: Solving the max-cut problem by large-scale parallelisation of GOMEA using GPGPU
No full textWith 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.Applied Mathematic
Constraint Handling in RV-GOMEA
No full textThe 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.Computer Science | Artificial Intelligenc
NedTrain Planner: Construeren van Flexibele Roosters
No full textHet bedrijf NedTrain beschikt over software om roosterproblemen op te lossen. De wens van NedTrain en het doel van dit project is om deze software uit te breiden met de functionaliteit om flexibele schema's te berekenen. Deze roosterproblemen hebben te maken met het probleem dat ook wel bekend staat als het Resource Constrained Project Scheduling Problem. Hierbij wordt er naar een schema gezocht voor bijvoorbeeld het onderhoud aan treinen. Doordat elke trein binnen een bepaalde tijd gerepareerd moet worden en er ook rekening gehouden moet worden met de beschikbare resources, is dit probleem moeilijk om op te lossen. De bestaande software van NedTrain bestaat uit een interface, genaamd de NedTrain Planner, en een solver, die er voor zorgt dat instanties opgelost worden. Deze software kan echter alleen vaste schema's genereren. Op het moment dat er activiteiten verplaatst worden, kunnen er conflicten ontstaan, waardoor het schema niet meer geldig is. Dit wordt opgelost door het implementeren van een nieuwe solver. Deze solver maakt gebruik van het chaining algoritme en de COIN Linear Programming library. Het chaining algoritme is nodig om te zorgen dat bij het verplaatsen van activiteiten het schema consistent blijft qua resources. De COIN LP library is gebruikt om flexibiliteitsintervallen te kunnen berekenen, die vervolgens worden weergegeven in de interface.AlgorithmicsElectrical Engineering, Mathematics and Computer Scienc
Warm-starting evolutionary plan optimization for high-dose-rate brachytherapy treatment to reduce optimization time
No full textComputer Scienc
Obtaining Smoothly Navigable Approximation Sets in Bi-Objective Multi-Modal Optimization with an Application to Prostate HDR Brachytherapy Automated Treatment Planning
No full textEven if a Multi-modal Multi-Objective Evolutionary Algorithm (MMOEA) is designed to find all locally optimal approximation sets of a Multi-modal Multi-objective Optimization Problem (MMOP), there is a risk that the found approximation sets are not smoothly navigable because the solutions belong to various niches, which reduces the insight for decision makers. Moreover, when the multi-modality of MMOPs increases, this risk grows and the trackability of finding all locally optimal approximation sets decreases. One example where this issue occurs is that of High-Dose-Rate (HDR) brachytherapy for prostate cancer. In HDR brachytherapy a treatment plan is to be optimized that irradiates a tumour with a prescribed dose, whilst sparing all of the healthy organs surrounding the tumour. The radiation is administered through a radioactive source that is stopped at certain dwell positions within a set of hollow catheters that have been implanted into the patient. In a treatment plan, each of the dwell positions is given a specific dwell time for which the source is kept at that location in order to irradiate the surrounding tissue. To tackle the navigability issues, two new MMOEAs are proposed: Multi-Modal Bézier Evolutionary Algorithm (MM-BezEA) and Set Bézier Evolutionary Algorithm (Set-BezEA). Both MMOEAs produce approximation sets that cover individual niches and exhibit inherent decision-space smoothness as they are parameterized by Bézier curves. MM-BezEA combines the concepts behind the recently introduced BezEA and MO-HillVallEA to find all locally optimal approximation sets. Set-BezEA employs a novel multi-objective fitness function formulation to find limited numbers of diverse, locally optimal, approximation sets for MMOPs of high multi-modality.Both algorithms, but especially MM-BezEA, are found to outperform the MMOEAs MO_Ring_PSO_SCD and MO-HillVallEA on MMOPs of moderate multi-modality with linear Pareto sets. Moreover, for MMOPs of high multi-modality, Set-BezEA is found to indeed be able to produce high-quality approximation sets, each pertaining to a single niche. Set-BezEA is also shown to be comparable to the current BRIGHT approach used in the Amsterdam UMC for the optimization of treatment plans for prostate cancer HDR brachytherapy, which opens the way for it to be introduced in the clinical practice in the future.Double degree in Computer Science and Embedded SystemsFast, accurate, and insightful brachytherapy treatment planning for cervical cancer through artificial intelligence (Brachytherapy treatment)Computer Science | Data Science and TechnologyElectrical Engineering | Embedded System
A surrogate-assisted evolutionary algorithm based on inverse distance weighting: Applied to a multi-objective deformable image registration problem
No full textSolutions to many real-life optimization problems take a long time to evaluate. This limits the number of solutions we can evaluate. When optimizing with an Evolutionary Algorithm (EA) a frequently used approach is to approximate the objective using a surrogate function, replacing the time-consuming real evaluation. This surrogate model is combined with a so-called acquisition function, to select promising candidate solutions. The acquisition function balances the trade-off between exploration of parameter space and the exploitation of the surrogate. These candidates are subject to an expensive evaluation with the true objective function and are used to update the surrogate model. Iteratively applying this process can effectively optimize global optimization problems. In this work, we propose a new multi-objective optimization algorithm with inverse distance weighting as surrogate function, which we call IDW-SAEA (inverse distance weighting surrogate assisted evolutionary algorithm). We introduce a new objective to the optimization problem to improve exploration and reduce the complexity of the acquisition function. We show this algorithm is competitive with state-of-the-art kriging-based surrogate-assisted EAs on certain benchmark problems. Additionally, we use the algorithm to optimize a practical problem: a Finite Element Method simulation of the cervix region with applications in radiotherapy for cervical cancer.Computer Scienc
Fitness-based linkage learning in the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm
Get PDFThe recently introduced Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) has been shown to be among the state-of-the-art for solving grey-box optimization problems where partial evaluations can be leveraged. A core strength is its ability to effectively exploit the linkage structure of a problem, which often is unknown a priori and has to be learned online. Previously published work on RV-GOMEA however demonstrated excellent scalability when the linkage structure is pre-specified appropriately. A mutual-information-based metric to learn linkage structure online, as commonly adopted in EDA’s and the original discrete version of GOMEA, did not lead to similarly excellent results, especially in a black-box setting. In this article, the strengths of RV-GOMEA are combined with a new fitness-based linkage learning approach that is inspired by differential grouping that reduces its computational overhead by an order of magnitude for problems with fewer interactions. The resulting new version of RV-GOMEA achieves scalability similar to when a predefined linkage model is used, outperforming also, for the first time, the EDA AMaLGaM upon which it is partially based in a black-box setting where partial evaluations can not be leveraged. This article is extended from the MSc thesis of Chantal Olieman, available at https://repository.tudelft.nl/ mythesis
Leveraging conditional linkage models in gray-box optimization with the real-valued gene-pool optimal mixing evolutionary algorithm
Get PDFOften, real-world problems are of the gray-box type. It has been shown that the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) is in principle capable of exploiting such a Gray-Box Optimization (GBO) setting using linkage models that capture dependencies between problem variables, resulting in excellent performance and scalability on both benchmark and real-world problems that allow for partial evaluations. However, linkage models proposed for RV-GOMEA so far cannot explicitly capture overlapping dependencies. Consequently, performance degrades if such dependencies exist. In this paper, we therefore introduce various ways of using conditional linkage models in RV-GOMEA. Their use is compared to that of non-conditional models, and to VkD-CMA, whose performance is among the state of the art, on various benchmark problems with overlapping dependencies. We find that RV-GOMEA with conditional linkage models achieves the best scalability on most problems, with conditional models leading to similar or better performance than non-conditional models. We conclude that the introduction of conditional linkage models to RV-GOMEA is an important contribution, as it expands the set of problems for which optimization in a GBO setting results in substantially improved performance and scalability. In future work, conditional linkage models may prove to benefit the optimization of real-world problems.Accepted Author ManuscriptAlgorithmic
- …
