Can genetic algorithms with the symmetric heuristic find the Ramsey number R(5,5)
المؤلف | Aija'am, Jihad Mohamad |
تاريخ الإتاحة | 2024-03-20T01:55:09Z |
تاريخ النشر | 2010 |
اسم المنشور | INFOS2010 - 2010 7th International Conference on Informatics and Systems |
المصدر | Scopus |
الملخص | Ramsey Theory studies the existence of highly regular patterns within a large system and proves that the complete disorder doesn't exist. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory. The Ramsey number R(m,n) is the smallest integer r such that a simple graph of r vertices has either a clique of size m or an independent set of vertices of size n as an induced subgraph. The evaluation of each Ramsey number is a combinatorial hard problem and only few numbers are currently known in spite of extensive research works carried out since more than six decades. In many cases, all we know is an upper and lower bound for very small values of the n and m. One of the most studied number is R(5,5) which is currently bounded by 43 ≤ R(5,5) ≤ 49. Many interesting research works have been carried out since 1989 to improve its lower bound without success. These works were based mainly on Genetic Algorithms, GAs. In this work, we discuss the application of a new genetic algorithm on R(5,5) in order to try to improve its lower bound from 43 to 44. Although, a graph solution on 43 vertices, G43, without neither a clique nor an independent set of vertices of size 5 couldn't be found, however, the proposed algorithm was able to build a G43 with only two cliques of size five. This shows clearly that we are close to a feasible solution and may be able to establish a new lower bound in the near future. The performance of our GA comes mainly from a new idea at the parent generation phase. This idea consists of obtaining first a chromosome solution for a graph of lower size Gi, and to use it as a starting point to generate the initial parent chromosomes for a graph of higher size Gi+1. These new chromosomes are then processed by the GA operations. This process is iterated staring from a graph on 36 vertices till the current graph on 43 vertices. We prove that the symmetric heuristic used by Exoo doesn't exist for all graphs of order higher than 42 associated with R(5,5)text. |
اللغة | en |
الناشر | IEEE |
الموضوع | Algorithms Cobminatorics Ramsey number |
النوع | Conference Paper |
الصفحات | - |
الملفات في هذه التسجيلة
الملفات | الحجم | الصيغة | العرض |
---|---|---|---|
لا توجد ملفات لها صلة بهذه التسجيلة. |
هذه التسجيلة تظهر في المجموعات التالية
-
علوم وهندسة الحاسب [2288 items ]