Transcript PPT
fractals and patterns c o u r s e l a y o u t introduction molecular biology biotechnology bioMEMS bioinformatics bio-modeling cells and e-cells transcription and regulation cell communication neural networks dna computing fractals and patterns the birds and the bees ….. and ants i n t r o d u c t i o n computer scientists and biological systems Some limitations of today’s computers Computers crash! (OS usually to blame) The complexity of computer programmes is limited. The biggest programmes are less complicated than the simplest biological cell. Computers don’t self-replicate. They don’t self-organise. They don’t fix themselves. Computers are always right, but don’t always give the answers we want to know. Computers are unforgiving. potential implications Pretty soon computers will miniaturise to molecular scales. This transition will require noise/defect-tolerance self-assembly/self-organisation at the hardware level Software will need to cope with ever-increasing complexity. Can software self-organise? Self-evolving software is already in use both in traditional computing & robotics. Computer systems are networked in massive complex and dynamic architectures. Distributed approaches to managing networks/grids are being implemented. Specifically, ant algorithms are used in re-organising internet connectivity in the face of node failures. biological systems How do biological systems deal with these issues? Biological performance is dynamic flexible, adaptive robust, noise/defect tolerant the slime mould Is no more than a collective manifestation of ameoba It self-organised in the face of duress (food deprivation, pressure for self-preservation/self-replication). It is completely decentralised/distributed: There is no leader. Each amoeba follows simple rules. Individual amoebas are not reliable. The amoeba is adaptive; its function is contextdependent. Interactions among different levels of organisation The solution is defined in terms of the system at large (slime mould and its survival, not individual amoeba). fractals and patterns where are fractals star distribution in the galaxy rings of Saturn weather patterns trees geological formations vascular networks bioelectrical activity dendritic branching patterns found? rings of saturn fractals in biology Time series - EMG, ECG, EEG Codes - DNA Population distribution / Urban expansion Gait analysis Vessel distribution Diabetic retinopathy, lung bronchioli Pathology Classification of images Neurophysiology chaos or complexity Lorenz studied the weather John von Neumann built the first computer to control the weather. Von Neuman had overlooked the possibility of chaos, with instability at every point. Edward Lorenz saw a fine geometrical structure, order masquerading as randomness. Lorenz looked for a link between a-periodicity and unpredictability. lorenz attractor A snapshot of a chaotic process another attractor Lorenz’s Butterfly effect Lorenz submitted a paper in 1972, titled, “Predictability: Does the Flap of a Butterfly’s Wings in Brazil set off a Tornado in Texas?” In other words, sensitive dependence on initial conditions. definition of fractals Mandelbrot’s definition A fractal set is a metric space for which the Hausdorff-Besicovitch dimension D is greater than the topological dimension DT Fractals for the layperson Non Euclidean forms that are not easily described by Euclidean geometry A fractal set is characterised by an unlimited process of repeated transformations of an invariant geometrical form. mandlebrot mandlebrot fractal neuron Purkinje cell construction using recursive growth rule with fractal scaling self similarity fractals in biology brief history of fractals Although fractals were imagined over a century ago, they were not easily seen until decades age when high speed digital computers were readily available. It was not until the late 1970’s that the word fractal came into existence, coined by Benoit Mandelbrot. history continued Benoit Mandelbrot was born in Warsaw, Poland, on November 20, 1924. His family was Jewish and had originally come from Lithuania. In 1936, the growth of Nazi power led the Mandelbrot family to move to France. 1944 brought brought the liberation of France and the beginning of Mandelbrot’s university education by Gaston Julia and others. Mandelbrot worked at an IBM research center studying chaotic data in economics. He coined the term “fractal”. history continued As a child in France, Mandelbrot wondered how to use the smooth regularities of Euclidean shapes to model the complexity of the world he saw around him. Where were the circles in nature? Where were the parallel lines and infinite planes? He concluded “clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth...” (quoted in Briggs, 1992, p. 157) features of fractals 1. Self similarity (part is similar to the whole) 2. Fractional dimension 3. The result of infinite iterations 4. Too irregular to be described in traditional geometric language features of fractals self similarity Ferns seen previously Sierpenski triangle Koch snowflake Julia set Others other Julia Set fractals Mandelbrot Set fractals in nature fractals in nature fractals are... self-similar structures Sierpenski triangle and Koch snowflake Koch snowflake von Koch (1905) start with 2 shapes an initiator and a generator replace each straight line with a copy of the generator that copy should be reduced in size and displaced to have the same end points as the line being replaced Koch snowflake http://ecademy.agnesscott.edu/~lriddle/ifs/ksnow/ksnow.htm Koch snowflake fractals in computer graphics patterns properties of biological systems collective behaviour self-organisation, self-assembly and self-repair self-replication/reproduction Emergence: Organisation of structure & function is achieved by the system as a coherent, organic and autonomous entity, even though this whole consists of components which are themselves autonomous. The whole is greater than the sum of the parts. pattern formation in nature pattern formation in nature from pattern formation to computing? Conjecture If principles of pattern formation underlie the development of a fetus, why not the development of program or an electronic circuit? Computers need not be as complex as biological machines. Maybe by incorporating key principles from biology we can already achieve much improved functionality. First baby steps Pattern formation could be useful if… We can extract minimal principles to mimic it. We can harness the patterns for useful computation. Lindenmayer systems L-systems define sets of local rules for making patterns. Requirements: an initial term and a set of rules. A simple rewriting system: Rule: A AB would develop as follows: A … AB … ABB … ABBB… Notice: early strings are subcomponents of later strings. Also, strings are self similar at all levels. Adding rule B BA, gives: A … AB … ABBA … ABBA BAAB … ABBA BAAB BAAB ABBA … ABBA BAAB BAAB ABBA BAAB ABBA ABBA BAAB … ABBA BAAB BAAB ABBA BAAB ABBA ABBA BAAB BAAB ABBA ABBA BAAB ABBA BAAB BAAB ABBA … geometric rewriting systems Replace letters w/ geometries Grow pictures, not sentences… geometric rewriting systems Turtle graphics approach: Imagine a turtle that can only understand three commands: F (move forward a distanc e d, drawing a line); + (turn left through ao), - (turn right t hrough ao). Set d=1, a=90. Give turtle initial string of commands (say F-F-F-F). Then, apply set of rewrite rules again and again and again… Example rewrite rule: F F-F+F+FF-F-F+F (The resulting patterns will be examples of quadratic Koch islands) geometric rewriting systems from lines to trees To generate more life-like shapes First, we need a way of representing branches. To do this , Lindenmayer employs a bracketing notation: [ Before carrying on, push the current state of the turtle onto a the top of a pushdown stack (i.e., remember the current position and orientation of the turtle for later). ] Before carrying on, pop the state from the top of the stack and make it the current state of the turtle. This will often move the turtle to a different (earlier) part of the shape, or rotate it, or perhaps alter its state in some other way. How does stack system affect L-system’s behaviour? branching structures & self-similarity Imagine a simple L-System featuring brackets Initiator: F Rewrite Rules:F F [+F] [-F] F ; a=30o 0: F 1: F[+F][-F]F 2: F[+F][-F]F [+F[+F]-F]F] [-F[+F]-F]F] F[+F][-F]F 3: etc. Recursion + branching = tree-like structures branching structures & self-similarity Tree-like structures and other shapes that look the same on every scale, are called self-similar systems. These selfsimilar structures are simple examples of fractals. exploring simple L-systems It isn’t hard to discover initial states, rules, and constants which produce recognisably plant-like structures. However, when generalised to three dimensions, coupled with appropriate textures and colouration, and altered to include leaves, flowers, etc., L-systems have been used to generate some truly remarkable life-like images. s om e u n i f yi ng conc ept s /i ns pi ra tions Eliminate pre-imposed hierarchies, eliminate leaders Allow a decentralised (distributed) approach and parallelism Allow simple rules for cooperation among components Allow interactions among different levels of organisation Define solutions in terms of system-wide variables Computers need not be as complex as biological machines. By incorporating key principles we hope to achieve much improved functionality. pattern formation in nature how leopard gets its spots? (Murray, SciAm, March 88) pattern formation in nature pattern formation in nature t a i l s pattern formation in nature Size is important: it can’t be too small or to large to support spots. reaction-diffusion cause two coloured two coloured Valais goat machine produces distinctive wave patterns the birds and the bees what about the birds? Things that help us understand how living things work Flocking Simulation Simulated evolution Computational biology what’s the use? Living things are very successful. Harness that success for computational systems. People are used to interacting with living things. Make computational systems easy to use. drawing the right lessons It’s the shape of the wing, rather than the flapping, that enables controlled flight. the simple local rules What rules determine their individual behavior? Proximity - collision avoidance Mimicking - velocity matching Adapting to the environment - flock centering. s t u d y t h ei r b e h a v i o r .. . . . not always the same leader....... How close? Obstacles? and that means.... Collision avoidance .... pull away before they crash into one another. Velocity matching ... try to go about the same speed as their neighbors in the flock. Flock centering ... try to move toward the center of the flock as they perceive it. we do this when we’re driving ... cars or bikes PROXIMITY MIMICKING & ADAPTING cooperative group intelligence? Flocks of birds travel in an orderly fashion and yet avoid obstacles? http://members.ozemail.com.au/~dcrombie/project/applet.html . global dynamics from local agents THE FLOCK emergence Flocking is a particularly evocative example of emergence: where complex global behavior can arise from the interaction of simple local rules. interface and implementation …and the bees? .... and ants do ants follow rules? ants were closely studied… Southwest’s cargo & routing system profited from studying how ants behave The average flight was using only 7% of its cargo space; yet there was not enough space to accommodate cargo. THE STRATEGY: employees loaded the first flight going in the right direction. THE RESULT: employees spent a lot of time moving cargo around and filling aircraft needlessly. ants find the shortest path Ants find the most efficient routes to a food source. ants finding the shorter path return sooner. ants following the shorter path reinforce the odor – pheromones – on the shorter path ants communicate even shorter paths to groups or individuals in the ant colony, as the pheromones dissipate. but single ants? a single ant acts randomly… a colony of ants provides sustenance and defensive protection for the entire population… the ants combine to produce an effect that is much more than the sum of the parts. again global effects from local interactions. ??? food foraging in ant colonies A computer simulation of an ant colony performing an efficient search: Blue spot in the middle is an ant nest; other 3 spots represent food sources. Ants (red dots) use chemical signals (green) to find the shortest path to the food and alter their signals as the food is depleted. You may not like the idea of comparing humans to ants…. Norbert Weiner’s THE HUMAN USE OF HUMAN BEINGS 51 (1950): “The aspiration of the fascist for a human state based on the model of the ant results from a profound misapprehension both of the nature of the ant and of the nature of man.” But man has been compared to an ant for some time. Herbert Simon, THE SCIENCES OF THE ARTIFICIAL 25 (1969), described the ant: as a simple being and the path of an ant across a “windand wave-molded beach” as irregular and random but with a sense of direction - predicated upon the environment. And described man: “…viewed as a behaving system, [as] quite simple. The apparent complexity of his behavior over time is largely a reflection of the complexity of the environment in which he finds himself.” What’s so special about a swarm or colony? Three characteristics Flexibility – the colony can adapt to a changing environ ment. Robustness – even when one or more individuals fail, the group can still perform. Self-organization – activities are neither centrally located nor locally supervised. Th u s , t h e c l a s s i c t r av e li n g s a l e s m a n p r o b l e m The shortest route for a saleman to visit a specified number of cities (n) before he may return home….. He must try all the possible combinations of city-to-city connections. As the number (n) of cities increases, this exercise takes a prohibitively long time (as there are billions of route possibilities among just 15 cities (n = 15)). a n t o pt i mi za ti on : a n ea s i er ca lc u la ti on … . Computer Scientist Marco Dorigo of the Free University of Brussels, Belgium devised: A path optimization method, a virtual sales trip across a digital landscape, by which each artificial ant, or agent, hops from point to point on an electronic map and deposits the digital equivalent of pheromones. After the agent ants have completed their tours, the program sums up the result, and repeats. Guess what: the paths shorten with successive trials. so what did Southwest discover… It was better to send a package, at least initially, in the wrong direction. They slashed freight transfer costs by as much as 80%. Decreased the workload by as much as 20%. Reduced the overnight transfers. Cut back cargo storage and wages. Few planes are now filled with cargo. ant-colony optimum routing Ruud Schoonderwoerd, HP labs in Bristol, England: Help switching stations pass packets of information efficiently across telecommunications networks Antlike agents wander a network and report where they experience delays and for how long. With that information, the software then updates switching station routing tables to improve the network’s performance. a path around the world Ant colony optimization path some For want For want For want For want For want folklore Intermezzo of a nail, the shoe was lost; of a shoe, the horse was lost; of a horse, the rider was lost; of a rider, the battle was lost; of a battle, the kingdom was lost. swarm intelligence Definition Intelligence, predicated upon the ability to adapt, as the birds in flock did, thus arising from and enhanced by interactions between and among the individuals in the “swarm” swarm intelligence For purposes of swarm intelligence: two heads (or three) are better than one. no man (or woman) is an island! Intuitively, each of us believes that swarm intelligence is how we operate, collectively and cooperatively, dependent on mimicking the selected information we receive and varying it to fit the changing set of circumstances in which we find ourselves; in this way we adapt; some writers have argued that intelligence is the ability to adapt. swarm intelligence Groups show marginally better performance than solo performers – but why? more folk do better! can machines model what is intelligent? Minds process symbolic information, derive conclusions from premises, store information and recall it when it is appropriate … So can’t Computers do that too? when does artificial intelligence seem human? versus MAN MACHINE the Turing criterion If the keyboard user can’t tell by questions whether the computer’s responses were generated by a human or a machine, then the computer is considered intelligent. biomorphic computing biomorphic computing using biology to inform computational systems possible dimensions of biomorphic computing Small (nanotechnology) to large (modeling global ecosystems) Short (packet-switching based on ant foraging) to long (evolving virtual creatures) Similar to humans (social HCI) to different from humans (simulating the running motion of the Death’s Head cockroach) things that move like living things Robots (MIT Leg Lab, Stanford PolyPEDAL Lab, etc.) Simulations (video games, movies) things that think like living things Learning (speech recognition, pattern matching) Coordinated/cooperative behavior (robot soccer, flocking simulations) t hi n g s t h a t a d a p t t o c h a n g i n g c i r c u m s t a n c e s things that develop like living things