Utilizing knowledge of the problem of interest and lessons learned from solving similar problemswould help to find the final optimal solution of better quality. A hyper-heuristic algorithm is to gain an advantage of s...
详细信息
ISBN:
(纸本)9789811307614;9789811307607
Utilizing knowledge of the problem of interest and lessons learned from solving similar problemswould help to find the final optimal solution of better quality. A hyper-heuristic algorithm is to gain an advantage of such process. In this paper, we present an evolutionary algorithm based hyper-heuristic framework for solving the set packing problem (SPP). The SPP is a typicalNP-hard problem. The hyper-heuristic is comprising of high level and low level. The higher level is mainly engaged in generating or constructing a heuristic. An evolutionary algorithm with guided mutation (EA/G) is employed at the high level. Whereas a set of problem-independent and problem-specific heuristics, called low level heuristics, are employed at the low level of hyper-heuristic. EA/G is recently added to the class of the evolutionary algorithms that try to utilize the complementary characteristics of genetic algorithms (GAs) and estimation of distribution algorithms (EDAs) to generate new offspring. In EA/G, the guided mutation operator generates an offspring by sampling the probability vector. The proposed approach is compared with the state-of-the-art approaches reported in the literature. The computational results show the effectiveness of the proposed approach.
This paper introduces the origination, concept of ground holding policy and research literature review firstly. Next, three types of models are built for single airport ground holding problem (SAGHP), multi airport gr...
详细信息
ISBN:
(纸本)9781538692981
This paper introduces the origination, concept of ground holding policy and research literature review firstly. Next, three types of models are built for single airport ground holding problem (SAGHP), multi airport ground holding problem (MAGHP) and dynamic single airport ground holding problem (dSAGHP). For solving algorithms, two conventional methods of First Come First Served (FCFS) and dynamic Sequencing Window are explained briefly, then one heuristic algorithm named estimation of distribution algorithm (EDA) is illustrated in detail to solve the ground delay problems, including problem-specific modeling, probability learning and new solutions sampling. Finally, experiment results based on simulation instances and discussions are given.
In this paper, we introduce a copula-based EDA that uses a Discrete Vine-Copula (DVC) model. This model is particularly suited to represent distributions in the permutation representation. To demonstrate the effective...
详细信息
ISBN:
(纸本)9781450367486
In this paper, we introduce a copula-based EDA that uses a Discrete Vine-Copula (DVC) model. This model is particularly suited to represent distributions in the permutation representation. To demonstrate the effectiveness of the proposed Discrete-Vine-Copula based EDAs (DVCEDA), we perform a set of experiments on instances of the known TSP problems. The results obtained are promising to extend the work on other class of problems.
estimation of distribution algorithms have been successfully used for solving many combinatorial optimization problems. One type of problems in which estimation of distribution algorithms have presented strong competi...
详细信息
ISBN:
(纸本)9781450367486
estimation of distribution algorithms have been successfully used for solving many combinatorial optimization problems. One type of problems in which estimation of distribution algorithms have presented strong competitive results are permutation-based combinatorial optimization problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models is distance-based exponential models, and one example of this class is the Mallows model. In spite of the practical success, the theoretical analysis of estimation of distribution algorithms for permutation-based combinatorial optimization problems has not been extensively developed. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of estimation of distribution algorithms based on the Mallows model by using an infinite population to associate a dynamical system to the algorithm. Several scenarios, with different fitness functions and initial probability distributions of increasing complexity, are analyzed obtaining unexpected results in some cases.
Model-building optimisation methods aim to learn the structure underlying a problem and exploit this to direct the exploration of solutions. This generally interleaves two processes: Generating samples (from the model...
详细信息
ISBN:
(纸本)9781450349390
Model-building optimisation methods aim to learn the structure underlying a problem and exploit this to direct the exploration of solutions. This generally interleaves two processes: Generating samples (from the model), and updating the model (using selected samples). In most estimation of distribution algorithms (EDAs), e.g. BOA, selection is used only in the laSer, to determine which samples are retained for updating the model. In contrast, other evolution-inspired algorithms (such as rHN-G and MACRO) use selection differently - within the process that generates samples from the model. It has been hypothesised that this 'constructive selection' process can facilitate optimisation that other EDAs cannot but this has not been previously shown. Here we investigate these distinctions using constraint optimisation problems with a very simple modular structure. We find that a simple constructive selection method (rHN-g) can solve these problems in time polynomial in the problem size whereas other methods, such as BOA, require exponential time. We confirm that this result arises not from any difficulty in acquiring an accurate model but because of how samples are generated given the model. This suggests that by using constructive selection other EDAs could exploit the models they learn more efficiently to solve otherwise unsolvable problems.
Finding multiple roots of nonlinear equations systems (NESs) in a single run is an important yet difficult task. It requires to keep a balance between explorative and exploitative traits. In this paper, we present a r...
详细信息
ISBN:
(纸本)9781728121536
Finding multiple roots of nonlinear equations systems (NESs) in a single run is an important yet difficult task. It requires to keep a balance between explorative and exploitative traits. In this paper, we present a random walk mutation-based differential evolution (DE) with estimation of distribution algorithm (EDA) to address this problem. The major characteristics are: i) the random walk mutation is capable of preserving the population diversity, which guides individuals to move toward different promising regions;ii) probability selection is employed to provide suitable parent individuals for evolution;iii) EDA is used to accelerate the convergence and obtains the roots. To evaluate the performance of our approach, 30 NESs with diverse features are selected as test suite. Experimental results indicate that the proposed approach is able to yield better performance compared with other state-of-the-art methods.
The Quadratic Assignment Problem (QAP) is a specially challenging permutation-based np-hard combinatorial optimization problem, since instances of size n > 40 are seldom solved using exact methods. In this sense, m...
详细信息
ISBN:
(纸本)9781450367486
The Quadratic Assignment Problem (QAP) is a specially challenging permutation-based np-hard combinatorial optimization problem, since instances of size n > 40 are seldom solved using exact methods. In this sense, many approximate methods have been published to tackle this problem, including estimation of distribution algorithms (EDAs). In particular, EDAs have been used to solve permutation problems by introducing distance based exponential models, such as the Mallows Models. In this paper we approximate the QAP with a Hamming distance based kernels of Mallows Models. Based on the benchmark instances, we have observed that our approach is competitive, reaching the best-known solution in 71% of the tested instances, especially on large instances (n > 125), where it is able to outperform state of the art results in 43 out of 288 instances.
This paper describes an artificial immune algorithm (IA) combined with estimation of distribution algorithm (EDA), named IA-EDA, for the traveling salesman problem (TSP). Two components are incorporated in IA-EDA to f...
详细信息
This paper describes an artificial immune algorithm (IA) combined with estimation of distribution algorithm (EDA), named IA-EDA, for the traveling salesman problem (TSP). Two components are incorporated in IA-EDA to further improve the performance of the conventional IA. First, aiming to strengthen the information exchange during different solutions, two kinds of EDAs involving univariate marginal distributionalgorithm and population-based incremental learning are altered based on the permutation representation of TSP. It is expected that new promising candidate solutions can be sampled from the constructed probabilistic model of EDA. Second, a heuristic refinement local search operator is proposed to repair the infeasible solutions sampled by EDA. Therefore, IA-EDA can alleviate the deficiencies of the conventional IA and can find better solutions for TSP by well balancing the exploitation and exploration of the search. Experiments are conducted based on a number of benchmark instances with size up to 100 000 cities. Simulation results show that IA-EDA is effective for improving the performance of the conventional IA and can produce better or competitive solutions than other hybrid algorithms. (C) 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.
Exact fingertip positions are of particular importance to the fingertip-based human-computer interaction. We build a multi-objective optimization model for the problem of fingertip localization, and present a method t...
详细信息
Exact fingertip positions are of particular importance to the fingertip-based human-computer interaction. We build a multi-objective optimization model for the problem of fingertip localization, and present a method to solve the above model based on evolutionary algorithms. When building the model, we take the positions of a series of pixels as the decision variable, the shape of the hand-edge curve corresponding to each of the pixels as one objective function, and the distance between each of the pixels and the gravity center of the palm as the other objective function. In addition, based on the correlation among the positions of pixels of the fingertip regions, we present a multi-objective estimation of distribution algorithm to solve the model so as to obtain the best pixel set, thus gaining the fingertip positions. The experimental results demonstrate the effectiveness of the proposed model and algorithm. (C) 2017 Elsevier Ltd. All rights reserved.
This paper considers systems that comprise one-shot devices and support equipment. One-shot devices are stored for long periods of time, and failures are detected only upon inspection. The support equipment needed to ...
详细信息
This paper considers systems that comprise one-shot devices and support equipment. One-shot devices are stored for long periods of time, and failures are detected only upon inspection. The support equipment needed to operate one-shot devices is maintained immediately upon failure. This paper addresses the inspection schedule problem for such systems with limited maintenance resources. The interval availability and life cycle cost are used as optimization criteria. The aim is to determine near-optimal inspection intervals for one-shot systems to minimize the expected life cycle cost and satisfy the target interval availability between inspection periods. An estimation of distribution algorithm (EDA) and a heuristic method are proposed to find the near-optimal solutions, and numerical examples are given to demonstrate the effects of the various model parameters to the near-optimal inspection intervals. (C) 2017 Elsevier Ltd. All rights reserved.
暂无评论