臺灣博碩士論文加值系統

演化式計算包括演化式規劃、演化式策略、基因演算法、基因規劃等，已經被廣泛的使用來解決最佳化的問題，尤其在大規模且複雜的系統中尋找最佳解。然而，這類的演算法，如果沒有整合足夠的知識，在演化的過程中，將會增加演化成本並影響演化效能及收斂的情形。而且一般的基因演算法只針對某一問題而設計，如果遇到另一個問題，就產生重新計設的成本。有鑑於此，本篇論文提出一般化的基因演算法，並整合由約略集合所產生的知識規則。只要能將一個問題分解成多個功能需求，就可以用一般化的基因演算法加以解決，而且整合由約略集合理論所發掘出來的知識，確實能提高此基因演算法的效能以及加速收斂，特別是用在簡化母體或限制交配這二方面。

The evolutionary computing (EC) comprises techniques of evolutionary programming, evolution strategies, genetic algorithms, and genetic programming. It has been widely used to solve optimization problems for large scale and complex systems. However, (i) without incorporating with sufficient knowledge, it does have a significant impact on the efficiency of the search for an optimal solution. (ii) In addition, the genetic algorithm in previous literatures is modeled to solve one problem exactly. It is required redesign cost for GA to apply to another problem. Due to the two reasons, this thesis develops a generic genetic algorithm incorporating with the knowledge extracted from the rough set theory. The advantages of the proposed solution approach includes: (i) it is modeled to solve generic problems which are decomposed into functional requirements, (ii) by incorporating the rough set theory, the discovered knowledge can contribute to improving the performance and efficiency of the proposed GA, specifically on initial population and constraining crossover.

Table of Contents
Acknowledgement ………………………………………………… i
Chinese Abstract………………………………………………… ii
Abstract ………………………………………………………… iii
Table of Content ……………………………………………… iv
List of Figures ……………………………………………… vi
List of Tables ………………………………………………… viii
Chapter 1. Introduction ……………………………………… 1
Chapter 2. Algorithm Development of the rough set theory …4
2.1. The Reduct Generation Procedure ……… 5
2.2. The rule identification algorithm with weight
analysis …………………………………… 6
2.3. The weight analysis for final reduct rules
…………………………………………………… 7
Chapter 3. The generic genetic algorithm incorporates with the
rough set theory ………………………………… 9
3.1. Symbols and notation ……………………… 11
3.2. Representation ……………………………… 12
3.3. Objective function ………………………… 13
3.4. Evolutionary operators and process …… 14
Chapter 4. The application of the proposed solution approach and an illustrative example ……………………………… 21
4.1. The application …………………………… 21
4.2. An illustrative example: PC synthesis … 26
4.2.1 The application of the rough set theory
…………………………………………… 26
4.2.2 The process of this case solved by the
roposed solution approach ………… 32
4.3. The other ways for the rough set to incorporate
with the GA ………………………………… 43
4.3.1 The rough set incorporated with the GA by
constraining crossover ……………… 43
4.3.2 The rough set incorporated with the GA by
reducing initial population and constraining
crossover ………………………………… 46
4.4. Discussion …………………………………… 48
Chapter 5. Conclusions ……………………………………… 50
References ……………………………………………………… 51
Appendix A ……………………………………………………… 56
List of Figures
Figure 3-1 The flow chart of the generic GA
incorporated with the rough set theory
……………………………………………… 10
Figure 3-2 An illustrative example of the functional
requirement hierarchy ………………… 11
Figure 3-3 Crossover operator …………………… 14
Figure 3-4 Crossover process ……………………… 15
Figure 3-5 Mutation operator ……………………… 15
Figure 3-6 Mutation process ……………………… 15
Figure 3-7 The flowchart of the proposed solution
approach ………………………………… 17
Figure 4-1 The matrix of the rule identification
……………………………………………… 29
Figure 4-2 The corresponding weights of the matrix in
Figure 4-1 ……………………………… 30
Figure 4-3 The Convergence of the porposed GA
……………………………………………… 41
Figure 4-4 The comparison of convergence between the
proposed GA and standard GA ………… 42
Figure 4-5 The convergence of the proposed GA
(constrain crossover) ………………… 45
Figure 4-6 The comparison of convergence between the
proposed GA (constrain crossover) and the
standard GA ……………………………… 46
Figure 4-7 The convergence of the proposed GA (reduce
initial population and constrain crossover)
……………………………………………… 47
Figure 4-8 The comparison of convergence between the
proposed GA (reduce initial population and
constrain crossover) and the standard GA
……………………………………………… 48
Figure A-1. The matrix of the rule identification
……………………………………………… 56
Figure A-2. The corresponding weight of matrix in
Figure A-1 ……………………………… 57
Figure A-3. The next step of Figure A-2 ………… 58
Figure A-4. The next step of Figure A-3 ………… 59
Figure A-5. The next step of Figure A-4 ………… 60
Figure A-6. The next step of Figure A-5 ………… 61
Figure A-7. The next step of Figure A-6 ………… 62
List of Tables
Table 4-1 A list of examples solved by the proposed
solution approach ……………………… 21
Table 4-2 The description of all attributes in
Table 4-3 ………………………………… 26
Table 4-3 The partial original data source of the PC
synthesis ………………………………… 27
Table 4-4 The value of reducts for the data in
Table 4-3 ………………………………… 27
Table 4-5 Expanded with weights of Table 4-3 …28
Table 4-6 The counted weights of each entry in each
reduct …………………………………… 29
Table 4-7 The final value reducts ……………… 32
Table 4-8 The explanations of reduct rules in Table 4.5
……………………………………………… 32
Table 4-9 Expanded with weights of Table 4-7 …33
Table 4-10 The weight of each entry of reduct rules
……………………………………………… 34
Table 4-11 The reduced initial population …… 34
Table 4-12 The Feasible Subset of the CPU …… 36
Table 4-13 Initialization population whose domain is
constrained by reduct rules ………… 37

