16 Search Results for "Rowe, Jonathan E."


Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
Tight Bounds for Blind Search on the Integers

Authors: Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.

Cite as

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2008.1348,
  author =	{Dietzfelbinger, Martin and Rowe, Jonathan E. and Wegener, Ingo and Woelfel, Philipp},
  title =	{{Tight Bounds for Blind Search on the Integers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{241--252},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348},
  URN =		{urn:nbn:de:0030-drops-13486},
  doi =		{10.4230/LIPIcs.STACS.2008.1348},
  annote =	{Keywords: }
}
Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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}
}
Document
Runtime Analysis of a Simple Ant Colony Optimization Algorithm

Authors: Frank Neumann and Carsten Witt

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


Abstract
Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in a finite amount of time. We present the first runtime analysis of a simple ACO algorithm that transfers many rigorous results with respect to the expected runtime of a simple evolutionary algorithm to our algorithm. In addition, we examine the choice of the evaporation factor, which is a crucial parameter in such an algorithm, in greater detail and analyze its effect with respect to the runtime.

Cite as

Frank Neumann and Carsten Witt. Runtime Analysis of a Simple Ant Colony Optimization Algorithm. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{neumann_et_al:DagSemProc.06061.8,
  author =	{Neumann, Frank and Witt, Carsten},
  title =	{{Runtime Analysis of  a Simple Ant Colony Optimization Algorithm}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--17},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06061.8},
  URN =		{urn:nbn:de:0030-drops-5928},
  doi =		{10.4230/DagSemProc.06061.8},
  annote =	{Keywords: Randomized Search Heuristics, Ant Colony Optimization, Runtime Analysis}
}
  • Refine by Author
  • 6 Rowe, Jonathan E.
  • 4 Arnold, Dirk V.
  • 4 Witt, Carsten
  • 2 Auger, Anne
  • 2 Jansen, Thomas
  • Show More...

  • Refine by Classification

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

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 9 2006
  • 7 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail