четверг, 3 мая 2012 г.

Exploring Chaos through Python and Tkinter


This relatively long entry describes some of my attempts to explore interesting stuff related to the origins of Chaos Theory. The experiments I describe here were carried out several decades ago, so I haven't invented something new, although I suppose that the stuff I show may encourage the reader to study the field on his own. 

While the first and the third parts focus on things related to Chaos Theory, some simple although nice math and, mainly, on the impression that this stuff made on me, the second part exposes code that I've written trying to achieve two goals. First, I actually wanted to do the metnioned experiments on my own, second, I tried to gain some experience with Tkinter python package for creating GUIs. Due to simplicity of the experiment I suppose that Part Two may be interesting only for those, who want to take a look on the simple interactions with Tkinter.

(In case you want just to see how complex can be the behavior of the simplest possible discrete chaotic systems, you may visit my site - there are some playable graphs)

Have a nice reading!

Part One

Several years ago being a first- or second-year undergraduate student I came across a reference to a book 'Chaos' by James Gleik. The name of the book was maybe the only thing I knew about it, although, combined with the fact that it is a popular piece of writing devoted to the mathematical theory, that was enough to attract my interest. I knew nothing about Chaos Theory except for the notion that it attempts to bring some measure of order to the things which seem perfectly disordered. In fact this sole idea was a point drawing my interest to the Chaos Theory and to the above piece of reading.

The printed version wasn't available for me when I discovered that it exists out there and I didn't like to read from computer screen (actually I still don't like to), but I haven't forgotten about it and preserved my interest to the subject till the moment this winter when I obtained an e-book reader, so 'Chaos' was the first book that I uploaded to my new gadget.

The book turned out to be worth waiting that long - I haven't felt disappointed even for a minute while reading it. Moreover I doubt that I would enjoy the book that much should I read it several years ago. Roughly speaking it is composed of the stories showing different scientists discovering some pattens of chaotic behaviour in their particular fields of study. Obviously all the stories appear to be linked together - at least by the means of Chaos Theory - the new science which was given birth by all these scientists. One such story describes the ecologists' attempts to mathematically model population dynamics. Their approach, outlined in the book, looks very simple - it suggests displaying the population size as a value varying (or measured) along discrete time intervals (say once per year) and the core idea is to introduce feedback. In terms of modelling population dynamics the existence of feedback means that the population size for some year (or another time interval being used) depends on it's size in the previous year. The scientists have chosen to describe this dependency in terms of very simple mathematical functions and were expecting to see simple behaviour as a result. To be precise they thought their model would either get to equilibrium or would oscillate between two points. The former means that population size stays the same from year to year while the latter suggests that there are two distinct sizes of population which show up cyclically one after another. However the result was quite surprising - the model turned out to be capable of producing complex behaviour - it could either follow a pattern more sophisticated than those described above or even fail to produce any pattern at all - that is behave in a way that looks absolutely random - and this happened despite the model's internal simplicity. This discovery impressed me ferociously and the simplicity of maths upon which the model is based encouraged me to explore the thing on my own.

For the purpose of studying strange behaviour of simple functions I should have choosen some computing programming environment like Mathcad or Octave or even simpler tool like Microsoft Excel - being able to define numeric sequences and to plot simple graphs would be enough. Despite the obvious simplictiy and efficiency of such an approach I've stepped another track. This semester I need to complete a small project which I've decided to do using Python programming language. The project requires some simple visualization and GUI stuff which I'am going to implement by means of Tkinter - a well-known python package intended for creating GUIs. So implementing a tool for displaying simple graphs seemed a perfect task in terms of getting acquainted with the GUI toolkit.

At this point it is evident that I've choosen the visualization approach to examine the complexity appearing from simple functions. That means I've decided to produce some numeric sequences representing the model's behaviour, plot the results and let my eyes capture some interesting stuff. Such a technique may be imperfect in terms of accuracy but it often helps a lot to develop a bit of understanding of the system being explored and enables discovering some patterns in it's behaviour. Finally it seems that producing graphs is the first thing any researcher would do having faced some new stuff.

I feel I should make one more clarification before turning to coding: the main purpose for implementing all the stuff that I will describe shortly was to get familiar with Tkinter tools - that's why I've choosen python and Tkinter for solving the task. Such a choice would definitely be an overkill should I pursue another goal. Even in case you use python for your dives into some simple math there are packages designed for plotting - I would recommend matplotlib package if you need one. So while this entry shows the wrong way of exploring math, it focuses on some very basic things related to python and interactions with GUI package.

Part Two

So here is the plan for our short and childish expedition to the field of Chaos Theory. First we are going to introduce simple convenience routines for turning functions (in math sense) into numeric sequences which are easy to plot. After that we'll implement a simple class intended for showing a graph for numeric sequence by means of Tkinter tools. Finally, having implemented our simple machinery, we will plot some graphs to notice an amazing variance in behaviour produced by very simple models.

Easy things first. Let's implement two different versions of our function-to-sequence routine. First one will treat input function as a classic function of one argument taking some x value as an input and producing corresponding y value as an output.

My extremely simple procedure takes startX and finishX arguments used to determine input value range. The range is combined with count argument to determine the step size which is difference between any two neighbouring input values. Using boundaries and step size the routine calculates input values and corresponding function values one by one. The latter are stored in a common list variable which is returned to the caller when the calculations reach the maximum argument value equal to xFinish.

The second version of the routine acts a little bit different. Being designed to treat it's first argument as an iterated function, binding next value to the previous one and capable of producing sequence of numbers this way, it requires neither the range of input values nor the stride. Still it needs to know where to start calculations - hence it takes a startX argument. Besides that we need to provide a count argument, telling the routine how long a sequence should it produce.

As you can see from the code above, on each iteration the procedure takes the last produced value and feeds it to the function to determine the next one which is then appended to a list of produced values. When the length of the list reaches the limit specified by count variable, the calculations are stopped and the entire sequence is returned to the caller. So far, so good.

Now when we are able to produce the numbers which we want to display it is definitely a perfect moment to learn how to draw some simple stuff using the Tkinter package - here comes the drawing fun.

First let us decide what precisely are we going to plot. I would like to simplify the task to focus on drawing stuff, although we should avoid oversimplifying. Luckily our tasks gives us a lot of room for simplification: the iterated functions that I will show are producing values lying between 0.0 and 1.0 (in case the initial value is in this same interval). That allows us to shrink the task to producing the plotter routines showing the same interval, hence we don't need to produce any scaling routines except for those mapping our [0.0, 1.0] range to some part of the screen. Now, when the clarification is made, let me explain what will we implement. 

Our simple plotter will be able to show simple graph of some numeric sequence. Each point of our graph will represent some member of our sequence with vertical coordinate representing the value of this member, and horizontal coordinate showing it's index. This way looking at the graph from the left to the right we'll be able to see how the system evolves from period to period. To improve understanding of such a graph we will also provide a simple grid along with some words. As you can see I am not going to show any user-interactions stuff now - you may explore it on your own if you wish to - believe me, Tkinter makes these things very simple.

Tkinter package includes lots of different widget types, and particulary the Canvas widget which suits our needs perfectly. It's main purpose is to allow coordinate-based drawing of simple primitives like lines, rectangles and arcs, although we will need only lines. We will organize our plotter code as a python-class and here is it's method responsible for drawing the grid by means of canvas widget:

It's only argument (self) shows us that it belongs to some class. The reference to Canvas widget is stored in the class instance variable 'canvas'. The first 4 calls to self.canvas.create_line(..) draw a simple green box around the plotting area. The left, right, lower and upper variables store the coordinates of the plotting area's boundaries - these are determined before the call to the DrawGrid(..) method. After drawing the plot boundaries the routine creates the grid itself - first horizontal lines and then vertical ones. Because we want these to be dashed we create a 'dashPattern' variable and pass it to canvas.create_line's 'dash' keyword argument. The 'dashPattern' is a simple list and in our particular case it states that 4 filled pixels of the line being drawn must be followed by 4 blank pixels. The last note here is that while the vertical grid stride is determined in place - right before drawing the horizontal lines of the grid - the horizontal stride is determined in a separate function:

The only purpose of devoting a function to this simple calculation is that the horizontal stride is also used while plotting the graph itself, thus the XStep(..) method allows us to decrease code duplication and avoid detaching the graph from the grid. 

Next we will show a simple info string saying what are the minimum and maximum values in our numeric sequence. This task is accomplished by the DrawLabels(..) method:

This simple two-liner first creates the info string and then shows it calling the Canvas widget create_text(..) method. Considering the text positioning, the coordinates of the upper left corner of the text are specified via the first tuple argument of create_text(..). Notice that vertical coordinate increases from top to bottom - that's why we specify text's vertical coordinate as a fraction of plotting area's upper boundary coordinate and still don't get stupid result. 

We've just provided routines for drawing a grid and some text, so we can't wait for implementing the method that will draw the graph. After seeing my DrawGrid(..) method you might have thought that it is quite simple to draw the graph - you are perfectly right. Here is the routine:

First we store the lines color and the gorizontal stride in local variables and then we simply draw the lines in a loop. Here I use Transform(..) method to get points vertical coordinate based on the corresponding number's value, while the point's horizontal coordinate is obtained by multiplying the points index by the horizontal stride value. The Transform(..) method is very simple - it just calculates the height multiplying the argument by the whole plotting range's height. The fact that vertical coordinate increases from top to bottom makes us subtract the above product from the lower boundary coordinate instead of adding them together: 

In fact we're finished with drawing. To complete our simple plotter class we only need to initialize all the instance variables we use and write the code that will call the above routines. Here's the method responsible for calculating the plotting are boundaries:

The calculations are pretty obvious, so I will just point out that self.sizeQuotient is a varible which determines how big a gap do we want to have between the plot and the window's borders. Another method is the one responsible for initializing Tk environment and creating canvas widget - this one is also short and straightforward:

First it calls the Tk() routine providing us with a root object. Each Tkinter application has such an object and uses it to create and manage widgets, provide user interactions and so on - roughly speaking, it represents the main window as well as the whole GUI application. After that we create a Canvas widget linked to the root object. Finally we bind all our routines together in the __init__ method of our class:

Although it is the longest method of the Plotter class, there is nothing complicated about it - we only store some arguments in instance variables and call the initialization and drawing routines. The last step involves packing our canvas and running the application's events loop. Packing means determining the widget's geometry, although from the Tkinter user's point of view it is performed via a simple call to the widget's pack() method - all the geometry management stuff runs behind the scenes. As for the main loop, the call to root's mainloop() method makes Tkinter show the widgets associated with the root window and take control of the application. In this state Tk watches the user's actions and calls the code linked to them if there is some.

Now if we want to plot some numeric sequence we just need to pass it to Plotter constructor and that will automatically bring up a window with the graph. (Note: I don't actually consider calling all the routines from the __init__ method a very good practice, although in our simple case it looks quite suitable and is barely able to cause any problems.)

Part Three

So now, having implemented some pretty simple tools, let us produce some images. First goes a plot for a classic y = 2.2x * (1 - x) function. I suppose everyone knows what does the corresponding parabolla graph looks like. Below you can see the code creating desired sequence and an instance of Plotter class. There is also an image of the window produced by this code - the graph looks precisely like something you could expect.

As you remember our initial purpose was to explore the behaviour of simple iterated functions. In fact the above function, if it is interpreted like an iterated one, may be considered a good approximation for modelling population dynamics. Let me explain the basic idea behind such a model: as you can see from the last graph the function outputs zero if it's argument is equal to 0.0 or 1.0. In terms of population size it means that if there are no animals in population (0.0) there won't be any on the next step. From the other side, if the population is too big (1.0) we can say that the available food is not enough to support it, and therefore it becomes extinct. Meanwhile, if the size lies somewhere between these boundaries the function outputs some non-zero value that may be considered the size of population on the next step. Here is a graph showing the behaviour of such a system and the code used to produce it:

The picture shows that our system falls to an equilibrium, meaning that the population stays the same. One could easily predict such a behaviour - it actually is frequently present in real populations of animals. Now let's introduce a slight change - we will only increase the function's quotient by 1.0 and see what happens. 

Here comes about quite a nice thing - we get a system that oscillates between two values (popullation sizes). While that's still a kind of behaviour that one could've expected from our simple quadratic function, the graph is at least more interesting than the first one, nevertheless let's not limit ourselves and try to produce something more interesting. Now it's even "easier" - we just increase the same quotient by 0.3 and here's what we get:

Isn't that fascinating? The plot shows that the last slight change to our extremely simple system made it oscillate between four different points, that is the period of oscillations is equal to 4 time periods (e.g. years). Note that we haven't changed the class of a function - we've just increased one numeric quotient and this slight change produced quite different behaviour. Here is the question: what will we see if the quotient is increased by another 0.3? You may have already captured the pattern suggesting that we will come to another period doubling and get a system that oscillates between 8 distinct values. Although the guess is nice, the thing looks quite different:

The behaviour shown in the graph above looks chaotic - at least for 200 steps plotted we can see no repetitions at all. It may mean either that the system oscillates with a period greater than 200, or that it behaves chaotically. In fact should we increment the quotient in lesser steps we would produce the systems that osciallate with periods of 8, 16 and so on - you may check this on your own. As for me, the difference between chaotic behaviour and oscillations with large periods is quite small in comparison with the simplicity of the model used to produce these graphs - the fascinating thing here is the amount of changes that we need to introduce to switch the behaviour of the model - increasing or decreasing one quotient by a fraction of 1 seems a very small modification. It becomes absolutely clear when one notices that the farther one goes increasing the quotient, the lesser is the size of the step required to achieve the next period doubling. 

On the other side, should we increase the quotient too much, the sequence becomes unbound and quickly goes to infinity - you can see this experimenting with a quotient of, say, 5.0. In fact you won't be able to produce any graph, because of python exception saying that the (absolute) value of the produced number is too large to be properly represented.

The complex behaviour shown by the last graph has to do with the thing called "sensitive dependence on initial conditions" which may be considered a central idea of Chaos Theory. Simply speaking, the term is used to describe a situation when the behaviour of a system strongly depends on the systems actual state and the minor, even unobserveable, change in the state may dramatically change the behaviour. Another experiment you could do to explore the idea involves changing the initial value for the fourth (the last one) sequence from 0.2 to another value in (0.0, 1.0) range - this way you may notice that the produced plot looks different from the figure #5.

The last note I should make is that the behaviour of our system haven't become absolutely random - we may still notice some common patterns, but there is no precise repetition - i.e. (during the observeable period of time) the system doesn't pass through the same state twice. So Chaos and Randomness are different things - while the latter prohibits precise predictions, the former does not, although such predictions require knowledge of the law governing the system and, besides that, the ability to precisely measure the system's current state. The requirement for a precise measurement is directly linked to the notion of "sensitive dependence on initial conditions" and is very hard to satisfy, because to escape the impact of "sensitive dependence" one needs to achieve infinite measurement precision - which must be infinitely hard to achieve. If it is not achieved (and in fact it isn't ever), the minimal difference between the actual state and the measured one may be large enough for actual behaviour to be completely different from the predicted one. So what's the difference between Randomness and Chaos now?

Some links

If you're interested in creating GUIs for python applications I strongly recommend that you check out the Tkinter page on python.org and this nice guide to Tkinter. If you only need to support your python programs with nice plots, then please follow the links to the matplotlib package page. These simple examples may be useful if you need some help understanding how to work with this powerful tool.

As for the Chaos book, here it is on amazon.com. You may also find the Wikipedia article about James Gleick - the author of the book - quite interesting.

Finally here is the link to github repository, containing all the code I describe in the entry.

Комментариев нет:

Отправить комментарий