Comprehensive quality-aware automated semantic web service composition is an NP-hard problem, where service composition workflows are unknown, and comprehensive quality, i.e., Quality of services (QoS) and Quality of semantic matchmaking (QoSM) are simultaneously optimized. The objective of this problem is to find a solution with optimized or near-optimized overall QoS and QoSM within polynomial time over a service request. In this paper, we proposed novel memetic EDA-based approaches to tackle this problem. The proposed method investigates the effectiveness of several neighborhood structures of composite services by proposing domain-dependent local search operators. Apart from that, a joint strategy of the local search procedure is proposed to integrate with a modified EDA to reduce the overall computation time of our memetic approach. To better demonstrate the effectiveness and scalability of our approach, we create a more challenging, augmented version of the service composition benchmark based on WSC-08 bansal2008wsc and WSC-09 kona2009wsc . Experimental results on this benchmark show that one of our proposed memetic EDA-based approach (i.e., MEEDA-LOP) significantly outperforms existing state-of-the-art algorithms.
Recently, EDA has been used as a technique to tackle permutation-based optimization problems @cite_9 . In particular, a distribution model is learned iteratively for each population. Subsequently, new offsprings are generated based on the learned model. Moreover, domain-dependent local search operators are often introduced to enhance the performances of EDA. For example, a probability matrix that is related to the job priority permutation of a solution is learned in EDA-based flow-shop scheduling problem, and different job-based local search operators were proposed to enhance the exploitation ability of EDA @cite_4 . An Edge Histogram Matrix is applied to uncertain capacitated arc routing problems and is leaned from solutions represented by a set of routes @cite_30 . To make local improvements, different move operators, such as single insertion and swap, are also proposed.
@cite_30 @cite_9 @cite_4
2037166173 2088303535
In this paper, an estimation of distribution algorithm (EDA)-based memetic algorithm (MA) is proposed for solving the distributed assembly permutation flow-shop scheduling problem (DAPFSP) with the objective to minimize the maximum completion time. A novel bi-vector-based method is proposed to represent a solution for the DAPFSP. In the searching phase of the EDA-based MA (EDAMA), the EDA-based exploration and the local-search-based exploitation are incorporated within the MA framework. For the EDA-based exploration phase, a probability model is built to describe the probability distribution of superior solutions. Besides, a novel selective-enhancing sampling mechanism is proposed for generating new solutions by sampling the probability model. For the local-search-based exploitation phase, the critical path of the DAPFSP is analyzed to avoid invalid searching operators. Based on the analysis, a critical-path-based local search strategy is proposed to further improve the potential solutions obtained in the EDA-based searching phase. Moreover, the effect of parameter setting is investigated based on the Taguchi method of design-of-experiment. Suitable parameter values are suggested for instances with different scales. Finally, numerical simulations based on 1710 benchmark instances are carried out. The experimental results and comparisons with existing algorithms show the effectiveness of the EDAMA in solving the DAPFSP. In addition, the best-known solutions of 181 instances are updated by the EDAMA. Estimation of distribution algorithms (EDAs) are a set of algorithms that belong to the field of Evolutionary Computation. Characterized by the use of probabilistic models to represent the solutions and the dependencies between the variables of the problem, these algorithms have been applied to a wide set of academic and real-world optimization problems, achieving competitive results in most scenarios. Nevertheless, there are some optimization problems, whose solutions can be naturally represented as permutations, for which EDAs have not been extensively developed. Although some work has been carried out in this direction, most of the approaches are adaptations of EDAs designed for problems based on integer or real domains, and only a few algorithms have been specifically designed to deal with permutation-based problems. In order to set the basis for a development of EDAs in permutation-based problems similar to that which occurred in other optimization fields (integer and real-value problems), in this paper we carry out a thorough review of state-of-the-art EDAs applied to permutation-based problems. Furthermore, we provide some ideas on probabilistic modeling over permutation spaces that could inspire the researchers of EDAs to design new approaches for these kinds of problems. Several Estimation of Distribution Algorithms (EDAs) based on Markov networks have been recently proposed. The key idea behind these EDAs was to factorise the joint probability distribution of solution variables in terms of cliques in the undirected graph. As such, they made use of the global Markov property of the Markov network in one form or another. This paper presents a Markov Network based EDA that is based on the use of the local Markov property, the Markovianity, and does not directly model the joint distribution. We call it Markovianity based Optimisation Algorithm. The algorithm combines a novel method for extracting the neighbourhood structure from the mutual information between the variables, with a Gibbs sampler method to generate new points. We present an extensive empirical validation of the algorithm on problems with complex interactions, comparing its performance with other EDAs that use higher order interactions. We extend the analysis to other functions with discrete representation, where EDA results are scarce, comparing the algorithm with state of the art EDAs that use marginal product factorisations. The question of finding feasible ways for estimating probability distributions is one of the main challenges for Estimation of Distribution Algorithms (EDAs). To estimate the distribution of the selected solutions, EDAs use factorizations constructed according to graphical models. The class of factorizations that can be obtained from these probability models is highly constrained. Expanding the class of factorizations that could be employed for probability approximation is a necessary step for the conception of more robust EDAs. In this paper we introduce a method for learning a more general class of probability factorizations. The method combines a reformulation of a probability approximation procedure known in statistical physics as the Kikuchi approximation of energy, with a novel approach for finding graph decompositions. We present the Markov Network Estimation of Distribution Algorithm (MN-EDA), an EDA that uses Kikuchi approximations to estimate the distribution, and Gibbs Sampling (GS) to generate new points. A systematic empirical evaluation of MN-EDA is done in comparison with different Bayesian network based EDAs. From our experiments we conclude that the algorithm can outperform other EDAs that use traditional methods of probability approximation in the optimization of functions with strong interactions among their variables. A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported. A key search mechanism in Evolutionary Algorithms is the mixing or juxtaposing of partial solutions present in the parent solutions. In this paper we look at the efficiency of mixing in genetic algorithms (GAs) and estimation-of-distribution algorithms (EDAs). We compute the mixing probabilities of two partial solutions and discuss the effect of the covariance build-up in GAs and EDas. Moreover, we propose two new Evolutionary Algorithms that maximize the juxtaposing of the partial solutions present in the parents: the Recombinative Optimal Mixing Evolutionary Algorithm (ROMEA) and the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA). This chapter presents results on the application of the concept of entropy to estimation of distribution algorithms (EDAs). Firstly, the Boltzmann mutual information curves are introduced. They are shown to contain a lot of information about the difficulty of the functions. Next, a design method of discrete benchmark functions is presented. The newly developed approach allows the construction of both single and random classes of functions that obey a given collection of probabilistic constraints. This application and the next — the construction of low cost search distributions — are based on the principle of maximum entropy. The last proposal is the linear entropic mutation (LEM), an approach that measures the amount of mutation applied to a variable as the increase of its entropy. We argue that LEM is a natural operator for EDAs because it mutates distributions instead of single individuals. Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming community. In this paper, we introduce a simple hybrid algorithm for job-shop scheduling that leverages both the fast, broad search capabilities of modern tabu search algorithms and the scheduling-specific inference capabilities of constraint programming. The hybrid algorithm significantly improves the performance of a state-of-the-art tabu search algorithm for the job-shop problem and represents the first instance in which a constraint programming algorithm obtains performance competitive with the best local search algorithms. Furthermore, the variability in solution quality obtained by the hybrid is significantly lower than that of pure local search algorithms. Beyond performance demonstration, we perform a series of experiments that provide insights into the roles of the two component algorithms in the overall performance of the hybrid. In recent years, quite a few search algorithms have been used to solve Web service composition problem. However, it is still lack of systematic analysis about these methods. In the paper, we attempt to analyze the effect of three typical meta-heuristic search algorithms. The experimental analysis is performed according to the search-based Web service composition framework. In the experiments, we mainly carry out the analysis as follows: different abstract service number, different candidate service number and different QoS constraint strength. Based on the above analysis, some guidelines of realizing Web service composition via search algorithms are yielded. For example, EDA is suitable for the composition problem with large abstract service number. PSO is more effective for the case of large candidate service number. GA is a good choose for the little-scale Web service composition problem. In addition, EDA can effectively settle the composition problem with strong QoS constraint. GA is suitable for the problem with medium constraint strength, and PSO has the poor ability to tackle the QoS constraint with high strength. We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2 p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4. Biometric sensors and portable devices are being increasingly embedded into our everyday life, creating the need for robust physiological models that efficiently represent, analyze, and interpret the acquired signals. We propose a knowledge-driven method to represent electrodermal activity (EDA), a psychophysiological signal linked to stress, affect, and cognitive processing. We build EDA-specific dictionaries that accurately model both the slow varying tonic part and the signal fluctuations, called skin conductance responses (SCR), and use greedy sparse representation techniques to decompose the signal into a small number of atoms from the dictionary. Quantitative evaluation of our method considers signal reconstruction, compression rate, and information retrieval measures, that capture the ability of the model to incorporate the main signal characteristics, such as SCR occurrences. Compared to previous studies fitting a predetermined structure to the signal, results indicate that our approach provides benefits across all aforementioned criteria. This paper demonstrates the ability of appropriate dictionaries along with sparse decomposition methods to reliably represent EDA signals and provides a foundation for automatic measurement of SCR characteristics and the extraction of meaningful EDA features. GAP is a Java-designed exploratory data analysis (EDA) software for matrix visualization (MV) and clustering of high-dimensional data sets. It provides direct visual perception for exploring structures of a given data matrix and its corresponding proximity matrices, for variables and subjects. Various matrix permutation algorithms and clustering methods with validation indices are implemented for extracting embedded information. GAP has a friendly graphical user interface for easy handling of data and proximity matrices. It is more powerful and effective than conventional graphical methods when dimension reduction techniques fail or when data is of ordinal, binary, and nominal type. Earth Observation Satellite (EOS) scheduling is an important oversubscribed constraint optimization problem. Permutation-based scheduling methods have recently been shown to be effective on these problems. However, the new agile EOS satellites present additional scheduling complexity because they allow image acquisition over a window of possible observation times. Constraint propagation algorithms have been successfully applied in traditional local search methods for these problems. In this paper, we describe a synthesis of permutation-based search and constraint propagation for agile EOS scheduling. Our approach incorporates the advantages of both techniques. We obtain the large neighbourhood behaviour of permutation search for oversubscribed resource scheduling problems. As well, we exploit the power of constraint propagation to retain as much flexibility as possible while building the schedule. We investigate different local optimization algorithms (including hill-climbing, simulated annealing and squeaky wheel optimization) coupled with constraint propagation over image acquisition time windows. We compare our method to recent permutation-based methods for non-agile EOS scheduling which rely upon a greedy scheduler for assigning image acquisition times. Experiments are performed on synthetic EOS data sets using both uniform random image targets and actual urban image target sets. We measure both schedule quality and solution degradation as new image requests are added dynamically to the problem. Our results suggest that permutation-based search coupled with constraint propagation works very well for agile EOS scheduling. In recent decades, a plethora of dedicated evolutionary algorithms (EAs) have been crafted to solve domain-specific complex problems more efficiently. Many advanced EAs have relied on the incorporation of domain-specific knowledge as inductive biases that is deemed to fit the problem of interest well. As such, the embedment of domain knowledge about the underlying problem within the search algorithms is becoming an established mode of enhancing evolutionary search performance. In this paper, we present a study on evolutionary memetic computing paradigm that is capable of learning and evolving knowledge meme that traverses different but related problem domains, for greater search efficiency. Focusing on combinatorial optimization as the area of study, a realization of the proposed approach is investigated on two NP-hard problem domains (i.e., capacitated vehicle routing problem and capacitated arc routing problem). Empirical studies on well-established routing problems and their respective state-of-the-art optimization solvers are presented to study the potential benefits of leveraging knowledge memes that are learned from different but related problem domains on future evolutionary search. Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property. This extended abstract summarizes our work "The Benefit of Recombination in Noisy Evolutionary Search," which appeared in Proceedings of International Symposium on Algorithms and Computation (ISAAC), 2015, pp. 140--150. For problem solving, making reactive decisions based on problem description is fast but inaccurate, while search-based planning using heuristics gives better solutions but could be exponentially slow. In this paper, we propose a new approach that improves an existing solution by iteratively picking and rewriting its local components until convergence. The rewriting policy employs a neural network trained with reinforcement learning. We evaluate our approach in two domains: job scheduling and expression simplification. Compared to common effective heuristics, baseline deep models and search algorithms, our approach efficiently gives solutions with higher quality. Given an undirected graph with costs associated with each edge as well as each pair of edges, the quadratic minimum spanning tree problem (QMSTP) consists of determining a spanning tree of minimum cost. QMSTP is useful to model many real-life network design applications. We propose a three-phase search approach named TPS for solving QMSTP, which organizes the search process into three distinctive phases which are iterated: (1) a descent neighborhood search phase using two move operators to reach a local optimum from a given starting solution, (2) a local optima exploring phase to discover nearby local optima within a given regional area, and (3) a perturbation-based diversification phase to jump out of the current regional search area. TPS also introduces a pre-estimation criterion to significantly improve the efficiency of neighborhood evaluation, and develops a new swap-vertex neighborhood (as well as a swap-vertex based perturbation operator) which prove to be quite powerful for solving a series of special instances with particular structures. Computational experiments based on 7 sets of 659 popular benchmarks show that TPS produces highly competitive results compared to the best performing approaches in the literature. TPS discovers improved best known results (new upper bounds) for 33 open instances and matches the best known results for all the remaining instances. Critical elements and parameters of the TPS algorithm are analyzed to understand its behavior. HighlightsQMSTP is a general model able to formulate a number of network design problems.We propose a three phase search heuristic (TPS) for this problem.TPS is assessed on 7 groups of 659 representative benchmarks of the literature.TPS finds improved best solutions for 33 challenging instances.TPS finds all the optimal solutions for the 29 instances transformed from the QAP. We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86 of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature. We apply reinforcement learning methods to learn domain-specific heuristics for job shop scheduling. A repair-based scheduler starts with a critical-path schedule and incrementally repairs constraint violations with the goal of finding a short conflict-free schedule. The temporal difference algorithm TD(λ) is applied to tram a neural network to learn a heuristic evaluation function over states. This evaluation function is used by a one-step lookahead search procedure to find good solutions to new scheduling problems. We evaluate this approach on synthetic problems and on problems from a NASA space shuttle pay load processing task. The evaluation function is trained on problems involving a small number of jobs and then tested on larger problems. The TD scheduler performs better than the best known existing algorithm for this task--Zwehen's iterative repair method based on simulated annealing. The results suggest that reinforcement learning can provide a new method for constructing high-performance scheduling systems. Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have simple structures; in particular, each job is a single self contained entity. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have more complex structures. In this paper, we consider two classical scheduling models that capture complex job structures: 1) concurrent open-shop scheduling and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for open-shop scheduling and precedence constrained scheduling, and show hardness results.