Complex Adaptive Systems Workshop
Spring 1999
3004 Black Engineering
10:00-11:30 Wednesday
Contact:
Dan
Ashlock
(danwell@IASTATE.EDU)
Seminar Dates, Click for Information
Jan. 13th
No meeting the first week.
Jan. 20th
Speaker:
Daniel Ashlock
Title: Possible Worlds.
Reading: Chapter 1 of Possible Worlds by John Casti.
Abstract
This talk will intropduce complex adaptive systems in the context of
modeling and of Casti's book. This session will also serve as an
introduction to the complex adaptive systems group for new members.
Jan 27th
CANCELED
Feb. 3rd
Speaker:
Daniel Ashlock
Title: Evolutionary computation for texture synthesis.
Reading: Texture Synthesis with Tandem Genetic Algorithms.
Available in .pfd or
postscript.
Abstract
We describe an attack on the problem of synthesizing textures. We
use a pair of genetic algorithms to create fast one-pass generating
algorithms for five black-and-white textures. This is done using only
examples of those textures as input. The key to success is the use of a
pair of genetic algorithms and a special structure called a foot
pattern. The first genetic algorithm locates a foot pattern
(roughly a viewpoint) from which the example texture looks the least
random. The second genetic algorithm then uses this viewpoint as the
core of a fitness function that captures some part of the notion "this
texture looks like that one". With this "looks like" fitness
function available, the second genetic algorithms synthesizes a
non-parametric partially ordered Markov model for the example texture.
The genetic algorithms used are themselves are quite standard, but their
pairing and the fitness functions used yield a breakthrough in
black-and-white texture synthesis. Extending these techniques to gray
scale and colored textures is possible, but suffers from combinatorial
explosion. Suggestions on overcoming the difficulties of such extension
appear in the discussion of future work.
Feb. 10th
Speaker: Jennifer Freeman
Title: Catching Chickens with Genetic Algorithms
Reading: Solving a Real-World Problem Using an Evolving
Heuristically Driven Schedule Builder, by Emma Hart, Peter Ross, and
Jeremy Nelson.
Abstract
This work addresses the real-life scheduling problem of a Scottish
company that must produce daily scheduled for the catching and
transportation of large numbers of live chickens. The problem is
complex and highly constrained. We show that it can be successfully
solved by division into two subproblems and solving each using a
separate genetic algorithm(GA). We address the problem of whether
produces locally optimal solutions and how to overcome this. We extend
the traditional approach of evolving a "permutation+schedule builder" by
concentrating on evolving the schedule builder itself. This results in
a unique schedule builder being built for each daily scheduling problem,
each individually tailored to deal with the particular features of that
problem. This results in a robust, fast, and flexible system that can
cope with most of the circumstances imaginable at the factory. We also
compare the performance of a GA approach to several other evolutionary
methods and show that population-based methods are superior to both
hill-climbing and simulated annealing in the quality of solutions
produced. Populations-based methods also have the distinct advantage of
producing multiple, equally fit solutions, which is of particular
importance when considering the practical aspects of the problem.
Feb. 17th
Speaker: Veronica Dark
Title: Sex Differences in Jelousy in Evolutionary
and Cultural Perspective
Reading:Sex Differences in Jelousy in Evolutionary
and Cultural Perspective
Abstract
As predicted by models derived from evolutionary psychology, men within
the United States have been shown to exhibit greater psychological and
physiological distress to sexual than to emotional infidelity of their
partner, and women have been shown to exhibit more distress to emotional
than to sexual infidelity. Because cross-cultural tests are critical
for evolutionary hypotheses, we examined these sex differences in three
parallel studies conducted in the Netherlands (N=207), Germany(N=200),
and the United States(N=224). Two key findings emerged. First, the sex
differences in sexual jealousy are robust across these cultures,
providing support for the evolutionary psychology model. Second, the
magnitude of the sex difference varies somewhat across cultures - large
for the United States, medium for Germany and the Netherlands.
Discussion focuses on the evolutionary psychology of jealousy and the
sensitivity of sex differences in the sexual sphere to cultural
input.
Feb. 24th
Speaker: Jack Dekker
Title: The Behavior of Weedy Foxtail (Setaria spp.) Seeds: A complex
adaptive system in need of Model Formalization (and maybe a game)
Reading: Emergent Weedy Foxtail Seed Germinability Behavior
Please check my WWW site and the Weedy Foxtail pages:
Abstract
The weedy foxtails (Setaria spp.) are an important group of invasive,
colonizing plants whose biogeographical distribution is a function of
many contributing sources. For the last 10 years I have discovered many
clues about why this humble plant is so successful throughout the
temperate regions of the world. These insights include the
characterization of its population genetic structure, seed bank
dynamics, embryogenesis and seed genesis, and the discovery of three
"lost" Ph.D. theses from the 1960's. In this paper I present an outline
of weedy foxtail behavioral, habitat and morphological clues in support
of four hypotheses: (1) the biogeographical distribution of weedy
foxtails (Setaria spp.) is an evolutionary adaptation to changing soil
oxygen-water availability; (2) seed germination is regulated by the
functional qualities of the transfer aleurone layer of the placental
pore; (3) seed dormancy is reversible, and is induced when oxygen-water
availability and uptake is restricted; and (4) seed germination and
seedling emergence occurs when adequate amounts of oxygen-water reach
the embryo. These observations reveal that dormancy induction,
after-ripening, and germination of the seed may all be unified by the
regulation of oxygen entry into the embryo by the transfer aleurone
cells of the placental pore. Weedy foxtail seed behavior is an emergent
property arising from contributions within the plant organizational
hierarchy (i.e. species-group through sub-cellular sites). Foxtail seed
behavior is also an emergent property of the interaction amongst the
three different foxtail genomes and their tissues (i.e. embryo,
endosperm, caryopsis coat, aleurone transfer cells and the hull).
In this seminar I will very briefly present an overview of foxtail
seed behavior for non-biologists. I will spend the majority of the time
discussing my weed system as a complex adaptive system, including
thoughts about general properties of CAS's. I will present my ideas
about hierarchical interactions leading to observed behavior, and ideas
about information creation, transformation and utilization by the seed.
I am especially interested in attracting partners to this model
formalization process. I will also suggest comprehensive and discrete
approaches including algorithms, models and maybe even a game (WeedPatch
tm). I even have one good engineering problem (passive water
oxygenation and wicking by seed envelopes).
Mar. 3rd
Speaker: Hui-Hsien Chou
Title: Cellular Automata, Self-Replication and Artificial Life
Reading:Problem Solving During Artificial Selection of Self
Replicating Loops(Physica D293-312)
Abstract
Past cellular automata models of self-replication have generally done
only one thing: replicate themselves. However, it has recently been
demonstrated that such self replicating structures can be programmed to
also carry out a task during the replication process. Past models of
this sort have been limited in that the "program" involved is copied
unchanged from parent to child so that, so that each generation of
replicants is executing exactly the same program on exactly the same
data. Here we take a different approach in which each replicant
receives a distinct partial solution that is modified during
replication. Under artificial selection, replicants with promising
solutions proliferate while those with failed solutions are lost. We
show that this approach can be successfully applied to solving an
NP-complete problem, the satisfiability problem. Bounds are given on
the cellular space size and time needed to solve a given problem, and
simulations demonstrate this approach works effectively. These and
other recent results raise the possibility of evolving self-replicating
structures that have a simulated metabolism or that carry out useful
tasks.
Mar. 10th
Speaker:
Kirk Moloney
Title: Modeling Ecological Systems in Space:
Complex?->Yes ::: Adaptive?->Not Yet!
Reading: Plant-Herbivore Coevolution in a Spatially
and Genetically Explicit Model.
Abstract
Recently, ecologists have focused a great deal of attention on
understanding the impact of spatial relationships on ecological
processes. This has been aided by the ready availability of cheap
computing resources. With these, it has been possible to develop models
examining the complex interactions that occur within a spatial context.
One shortcoming, however, is that the traits of the organisms in
ecological models are fixed and do not change in response to varying
model conditions. There have only been a few attempts (one that I know
of) to develop ecological models that allow evolutionary (adaptive)
changes to take place. In my presentation, I will first outline the
state of the art in modeling spatial interactions in ecological systems
and then will discuss the potential insights to be gained from allowing
model organisms to adapt within these systems.
Mar. 17th
Spring Break
Mar. 24th
Speaker:
Kirk Moloney
Title: Modeling Ecological Systems in Space:
Complex?->Yes ::: Adaptive?->Not Yet!
Reading: Plant-Herbivore Coevolution in a Spatially
and Genetically Explicit Model.
Abstract
Kirk is continuing his talk from before break. This week he will
present his own stuff.
March 31st
Speaker:
Dan Ashlock
Title: Fusing greedy and genetic algorithms.
Reading: Evolutionary Algorithms for Vertex Cover by Isaac K. Evans
Abstract
Genetic algorithms and greedy algorithms are both examples of algorithms
that represent a prayer to luck that one can solve a problem without
having to do too much work. In this talk I will explain what greedy
algorithms are and then give a technique for fusing greedy algorithms
with genetic algorithms. In a sense the genetic algorithms gene will
reprioratize the moves made by the greedy algorithm.
Apr. 7th
Speaker: Paul D. Mitchell
Title: Stochastic Metamodels to Simplify Complex Adaptive Systems:
The Case of Corn Rootworm and Transgenic Agriculture
Reading: None
Abstract
Stochastic metamodels are potentially useful tools to simplify models of
complex adaptive systems and thus facilitate their integration into
higher-order complex systems. Application of the technique to a model
of the agriculturally important corn rootworm complex adaptive system
provides an illustration.
A general overview of the corn rootworm complex adaptive system and
resistance management problems associated with new transgenic cultivars
(e.g. Bt corn) begins the presentation. A stochastic dynamic population
model of the complex system is described, then a stochastic metamodel of
this model is described. Integration of this metamodel into a
higher-order system is illustrated by utilizing the metamodel for
economic analysis of various corn rootworm management techniques. The
presentation ends with discussion of linking the population model with a
genetics model to create a complex adaptive system model to analyze
resistance management problems associated with transgenic cultivars.
Apr. 14th
Speaker:
Roger D. Maddux,
Department of Mathematics
Title: Experiments in the Composition of Music by Computer.
Reading:Experiments in the Composition of Music by Computer.
Abstract
Four experimental programs illustrating various compositional ideas
were written for this project. One of them, called HCM, implements
rules for composing one- and two-voiced melodies. The rules are taken
from the first two chapters of The Craft of Musical Composition, Vol.2,
by Paul Hindimith.
HCM uses an evolutionary algorithm.
Apr. 21st
Speaker:
Leigh Tesfatsion
Title: Further market power effects in evolutionary labor
markets with adaptive search.
Reading: Handout.
Abstract
My talk will report on further market power experiments for an
agent-based computational economics (ACE) model of a labor market. In
particular, I will be extending the experimental results presented in
my Fall 1998 CAS Workshop talk by considering an important additional
treatment variable -- market concentration. I have also changed the
fitness measure from average to total payoffs, and I will comment on
the effects of this change.
In my ACE labor market framework, employers repeatedly choose and
refuse worksite partners on the basis of continually updated expected
returns, engage in worksite interactions modelled as prisoner's
dilemma games, and evolve their worksite strategies over time. Three
treatment factors affecting the relative market power of workers and
employers are experimentally varied: market structure (two-sided,
partially fluid, and endogenous type); market concentration (ratio of
workers to employers); and market capacity (ratio of potential work
offers to potential job openings). Particular attention will be
focused on experimentally determined correlations between market power
and the formation of contractual networks among workers and employers,
and between contractual network formation and the types of worksite
interactions and welfare outcomes that these conrtracrtual networks
support.
Apr. 28th
Speaker:
David Fogel, Vice President and Chief Scientist,
Natural Selection Incoporated.
Title: Complex Systems and Complex Solutions.
Reading: None.
Abstract
Complex systems continue to gain increasing attention. Of particular
interest is our ability to model complex adaptive systems in the hope
that we can predict the behavior of those systems, and perhaps even
control that behavior. An important consideration relates to the
sensitivity of these models. Examples will be offered indicating that
some well-accepted models of complex adaptive systems are not robust to
modifications, even when these are offered to increase the fidelity of
the models. The results provide an impetus for reconsidering our
confidence in models of complex adaptive systems.