17 Search Results for "Arnold, Dirk V."

Document
Research
DOI: 10.4230/TGDK.4.1.3
Semantically Reflected Programs

Authors: Eduard Kamburjan, Vidar Norstein Klungre, Yuanwei Qu, Rudolf Schlatte, Egor V. Kostylev, Martin Giese, and Einar Broch Johnsen

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract
This paper addresses the dichotomy between the formalization of structural and the formalization of executable behavioral knowledge by means of semantically lifted programs, which explore an intuitive connection between imperative programs and knowledge graphs. While knowledge graphs and ontologies are eminently useful to represent formal knowledge about a system’s individuals and universals, programming languages are designed to describe the system’s evolution. To address this dichotomy, we introduce a semantic lifting of the program states of an executing progam into a knowledge graph, for an object-oriented programming language. The resulting graph is exposed as a semantic reflection layer within the programming language, allowing programmers to leverage knowledge of the application domain in their programs during execution. In this paper, we formalize semantic lifting and semantic reflection for a small imperative programming language, SMOL, explain the operational aspects of the language, and consider type correctness and virtualization for runtime program queries through the semantic reflection layer. We illustrate semantic lifting and semantic reflection through a case study of geological modeling and discuss different applications of the technique. The language implementation is open source and available online.
Cite as

Eduard Kamburjan, Vidar Norstein Klungre, Yuanwei Qu, Rudolf Schlatte, Egor V. Kostylev, Martin Giese, and Einar Broch Johnsen. Semantically Reflected Programs. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 3:1-3:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{kamburjan_et_al:TGDK.4.1.3,
  author =	{Kamburjan, Eduard and Klungre, Vidar Norstein and Qu, Yuanwei and Schlatte, Rudolf and Kostylev, Egor V. and Giese, Martin and Johnsen, Einar Broch},
  title =	{{Semantically Reflected Programs}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:52},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.3},
  URN =		{urn:nbn:de:0030-drops-256884},
  doi =		{10.4230/TGDK.4.1.3},
  annote =	{Keywords: Knowledge Graphs, Ontologies, Object-Oriented Modelling, Imperative Programming Languages, Reflection, Type Safety}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.34
The Lambda Calculus Is Quantifiable

Authors: Valentin Maestracci and Paolo Pistone

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
In this paper we introduce several quantitative methods for the lambda-calculus based on partial metrics, a well-studied variant of standard metric spaces that have been used to metrize non-Hausdorff topologies, like those arising from Scott domains. First, we study quantitative variants, based on program distances, of sensible equational theories for the λ-calculus, like those arising from Böhm trees and from the contextual preorder. Then, we introduce applicative distances capturing higher-order Scott topologies, including reflexive objects like the D_∞ model. Finally, we provide a quantitative insight on the well-known connection between the Böhm tree of a λ-term and its Taylor expansion, by showing that the latter can be presented as an isometric transformation.
Cite as

Valentin Maestracci and Paolo Pistone. The Lambda Calculus Is Quantifiable. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maestracci_et_al:LIPIcs.CSL.2025.34,
  author =	{Maestracci, Valentin and Pistone, Paolo},
  title =	{{The Lambda Calculus Is Quantifiable}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.34},
  URN =		{urn:nbn:de:0030-drops-227911},
  doi =		{10.4230/LIPIcs.CSL.2025.34},
  annote =	{Keywords: Lambda-calculus, Scott semantics, Partial metric spaces, B\"{o}hm trees, Taylor expansion}
}
Document
DOI: 10.4230/DagSemProc.08051.1
08051 Abstracts Collection – Theory of Evolutionary Algorithms

Authors: Dirk V. Arnold, Anne Auger, Carsten Witt, and Jonathan E. Rowe

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
From Jan. 27, 2008 to Feb. 1, 2008, the Dagstuhl Seminar 08051 ``Theory of Evolutionary Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Dirk V. Arnold, Anne Auger, Carsten Witt, and Jonathan E. Rowe. 08051 Abstracts Collection – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.08051.1,
  author =	{Arnold, Dirk V. and Auger, Anne and Witt, Carsten and Rowe, Jonathan E.},
  title =	{{08051 Abstracts Collection – Theory of Evolutionary Algorithms}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.1},
  URN =		{urn:nbn:de:0030-drops-15242},
  doi =		{10.4230/DagSemProc.08051.1},
  annote =	{Keywords: Evolutionary Computation, Theory of Evolutionary Algorithms}
}
Document
DOI: 10.4230/DagSemProc.08051.2
08051 Executive Summary – Theory of Evolutionary Algorithms

Authors: Dirk V. Arnold, Anne Auger, Jonathan E. Rowe, and Carsten Witt

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
The 2008 Dagstuhl Seminar "Theory of Evolutionary Algorithms" was the fifth in a firmly established series of biannual events. In the week from Jan. 27, 2008 to Feb. 1, 2008, 47 researchers from nine countries discussed their recent work and trends in evolutionary computation.
Cite as

Dirk V. Arnold, Anne Auger, Jonathan E. Rowe, and Carsten Witt. 08051 Executive Summary – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.08051.2,
  author =	{Arnold, Dirk V. and Auger, Anne and Rowe, Jonathan E. and Witt, Carsten},
  title =	{{08051 Executive Summary – Theory of Evolutionary Algorithms}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.2},
  URN =		{urn:nbn:de:0030-drops-14812},
  doi =		{10.4230/DagSemProc.08051.2},
  annote =	{Keywords: Evolutionary Algorithms, Theory of Evolutionary Algorithms}
}
Document
DOI: 10.4230/DagSemProc.08051.3
A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem

Authors: Jun He, Yuren Zhou, and Xin Yao

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
Constraints exist in almost every optimization problem. Different constraint handling techniques have been incorporated with genetic algorithms (GAs), however most of current studies are based on computer experiments. An example is Michalewicz's comparison among GAs using different constraint handling techniques on the 0-1 knapsack problem. The following phenomena are observed in experiments: 1) the penalty method needs more generations to find a feasible solution to the restrictive capacity knapsack than the repair method; 2) the penalty method can find better solutions to the average capacity knapsack. Such observations need a theoretical explanation. This paper aims at providing a theoretical analysis of Michalewicz's experiments. The main result of the paper is that GAs using the repair method are more efficient than GAs using the penalty method on both restrictive capacity and average capacity knapsack problems. This result of the average capacity is a little different from Michalewicz's experimental results. So a supplemental experiment is implemented to support the theoretical claim. The results confirm the general principle pointed out by Coello: a better constraint-handling approach should tend to exploit specific domain knowledge.
Cite as

