Novel operating theatre scheduling method based on estimation of distribution algorithm

In order to improve the efficiency of operating rooms,reduce the costs for hospitals and improve the level of service qualities, a scheduling method was developed based on an estimation of distribution algorithm（ EDA）. First, a scheduling problem domain is described. Based on assignment constraints and resource capacity constraints, the mathematical programming models are set up with an objective function to minimize the system makespan. On the basis of the descriptions mentioned above, a solution policy of generating feasible scheduling solutions is established. Combined with the specific constraints of operating theatres, the EDA-based algorithm is put forward to solve scheduling problems. Finally, simulation experiments are designed to evaluate the scheduling method. The orthogonal table is chosen to determine the parameters in the proposed method. Then the genetic algorithm and the particle swarm optimization algorithm are chosen for comparison with the EDA-based algorithm, and the results indicate that the proposed method can decrease the makespan of the surgical system regardless of the size of operations. Moreover, the computation time of the EDA-based algorithm is only approximately 5 s when solving the large scale problems, which means that the proposed algorithm is suitable for carrying out an on-line scheduling optimization of the patients.

Robust Airfoil Optimization with Multi-objective Estimation of Distribution Algorithm

A transonic airfoil designed by means of classical point-optimization may result in its dramatically inferior performance under off-design conditions. To overcome this shortcoming, robust design is proposed to find out the optimal profile of an airfoil to maintain its performance in an uncertain environment. The robust airfoil optimization is aimed to minimize mean values and variances of drag coefficients while satisfying the lift and thickness constraints over a range of Mach numbers. A multi-objective estimation of distribution algorithm is applied to the robust airfoil optimization on the base of the RAE2822 benchmark airfoil. The shape of the airfoil is obtained through superposing ten Hick-Henne shape functions upon the benchmark airfoil. A set of design points is selected according to a uniform design table for aerodynamic evaluation. A Kriging model of drag coefficient is constructed with those points to reduce computing costs. Over the Mach range from 0.7 to 0.8, the airfoil generated by the robust optimization has a configuration characterized by supercritical airfoil with low drag coefficients. The small fluctuation in its drag coefficients means that the performance of the robust airfoil is insensitive to variation of Mach number.

Combinations of Estimation of Distribution Algorithms and Other Techniques

This paper summaries our recent work on combining estimation of distribution algorithms （EDA） and other techniques for solving hard search and optimization problems： a） guided mutation, an offspring generator in which the ideas from EDAs and genetic algorithms are combined together, we have shown that an evolutionary algorithm with guided mutation outperforms the best GA for the maximum clique problem, b） evolutionary algorithms refining a heuristic, we advocate a strategy for solving a hard optimization problem with complicated data structure, and c） combination of two different local search techniques and EDA for numerical global optimization problems, its basic idea is that not all the new generated points are needed to be improved by an expensive local search.

Archimedean copula estimation of distribution algorithm based on artificial bee colony algorithm

The artificial bee colony （ABC） algorithm is a com- petitive stochastic population-based optimization algorithm. How- ever, the ABC algorithm does not use the social information and lacks the knowledge of the problem structure, which leads to in- sufficiency in both convergent speed and searching precision. Archimedean copula estimation of distribution algorithm （ACEDA） is a relatively simple, time-economic and multivariate correlated EDA. This paper proposes a novel hybrid algorithm based on the ABC algorithm and ACEDA called Archimedean copula estima- tion of distribution based on the artificial bee colony （ACABC） algorithm. The hybrid algorithm utilizes ACEDA to estimate the distribution model and then uses the information to help artificial bees to search more efficiently in the search space. Six bench- mark functions are introduced to assess the performance of the ACABC algorithm on numerical function optimization. Experimen- tal results show that the ACABC algorithm converges much faster with greater precision compared with the ABC algorithm, ACEDA and the global best （gbest）-guided ABC （GABC） algorithm in most of the experiments.

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

The multi-compartment electric vehicle routing problem(EVRP)with soft time window and multiple charging types(MCEVRP-STW&MCT)is studied,in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process,are employed.A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost,distribution cost,time window penalty cost and charging service cost.To solve the problem,an estimation of the distribution algorithm based on Lévy flight(EDA-LF)is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum.Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm.In addition,when comparing with existing algorithms,the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances.Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.

A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine

The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.

Gaussian process assisted coevolutionary estimation of distribution algorithm for computationally expensive problems

In order to reduce the computation of complex problems, a new surrogate-assisted estimation of distribution algorithm with Gaussian process was proposed. Coevolution was used in dual populations which evolved in parallel. The search space was projected into multiple subspaces and searched by sub-populations. Also, the whole space was exploited by the other population which exchanges information with the sub-populations. In order to make the evolutionary course efficient, multivariate Gaussian model and Gaussian mixture model were used in both populations separately to estimate the distribution of individuals and reproduce new generations. For the surrogate model, Gaussian process was combined with the algorithm which predicted variance of the predictions. The results on six benchmark functions show that the new algorithm performs better than other surrogate-model based algorithms and the computation complexity is only 10% of the original estimation of distribution algorithm.

An effective estimation of distribution algorithm for parallel litho machine scheduling with reticle constraints

In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.

Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

This paper presents a Markov random field （MRP） 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.

Histogram-Based Estimation of Distribution Algorithm:A Competent Method for Continuous Optimization

Designing efficient estimation of distribution algorithms for optimizing complex continuous problems is still a challenging task. This paper utilizes histogram probabilistic model to describe the distribution of population and to generate promising solutions. The advantage of histogram model, its intrinsic multimodality, makes it proper to describe the solution distribution of complex and multimodal continuous problems. To make histogram model more efficiently explore and exploit the search space, several strategies are brought into the algorithms： the surrounding effect reduces the population size in estimating the model with a certain number of the bins and the shrinking strategy guarantees the accuracy of optimal solutions. Furthermore, this paper shows that histogram-based EDA （Estimation of distribution algorithm） can give comparable or even much better performance than those predominant EDAs based on Gaussian models.

Intelligent Scheduling Controller Design for Networked Control Systems Based on Estimation of Distribution Algorithm

The use of communication networks in control loops has gained increasing attention in recent years due to its advantages and flexible applications. The network quality-of-service （QoS） in those socalled networked control systems always fluctuates due to changes of the traffic load and available network resources, This paper presents an intelligent scheduling controller design approach for a class of NCSs to handle network QoS variations, The sampling period and control parameters in the controller are simultaneously scheduled to compensate for the network QoS variations. The estimation of distribution algorithm is used to optimize the sampling period and control parameters for better performance. Compared with existing networked control methods, the controller has better ability to compensate for the network QoS variations and to balance network loads. Simulation results show that the plant setting time with the intelligent scheduling controller is reduced by about 64.0% for the medium network load and 49.1% for high network load and demonstrate the effectiveness of the proposed approaches.

Estimation of distribution algorithm enhanced particle swarm optimization for water distribution network optimization

The optimization of a water distribution network （WDN） is a highly nonlinear, multi-modal, and constrained combinatorial problem. Particle swarm opti- mization （PSO） has been shown to be a fast converging algorithm for WDN optimization. An improved estimation of distribution algorithm （EDA） using historic best positions to construct a sample space is hybridized with PSO both in sequential and in parallel to improve population diversity control and avoid premature conver- gence. Two water distribution network benchmark exam- ples from the literature are adopted to evaluate the performance of the proposed hybrid algorithms. The experimental results indicate that the proposed algorithms achieved the literature record minimum （6.081 MS） for the small size Hanoi network. For the large size Balerma network, the parallel hybrid achieved a slightly lower minimum （1.921M） than the current literature reported best minimum （1.923MC）. The average number of evaluations needed to achieve the minimum is one order smaller than most existing algorithms. With a fixed, small number of evaluations, the sequential hybrid outperforms the parallel hybrid showing its capability for fast convergence. The fitness and diversity of the populations were tracked for the proposed algorithms. The track record suggests that constructing an EDA sample space with historic best positions can improve diversity control significantly. Parallel hybridization also helps to improve diversity control yet its effect is relatively less significant.

Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation

The ability to assess the reliability of safety-critical systems is one of the most crucial requirements in the design of modern safety-critical systems where even a minor failure can result in loss of life or irreparable damage to the environment.Model checking is an automatic technique that verifies or refutes system properties by exploring all reachable states(state space)of a model.In large and complex systems,it is probable that the state space explosion problem occurs.In exploring the state space of systems modeled by graph transformations,the rule applied on the current state specifies the rule that can perform on the next state.In other words,the allowed rule on the current state depends only on the applied rule on the previous state,not the ones on earlier states.This fact motivates us to use a Markov chain(MC)to capture this type of dependencies and applies the Estimation of Distribution Algorithm(EDA)to improve the quality of the MC.EDA is an evolutionary algorithm directing the search for the optimal solution by learning and sampling probabilistic models through the best individuals of a population at each generation.To show the effectiveness of the proposed approach,we implement it in GROOVE,an open source toolset for designing and model checking graph transformation systems.Experimental results confirm that the proposed approach has a high speed and accuracy in comparison with the existing meta-heuristic and evolutionary techniques in safety analysis of systems specified formally through graph transformations.

