Search

Recent work in combinatorial optimisation have demonstrated that neighbouring solutions of a local optima may belong to more favourable attraction basins. In this sense, the perturbation strategy plays a critical role on local search based algorithms to kick the search of the algorithm into more prominent areas of the space. In this paper, we investigate the landscape rotation as a perturbation strategy to redirect the search of an stuck algorithm. This technique rearranges the mapping of solutions to different objective values without altering important properties of the problem's landscape such as the number and quality of optima, among others. Particularly, we investigate two rotation based perturbation strategies: (i) a profoundness rotation method and (ii) a broadness rotation method. These methods are applied into the stochastic hill-climbing heuristic and tested and compared on different instances of the quadratic assignment problem against other algorithm versions. Performed experiments reveal that the landscape rotation is an efficient perturbation strategy to shift the search in a controlled way. Nevertheless, an empirical investigation of the landscape rotation demonstrates that it needs to be cautiously manipulated in the permutation space since a small rotation does not necessarily mean a small disturbance in the fitness landscape.

In previous work, we proposed and studied a new dynamic formulation of the Location-allocation (LA) problem called the Dynamic-Customer Location-allocation (DC-LA) problem. DC-LA is based on the idea of changes in customer distribution over a defined period, and these changes have to be taken into account when establishing facilities to service changing customers distributions. This necessitated a dynamic stochastic evaluation function Which came with a high computational cost due to a large number of simulations required in the evaluation process.In this paper, we investigate the use of racing, an approach used in model selection, to reduce the high computational cost by employing the minimum number of simulations for solution selection. Our adaptation of racing uses the Friedman test to compare solutions statistically. Racing allows simulations to be performed iteratively, ensuring that the minimum number of simulations is performed to detect a statistical difference.We present experiments using Population-Based Incremental Learning (PBIL) to explore the savings achievable from using racing in this way. Our results show that racing achieves improved cost savings over the dynamic stochastic evaluation function. We also observed that on average, the computational cost of racing was about 4.5 times loWer than the computational cost of the full dynamic stochastic evaluation.

We propose a new class of multi-objective benchmark problems on which we analyse the performance of four well established multi-objective evolutionary algorithms (MOEAs) – each implementing a different search paradigm – by comparing run-time convergence behaviour over a set of 1200 problem instances. The new benchmarks are created by fusing previously proposed single-objective interpolated continuous optimisation problems (ICOPs) via a common set of Pareto non-dominated seeds. They thus inherit the ICOP property of having tunable fitness landscape features. The benchmarks are of intrinsic interest as they derive from interpolation methods and so can approximate general problem instances. This property is revealed to be of particular importance as our extensive set of numerical experiments indicates that choices pertaining to (i) the weighting of the inverse distance interpolation function and (ii) the problem dimension can be used to construct problems that are challenging to all tested multi-objective search paradigms. This in turn means that the new multi-objective ICOPs problems (MO-ICOPs) can be used to construct well-balanced benchmark sets that discriminate well between the run-time convergence behaviour of different solvers.

In this paper, we introduce a new stochastic Location-Allocation Problem which assumes the movement of customers over time. We call this new problem Dynamic Customer Location-Allocation Problem (DC-LAP). The problem is based on the idea that customers will change locations over a defined horizon and these changes have to be taken into account when establishing facilities to service customers demands. We generate 1440 problem instances by varying the problem parameters of movement rate which determines the possible number of times a customer will change locations over the defined period, the number of facilities and the number of customers. We propose to analyse the characteristics of the instances generated by testing a search algorithm using the stochastic dynamic evaluation (based on the replication of customer movement scenarios) and a deterministic static evaluation (based on the assumption that customer will not move over time). We show that the dynamic approach obtains globally better results, but the performances are highly related to the parameters of the problem. Moreover, the dynamic approach involves a significantly high computational overhead.

By incorporating domain knowledge, simple greedy procedures can be defined to generate reasonably good solutions to many optimisation problems. However, such solutions are unlikely to be optimal and their quality often depends on the way the decision variables are input to the greedy method. Indirect optimisation uses meta-heuristics to optimise the input of the greedy decoders. As the performance and the runtime differ across greedy methods and meta-heuristics, deciding how to split the computational effort between the two sides of the optimisation is not trivial and can significantly impact the search. In this paper, an artificial scheduling problem is presented along with five greedy procedures, using varying levels of domain information. A methodology to compare different indirect optimisation strategies is presented using a simple Hill Climber, a Genetic Algorithm and a population-based Local Search. By assessing all combinations of meta-heuristics and greedy procedures on a range of problem instances with different properties, experiments show that encapsulating problem knowledge within greedy decoders may not always prove successful and that simpler methods can lead to comparable results as advanced ones when combined with meta-heuristics that are adapted to the problem. However, the use of efficient greedy procedures reduces the relative difference between meta-heuristics.

The Uncapacitated Location-Allocation problem (ULAP) is a major optimisation problem concerning the determination of the optimal location of facilities and the allocation of demand to them. In this paper, we present two novel problem variants of Non-Linear ULAP motivated by a real-world problem from the telecommunication industry: Uncapacitated Location-Allocation Resilience problem (ULARP) and Uncapacitated Location-Allocation Resilience problem with Restrictions (ULARPR). Problem sizes ranging from 16 to 100 facilities by 50 to 10000 demand points are considered. To solve the problems, we explore the components and configurations of four Genetic Algorithms [1]–[3] and [4] selected from the ULAP literature. We aim to understand the contribution each choice makes to the GA performance and so hope to design an Optimal GA configuration for the novel problems. We also conduct comparative experiments with Population-Based Incremental Learning (PBIL) Algorithm on ULAP. We show the effectiveness of PBIL and GA with parameter set: random and heuristic initialisation, tournament and fined_grained tournament selection, uniform crossover and bitflip mutation in solving the proposed problems.

In this paper, we introduce a dynamic variant of the Location-Allocation problem: Dynamic Location-Allocation Problem (DULAP). DULAP involves the location of facilities to service a set of customer demands over a defined horizon. To evaluate a solution to DULAP, we propose two holistic metric approaches: Static and Dynamic Approach. In the static approach, a solution is evaluated with the assumption that customer locations and demand remain constant over a defined horizon. In the dynamic approach, the assumption is made that customer demand, and demographic pattern may change over the defined horizon. We introduce a stochastic model to simulate customer population and distribution over time. We use a Genetic Algorithm and Population-Based Incremental Learning algorithm used in previous work to find robust and satisfactory solutions to DULAP. Results show the dynamic approach of evaluating a solution finds good and robust solutions.

In this paper, we introduce a new class of optimisation problems with tunable landscape features called Interpolated Continuous Optimisation Problems (ICOPs). ICOPs are defined by a search space, a set of solutions called seeds at selected positions, and their fitnesses. The rest of the fitness landscape is interpolated from the seeds using the inverse distance weighting interpolation function. We show that by evolving the position and the fitness of the seeds, we can generate extreme problems with respect to different fitness landscape measures.

Random Key (RK) is an alternative representation for permutation problems that enables application of techniques generally used for continuous optimisation. Although the benefit of RKs to permutation optimisation has been shown, its use within Estimation of Distribution Algorithms (EDAs) has been a challenge. Recent research proposing a RK-based EDA (RK-EDA) has shown that RKs can produce competitive results with state of the art algorithms. Following promising results on the Permutation Flowshop Scheduling Problem, this paper presents an analysis of RK-EDA for optimising the total flow time. Experiments show that RK-EDA outperforms other permutation-based EDAs on instances of large dimensions. The difference in performance between RK-EDA and the state of the art algorithms also decreases when the problem difficulty increases.

This paper improves a recently developed multi-objective particle swarm optimizer ([Formula: see text]) that incorporates dominance with decomposition used in the context of multi-objective optimization. Decomposition simplifies a multi-objective problem (MOP) by transforming it to a set of aggregation problems, whereas dominance plays a major role in building the leaders’ archive. [Formula: see text] introduces a new archiving technique that facilitates attaining better diversity and coverage in both objective and solution spaces. The improved method is evaluated on standard benchmarks including both constrained and unconstrained test problems, by comparing it with three state of the art multi-objective evolutionary algorithms: MOEA/D, OMOPSO, and dMOPSO. The comparison and analysis of the experimental results, supported by statistical tests, indicate that the proposed algorithm is highly competitive, efficient, and applicable to a wide range of multi-objective optimization problems.

Fitness modeling has received growing interest from the evolutionary computation community in recent years. With a fitness model, one can improve evolutionary algorithm efficiency by directly sampling new solutions, developing hybrid guided evolutionary operators or using the model as a surrogate for an expensive fitness function. This paper addresses several issues on fitness modeling of discrete functions, particularly how modeling quality and efficiency can be improved. We define the Markov network fitness model in terms of Walsh functions. We explore the relationship between the Markov network fitness model and fitness in a number of discrete problems, showing how the parameters of the fitness model can identify qualitative features of the fitness function. We define the fitness prediction correlation, a metric to measure fitness modeling capability of local and global fitness models. We use this metric to investigate the effects of population size and selection on the tradeoff between model quality and complexity for the Markov network fitness model.

The Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) has been of research interest for over two decades. The problem is composed of two interacting sub problems: mode assignment and activity scheduling. These problems cannot be solved in isolation because of the interaction that exists between them. Many evolutionary algorithms have been applied to this problem most commonly the Genetic Algorithm (GA). It has been common practice to improve the performance of the GA with some local search techniques. The Bi-population Genetic Algorithm (BPGA) is one of the most competitive GAs for solving the MRCPSP. In this paper, we improve the BPGA by hybridising it with an Estimation of Distribution Algorithm that focuses on improving how modes are generated. We also suggest improvement to the existing experimental methodology.

The challenges of solving problems naturally represented as permutations by Estimation of Distribution Algorithms (EDAs) have been a recent focus of interest in the evolutionary computation community. One of the most common alternative representations for permutation based problems is the Random Key (RK), which enables the use of continuous approaches for this problem domain. However, the use of RK in EDAs have not produced competitive results to date and more recent research on permutation based EDAs have focused on creating superior algorithms with specially adapted representations. In this paper, we present RK-EDA; a novel RK based EDA that uses a cooling scheme to balance the exploration and exploitation of a search space by controlling the variance in its probabilistic model. Unlike the general performance of RK based EDAs, RK-EDA is actually competitive with the best EDAs on common permutation test problems: Flow Shop Scheduling, Linear Ordering, Quadratic Assignment, and Travelling Salesman Problems.

This paper presents a Markov random field (MRF) approach to estimating and sampling the probability distribution in populations of solutions. The approach is used to define a class of algorithms under the general heading distribution estimation using Markov random fields (DEUM). DEUM is a subclass of estimation of distribution algorithms (EDAs) where interaction between solution variables is represented as an undirected graph and the joint probability of a solution is factorized as a Gibbs distribution derived from the structure of the graph. The focus of this paper will be on describing the three main characteristics of DEUM framework, which distinguishes it from the traditional EDA. They are: 1) use of MRF models, 2) fitness modeling approach to estimating the parameter of the model and 3) Monte Carlo approach to sampling from the model.

The Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) is composed of two interacting sub- problems which are the mode assignment problem and the scheduling problem. Solving these sub-problems in isola- tion pose a challenge due to the interaction that exists be- tween them. We present a unified approach for applying a combination of algorithms to the sub-problems of the MR- CPSP. The use of Genetic algorithms and Estimation of Distribution Algorithms aims to exploit efficiently and syn- chronously the distinct search spaces presented by the two sub-problems.

We present an approach to generating problems of variable difficulty based on the well-known Proximate Optimality Principle (POP), often paraphrased as "similar solutions have similar fitness". We explore definitions of this concept in terms of metrics in objective space and in representation space and define POP in terms of coherence of these metrics. We hypothesise that algorithms will perform well when the neighbourhoods they explore in representation space are coherent with the natural metric induced by fitness on objective space. We develop an explicit method of problem generation which creates bit string problems where the natural fitness metric is coherent or anti-coherent with Hamming neighbourhoods. We conduct experiments to show that coherent problems are easy whereas anti-coherent problems are hard for local hill climbers using the Hamming neighbourhoods.

Problem structure, or linkage, refers to the interaction between variables in a black-box fitness function. Discovering structure is a feature of a range of algorithms, including estimation of distribution algorithms (EDAs) and perturbation methods (PMs). The complexity of structure has traditionally been used as a broad measure of problem difficulty, as the computational complexity relates directly to the complexity of structure. The EDA literature describes necessary and unnecessary interactions in terms of the relationship between problem structure and the structure of probabilistic graphical models discovered by the EDA. In this paper we introduce a classification of problems based on monotonicity invariance. We observe that the minimal problem structures for these classes often reveal that significant proportions of detected structures are unnecessary. We perform a complete classification of all functions on 3 bits. We consider nonmonotonicity linkage discovery using perturbation methods and derive a concept of directed ordinal linkage associated to optimization schedules. The resulting refined classification factored out by relabeling, shows a hierarchy of nine directed ordinal linkage classes for all 3-bit functions. We show that this classification allows precise analysis of computational complexity and parallelizability and conclude with a number of suggestions for future work.

In recent years much work has been don; on modelling the growth of malignant tumours with a view to predicting their development and optimizing the effect of chemotherapy on their alleviation. One approach has been to treat the tumour as a non‐linear system and the drug treatment as a control strategy. This has led to the use of calculus of variations and optimization techniques to produce optimal and sub‐optimal drug regimes. This paper uses the Gompertz equation as a model of tumour growth and attempts to minimize final tumour size in the presence of drug constraints. The optimization technique is novel in that it uses the genetic algorithm method to devise optimal drug regimes where individual regimes are encoded as ‘chromosomes’ and evolution is simulated in order to improve treatment strategies.

There exist several operators to search through permutation spaces that can benefit search and score algorithms when combined. This paper presents COMpetitive Mutating Agents (COMMA), an algorithm which uses geometric mutation operators to create a geometrically defined distribution of solutions. Sampling from the distribution generates solutions in a similar fashion as with Estimation of Distribution Algorithms (EDAs). COMMA is applied on classical permutation optimization benchmarks, namely the Quadratic Assignement and the Permutation Flowshop Scheduling Problems and its performance is compared with those of reference EDAs. Although COMMA does not require a model building step, results suggest that it is competitive with state-of-the-art EDAs. In addition, COMMA's underlying geometric-based sampling could be transposed to representations other than permutations.

Solving multi-objective problems usually results in a set of Perto-optimal solutions, or a Pareto front. Assessing the quality of these solutions, however, and comparing the performance of different multi-objective optimisers is still not very well understood. Current trends either model the outcome of the optimiser as a probability density function in the objective space, or defines an indicator that quantify the overall performance of the optimiser. Here an approach based on the concept of mutual information is proposed. The approach models the probability density function of the optimisers' output and use that to define an indicator, namely the amount of shared information among the compared Pareto fronts. The strength of the new approach is not only in better assessment of performance but also the interpretability of the results it provides.

Learning a good model structure is important to the efficient solving of problems by estimation of distribution algorithms. In this paper we present the results of a series of experiments, applying a structure learning algorithm for undirected probabilistic graphical models based on statistical dependency tests to three fitness functions with different selection operators, proportions and pressures. The number of spurious interactions found by the algorithm are measured and reported. Truncation selection, and its complement (selecting only low fitness solutions) prove quite robust, resulting in a similar number of spurious dependencies regardless of selection pressure. In contrast, tournament and fitness proportionate selection are strongly affected by the selection proportion and pressure.

D2MOPSO is a multi-objective particle swarm optimizer that incorporates the dominance concept with the decomposition approach. Whilst decomposition simplifies the multi-objective problem (MOP) by rewriting it as a set of aggregation problems, solving these problems simultaneously, within the PSO framework, might lead to premature convergence because of the leader selection process which uses the aggregation value as a criterion. Dominance plays a major role in building the leader's archive allowing the selected leaders to cover less dense regions avoiding local optima and resulting in a more diverse approximated Pareto front. Results from 10 standard MOPs show D2MOPSO outperforms two state-of-the-art decomposition based evolutionary methods.

The paper presents a novel approach to optimising cancer chemotherapy with respect to conflicting treatment objectives aimed at reducing the number of cancerous cells and at limiting the amounts of anti-cancer drugs used. The approach is based on the Particle Swarm Optimisaion (PSO) algorithm that decomposes a multi-objective optimisation problem into several scalar aggregation problems, thereby reducing its complexity and enabling an effective application of Computational Intelligence techniques. The novelty of the algorithm is in providing particles in the swarm with information from a set of defined neighbours and leaders that assists in finding versatile chemotherapeutic treatments.

In [1], we introduced Smart Multi-Objective Particle Swarm Optimisation using Decomposition (SDMOPSO). The method uses the decomposition approach proposed in Multi-Objective Evolutionary Algorithms based on Decomposition (MOEA/D), whereby a multi-objective problem (MOP) is represented as several scalar aggregation problems. The scalar aggregation problems are viewed as particles in a swarm; each particle assigns weights to every optimisation objective. The problem is solved then as a Multi-Objective Particle Swarm Optimisation (MOPSO), in which every particle uses information from a set of defined neighbours. This work customize SDMOSPO to cover binary problems and applies the proposed binary method on the channel selection problem for Brain-Computer Interfaces(BCI).

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by an evolutionary algorithm. This is of particular interest with expensive fitness functions where the cost of building the model is outweighed by the saving of using fewer function evaluations. In this paper we show how a Markov network model can be used as a surrogate fitness function in a genetic algorithm. We demonstrate this applied to a number of well-known benchmark functions and although the results are good in terms of function evaluations the model-building overhead requires a substantially more expensive fitness function to be worthwhile. We move on to describe a fitness function for feature selection in Case-Based Reasoning, which is considerably more expensive than the other benchmark functions we used. We show that for this problem using the surrogate offers a significant decrease in total run time compared to a GA using the true fitness function.

Cancer treatment by chemotherapy involves multiple applications of toxic drugs over a period of time. Optimising the schedule of these treatments can improve the outcome for the patient. A schedule of treatment and its effect on the tumour can be simulated by a mathematical growth model. However, when used in conjunction with a black-box optimisation algorithm such as an Evolutionary Algorithm (EA) to search for effective treatment schedules, the frequent use of the model can become computationally onerous. One approach to improve the efficiency of EAs is to use ‘fitness inheritance’, in which, for a proportion of candidate solutions, simple means are used to estimate the fitness, rather than use the computationally intensive model. We investigate two versions of fitness inheritance for the chemotherapy schedule optimisation problem, and demonstrate the significant improvement in efficiency that can be achieved. In particular, concerning the two main types of fitness inheritance (Averaged and Proportional), we find that the Averaged Inheritance strategy is highly effective in this case, and is strongly recommended for use in further investigations of chemotherapy optimisation using population-based search.

A novel Smart Multi-Objective Particle Swarm Optimisation method - SDMOPSO - is presented in the paper. The method uses the decomposition approach proposed in MOEA/D, whereby a multiobjective problem (MOP) is represented as several scalar aggregation problems. The scalar aggregation problems are viewed as particles in a swarm; each particle assigns weights to every optimisation objective. The problem is solved then as a Multi-Objective Particle Swarm Optimisation (MOPSO), in which every particle uses information from a set of defined neighbours. The paper also introduces a novel smart approach for sharing information between particles, whereby each particle calculates a new position in advance using its neighbourhood information and shares this new information with the swarm. The results of applying SDMOPSO on five standard MOPs show that SDMOPSO is highly competitive comparing with two state-of-the-art algorithms.

This paper discusses the effects of using directed intervention crossover approaches with Genetic Algorithms (GA) and demonstrates their application to scheduling of bio-control agents and cancer chemotherapy treatments. Unlike traditional approaches such as Single Point Crossover (SPC) or Uniform Crossover (UC), the directed intervention techniques actively choose the intervention level based on the fitness of the parents selected for crossover. This work shows that a fitness directed intervention crossover approach leads to significant improvements over SPC and UC when applied to the two different scheduling problems.

Selection is one of the defining characteristics of an evolutionary algorithm, yet inherent in the selection process is the loss of some information from a population. Poor solutions may provide information about how to bias the search toward good solutions. Many estimation of distribution algorithms (EDAs) use truncation selection which discards all solutions below a certain fitness, thus losing this information. Our previous work on distribution estimation using Markov networks (DEUM) has described an EDA which constructs a model of the fitness function; a unique feature of this approach is that because selective pressure is built into the model itself selection becomes optional. This paper outlines a series of experiments which make use of this property to examine the effects of selection on the population. We look at the impact of selecting only highly fit solutions, only poor solutions, selecting a mixture of highly fit and poor solutions, and abandoning selection altogether. We show that in some circumstances, particularly where some information about the problem is already known, selection of the fittest only is suboptimal.

In this paper we present an application of an Estimation of Distribution Algorithm (EDA) that uses a Markov network probabilistic model. The application is to the problem of bio-control in mushroom farming, a domain which admits bang-bang-control solutions. The problem is multi-objective and uses a weighted fitness function. Previous work on this problem has applied genetic algorithms (GA) with directed intervention crossover schemes aimed at effective biocontrol at an efficient level of intervention. Here we compare these approaches with the EDA Distribution Estimation Using Markov networks (DEUMd). DEUMd constructs a probabilistic model using Markov networks. Our experiments compare the quality of solutions produced by DEUMd with the GA approaches and also reveal interesting differences in the search dynamics that have implications for algorithm design.

This paper describes two directed intervention crossover approaches that are applied to the problem of deriving optimal cancer chemotherapy treatment schedules. Unlike traditional uniform crossover (UC), both the calculated expanding bin (CalEB) method and targeted intervention with stochastic selection (TInSSel) approaches actively choose an intervention level and spread based on the fitness of the parents selected for crossover. Our results indicate that these approaches lead to significant improvements over UC when applied to cancer chemotherapy scheduling.

Bayesian Networks are today used in various fields and domains due to their inherent ability to deal with uncertainty. Learning Bayesian Networks, however is an NP-Hard task [7]. The super exponential growth of the number of possible networks given the number of factors in the studied problem domain has meant that more often, approximate and heuristic rather than exact methods are used. In this paper, a novel genetic algorithm approach for reducing the complexity of Bayesian network structure discovery is presented. We propose a method that uses chain structures as a model for Bayesian networks that can be constructed from given node orderings. The chain model is used to evolve a small number of orderings which are then injected into a greedy search phase which searches for an optimal structure. We present a series of experiments that show a significant reduction can be made in computational cost although with some penalty in success rate.

Markov Networks (also known as Markov Random Fields) have been proposed as a new approach to probabilistic modelling in Estimation of Distribution Algorithms (EDAs). An EDA employing this approach called Distribution Estimation Using Markov Networks (DEUM) has been proposed and shown to work well on a variety of problems, using a unique fitness modelling approach. Previously DEUM has only been demonstrated on univariate and bivariate complexity problems. Here we show that it can be extended to a difficult multivariate problem and is capable of accurately modelling a fitness function and locating an optimum with a very small number of function evaluations.

This paper presents a medical problem solving environment (PSE) designed for modelling, simulation, and optimisation of clinical cancer chemotherapy. In order to find optimal chemotherapeutic treatments, two population-based evolutionary algorithms -- Genetic Algorithms and Particle Swarm Optimisation -- have been applied, which can use web services and grid computing to evaluate potential solutions in a distributed and customizable manner. The versatility and robustness of these algorithms make the suggested problem solving environment scalable and adaptable to other problem domains.

This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUMd). DEUMd belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUMd uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUMd in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUMd on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.

Cancer chemotherapy is a complex treatment mode that requires balancing the benefits of treating tumours using anti-cancer drugs with the adverse toxic side-effects caused by these drugs. Some methods of computational optimisation, Genetic Algorithms in particular, have proven to be useful in helping to strike the right balance. The purpose of this paper is to study how an alternative optimisation method – Particle Swarm Optimisation – can be used to facilitate finding optimal chemotherapeutic treatments, and to compare its performance with that of Genetic Algorithms.

This paper presents a practical methodology of improving the efficiency of genetic algorithms through tuning the factors significantly affecting GA performance. This methodology is based on the methods of statistical inference and has been successfully applied to both binary-and integer-encoded genetic algorithms that search for good chemotherapeutic schedules

We explore the application of an Estimation of Distribution Algorithm which uses a Markov Network to the problem of bio-control in mushroom farming. This falls into the category of “bang-bang control” problems and was previously used as an application for genetic algorithms with modified crossover operators. The EDA yields a small improvement in the solutions that are evolved. Moreover, the probabilistic models constructed closely match identifiable features in the underlying dynamics of the problem. We conclude that this is a useful by-product of the probabilistic modelling which can be further exploited. probabilistic model learned by DEUM. We will describe how a clear relationship can be drawn between probabilistic model and the underlying shape of the problem.

Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. A number of different probabilistic algorithms have been applied to it with varying success. In this paper we expand on this by applying two estimation of distribution algorithms to the problem. One is UMDA, which uses a univariate probabilistic model similar to previously applied EDAs. The other is hBOA, the first EDA using a multivariate probabilistic model to be applied to the chemotherapy problem. While instinct would lead us to predict that the more sophisticated algorithm would yield better performance on a complex problem like this, we show that it is outperformed by the algorithms using the simpler univariate model. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem which are unnecessary for its solution., Comment: Tech report, originally published at Missouri EDA Lab, in support of extended abstract (poster) with same title presented at GECCO 2008

Markov random field (MRF) modelling techniques have been recently proposed as a novel approach to probabilistic modelling for estimation of distribution algorithms (EDAs). An EDA using this technique was called distribution estimation using Markov random fields (DEUM). DEUM was later extended to DEUMd. DEUM and DEUMd use a univariate model of probability distribution, and have been shown to perform better than other univariate EDAs for a range of optimization problems. This paper extends DEUM to use a bivariate model and applies it to the Ising spin glass problems. We propose two variants of DEUM that use different sampling techniques. Our experimental result show a noticeable gain in performance.