Digenes: genetic algorithms to discover conjectures about directed and undirected graphs
We present Digenes, a new discovery system that aims to help researchers in graph theory. While its main task is to find extremal graphs for a given (function of) invariants, it also provides some basic support in proof conception. This has already been proved to be very useful to find new conjectures since the AutoGraphiX system of Caporossi and Hansen (Discrete Math. 212-2000). However, unlike existing systems, Digenes can be used both with directed or undirected graphs. In this paper, we present the principles and functionality of Digenes, describe the genetic algorithms that have been designed to achieve them, and give some computational results and open questions. This do arise some interesting questions regarding genetic algorithms design particular to this field, such as crossover definition.
Code (0)
등록된 구현이 없습니다.
Tasks
MathSimilar Papers 제목 키워드 기반
Conjectures, Tests and Proofs: An Overview of Theory Exploration
A key component of mathematical reasoning is the ability to formulate interesting conjectures about a problem domain at hand. In this paper, we give a brief overview of a theory exploration system called QuickSpec, which…
Automated Theorem ProvingMathematical ReasoningMathematical conjecture generation using machine intelligence
Conjectures have historically played an important role in the development of pure mathematics. We propose a systematic approach to finding abstract patterns in mathematical data, in order to generate conjectures about ma…
Epigenetics Algorithms: Self-Reinforcement-Attention mechanism to regulate chromosomes expression
Genetic algorithms are a well-known example of bio-inspired heuristic methods. They mimic natural selection by modeling several operators such as mutation, crossover, and selection. Recent discoveries about Epigenetics r…
Proving Conjectures Acquired by Composing Multiple Biases
We present the proofs of the conjectures mentioned in the paper published in the proceedings of the 2024 AAAI conference [1], and discovered by the decomposition methods presented in the same paper.
Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement …
Deep Reinforcement Learningreinforcement-learningReinforcement Learning