The goal of block mining is to obtain a set of genes that contain dependency among gene relationships. Such 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. Based on this concept, we propose a novel block mining method that is able to locate common structures or to establish new blocks (like a small piece of puzzle) from a set of high fit chromosomes. The identified blocks (puzzles) will also be updated generation by generation through the newly updated high fit chromosomes. We develop a heuristic re-combination procedure to form a new chromosome by re-combining the blocks. We call the new chromosomes generated as artificial chromosomes (ACs) and inject them into the evolutionary process when the convergence slope of the evolutionary process is less than a predefined threshold. This new algorithm retains the regular simple genetic algorithm (SGA) operations of crossover and mutation, and utilizes the ACs generated from elites to speed up the convergence process. Experimental results indicate that the puzzle-based method of chromosome generation is very efficient and effective in solving the traditional permutation flowshop scheduling problem. The new method can be applied to tackle other NP-complete problems such as scheduling and vehicle routing problems.
Genetic algorithm (GAs) relies on genetic operators such as selection, crossover, and mutation to search the solution space for optimal solutions. GA is a powerful search technique, which has been successfully applied to solve combinatorial problems in different disciplines. However, for combinatorial problems that are very difficult to solve even in moderate sizes such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and various machine scheduling problems, GA will converge prematurely. In other words, GA will be trapped into a local optimum at an early stage and cannot deliver the global optimal solution.
To prevent early convergence of GA as observed by Holland (1992), it is important to acquire linkage information to re-combine building blocks to ensure the success of GA. In addition, Goldberg et al. (1992) suggest that proper problem decomposition is one of the keys to ensure the effectiveness of GA. Since then, much research on the linkage learning design for GA has been conducted. The linkage model can be implicit, e.g., linkage learning GA (LLGA) (Harik and Goldberg, 1996), explicit, e.g., linkage identification by the nonlinearity check procedure (LINC) (Munetomo and Goldberg, 1999), probabilistic model building GA (PMBGA) (Pelikan et al., 2002), estimation of distribution algorithm (EDA) (Larrañaga and Lozano, 2001), or deterministic, e.g., dependency structure matrix GA (DSMGA) (Yu et al., 2003). However, the problem with explicit linkage learning is that the probabilistic model will also be premature and trapped into a local optimum. As for the explicit model, it is hard to identify a set of blocks or linkage set from the chromosome in real-world applications.
This research is based on the concept of the schema theorem to locate blocks from a set of high fit chromosomes. These short, low-order, and highly fit schemata are called “blocks”. Blocks can be considered as a plausible explanation for the success of GA. However, due to the nature of blocks, which depends on the problem and encoding of the chromosome, their behaviors are difficult to analyze. Therefore this research is different from previous studies that try to learn linkage relationships or building blocks (BBs) to create a new method. Instead, we propose a novel approach that locates a series of genes physically from a set of high-quality chromosomes or elites. We then apply the blocks mined from the elites to generate a set of artificial chromosomes, which are then injected into the evolutionary process to speed up the convergence of SGA. To reach this goal, we propose a simplified definition of building blocks, called blocks. Blocks are similar contiguous bits found in highly fit chromosomes. The motivation for this research is to merge such blocks with other genes to form a new chromosome. The quality of the new chromosome will be greatly improved.
The paper is organized as follows: Section 2 provides a literature review on the concept of building blocks and on the flowshop scheduling problem. Section 3 introduces the block mining and re-combination approach, and applies it to solve the flowshop scheduling problem. Section 4 presents the experimental results to evaluate the effectiveness of the proposed algorithm. Finally, Section 5 discusses the results, concludes the paper, and suggests topics for future research.
In this study we presented a block mining and re-combination-based genetic algorithm for solving the flowshop scheduling problem. The blocks are treated like puzzles and the re-combination procedure attempts to solve the puzzle to come up with a high fit solution. The quality of the blocks mined from the previous population has a great impact on the behavior of p-ACGA. In addition, the blocks can be continuously updated once a new set of elite is identified through the evolutionary process. The length of the block is kept in four in this research and the reason is that these blocks are similar to the fragments of a DNA in that if they are too big, they may contain redundant information that will be carried over throughout the evolutionary process and the final result may not be good. If the block length is too small, the information contained within each block may be too little and the re-combination process may not be able to come out with good-quality chromosomes. The characteristics of tradition GA are preserved in p-ACGA since the latter contains the crossover and mutation operators, which help improve the solution quality of the ACs. ACs are only injected when needed. The reason is that the solution speed can be greatly improved since the mining and re-combination processes do consume computational times.