Large-Scale Estimation of Distribution Algorithms with Adaptive Heavy Tailed Random Pro jection Ensembles

We present new variants of Estimation of Distribution Algorithms (EDA) for large-scale continuous optimisation that extend and enhance a recently proposed random projection (RP) ensemble based approach. The main novelty here is to depart from the theory of RPs that require (sub-)Gaussian random matrices for norm-preservation, and instead for the purposes of high-dimensional search we propose to employ random matrices with independent and identically distributed entries drawn from a t-distribution. We analytically show that the implicitly resulting high-dimensional covariance of the search distribution is enlarged as a result. Moreover, the extent of this enlargement is controlled by a single parameter, the degree of freedom. For this reason, in the context of optimisation, such heavy tailed random matrices turn out to be preferable over the previously employed (sub-)Gaussians. Based on this observation, we then propose novel covariance adaptation schemes that are able to adapt the degree of freedom parameter during the search, and give rise to a flexible approach to balance exploration versus exploitation. We perform a thorough experimental study on high-dimensional benchmark functions, and provide statistical analyses that demonstrate the state-of-the-art performance of our approach when compared with existing alternatives in problems with 1000 search variables.

Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks——A Case Study for the Optimal Ordering of Tables

Parameter setting for evolutionary algorithms is still an important issue in evolutionary computation. There are two main approaches to parameter setting： parameter tuning and parameter control. In this paper, we introduce self-adaptive parameter control of a genetic algorithm based on Bayesian network learning and simulation. The nodes of this Bayesian network are genetic algorithm parameters to be controlled. Its structure captures probabilistie conditional （in）dependence relationships between the parameters. They are learned from the best individuals, i.e., the best configurations of the genetic algorithm. Individuals are evaluated by running the genetic algorithm for the respective parameter configuration. Since all these runs are time-consuming tasks, each genetic algorithm uses a small-sized population and is stopped before convergence. In this way promising individuals should not be lost. Experiments with an optimal search problem for simultaneous row and column orderings yield the same optima as state-of-the-art methods but with a sharp reduction in computational time. Moreover, our approach can cope with as yet unsolved high-dimensional problems.

Duple-EDA and sample density balancing

In this paper, a new method is proposed to overcome the problem of local optima traps in a class of evolutionary algorithms, called estimation of distribution algorithms （EDAs）, in real-valued function optimization. The Duple-EDA framework is proposed in which not only the current best solutions but also the search history are modeled, so that long-term feedback can be taken into account. Sample Density Balancing （SDB） is proposed under the framework to alleviate the drift phenomenon in EDA. A selection scheme based on Pareto ranking considering both the fitness and the historical sample density is adopted, which prevents the algorithm from repeatedly sampling in a small region and directs it to explore potentially optimal regions, thus helps it avoid being stuck into local optima. An MBOA （mixed Bayesian optimization algorithm） version of the framework is implemented and tested on several benchmark problems. Experimental results show that the proposed method outperforms a standard niching method in these benchmark problems.

Hybrid optimization for charge planning problem in twin strands continuous casting production

Charge planning is one of batching problems for steelmaking and continuous casting production,and its optimization will be conducive to subsequent cast planning.Charge planning problem in the twin strands continuous casting production was studied,where casting width of the odd strand might be different from that of the even strand.Considering the different widths in the twin strands,the resulting counterweights and the constraints of steelmaking and continuous casting,a multiobjective optimization model was established to minimize the number of charges,the number of scale pairs,the surplus and the upgrading costs of steel grades.Furthermore,a hybrid optimization algorithm combined with heuristic and mutation-based estimation of distribution algorithm was proposed to solve the model.Experiments were conducted on several groups of test data collected from practical production orders of Baosteel.The computational results demonstrate that the proposed algorithm can generate better solutions than the manual method.The proposed model and algorithm proved to be effective and practical.

Unsupervised Dynamic Fuzzy Cognitive Map

Fuzzy Cognitive Map （FCM） is an inference network, which uses cyclic digraphs for knowledge representation and reasoning. Along with the extensive applications of FCMs, there are some limitations that emerge due to the deficiencies associated with FCM itself. In order to eliminate these deficiencies, we propose an unsupervised dynamic fuzzy cognitive map using behaviors and nonlinear relationships. In this model, we introduce dynamic weights and trend-effects to make the model more reasonable. Data credibility is also considered while establishing a machine learning model. Subsequently, we develop an optimized Estimation of Distribution Algorithm （EDA） for weight learning. Experimental results show the practicability of the dynamic FCM model. In comparison to the other existing algorithms, the proposed algorithm has better performance in terms of convergence and stability.