Beaubouef, T. and Lang, R., 1998, “Rough set techniques for uncertainty management in automated story generation,” Proceedings of the 36th Annual Conference on Southeast Regional Conference, ACM Press, New York, NY, pp. 326-331.
Bontempi, B. and Marcelli, A., 1994, “Machine learning and genetic algorithms: an application to character recognition,” Systems, Man, and Cybernetics, 1994. ''Humans, Information and Technology''., 1994 IEEE International Conference on, Vol. 3 , pp. 2225-2230.
Bruns, R., 1995, “Integration of constraint solving techniques in genetic algorithms,” Evolutionary Computation, 1995., IEEE International Conference on, Perth, WA , Australia, Vol. 1, pp. 33-38.
Cheng, C.-H., Lee, W.-K., and Wong, K.-F., 2002, “A Genetic Algorithm-Based Clustering Approach for Database Partitioning,” IEEE Transactions on Systems, Man, and Cybernetics- Part C: Applications and Reviews, Vol. 32, No. 3, pp. 215-230.
Cordόn, O., Herrera, F., Hoffmann, F., and Magdalena, L., 2001, Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases, World Scientific.
Deshayes, L., Dartigues, C., Ghodous, P., and Rigal, J. F., 2003, “Collaborative System for Cutting Data Management Based on STEP Standard,” Concurrent Engineering: Research and Applications, Vol. 11, No. 1, pp. 27-36.
Dote, Y. and Ovaska, S. J., 2001, “Industrial applications of soft computing: a review,” Proceedings of the IEEE, Vol. 89, No. 9, pp. 1243 -1265.
Eiben, A. E. and Schoenauer, M., 2002, “Evolutionary computing,” Information Processing Letters, Vol. 82, No. 1, pp. 1-6.
Goldberg, D.E., 1989, Genetic Algorithm in Search, Optimization, Machine Learning, Addison Wesley.
Gutiérrez Martínez, I. and Bello Pérez, R. E., 2003, “Making decision in case-based systems using probabilities and rough sets,” Knowledge-Based Systems, Vol. 16, No. 4, pp. 205-213.
Heckerman, D., Mannila, H., Pregibon, D., and Uthurusamy, R., 1997, Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, Menlo Park, AAAI Press, CA.
Hu, Y. and Yang, S.X., 2004, “A knowledge based genetic algorithm for path planning of a mobile robot,” Robotics and Automation, 2004. Proceedings. ICRA ''04. 2004 IEEE International Conference on, Vol. 5, pp. 4350-4355.
Jin, X. and Reynolds, R. G., 1999a, “Using knowledge-based system with hierarchical architecture to guide the search of evolutionary computation,” Tools with Artificial Intelligence, 1999. Proceedings. 11th IEEE International Conference on, Chicago, IL, USA, pp. 29-36.
Jin, X. and Reynolds, R. G., 1999b, “Using knowledge-based evolutionary computation to solve nonlinear constraint optimization problems: a cultural algorithm approach,” Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, Washington, DC, USA, Vol. 3, pp.1672-1678.
Jin, Y. (guest editor), 2003, “Call for paper: Special Issue on Knowledge Extraction and Incorporation in Evolutionary Computation,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews.
Khoo, K.G. and Suganthan, P.N., 2003, “Structural pattern recognition using genetic algorithms with specialized operators,” Systems, Man and Cybernetics, Part B, IEEE Transactions on, Vol. 33, Iss. 1, pp. 156 — 165.
Komorowski, J. and Zytkow, J., 1997, Principles of Data Mining and Knowledge Discovery, Springer-Verlag, New York.
Kusiak, A. and Tseng, T-L., 1999, “Modeling approach to data mining,” Proceedings of the Industrial Engineering and Production Management Conference, Glasgow, Scotland.
Kusiak, A., 2001, “Rough Set Theory: A Data Mining Tool for Semiconductor Manufacturing,” IEEE Transactions on Electronics Packaging Manufacturing, Vol. 24, No. 1, pp. 44-50.
Kusiak, A., Kern, J. A., Kernstine, K. H., and Tseng, T. L.(Bill), 2000, “Autonomous Decision-Making: A Data Mining Approach,” IEEE TRANSACTIONS ON INFORMATION TECHNOLOGY IN BIOMEDICINE, Vol. 4, No. 4, pp. 274-284.
Li, F. and Lindquist, T.M., 2003, “Knowledge guided genetic algorithm for optimal contracting strategy in a typical standing reserve market,” Power Engineering Society General Meeting, 2003, IEEE, Vol. 2, pp. 859-863.
Liang, W.Y. and O’Grady P., 2000, “A Constrained Evolutionary Search Formalism for Remote Design with Modules,” International Journal of Computer Integrated Manufacturing, Vol. 13, No. 2, pp. 65-79.
Maini, H., Mehrotra, K., Mohan, C., and Ranka, S., 1994, “Knowledge-based nonuniform crossover,” Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, Vol. 1, pp. 22-27.
Michalewicz, Z., 1996, Genetic Algorithms + Data Structures = Evolution Programs, 3rd, Springer.
Olhofer, M., Jin, Y., and Sendhoff, B., 2001, “Adaptive encoding for aerodynamic shape optimization using evolution strategies,” Evolutionary Computation, 2001. Proceedings of the 2001 Congress on, Seoul, South Korea, Vol. 1, pp. 576-583.
Ozdamar, L., 1999, “A genetic algorithm approach to a general category project scheduling problem,” Systems, Man and Cybernetics, Part C, IEEE Transactions on, Vol. 29, Iss. 1, pp. 44-59.
Pawlak, Z., 1982, “Rough sets,” International Journal of Computer and Information Sciences, Vol. 11, No. 5, pp. 341-356.
Pawlak, Z., 1984, “Rough Classification,” International Journal of Man-Machine Studies, Vol. 20, pp. 469-483.
Pawlak, Z., 1991a, Rough Sets, Dordrecht, Kluwer Academic Publishers, the Netherlands.
Pawlak, Z., 1991b, Rough Sets: Theoretical Aspects of Reasoning About Data, Kluwer Academic Publishers, Norwell, MA.
Pawlak, Z., 1992, “Rough Sets: A New Approach to Vagueness,” Fuzzy Logic for the Management of Uncertainty, L. A. Zadeh and J. Kacprzyk (eds.), John Wiley & Sons, New York, pp. 105-118.
Pawlak, Z., 1994, “Hard and Soft Sets,” Rough Sets, Fuzzy Sets and Knowledge Discovery, W.P. Ziarko (ed.), Springer-Verlag, London, pp. 130-135.
Pawlak, Z., 1998, “Reasoning about Data- A Rough Set Perspective,” L. Polkowski and A. Skowron (Eds.), RSCTC’98, LNAI 1424, pp. 25-34.
Questier, F., Arnaut-Rollier, I., Walczak, B., and Massart, D.L., 2002, “Application of rough set theory to feature selection for unsupervised clustering,” Chemometrics and Intelligent Laboratory Systems, Vol. 63, No. 2, pp. 155-167.
Simoudis, E., Han, J., and Fayyad, U., 1996, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, Menlo Park, AAAI Press, CA.
Slowinski, R. and Stefanowski, J., 1992, “RoughDAS and rough-class software implementation of the rough sets approach,” In Intelligent Decision Support—Handbook of Applications and Advances of the Rough Sets Theory, R. Slowinski (ed.), Kluwer Academic Publishers, Dordrecht, pp. 445-456.
Slowinski, R., 1992, Intelligent Decision Support Handbook of Applications and Advances of Rough Sets Theory, Kluwer Academic Publishers, the Netherlands.
Trabelsi A. and Delchambre, A., 2000, “Assessment on Tolerance Representation and Tolerance Analysis in Assemblies,” Concurrent Engineering: Research and Applications, Vol. 8, No. 4, pp. 244-262.
Tseng, T.-L.(Bill), 1999, “Quantitative Approaches for Information Modeling,” Ph.D. Dissertation, University of Iowa.
Yang, J. and Honavar, V., 1998, “Feature subset selection using a genetic algorithm,” Intelligent Systems, IEEE [see also IEEE Expert], Vol. 13, Iss. 2, pp. 44-49.
Yu, C.-Y., Wu, M.-H., and Wu, M., 2003, “Combining rough set theory with neural network theory for pattern recognition,” Robotics, Intelligent Systems and Signal Processing, 2003. Proceedings. 2003 IEEE International Conference on, Vol. 2, pp. 880 — 885.
Zhang, Y., Wu, C.-D. and Li, M.-X., 2003, “Rough Set and Genetic Algorithms in Path Planning of Robot,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi’an, pp. 698-701.
Ziarko, W.P., 1994, Rough Sets, Fuzzy Sets and Knowledge Discovery, Springer-Verlag, New York.