| 摘要(英) |
In this paper, we focus on the genetic algorithms for partitioning problems and purpose a new type of genetic algorithms called Relational Genetic Algorithm (RGA) including a new encoding called Relational Encoding and suitable genetic operators. Relational encoding is extended from equivalence relation and its structure is a matrix. It can suitably describe the structure of partitioning problems and the search space of genetic algorithms can be reduced. Therefore, this encoding can improve the efficiency of the genetic algorithm. At the same time, the operations of relational genetic algorithm does’nt have to depend on the heuristics for the specific problems.
The partitioning problems are NP-hard problems. If we use normally linear search to solve these problems, it is hard to optimize the solutions. Thus, we use artificial intelligent methods to search globally and try to find the optimal solution.
In the previous researches, there are three types of genetic algorithms for partitioning problems, and they are group-number encoding, permutation encoding, and grouping genetic algorithms (GGA). The first one and the second one belong to traditional encoding, so these encodings have high redundancy and would reduce the efficiency of the algorithms. Therefore, in this paper, our experiments are to compare our proposed algorithm, RGA, with GGA. Using random repair, the results of the experiments show that the performance of RGA is outstandingly better than that of GGA. Besides, using similar heuristics, RGA is also greater than GGA. These results prove that RGA is really a better genetic algorithm for the partitioning problems. |
| 參考文獻 |
[Appel, 97] K. Appel and W. Haaken (1977). “Every map is four-colourable I: discharging”, Illinois J. Math 21, 429-490.
[Bhuyan, 90] J. Bhuyan, V. Raghavan, and V. Elayavalli (1990). “Genetic-Based Clustering.”, Technical Report 90-4-1, The Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LA, March 1990.
[Brown, 05] E. C. Brown and R. T. Sumichrast (2005), “Evaluating performance advantages of grouping genetic algorithms”, Engineering Applications of Artificial Intelligence 18 , 1-12.
[Chiang, 96] W-C. Chiang and P. Kouvelis (1996), “An improved tabu search heuristic for solving facility layout design problem”. International Journal of Production Research, 34, 9, 2565-2585.
[Culberson, 96] J. Culberson and F. Luo (1996). “Exploring the k-Colorable Landscape with Iterated Greedy.” In D. Johnson and M. Trick (eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, 245-284.
[Eiben, 98]A. E. Eiben, J. K. van der Hauw, and J. I. van Hemert (1998), “Graph coloring with adaptive evolutionary algorithms”, J. Heuristics, vol. 4, no. 1, 25-46.
[Falkenauer, 92] E. Falkenauer (1992), “The grouping genetic algorithms—widening the scope of the GAs”. JORBEL—Belgian Journal of Operations Research, Statistics and Computer Science 33, 79-102.
[Falkenauer, 95] E. Falkenauer (1995), “Solving equal piles with the grouping genetic algorithm”, Proc. 6th Intnl. Conf. on Genetic Algorithms, ed. L. J. Eshelman, Morgan Kaufmann, San Francisco, 492-497.
[Falkenauer, 96] E. Falkenauer (1996), “A hybrid grouping genetic algorithm for bin packing”. J.Heuristics 2, 5-30.
[Falkenauer, 98] E. Falkenauer (1998), Genetic Algorithms for Grouping Problems. Wiley, New York.
[Goldberg, 89] D.E. Goldberg (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley.
[Greene, 00]W. A. Greene (2000). “Partitioning sets with genetic algorithms”. In J. Etheredge and B. Manaris (eds.), Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS-2000), 102-106. AAAI Press, Menlo Park, CA.
[Grimmet, 75] G. Grimmet and C. McDiarmid. (1975). “On Colouring Random Graphs,” Mathematical Proceedings of the Cambridge Philosophical Society 77, 313-324.
[Hartigan, 75] J. Hartigan (1975), Clustering Algorithms, John Wiley & Sons, New York.
[Hansen, 89] P. Hansen, B. Jaumard, and O. Frank. (1989), “Maximum sum-of-splits clustering.”, Journal of Classification, 6: 177-193.
[Holland, 75] J. H. Holland (1975), “Adaptation in Natural and Artificial Systems”, Ann Arbor: The University of Michigan Press.
[Johnson, 91] D. Johnson, C. Aragon, L. McGeoch, and C. Schevon. (1991). “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning”, Operations Research 39(3), 378-406.
[Jones, 91] D. R. Jones and M. A. Beltramo (1991), “Solving partitioning problems with genetic algorithms”, Proc. 4th Intnl. Conf. on Genetic Algorithms, eds. K. R. Belew and L. B. Booker,Morgan Kaufmann, San Francisco, 442-449.
[Smith, 85] D. Smith (1985), “Bin Packing with Adaptive Search,” In Proceeding of an International Conference on Genetic Algorithms and Their Application, 202-206.
[Syswerda, 89] G. Syswerda (1989), “Uniform Crossover in Genetic Algorithms”, In Proceedings of the Third International Conference on Genetic Algorithms, J. Schaffer (ed.), Morgan Kaufmann, 2-9. |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit