- 30 readers
- Pages displayed : 173112
- Unique visitors : 66188
- Pages displayed in last 24 hours : 185
- Unique visitors in last 24 hours : 6
Estimation of the Distribution Algorithm With a Stochastic Local Search for Uncertain Capacitated Arc Routing Problems
The uncertain capacitated arc routing problem is a challenging problem in which the demands of tasks, the costs of edges, and the presence of tasks and edges are uncertain. The objective of this problem is to find a robust optimal solution for a finite set of possible scenarios. In this paper, we propose a novel robust optimization approach, called an estimation of distribution algorithm (EDA) with stochastic local search (SLS), to tackle this problem. The proposed method integrates an EDA with a novel two phase SLS procedure to minimize the maximal total cost over a set of different scenarios. The SLS procedure avoids excessive fitness evaluations of unpromising moves in local search. Our experimental results on two sets of benchmark problems (a total of 55 problem instances) showed that the proposed approach outperformed existing state-of-the-art algorithms.
The estimation of distribution algorithms (EDAs) applied to genetic programming (GP) have been studied by a number of authors. Like all EDAs, they suffer from biases induced by the model building and sampling process. However, the biases are amplified in the algorithms for GP. In particular, many systems use stochastic grammars as their model representation, but biases arise due to grammar recursion. We define and estimate the bias due to recursion in grammar-based EDAs in GP, using methods derived from computational linguistics. We confirm the extent of bias in some simple experimental examples. We then propose some methods to repair this bias. We apply the estimation of bias, and its repair, to some more practical applications. We experimentally demonstrate the extent of bias arising from recursion, and the performance improvements that can result from correcting it.
In this paper, a novel self-learning gene expression programming (GEP) methodology named SL-GEP is proposed to improve the search accuracy and efficiency of GEP. In contrast to the existing GEP variants, the proposed SL-GEP features a novel chromosome representation in which each chromosome is embedded with subfunctions that can be deployed to construct the final solution. As part of the chromosome, the subfunctions are self-learned or self-evolved by the proposed algorithm during the evolutionary search. By encompassing subfunctions or any partial solution as input arguments of another subfunction, the proposed SL-GEP facilitates the formation of sophisticated, higher-order, and constructive subfunctions that improve the accuracy and efficiency of the search. Further, a novel search mechanism based on differential evolution is proposed for the evolution of chromosomes in the SL-GEP. The proposed SL-GEP is simple, generic and has much fewer control parameters than the traditional GEP variants. The proposed SL-GEP is validated on 15 symbolic regression problems and six even-parity problems. Experimental results show that the proposed SL-GEP offers enhanced performances over several state-of-the-art algorithms in terms of accuracy and search efficiency.
Evolutionary algorithms have been successfully applied for exploring both converged and diversified approximate Pareto-optimal fronts in multiobjective optimization problems, two- or three-objective in general. However, when solving problems with many objectives, nearly all algorithms perform poorly due to the loss of selection pressure in fitness evaluation. An extremely large objective space could inadvertently deteriorate the effect of an evolutionary operator. In this paper, we propose a new approach to directly handle the challenges to solve many-objective optimization problems (MaOPs). This novel design includes two stages: first, the whole population quickly approaches a small number of “target” points near the true Pareto front; then, the proposed diversity improvement strategy is applied to facilitate these individuals to spread and well distribute. As a case study, the proposed algorithm based on this design is compared with five state-of-the-art algorithms. Experimental results show that the proposed method exhibits improved performance in both convergence and diversity for solving MaOPs.
Hyper-heuristics have recently emerged as a powerful approach to automate the design of heuristics for a number of different problems. Production scheduling is a particularly popular application area for which a number of different hyper-heuristics have been developed and are shown to be effective, efficient, easy to implement, and reusable in different shop conditions. In particular, they seem to be a promising way to tackle highly dynamic and stochastic scheduling problems, an aspect that is specifically emphasized in this survey. Despite their success and the substantial number of papers in this area, there is currently no systematic discussion of the design choices and critical issues involved in the process of developing such approaches. This paper strives to fill this gap by summarizing the state-of-the-art approaches, suggesting a taxonomy, and providing the interested researchers and practitioners with guidelines for the design of hyper-heuristics in production scheduling. This paper also identifies challenges and open questions and highlights various directions for future work.
A Genetic Bankrupt Ratio Analysis Tool Using a Genetic Algorithm to Identify Influencing Financial Ratios
Financial ratios are key constituents of bankruptcy models. The bankruptcy prediction accuracy substantially improves when a limited number of ratios are used. From the literature, it has been found that human expertise has been applied to select financial ratios for bankruptcy models. Different experts tend to have different opinions and hence the bankruptcy prediction results depend upon their competency levels in that domain. Accordingly, there is a need for finding a systematic method or a tool to identify the influencing ratios. This paper develops a genetic bankrupt ratio analysis tool using a genetic algorithm to identify influencing ratios from different bankruptcy models and their influences in a quantitative form. The accuracy of values of influencing ratios is validated by comparing original threshold value of the bankruptcy models. The performance of influencing ratios has been compared with other feature selection techniques and the Altman model is considered to explain the effect of the influencing ratios.