According to the characteristics of the hybrid flow-shop scheduling problem (HFSP), the permutation based encoding and decoding schemes are designed and a probability model for describing the distribution of the solut...
详细信息
ISBN:
(纸本)9781467313988
According to the characteristics of the hybrid flow-shop scheduling problem (HFSP), the permutation based encoding and decoding schemes are designed and a probability model for describing the distribution of the solution space is built to propose a compact estimation of distribution algorithm (cEDA) in this paper. The algorithm uses only two individuals by sampling based on the probability model and updates the parameters of the probability model with the selected individual. The cEDA is efficient and easy to implement due to its low complexity and comparatively few parameters. Simulation results based on some widely-used instances and comparisons with some existing algorithms demonstrate the effectiveness and efficiency of the proposed compact estimation of distribution algorithm. The influence of the key parameter on the performance is investigated as well.
This paper concerns a highly effective and decomposed compact scheme for solving a highly oscillatory paraxial Helmholtz problem in radially symmetric fields. The decomposition is utilized in the transverse direction ...
详细信息
This paper concerns a highly effective and decomposed compact scheme for solving a highly oscillatory paraxial Helmholtz problem in radially symmetric fields. The decomposition is utilized in the transverse direction to eliminate the singularity of the differential equation in polar coordinates. Numerical stability of the splitting scheme is investigated. It is shown that the numerical method introduced is not only highly accurate and efficient due to its straightforward algorithmic structure, but also stable under reasonable constraints for practical applications. Computational examples are presented to illustrate our conclusions. (C) 2015 Elsevier B.V. All rights reserved.
In the field of stochastic optimisation, the so-called structural bias constitutes an undesired behaviour of an algorithm that is unable to explore the search space to a uniform extent. In this paper, we investigate w...
详细信息
ISBN:
(纸本)9783030581114;9783030581121
In the field of stochastic optimisation, the so-called structural bias constitutes an undesired behaviour of an algorithm that is unable to explore the search space to a uniform extent. In this paper, we investigate whether algorithms from a subclass of estimation of distribution algorithms, the compact algorithms, exhibit structural bias. Our approach, justified in our earlier publications, is based on conducting experiments on a test function whose values are uniformly distributed in its domain. For the experiment, 81 combinations of compact algorithms and strategies of dealing with infeasible solutions have been selected as test cases. We have applied two approaches for determining the presence and severity of structural bias, namely an (existing) visual and an (updated) statistical (Anderson-Darling) test. Our results suggest that compact algorithms are more immune to structural bias than their counterparts maintaining explicit populations. Both tests indicate that strong structural bias is found only in the cBFO algorithm, regardless of the choice of strategy of dealing with infeasible solutions, and cPSO with mirror strategy. For other test cases, statistical and visual tests disagree on some cases classified as having mild or strong structural bias: the former one tends to make harsher decisions, thus needing further investigation.
作者：
Rada, MiroslavCerny, MichalUniv Econ
Fac Finance & Accounting Nam W Churchilla 4 Prague 13067 3 Czech Republic Univ Econ
Fac Informat & Stat Nam W Churchilla 4 Prague 13067 3 Czech Republic
We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes...
详细信息
We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes). The algorithm is based on an incremental construction of the graph of cells of the arrangement. IncEnu is compared to Avis and Fukuda's Reverse Search (RS), including its later improvements by Sleumer and others. The basic versions of IncEnu and RS are not directly comparable, since they solve different numbers of linear programs (LPs) of different sizes. We therefore reformulate our algorithm as a version that permits comparison with RS in terms of the number of LPs solved. The result is that both IncEnu and RS have "the same" complexity-theoretic properties (compactness, output-polynomiality, worst-case bounds, tightness of bounds). In spite of the fact that IncEnu and RS have the same asymptotic bounds, it is proved that IncEnu is faster than RS by a nontrivial additive term. Our computational experiments show that for most test cases IncEnu is significantly faster than RS in practice. Based on the results obtained, we conjecture that IncEnu is O(d) times faster for nondegenerate arrangements, where d denotes the dimension of the arrangement.
The Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is innovative, there still remains room for improvement for our purpose. ...
详细信息
ISBN:
(纸本)0769514413
The Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is innovative, there still remains room for improvement for our purpose. This paper proposes a compact algorithm for placement based on the corner block list. By introducing dummy blocks into CBL, our algorithm can employ dummy blocks in the packing to represent the placement, including empty rooms, which the CBL cannot represent. Our algorithm can obtain fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows the effectiveness of the proposed method.
暂无评论