The development of cloud computing drives the research on parallel processing. One of the important problems in parallel processing is to minimize the makespan of the tasks with precedence constraints on multiprocesso...
详细信息
ISBN:
(纸本)9781509067817
The development of cloud computing drives the research on parallel processing. One of the important problems in parallel processing is to minimize the makespan of the tasks with precedence constraints on multiprocessors scheduling. In this paper, the property of the t-level (top-level) is analyzed, and a t-level (top level) driven search is proposed to enhance the exploitation ability of the efficient estimation of distributed algorithm (eEDA), which was developed for solving the precedence constrained scheduling problem. Numerical tests and comparisons are carried out. The results demonstrate that the t-level driven search is able to improve the optimization capacity of the eEDA under heterogeneous multiprocessor situation. Moreover, it is also shown that the eEDA with the t-level driven search on homogeneous computing systems is effective.
Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decis...
详细信息
Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decision variable space to construct probabilistic models from promising solutions. The probabilistic model used in EDA captures statistics of decision variables and their interdependencies with the optimization problem. Moreover, the aggregation of local search methods can notably improve the results of multi-objective evolutionary algorithms. Therefore, these hybrid approaches have been jointly applied to multi-objective problems. In this work, a Hybrid Multi-objective Bayesian estimation of distribution algorithm (HMOBEDA), which is based on a Bayesian network, is proposed to multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and configuration parameters of an embedded local search (LS). We tested different versions of HMOBEDA using instances of the multi-objective knapsack problem for two to five and eight objectives. HMOBEDA is also compared with five cutting edge evolutionary algorithms (including a modified version of NSGA-III, for combinatorial optimization) applied to the same knapsack instances, as well to a set of MNK-landscape instances for two, three, five and eight objectives. An analysis of the resulting Bayesian network structures and parameters has also been carried to evaluate the approximated Pareto front from a probabilistic point of view, and also to evaluate how the interactions among variables, objectives and local search parameters are captured by the Bayesian networks. Results show that HMOBEDA outperforms the other approaches. It not only provides the best values for hypervolume, capacity and inverted generational distance indicators in most of the experiments, but it also presents a high diversity solution set close to the estimated Pareto front.
Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood sea...
详细信息
Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP.
As the research interest in distributed scheduling is growing, distributed permutation flowshop scheduling problems (DPFSPs) have recently attracted an increasing attention. This paper presents a fuzzy logic-based hyb...
详细信息
As the research interest in distributed scheduling is growing, distributed permutation flowshop scheduling problems (DPFSPs) have recently attracted an increasing attention. This paper presents a fuzzy logic-based hybrid estimation of distribution algorithm (FL-HEDA) to address DPFSPs under machine breakdown with makespan criterion. In order to explore more promising search space, FL-HEDA hybridises the probabilistic model of estimation of distribution algorithm with crossover and mutation operators of genetic algorithm to produce new offspring. In the FL-HEDA, a novel fuzzy logic-based adaptive evolution strategy (FL-AES) is adopted to preserve the population diversity by dynamically adjusting the ratio of offspring generated by the probabilistic model. Moreover, a discrete-event simulator that models the production process under machine breakdown is applied to evaluate expected makespan of offspring individuals. The simulation results show the effectiveness of FL-HEDA in solving DPFSPs under machine breakdown.
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 pro...
详细信息
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 ***,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 ***,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle ***,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the ***,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.
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 ...
详细信息
ISBN:
(纸本)9783319458236;9783319458229
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.
The estimation of distribution algorithm is widely used to solve global optimization problems in recent years. The basic idea is using machine learning methods to extract relevant features of the search space among th...
详细信息
ISBN:
(纸本)9781509006229
The estimation of distribution algorithm is widely used to solve global optimization problems in recent years. The basic idea is using machine learning methods to extract relevant features of the search space among the selected individuals and to construct a probabilistic model for sampling new solutions. As we know, EDAs mainly focus on the global distribution information of population and are lack of solution location information. In this paper, we extend our previous work to propose a new EDA guided by the mean shift method, which is originally proposed as a density estimation method and is used as a local search method in this paper. In the new approach, at first a set of candidate solutions are generated by EDA. Then the mean shift method is used to refine some good parent solutions. Finally the sampled candidate solutions and the refined solutions are combined to form the offspring solutions. By this way, the global distribution information and the solution location information are used in offspring reproduction. We apply the new approach to a set of test instances and the experiment results indicate that the new algorithm can obtain good performance in most functions with a faster convergence rate.
This paper proposes an innovative hybrid estimation of distribution algorithm (HEDA) for the no-wait flow-shop scheduling problem (NFSSP) with sequence dependent setup times (SDSTs) and release dates (RDs) to minimize...
详细信息
ISBN:
(纸本)9783319422916;9783319422909
This paper proposes an innovative hybrid estimation of distribution algorithm (HEDA) for the no-wait flow-shop scheduling problem (NFSSP) with sequence dependent setup times (SDSTs) and release dates (RDs) to minimize the total completion time (TCT), which has been proved to be typically NP-hard combinatorial optimization problem with strong engineering background. Firstly, a speed-up evaluation method is developed according to the property of NFSSP with SDSTs and RDs. Secondly, the genetic information both order of jobs and the promising blocks of jobs are concerned to generate the guided probabilistic model. Thirdly, after the HEDA based global exploration, a problem dependent local search is developed to emphasize exploitation. Due to the reasonable balance between HEDA based global search and problem-dependent local search as well as the comprehensive utilization of the speed-up evaluation, TCT-NFSSP with SDSTs and RDs can be solved effectively and efficiently. Computational results and comparisons demonstrate the superiority of HEDA in terms of searching quality, robustness, and efficiency.
A multi-carpooling model is proposed for the multi-vehicle carpooling problem in distributed parallel computing environment. A two-stage stochastic optimization of the estimation of distribution algorithm solves the o...
详细信息
ISBN:
(纸本)9781509016983
A multi-carpooling model is proposed for the multi-vehicle carpooling problem in distributed parallel computing environment. A two-stage stochastic optimization of the estimation of distribution algorithm solves the optimum of the multi-carpooling problem with a carpooling probabilistic matrix. A ridable matrix initiates the carpooling probabilistic matrix, and the carpooling probabilistic matrix continues updating during the optimization. The carpooling model mines efficient and compromised ridesharing routes for shared riders by the optimization iterations. Experimental results indicate that the carpooling model has the characteristics of effective and efficient traffic including shorter waiting time, more passenger load, and less average riding distance.
A regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA) has been proposed for continuous multiobjective optimization problems. Generating promising solutions to approximate the populatio...
详细信息
ISBN:
(纸本)9781509006229
A regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA) has been proposed for continuous multiobjective optimization problems. Generating promising solutions to approximate the population is significant to RM-MEDA. In the reproduction of RM-MEDA, it adopts a Latin square design strategy to sample points in the latent space that is extended to cover the whole Pareto set. However, the setting of the extension scale is problem-dependent to some extent. To circumvent this issue, we propose a differential evolution based sampling (DES) scheme for RM-MEDA. DES mutates the projections of the parent solutions in the latent space to generate promising candidate offspring solutions. The empirical experiment results have shown the significant advantages of the DES scheme comparing to the Latin square design.
暂无评论