استفاده از داده کاوی برای پیدا کردن الگوها در راه حل های الگوریتم ژنتیک برای یک برنامه تولید کارگاهی

This paper presents a novel use of data mining algorithms for the extraction of knowledge from a large set of job shop schedules. The purposes of this work is to apply data mining methodologies to explore the patterns in data generated by a genetic algorithm performing a scheduling operation and to develop a rule set scheduler which approximates the genetic algorithm's scheduler. Genetic algorithms are stochastic search algorithms based on the mechanics of genetics and natural selection. Because of genetic inheritance, the characteristics of the survivors after several generations should be similar. In using a genetic algorithm for job shop scheduling, the solution is an operational sequence for resource allocation. Among these optimal or near optimal solutions, similar relationships may exist between the characteristics of operations and sequential order. An attribute-oriented induction methodology was used to explore the relationship between an operations’ sequence and its attributes and a set of rules has been developed. These rules can duplicate the genetic algorithm's performance on an identical problem and provide solutions that are generally superior to a simple dispatching rule for similar problems.

In recent years, information growth has proceeded at an explosive rate. While database management systems (DBMS) provide us with basic tools for the efficient storage and look-up of large data sets, the capabilities for collecting and storing data have far outpaced our abilities to analyze, summarize and extract “knowledge” from this data. Traditional methods of data analysis were based mainly on humans dealing directly with data. Large volumes of data overwhelm the traditional manual methods of data analysis and make the task of analysis more difficult and less efficient. Also, traditional methods of data analysis, such as spreadsheets and ad hoc queries, can create informative reports from data, but cannot analyze the contents of those reports by focusing on important knowledge. These methods help only in data collecting and computing. They do not assist in improving the analysis task. Moreover, they overemphasize the statistical aspects of data while ignoring the domain knowledge of data. As a result, traditional analysis can fail to reveal the physical natures that the data implies. Genetic algorithms (GAs) often provide fast solutions to traditional numeric problems. For example, a GA can generate schedules for a manufacturing job shop. However, GAs do not demonstrate repeatability or provide an explanation of how a solution is developed. Using data mining, this paper presents a method for inducing rules from the solutions of a GA, which describe its behavior. These rules have also been applied to similar job shop cases with success.

This research has shown that data mining can be used to learn from job shop schedules produced by genetic algorithms. In practice, the effort required to duplicate the GA's performance was significant. Data mining requires an understanding of the problem domain, a knowledge of mining algorithms and an insight into which attributes might be significant. In this study, the researchers were able to apply the sequencing knowledge from a single job shop problem solved many times, by a genetic algorithm, into a set of 24 rules, which, combined with 4 default rules learned from the data, optimally solved an identical problem. When compared to problems with the same structure (6×6 Job Shop) and different operation times and sequences, the rules were able to consistently outperform the Shortest Processing Time heuristic. However, the learned rules were unable to match the performance of the genetic algorithm on these problems. Future research should incorporate incremental learning into the mining process an allowing for multiple schedule scenarios in the data sets.