Jun He, Yuren Zhou, and Xin Yao. A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{he_et_al:DagSemProc.08051.3,
  author =	{He, Jun and Zhou, Yuren and Yao, Xin},
  title =	{{A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.3},
  URN =		{urn:nbn:de:0030-drops-14822},
  doi =		{10.4230/DagSemProc.08051.3},
  annote =	{Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis}
}
Document
DOI: 10.4230/DagSemProc.08051.4
Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases

Authors: Boris S. Mitavskiy and Chris Cannings

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
The evolutionary algorithm stochastic process is well-known to be Markovian. These have been under investigation in much of the theoretical evolutionary computing research. When mutation rate is positive, the Markov chain modeling an evolutionary algorithm is irreducible and, therefore, has a unique stationary distribution, yet, rather little is known about the stationary distribution. On the other hand, knowing the stationary distribution may provide some information about the expected times to hit optimum, assessment of the biases due to recombination and is of importance in population genetics to assess what's called a ``genetic load" (see the introduction for more details). In this talk I will show how the quotient construction method can be exploited to derive rather explicit bounds on the ratios of the stationary distribution values of various subsets of the state space. In fact, some of the bounds obtained in the current work are expressed in terms of the parameters involved in all the three main stages of an evolutionary algorithm: namely selection, recombination and mutation. I will also discuss the newest developments which may allow for further improvements of the bounds
Cite as

Boris S. Mitavskiy and Chris Cannings. Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{mitavskiy_et_al:DagSemProc.08051.4,
  author =	{Mitavskiy, Boris S. and Cannings, Chris},
  title =	{{Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases}},
  booktitle =	{Theory of Evolutionary Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.4},
  URN =		{urn:nbn:de:0030-drops-14845},
  doi =		{10.4230/DagSemProc.08051.4},
  annote =	{Keywords: Genetic algorithms, Markov chains, stationary distribution, lumping quotient}
}
Document
DOI: 10.4230/DagSemProc.08051.5
N-gram GP: Early results and half-baked ideas

Authors: Nicholas Freitag McPhee and Riccardo Poli

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
In this talk I present N-gram GP, a system for evolving linear GP programs using an EDA style system to update the probabilities of different 3-grams (triplets) of instructions. I then pick apart some of the evolved programs in an effort to better understand the properties of this approach and identify ways that it might be extended. Doing so reveals that there are frequently cases where the system needs two triples of the form ABC and ABD to solve the problem, but can only choose between them probabilistically in the EDA phase. I present the entirely untested idea of creating a new pseudo-instruction that is a duplicate of a key instruction. This could potentially allow the system to learn, for example, that AB is always followed by C, while AB' is always followed by D.
Cite as

Nicholas Freitag McPhee and Riccardo Poli. N-gram GP: Early results and half-baked ideas. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{mcphee_et_al:DagSemProc.08051.5,
  author =	{McPhee, Nicholas Freitag and Poli, Riccardo},
  title =	{{N-gram GP: Early results and half-baked ideas}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.5},
  URN =		{urn:nbn:de:0030-drops-14838},
  doi =		{10.4230/DagSemProc.08051.5},
  annote =	{Keywords: Genetic programming, estimation of distribution algorithms, linear GP, machine learning}
}
Document
DOI: 10.4230/DagSemProc.08051.6
Runtime Analysis of Binary PSO

Authors: Dirk Sudholt and Carsten Witt

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

Abstract
We investigate the runtime of the Binary Particle Swarm Optimization (PSO) algorithm introduced by Kennedy and Eberhart (1997). The Binary PSO maintains a global best solution and a swarm of particles. Each particle consists of a current position, an own best position and a velocity vector used in a probabilistic process to update the particle's position. We present lower bounds for a broad class of implementations with swarms of polynomial size. To prove upper bounds, we transfer a fitness-level argument well-established for evolutionary algorithms (EAs) to PSO. This method is then applied to estimate the expected runtime on the class of unimodal functions. A simple variant of the Binary PSO is considered in more detail. The1-PSO only maintains one particle, hence own best and global best solutions coincide. Despite its simplicity, the 1-PSO is surprisingly efficient. A detailed analysis for the function Onemax shows that the 1-PSO is competitive to EAs.
Cite as

Dirk Sudholt and Carsten Witt. Runtime Analysis of Binary PSO. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{sudholt_et_al:DagSemProc.08051.6,
  author =	{Sudholt, Dirk and Witt, Carsten},
  title =	{{Runtime Analysis of Binary PSO}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.6},
  URN =		{urn:nbn:de:0030-drops-14800},
  doi =		{10.4230/DagSemProc.08051.6},
  annote =	{Keywords: Particle swarm optimization, runtime analysis}
}
Document
DOI: 10.4230/DagSemProc.06061.1
06061 Abstracts Collection – Theory of Evolutionary Algorithms

Authors: Dirk V. Arnold, Thomas Jansen, Jonathan E. Rowe, and Michael D. Vose

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
From 05.02.06 to 10.02.06, the Dagstuhl Seminar 06061 ``Theory of Evolutionary Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Dirk V. Arnold, Thomas Jansen, Jonathan E. Rowe, and Michael D. Vose. 06061 Abstracts Collection – Theory of Evolutionary Algorithms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.06061.1,
  author =	{Arnold, Dirk V. and Jansen, Thomas and Rowe, Jonathan E. and Vose, Michael D.},
  title =	{{06061 Abstracts Collection – Theory of Evolutionary Algorithms}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.1},
  URN =		{urn:nbn:de:0030-drops-6009},
  doi =		{10.4230/DagSemProc.06061.1},
  annote =	{Keywords: Evolutionary algorithms, evolutionary computation, theory}
}
Document
DOI: 10.4230/DagSemProc.06061.2
06061 Executive Summary – Theory of Evolutionary Algoritms

