LINKAGE LEARNING BY BLOCK MINING IN GENETIC ALGORITHM FOR PERMUTATION FLOW-SHOP SCHEDULING PROBLEMS

摘要

In Permutation Flow-shop Scheduling problems solving, Genetic Algorithm (GA) had been regarded as a meta-heuristic for approximation in combinatorial optimization. However, the standard Genetic Algorithm has suffered from slow convergence and trapped into local optimum when meeting the problems with higher complexities. In this research, we introduce a new heuristic by using the concept of Ant Colony Optimization (ACO) to extract patterns from the chromosomes generated in previous generations. The proposed heuristic is composed of two phases: 1. the blocks mining phase using ACO approach to establish a set of non-overlap block archive and the rest of cities in set S, and 2. a block recombination phase which will combine the set of blocks with the rest of jobs to form an artificial chromosome (AC). The goal of blocks mining is to obtain a set of genes which contain dependencies among gene relationships. These blocks without overlapping of genes can be further merged to form a new chromosome and the quality of the new chromosome can be greatly improved. The artificial chromosomes generated then will be injected into the GA process to speed up the convergence. From the result of experiments, the proposed puzzle-based ACGA or p-ACGA is validated significantly outperforms than other approaches on Permutation Flow shop Scheduling Problems.