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.

Feature Extraction of Localized Scattering Centers Using the Modified TLS-Prony Algorithm and Its Applications

This paper presents an all-parametric model of radar target in optic region, in which the localized scattering center's frequency and aspect angle dependent scattering level, distance and azimuth locations are modeled as the feature vectors. And the traditional TLS-Prony algorithm is modified to extract these feature vectors. The analysis of Cramer-Rao bound shows that the modified algorithm not only improves the restriction of high signal-to-noise ratio(SNR)threshold of traditional TLS-Prony algorithm, but also is suitable to the extraction of big damped coefficients and high-resolution estimation of near separation poles. Finally, an illustrative example is presented to verify its practicability in the applications. The experimental results show that the method developed can not only recognize two airplane-like targets with similar shape at low SNR, but also compress the original radar data with high fidelity.

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.

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.

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 estimation algorithm for torpedo tracking in undersea environment

A novel estimation algorithm is introduced to handle the popular undersea problem called torpedo tracking with angle-only measurements with a better approach compared to the existing filters. The new algorithm produces a better estimate from the outputs produced by the traditional nonlinear approaches with the assistance of simple noise minimizers like maximum likelihood filter or any other algorithm which belongs to their family. The introduced method is extended to the higher version in two ways. The first approach extracts a better estimate and covariance by enhancing the count of the intermediate filters, while the second approach accepts more inputs so as to attain improved performance without enhancement of the intermediate filter count. The ideal choice of the placement of towed array sensors to improve the performance of the proposed method further is suggested as the one where the line of sight and the towed array are perpendicular. The results could get even better by moving the ownship in the direction of reducing range. All the results are verified in the MATLAB environment.

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.

An Improved Underwater Acoustic Network Localization Algorithm

Underwater sensor network can achieve the unmanned environmental monitoring and military monitoring missions.Underwater acoustic sensor node cannot rely on the GPS to position itself,and the traditional indirect positioning methods used in Ad Hoc networks are not fully applicable to the localization of underwater acoustic sensor networks.In this paper,we introduce an improved underwater acoustic network localization algorithm.The algorithm processes the raw data before localization calculation to enhance the tolerance of random noise.We reduce the redundancy of the calculation results by using a more accurate basic algorithm and an adjusted calculation strategy.The improved algorithm is more suitable for the underwater acoustic sensor network positioning.

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.

Algorithm of heating temperature for Chongqing's winter greenhouses

Internal temperature is crucial to plant growth in the greenhouse. We investigated the patterns of constructing and managing greenhouses in Chongqing, and developed an algorithm of heating temperature for closed winter plastic greenhouses under the conditions of no man-made illumination, no ventilation and hot wind machine as the heating equipment, which are the most adopted pattern of greenhouses in Chongqing area. The algorithm includes two functions of temperature outside the greenhouse, which calculate the values of the warming estimation coefficient (WEC) and the gap between temperatures inside and outside the greenhouse with the measured data of outside temperature, and then give the value of internal temperature; the heat rating of heating facilities required by a greenhouse can be determined by this algorithm with given values of floor area and internal temperature, measured outside temperature and calculated WEC. Verification of the algorithm demonstrates a desirable accuracy of estimation. Algorithms of computing heating temperature for greenhouses of different constructing and managing patterns and in different geographic conditions can also be derived in a similar way. This research presents a paradigm for developing a feasible method to fit out greenhouses with appropriate heating facilities, aiming at energy efficient and cost efficient production.

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.

Relative efficiency appraisal of discrete choice modeling algorithms using small-scale maximum likelihood estimator through empirically tailored computing environment

Discrete choice models are widely used in multiple sectors such as transportation, health, energy, and marketing, etc., where the model estimation is usually carried out by using commercial software. Nonetheless, tailored computer codes offer modellers greater flexibility and control of unique modelling situation. Aligned with empirically tailored computing environment, this research discusses the relative performance of six different algorithms of a discrete choice model using three key performance measures： convergence time, number of iterations, and iteration time. The computer codes are developed by using Visual Basic Application （VBA）. Maximum likelihood function （MLF） is formulated and the mathematical relationships of gradient and Hessian matrix are analytically derived to carry out the estimation process. The estimated parameter values clearly suggest that convergence criterion and initial guessing of parameters are the two critical factors in determining the overall estimation performance of a custom-built discrete choice model.

A Self-Position Estimation Algorithm for Multiple Mobile Robots Using Two Omnidirectional Cameras and an Accelerometer