Authors: Dirk V. Arnold, Thomas Jansen, Jonathan E. Rowe, and Michael D. Vose

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
The 2006 Dagstuhl Seminar ``Theory of Evolutionary Algorithms'' carried forward a series of Dagstuhl seminars that started in 2000 and has become an established event in the community. In the week from from 05.02.2006 to 10.02.2006, 56 researchers from 12 countries discussed their recent work and recent trends in evolutionary computation.
Cite as

Dirk V. Arnold, Thomas Jansen, Jonathan E. Rowe, and Michael D. Vose. 06061 Executive Summary – Theory of Evolutionary Algoritms. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:DagSemProc.06061.2,
  author =	{Arnold, Dirk V. and Jansen, Thomas and Rowe, Jonathan E. and Vose, Michael D.},
  title =	{{06061 Executive Summary – Theory of Evolutionary Algoritms}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.2},
  URN =		{urn:nbn:de:0030-drops-5995},
  doi =		{10.4230/DagSemProc.06061.2},
  annote =	{Keywords: Evolutionary algorithms, evolutionary computation, theory}
}
Document
DOI: 10.4230/DagSemProc.06061.3
A Mathematical Modelling Technique for the Analysis of the Dynamics of a Simple Continuous EDA

Authors: Marcus Gallagher and Bo Yuan

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
We describe a mathematical model for the infinite-population dynamics of a simple continuous EDA: UMDAc. Using this model, it is possible to numerically generate the dynamics of the algorithm on a fitness function of known form. The technique is compared with existing analysis and illustrated on a number of simple test problems. The model is also used to examine the effect of adding an amplification constant to the variance parameter of the UMDAc model.
Cite as

Marcus Gallagher and Bo Yuan. A Mathematical Modelling Technique for the Analysis of the Dynamics of a Simple Continuous EDA. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gallagher_et_al:DagSemProc.06061.3,
  author =	{Gallagher, Marcus and Yuan, Bo},
  title =	{{A Mathematical Modelling Technique for the Analysis of the Dynamics of a Simple Continuous EDA}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.3},
  URN =		{urn:nbn:de:0030-drops-5940},
  doi =		{10.4230/DagSemProc.06061.3},
  annote =	{Keywords: Estimation of Distribution Algorithms}
}
Document
DOI: 10.4230/DagSemProc.06061.4
A New Quartet Tree Heuristic for Hierarchical Clustering

Authors: Rudi Cilibrasi and Paul M. B. Vitany

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
We present a new quartet heuristic for hierarchical clustering from a given distance matrix. We determine a dendrogram (ternary tree) by a new quartet method and a fast heuristic to implement it. We do not assume that there is a true ternary tree that generated the distances and which we with to recover as closeley as possible. Our aim is to model the distance matrix as faithfully as possible by the dendrogram. Our algorithm is essentially randomized hill-climbing, using parallellized Genetic Programming, where undirected trees evolve in a random walk driven by a prescribed fitness function. Our method is capable of handling up to 60--80 objects in a matter of hours, while no existing quartet heuristic can directly compute a quartet tree of more than about 20--30 objects without running for years. The method is implemented and available as public software at www.complearn.org. We present applications in many areas like music, literature, bird-flu (H5N1) virus clustering, and automatic meaning discovery using Google.
Cite as

Rudi Cilibrasi and Paul M. B. Vitany. A New Quartet Tree Heuristic for Hierarchical Clustering. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{cilibrasi_et_al:DagSemProc.06061.4,
  author =	{Cilibrasi, Rudi and Vitany, Paul M. B.},
  title =	{{A New Quartet Tree Heuristic for Hierarchical Clustering}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.4},
  URN =		{urn:nbn:de:0030-drops-5985},
  doi =		{10.4230/DagSemProc.06061.4},
  annote =	{Keywords: Genetic programming, hierarchical clustering, quartet tree method}
}
Document
DOI: 10.4230/DagSemProc.06061.5
How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?

Authors: Boris S. Mitavskiy and Jonathan E. Rowe

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
The state space of the Markov chain modelling an evolutionary algorithm is quite large especially if the population space and the search space are large. I shell introduce an appropriate notion of "coarse graining" for such Markov chains. Indeed, from the mathematical point of view, this can be called a quotient of a Markov chain by an equivalence relation over the state space. The newly obtained Markov chain has a significantly smaller state space and it's stationary distribution is "coherent" with the initial large chain. Although the transition probabilities of the coarse-grained Markov chain are defined in terms of the stationary distribution of the original big chain, in some cases it is possible to deduce interesting information about the stationary distribution of the original chain in terms of the quatient chain. I will demonstrate how this method works. I shell also present some simple results and open questions.
Cite as

Boris S. Mitavskiy and Jonathan E. Rowe. How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mitavskiy_et_al:DagSemProc.06061.5,
  author =	{Mitavskiy, Boris S. and Rowe, Jonathan E.},
  title =	{{How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.5},
  URN =		{urn:nbn:de:0030-drops-5964},
  doi =		{10.4230/DagSemProc.06061.5},
  annote =	{Keywords: Markov chains, Evolutionary algorithms, coarse graining quotients of irreducible Markov chains, concentration on the uniform populations}
}
Document
DOI: 10.4230/DagSemProc.06061.6
On Complexity of Optimized Crossover for Binary Representations

Authors: Anton Eremeev

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
We consider the computational complexity of producing the best possible offspring in a crossover, given two solutions of the parents. The crossover operators are studied on the class of Boolean linear programming problems, where the Boolean vector of variables is used as the solution representation. By means of efficient reductions of the optimized gene transmitting crossover problems (OGTC) we show the polynomial solvability of the OGTC for the maximum weight set packing problem, the minimum weight set partition problem and for one of the versions of the simple plant location problem. We study a connection between the OGTC for linear Boolean programming problem and the maximum weight independent set problem on 2-colorable hypergraph and prove the NP-hardness of several special cases of the OGTC problem in Boolean linear programming.
Cite as

Anton Eremeev. On Complexity of Optimized Crossover for Binary Representations. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{eremeev:DagSemProc.06061.6,
  author =	{Eremeev, Anton},
  title =	{{On Complexity of Optimized Crossover for Binary Representations}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.6},
  URN =		{urn:nbn:de:0030-drops-5932},
  doi =		{10.4230/DagSemProc.06061.6},
  annote =	{Keywords: Genetic Algorithm, Optimized Crossover, Complexity}
}
Document
DOI: 10.4230/DagSemProc.06061.7
On Turing complete T7 and MISC F--4 program fitnes landscapes

Authors: William B. Langdon and Riccardo Poli

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

Abstract
We use the minimal instruction set F-4 computer to define a minimal Turing complete T7 computer suitable for genetic programming (GP) and amenable to theoretical analysis. Experimental runs and mathematical analysis of the T7, show the fraction of halting programs is drops to zero as bigger programs are run.
Cite as

William B. Langdon and Riccardo Poli. On Turing complete T7 and MISC F--4 program fitnes landscapes. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{langdon_et_al:DagSemProc.06061.7,
  author =	{Langdon, William B. and Poli, Riccardo},
  title =	{{On Turing complete T7 and MISC F--4 program fitnes landscapes}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.7},
  URN =		{urn:nbn:de:0030-drops-5956},
  doi =		{10.4230/DagSemProc.06061.7},
  annote =	{Keywords: Genetic programming}
}
  • Refine by Type
  • 17 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 6 2008
  • 9 2006

  • Refine by Author
  • 5 Rowe, Jonathan E.
  • 4 Arnold, Dirk V.
  • 4 Witt, Carsten
  • 2 Auger, Anne
  • 2 Jansen, Thomas
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 TGDK
  • 15 DagSemProc

  • Refine by Classification
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Modeling and simulation
  • 1 Software and its engineering → Object oriented languages
  • 1 Theory of computation → Lambda calculus
  • 1 Theory of computation → Program semantics

  • Refine by Keyword
  • 3 Evolutionary algorithms
  • 3 Genetic programming
  • 2 Markov chains
  • 2 Theory of Evolutionary Algorithms
  • 2 evolutionary computation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact