Just imagine, you attend a course in Korean for 14 weeks and must then give a lecture to an audience of Korean experts about the special features of grammatical exceptions in this same language. The situation that three ETH Zurich students from the Computer Engineering and Networks Laboratory (D-ITET) experienced recently in Tours, France, must have felt rather like that. The budding electrical engineers Samuel Gähwiler, Mathias Karlsson and Matthias Egli presented their own first scientific paper at the Eighth International Conference on Artificial Evolution. Even though a few months previously they had neither any idea of artificial evolution nor any experience in presentations to international experts. Mathias Karlsson, who had accepted this task, beams and recalls that “It was a rather special feeling.” This story has one particularly remarkable feature: not merely the fact that students at the Bachelor stage submit their own paper and survive the official review process, but on top of that they are also awarded a prize for their work. Samuel Gähwiler explains with a laugh that “Many of those present were astonished when they learned that we are still at the start of the degree programme.”

A demanding optimisation problem

Their paper originated from a student project. The task that the total of twelve participants were set at the start of the semester was quite trivial at first glance: they were asked to develop software to construct a tower of building blocks. However, what was wanted was not just any old design. On the contrary, the program was required to build a tower of 20 or 50 blocks projecting by the maximum overhang beyond a table edge without collapsing. Eckart Zitzler, Assistant Professor for System Optimisation at D-ITET, explains that “It involved a highly sophisticated optimisation problem that is also representative for many practical design problems – regardless of whether they concern the design of computers, engines or bridges. A pre-condition was that the task had to be solved by using what is known as an evolutionary algorithm. In principle this imitates natural evolution. The latter can be regarded as the solution to an optimisation problem in the sense that it is used by living organisms to achieve continuous adaptation to the prevailing environmental conditions through selection, mutation and recombination. According to Zitzler, “We were set the task of imitating this process in relation to tower building.”

Thus their task was to develop an algorithm that starts by generating a population of blocks, chooses a proportion of them by selection, and modifies these by mutation and recombination in such away that ultimately they form the optimum tower. For simplicity the space is limited to two dimensions. The students split into three groups: the first dealt with the algorithm, the second with the section of the program that checked the stability of the tower after each intermediate step, and the third worked on the graphical presentation of the entire concept. They met together once a week for a joint meeting also attended by their supervisors Tim Hohm and Stefan Bleuler. Hohm recalls that “The greatest difficulty for the students was to move from the concept to the implementation.” They sometimes underestimated the fact that many things can still go wrong in spite of an apparently perfect design.

Excluding the impossible

Nevertheless the group had mastered their task well. Theoretically with 50 blocks a maximum overhang of about 3.28 block lengths should be achievable. The students reached 2.97 and had thus discovered an algorithm approximating very closely to the optimum. The crucial points lay in representing and operationalising the selection and variation. Representing the blocks by X and Y co-ordinates in two-dimensional space leads to the problem that the blocks can be pushed into one another. The tower would be stable, but of course in reality it is impossible for blocks to overlap. Eckart Zitzler explains that “The students had to consider how they could exclude such cases either from the outset or afterwards.” They found a very elegant solution: only the X co-ordinates of the blocks are taken into account in the calculation, but in addition attention is also paid to the sequence in which they are stacked to form a tower. They fall down from the top to the bottom, as it were, and thus always end up one on top of another but never inside one another.

A learning effect at many levels

The group also found suitable solutions to operationalise the selection and variation. The selection is based on a random algorithm. Mutation is imitated by changing the X position of an individual block, for which there are two variants: either only that single block is shifted, or alternatively all the blocks lying on top of it are moved as well. For recombination in the context of evolution, portions of blocks are cut off by computation and reassembled in a different way. The students subsequently recreated the best tower that they were able to generate in this way, using real wood blocks – and a lot of glue. Samuel Gähwiler explains “Of course we cannot build as perfectly as the computer. Even the surface of the blocks is too irregular for that.” He invested five to ten hours each week in the project, but says it was worthwhile because it had a large learning effect. Mathias Karlsson also says that “The concept of an evolutionary algorithm was a big question mark before that, but now at least I understand the basic idea.” However, he says the main benefit came from working in a team, to which they were rather unaccustomed until then and which was occasionally nerve-wracking. Samuel Gähwiler recalls with a sigh that “Sometimes we had to spend a long time in tedious discussions.” Nonetheless he never had any doubts about investing even more time in writing a scientific paper after completing the student project in the three-way team. He says it was “A wonderful opportunity as a third semester student.”