This paper proposes a self-position estimate algorithm for the multiple mobile robots; each robot uses two omnidirectional cameras and an accelerometer. In recent years, the Great East Japan Earthquake and large-scale disasters have occurred frequently in Japan. From this, development of the searching robot which supports the rescue team to perform a relief activity at a large-scale disaster is indispensable. Then, this research has developed the searching robot group system with two or more mobile robots. In this research, the searching robot equips with two omnidirectional cameras and an accelerometer. In order to perform distance measurement using two omnidirectional cameras, each parameter of an omnidirectional camera and the position and posture between two omnidirectional cameras have to be calibrated in advance. If there are few mobile robots, the calibration time of each omnidirectional camera does not pose a problem. However, if the calibration is separately performed when using two or more robots in a disaster site, etc., it will take huge calibration time. Then, this paper proposed the algorithm which estimates a mobile robot＇s position and the parameter of the position and posture between two omnidirectional cameras simultaneously. The algorithm proposed in this paper extended Nonlinear Transformation （NLT） Method. This paper conducted the simulation experiment to check the validity of the proposed algorithm. In some simulation experiments, one mobile robot moves and observes the circumference of another mobile robot which has stopped at a certain place. This paper verified whether the mobile robot can estimate position using the measurement value when the number of observation times becomes 10 times in n/18 of observation intervals. The result of the simulation shows the effectiveness of the 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.

Failure analysis on China power grid based on power law

This paper is concerned with the mechanism of blackouts in China power system from the viewpoint of self-organized criticality. By using two estimation algorithms of scaled window variance （SWV） and rescaled rangestatistics （R/S）, this paper studies the blackout data in China power system during 1988-1997. The result of analysis shows that the blackout data of 1994-1997 coincides well with the autocorrelation. Furthermore, it is found that the function of blackout probability vs. blackout size exhibits power law distribution.

Joint Analysis Method for Major Genes Controlling Multiple Correlated Quantitative Traits

Based on the major gene and polygene mixed inheritance model for multiple correlated quantitative traits, the authors proposed a new joint segregation analysis method of major gene controlling multiple correlated quantitative traits, which include major gene detection and its effect and variation estimation. The effect and variation of major gene are estimated by the maximum likelihood method implemented via expectation-maximization （EM） algorithm. Major gene is tested with the likelihood ratio （LR） test statistic. Extensive simulation studies showed that joint analysis not only increases the statistical power of major gene detection but also improves the precision and accuracy of major gene effect estimates. An example of the plant height and the number of tiller of F2 population in rice cross Duonieai x Zhonghua 11 was used in the illustration. The results indicated that the genetic difference of these two traits in this cross refers to only one pleiotropic major gene. The additive effect and dominance effect of the major gene are estimated as -21.3 and 40.6 cm on plant height, and 22.7 and -25.3 on number of tiller, respectively. The major gene shows overdominance for plant height and close to complete dominance for number of tillers.

Nonparametric VSS-APA based on precise background noise power estimate

The adaptive algorithm used for echo cancellation(EC) system needs to provide 1) low misadjustment and 2) high convergence rate. The affine projection algorithm(APA) is a better alternative than normalized least mean square(NLMS) algorithm in EC applications where the input signal is highly correlated. Since the APA with a constant step-size has to make compromise between the performance criteria 1) and 2), a variable step-size APA(VSS-APA) provides a more reliable solution. A nonparametric VSS-APA(NPVSS-APA) is proposed by recovering the background noise within the error signal instead of cancelling the a posteriori errors. The most problematic term of its variable step-size formula is the value of background noise power(BNP). The power difference between the desired signal and output signal, which equals the power of error signal statistically, has been considered the BNP estimate in a rough manner. Considering that the error signal consists of background noise and misalignment noise, a precise BNP estimate is achieved by multiplying the rough estimate with a corrective factor. After the analysis on the power ratio of misalignment noise to background noise of APA, the corrective factor is formulated depending on the projection order and the latest value of variable step-size. The new algorithm which does not require any a priori knowledge of EC environment has the advantage of easier controllability in practical application. The simulation results in the EC context indicate the accuracy of the proposed BNP estimate and the more effective behavior of the proposed algorithm compared with other versions of APA class.

Semantic Region Estimation of Assistant Robot for the Elderly Long-Term Operation in Indoor Environment

In this work, in order to improve spatial recognition abilities for the long-term operation tasks of the assistant robot for the elderly, a novel approach of semantic region estimation is proposed. We define a novel graphbased semantic region descriptions, which are estimated in a dynamically fashion. We propose a two-level update algorithm, namely, Symbols update level and Regions update level. The algorithm firstly adopts particle filter to update weights of the symbols, and then use the Viterbi algorithm to estimate the region the robot stays in based on those weights, optimally. Experimental results demonstrate that our proposed approach can solve problems of the long-term operation and kidnapped robot problem.

Motion Estimation Based on Global and Local Compensability Analysis

This paper reports our study of a novel motion estimation algorithm based on global and local compensability analysis. The spatial correlation of motion field is used to reduce the burden of estimation computation and extra bit rate for motion vectors. Experimental results show that this algorithm is more efficient than the conventional methods, especially for temporal activity regions.