 |
|
Universiteit Leiden
Center for Natural Computing |
|
|
| Natural Computing Day |
Invitation
The Leiden Center for Natural Computing (LCNC) cordially invites you to
attend the Natural Computing Day which will take place in Leiden on
June 10, 1998 on the occasion of the official opening of LCNC.
The program for this day is as follows.
|
09.30-10.00 | Welcome |
|
10.00-10.30 | Official Opening of LCNC |
|
10.30-11.30 | Blaise Pascal Lecture
Prof. T. Head, SUNY at Binghamton, New York, U.S.A.
"DNA Computing - Its Beauty and Challenges" |
|
11.30-12.00 | Coffee/Tea |
|
12.00-13.00 | Prof. A. Salomaa, TUCS, Turku, Finland
"Lindenmayer and Watson-Crick. Impacts from Biology to
Language Theory" |
|
13.00-14.00 | Lunch |
|
14.00-15.00 | Prof. Z. Michalewicz, University of North Carolina at
Charlotte, U.S.A.
"How to Solve it? Evolutionary Approach" |
|
15.00-15.15 | Coffee/Tea |
|
15.15-16.15 | Prof. H.-P. Schwefel, University of Dortmund, Germany
"Evolutionary Computation: Yesterday, Today, and
Tomorrow" |
Free lunch is offered to those who will register for this event.
To register, please contact the secretary of LCNC,
Mrs. Marloes Boon-van der Nat, not later than June 8, 1998 (telephone:
+31-71-5277061, e-mail: marloes@wi.leidenuniv.nl, fax: +31-71-5276985,
Leiden University, LIACS, P.O. Box 9512, 2300 RA Leiden, The Netherlands).
We look forward to see you in Leiden on June 10.
The location for the meeting is room 174, Niels Bohrweg 1, Leiden.
For more information about this day you can contact:
Prof. Dr. J.N. Kok (e-mail: joost@wi.leidenuniv.nl, telephone: +31-71-5277057),
or Prof. Dr. G. Rozenberg (e-mail: rozenber@wi.leidenuniv.nl, telephone:
+31-71-5277067).
Abstracts
T. Head: DNA Computing - Its Beauty and Challenges
DNA computing sprang to the attention of the scientific world on November
11, 1994 with a publication in the journal "Science" by Leonard Adleman.
This seminal paper reported the `wet lab' solution of a small instance of
a classical computational problem (the Hamiltonian path problem). Large
instances of this problem are known to make heavy resource demands on
conventional computers. Adleman encoded the description of the problem
instance as a set of single stranded DNA molecules. In a test tube of
water he allowed the molecules to join (anneal) into double stranded
form. Each new elongated strand was permanently linked using an enzyme
called a ligase. The encoding had been planned to allow the molecules
representing the solution of the problem to be isolated from the total
contents of the test tube. Adleman's biomolecular computation succeeded in
finding the unique path that was the solution of the problem instance he
had chosen. Thus was born DNA computing - a mere three and a half years
ago. Now the governments of Japan and the United States each support
multi-university cooperating research groups that are carrying out
fundamental investigations concerning the potential of DNA computing.
These are high risk programs, but they may lead to revolutionary
developments. The practical concern is whether DNA computations can be
developed that will `scale up' to compete with conventional computing
systems. Optimistic assessments can be found in the literature that
express hope for improvements by many powers of ten in operations per
second, energy efficiency, and information storage density. With the
opening of the "Leiden Center for Natural Computing", with biomolecular
computing anticipated to play a major role, Leiden University is now on an
exciting adventure.
This introductory talk will consist of (1) the design for a DNA solution
of a tiny Hamiltonian path problem in the Adleman style; (2) introductory
remarks concerning DNA splicing systems; and (3) comments concerning
additional successful DNA computations that have been carried out in other
laboratories.
A. Salomaa: Lindenmayer and Watson-Crick.
Impacts from Biology to Language Theory
The study of Lindenmayer systems, originating from developmental biology,
has been traditionally very strong in the theory of formal languages.
Recently new vistas have been opened by models of DNA computing.
Traditional aspects of language theory have been combined with issues
dealing with Watson-Crick complementarity. The lecture is both an
introduction to DNA computing and a discussion of recent technical work on
its language-theoretic aspects, notably the so-called Watson-Crick DOL
systems and the computational universality due to complementarity. Most
of the lecture will be understandable to a broad audience.
Z. Michalewicz: How to Solve it? Evolutionary Approach
During the last three decades there has been a growing interest in
algorithms which rely on analogies to natural processes. The emergence of
massively parallel computers made these algorithms of practical interest.
The best known algorithms in this class include evolutionary programming,
genetic algorithms, evolution strategies, simulated annealing, classifier
systems, and neural networks.
During the talk we discuss a subclass of these algorithms - those which
are based on the principle of evolution (survival of the fittest). In
such algorithms a population of individuals (potential solutions)
undergoes a sequence of unary (mutation type) and higher order (crossover
type) transformations. These individuals strive for survival: a selection
scheme, biased towards fitter individuals, selects the next generation.
After some number of generations, the program converges - the best
individual represents near-optimum solution. A common term, recently
accepted, refers to such techniques as `evolutionary computation' methods.
We will address a few basic questions connected with evolutionary
computation methods: why do we need them? what are they? what are their
basic components? how can they solve problems? how can they be extended?
H.-P. Schwefel:
Evolutionary Computation - Yesterday, Today, and Tomorrow
The idea of imitating life and especially its generative process, called
evolution, on computers has at least two roots and two aims. One root is
the observation that living beings often are quite well adapted to their
environment, the other is the hypothesis that this is the result of an
evolutionary process over generations of many individuals. One aim thus
is to mimic the rules of that game of life in order to gain iterative
amelioration procedures, the other is to derive insight into the mimicked
organic evolution process by analyzing the algorithms' behavior. At
least three strains of Evolutionary Algorithms [EAs] must be mentioned
today: Genetic Algorithms [GAs], Evolutionary Programming [EP], and
Evolution Strategies [ESs]. Born in the Sixties and grown up to remarkable
extensions as well as many successful applications, the three
instantiations of one basic idea have maintained substantial differences,
a fact which is in line with the principle of requisite variety for
allowing further improvements. The similarities and differences in
modeling mutation, recombination, and selection operators as well as some
successful adoptions of further evolutionary principles will be
pinpointed.
