Experiments of Intelligent Algorithms on Ramsey Graphs

International Arab Journal of Information Technology (IAJIT)

Maryam Madani¹  Shadpour Mallakpour² 

[1] Department of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Department of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. IranDepartment of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$;Department of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Nanotechnology and Advanced Materials Institute, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Department of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. IranDepartment of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Nanotechnology and Advanced Materials Institute, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Nanotechnology and Advanced Materials Institute, Isfahan University of Technology, Isfahan 84156-83111, I. R. IranDepartment of Chemistry, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$Nanotechnology and Advanced Materials Institute, Isfahan University of Technology, Isfahan 84156-83111, I. R. Iran$$

关键词: Metaheuristic;    hybrid algorithms;    optimization;    combinatorics;    Ramsey numbers. ;   

DOI  :  

学科分类：计算机科学（综合）

来源: Zarqa University

【 摘 要 】

Ramsey numbers are known to be hard combinatorial problems that have many important applications including number theory, algebra, geometry, topology, set theory, logic, ergodic theory, information theory, and theoretical computer science.  The evaluation of Ramsey numbers using intelligent algorithms has been extensively studied in the last decades and only few numbers are currently known. Almost all of these methods failed to find the exact value of Ramsey numbers as they are over constraints problem. They have succeeded only to improve some upper and lower bounds of these numbers. In this work, we have tested the following intelligent algorithm: Backtracking, local search, tabu search and simulated annealing on some extremely hard instances of Ramsey numbers namely R (5, 9) - 120 and R (6, 8) - 121. As we failed to solve these hard instances using the previous techniques, we decided to combine them together in a hybrid metaheuristic algorithm and succeeded to generate the expected solutions. This new hybrid algorithm seems efficient and promising. It can be applied also on different combinatorial problems even if deep mathematical properties of the problems' domain are not on hand. Keywords: Metaheuristic, hybrid algorithms, optimization, combinatorics, Ramsey numbers.  Received November 19, 2005; accepted April 5, 2006

【 授权许可】

Unknown