In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution algorithms (EDAs) with genetic algorithms (GAS). The probab...
详细信息
In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution algorithms (EDAs) with genetic algorithms (GAS). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilisticmodels and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA(hybrid) to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA(hybrid) outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs. (C) 2011 Elsevier Ltd. All rights reserved.
In this paper, a novel genetic algorithm is developed by generating artificial chromosomes with probability control to solve the machine scheduling problems. Generating artificial chromosomes for Genetic algorithm (AC...
详细信息
In this paper, a novel genetic algorithm is developed by generating artificial chromosomes with probability control to solve the machine scheduling problems. Generating artificial chromosomes for Genetic algorithm (ACGA) is closely related to evolutionaryalgorithms Based on probabilisticmodels (EAPM). The artificial chromosomes are generated by a probability model that extracts the gene information from current population. ACGA is considered as a hybrid algorithm because both the conventional genetic operators and a probability model are integrated. The ACGA proposed in this paper, further employs the "evaporation concept" applied in Ant Colony Optimization (ACO) to solve the permutation flowshop problem. The "evaporation concept" is used to reduce the effect of past experience and to explore new alternative solutions. In this paper, we propose three different methods for the probability of evaporation. This probability of evaporation is applied as soon as a job is assigned to a position in the permutation flowshop problem. Experimental results show that our ACGA with the evaporation concept gives better performance than some algorithms in the literature.
This paper proposed Self-Guided genetic algorithm, which is one of the algorithms in the category of evolutionaryalgorithm based on probabilisticmodels (EAPM), to solve strong NP-Hard flowshop scheduling problems wi...
详细信息
ISBN:
(纸本)9781424429585
This paper proposed Self-Guided genetic algorithm, which is one of the algorithms in the category of evolutionaryalgorithm based on probabilisticmodels (EAPM), to solve strong NP-Hard flowshop scheduling problems with the minimization of makespan. Most EAPM research explicitly used the probabilistic model from the parental distribution, then generated solutions by sampling from the probabilistic model without using genetic operators. Although EAPM is promising in solving different kinds of problems, Self-Guided GA doesn't intend to generate solution by the probabilistic model directly because the time-complexity is high when we solve combinatorial problems, particularly the sequencing ones. As a result, the probabilistic model serves as a fitness surrogate which estimates the fitness of the new solution beforehand in this research. So the probabilistic model is used to guide the evolutionary process of crossover and mutation. This research studied the flowshop scheduling problems and the corresponding experiment were conducted. From the results, it shows that the Self-Guided GA outperformed other algorithms significantly. In addition, Self-Guided GA works more efficiently than previous EAPM. As a result, Self-Guided GA is promising in solving the flowshop scheduling problems.
暂无评论