The Baldwin Effect

Often in nature there seem to be a connection between learning and evolution. Some traits that are inherited today seem to first have been passed from parent to child by learning. First it was thought that genes actually could change as the result of learning, this is called Lamarckism, today we know this is not the case. The genes are the same through the life of an organism.

So how does it happen that learnt traits can enter the genome. It is really not that strange. If a behaviour starts to spread among a group of individuals and parents teach this behaviour to their children those children more adept at that behaviour will have a slight advantage. This is called the Baldwin effect.

This is interesting because when designing an evolutionary algorithm this should be accounted for. Introducing learning and teaching could have beneficial effects on the fitness landscape. The fitness of an organism should not be calculated on the genes but on the phenotype. Allowing the phenotype to change, by learning or by physically adapting, during it's life allows the genes to express their potential. The genes can be more general in their expression, you don't need a gene that says 'this creature climb trees' but instead say 'this creature is agile', 'this creature is strong' and 'this creature has claws'. The tree climbing part is part of the behaviour that is passed by learning and the physical traits increases the ability to fulfill that behaviour.

Introducing a phenotype gives other benefits. You want the genes to behave well during crossover but at the same time you want a fitness to be calculated from the genes in an easy way. Crossover works best when genes that cooperate is close in the genome. They want to get passed as a bundle. So allowing genes to be able to move within the genome, called transposition and occurs in real cells during recombination, allows genes that cooperate to move together and so increasing the chance that they will get passed together. And when you allow genes to move around it is often beneficial to introduce the concept of a phenotype that is easier to use for matching the organisms against each other.

Stirling meets Wankel

I have already talked about the Wankel engine. The beauty of one rotor spinning in the same direction all the time. The Wankel engine normally works by combustion though. This makes a quite inefficient use of fuel as the fuel doesn't burn optimally during combustion. The Wankel construction further worsens this by the shape of the combustion chamber, making Wankel engines consume even more fuel than their crank engine counterparts.

But there exist a different type of engine that makes much better use of the fuel. I am thinking about the Stirling engine or air engine as it was called by Stirling himself when he invented it 1816. This engine works by converting a temperature difference into rotational enegy. The basic principle is that a gas that is heated expands and a gas that is compressed increases in temperature. One part of the engine is hot and the other cold. Gas is expanded in the hot part and decompressed in the cold part. This construction usually make Stirling engines quite large as they need big cooling radiators.

The Wankel engine's drawback regarding fuel consumption and the bulkiness of the Stirling can maybe be overcome by combining them. We may not see Stirling engines in cars as the sole provider of energy but it could be used when acceleration is not needed. During constant speed on the highway for example. Stirlings have been used to great success in submarines where their quiet running and less need of oxygen is great benefits.

Some work has been done to fuse these two designs together. The QuasiTurbine and the Trochilic engine are good examples how the future may look like. I think there is much more to do in this field.

Wriggling on a hook

A worm of unit length is caught on a hook. He can only move in the plane i.e not in three dimensions. He can not exert any momentum against the hook which means that his center of gravity always will be on the vertical line from the hanging point to the ground. Suppose now he wriggles around as much as he can.

What is the area covered by the worm during his wriggling?

A value for the area and a short description of how you found it will suffice as an answer. Solve this puzzle and you will enter the "Fields of Gold" hall of fame together with Pooh (who solved the first cornfield puzzle and the fuse burning puzzle) and future master puzzle solvers.

Male and Female Issues

When two singles decides to move in together in a new apartment they usually have to decide who's stuff goes were. Who's TV are we going to use, who's dinner table and so on. Some of the stuff got to go to the landfill. Two hard heads may never be able to decide, they just love their stuff too much.

Funny thing is that solving that problem may just have been the cause of it! Bear with me, that sentence will clear up in a moment.

The first cells with cytoplasmic genes(genes not in the nucleus), had to solve exactly this problem,who's mitochondria are we going to use when we merge. Both cells are very eager to share and recombine their nucleus but what to do with the stuff that comes along.

The solution to this problem may very well be the introduction of gender. The female brings the cytoplasmic genes and the male has to ditch his. This is very plausible because there is a huge cost for having two or more genders. Having several genders means that you have to find a suitable partner when you want to have kids. Just mating with anyone would sure be easier. From an evolutionary perspective gender makes it harder to pass on the genes. There must be a huge benefit, and that may very well be the ability to have symbionts inside the cell.

Free the Red Queen

When you design an evolutionary algorithm(EA) you are approaching evolution in a different way than how evolution works in nature. Nature doesn't use evolution to solve a problem, evolution is an inherent property of life.

This difference is very apparent when you consider parasites and co-evolution in general. In nature parasites are something bad that organisms need to be able to counter. Matt Ridley devised the Red Queen hypothesis with regard to this. The Red Queen concept is taken from Alice in Wonderland in which Alice meets the Red Queen. The Red Queen is running as fast as she can all the time. The unfortunate Queen is under the assumption that she must run as fast as she can in order to stand still. This is how evolution works in nature. There are several levels of evolution. You have to be able to survive and counter the static effects of nature. Secondly you have to be able to cope with the changing effects, you have to be able to adapt. Thirdly it is beneficial to be able to adapt to adapting counterparts like parasites. You see the point, this reasoning never stops and we are facing the same problem as the Red Queen. Evolution guides us to be able to better take advantage of and counter, evolution.

So designing an EA you have to design an artificial environment. The easiest way is to have a static environment. The function measuring the fitness is set beforehand and is equal from generation to the next. The next stage is to introduce competition among individuals in the population. This is good if you don't have a good understanding about what the goal actually is, but you know that there must be a best way to do it, like playing a game of chess. Here many designers of EA meet a tough challenge. They see that their population converge too fast. After a while all the individuals look the same and only mutations can make progress to better fitness. This is very suboptimal. So how can you keep you artificial population diverse?

Enter the Red Queen. You introduce parasites. Here parasites are good, they force the population to be diverse. The parasites quickly adapt to the host population and prey on the majority. If one parasite evolves that is able to prey on a major sub-population his children will have much easier to find suitable hosts and so they have a clear benefit.

Introducing parasites makes the fitness landscape change. Parasites are able to make valleys less deep and mountains less high in an ever changing way. They can never really turn the landscape inside out but they can make it much easier for sub-populations to escape a local minima and they keep the whole population from settling in one valley.

So, should you introduce the parasites in the same way as you design the fitness landscape? Ideally no. In nature the parasites appear just by themselves because the Red Queen is loose. Co-evolution sometimes give rise to symbiosis like in the case of the mitochondria and sometime give rise to parasites. Ideally you should set the Red Queen free.

Burn the fuse

I have gotten a hint that my puzzles have been to analytical so far. So by the following puzzle I hope I can engage the more natural numbered readers.

You have two separate cords of dynamite fuse. Both cords will take one hour each to burn but they don't burn at even rate i.e. half a cord won't necessarily take half an hour to burn.

How should you burn the fuses to measure 45min?

Solution: Found by Pooh. See comments.

Is the coin about to flip?

Today I became aware of that my blog was linked to by someone I didn't know. I got curious of course and looked it up. The site was about flippism, that didn't make me any wiser. But looking deeper I found the key and I felt really good about it.

Looking around a bit more I found out that flippism seems populated by Icelanders. Now I felt even better being an avid reader of the Icelandic sagas. When I was younger I spent one month driving around Iceland looking up placed from the sagas. I met a professor in archeology there and tried to get him to talk about the sagas and the remains, unfortunately he was not into flippism and didn't even acknowledge that the location of Bergthorsknoll was known, the earth moves he said. I found it on the map though and I was not disappointed by the view there, just beautiful.

Driving around Iceland was adventurous. I was driving a Ford Escort which had never seen anything but paved roads. As I had set my mind on going to Snaefellsjökull I had to take the car out on the gravel. It didn't take long before the gas tank had sustained to much punishment. Gasoline started to leak out and I had to rush back to civilization consuming 1 gallon a mile.

During my high school years earning the epithet of 'flippig' was good. 'Flippig' is a Swedish word which I don't have a good translation for but it was assigned to the somewhat uncontrollable and creative. Seems like there is a connection there. So far I'm only on the watching list but who knows, maybe I will finally reach the realm of flippism.

Spinning triangle

Most engines today use the piston and crankshaft system. Explosions in the cylinders make the crankshaft turn. Is it possible to construct an engine without a crankshaft? There is one very neat design, the Wankel engine. It doesn't have pistons but instead just one rotor formed like a Reuleaux triangle. This shape is by the way the solution to the second cornfield puzzle. It is a curve of constant width. You can construct such curves from any odd edged equal sided polygon, Britain had some 20p and 50p coins that had these shapes. They had the neat property that slot machines could recognize the width easily while the coins contained less metal than a circular coin of the same width.

The neat thing about the Wankel engine is that intake, expansion,compression and exhaust happens in different parts of the housing allowing the rotor to turn continuously. A gear in the middle of the rotor turn the drive shaft. Mazda seems determined to make it practical and their Renesis engine looks very promising. I hope we will see more development of this beautiful engine in the future.

Our common friend

Animals, plants and fungi have a common friend. Inside our cells is the remnant of another creature. This little friend provides us with power, converts the food we eat to ATP which is a molecule the cell can use when energy is needed. This friend contains it's own DNA and has it's own protein plant.

Sometime in the distant past two different cells bonded. One cell absorbed the other by endocytosis and allowed it to live inside it. The symbiosis was very successful and gave rise to most of the advanced life forms we see today.

I'm talking about the mitochondrion. It divides by itself outside of the normal cell cycle, it basically lives it's own life inside the cell. This means that the mitochondrial DNA is not inherited in the same way as the nucleus DNA. We humans get our mitochondria from our mothers. Their genes mutate and evolve and allows us to study our maternal heritage. This shows us that all living humans descend on the female side from a woman living at about 150000 years ago, sometimes called mitochondrial Eve.

The interesting thing is that the genes of the mitochondria compete in the same way as the nucleus genes. What happens when genes compete? The genes are selfish as Richard Dawkins puts it. All genes try to be the one that gets passed on to the next generation. Some do it the honest way by being good and doing something useful and some try to fool the system. An interesting thing about the mitochondrial genes is that they do not compete on the same terms as the nucleus genes as they only gets passed on the female side. Being in a male is not useful for a mitochondrial gene, it can never be passed on from a male.

So here is a radical idea. In a very selfish sense it would make sense for such a gene to cause male homosexuality. If present in a mother the gene would be passed along to all grandchildren. As we humans inherit wealth this would increase the chances for the grandchildren as they don't have to share the wealth with offspring from the male siblings of their mothers.

Searching a tree

What games are interesting to us? They should not be too easy and not too hard. By that I mean, if it's too easy one player would always win, if it is too hard nobody would have any clue were to move. Examples of too easy games are abundant as many games for children are in this category. Too hard games are not around as nobody finds them interesting.

A grown up playing Nim with a child finds it quite boring as he knows what to do to win while the child still finds it interesting. We say that the game of Nim is solved. For the general version of Nim with several piles there exists a nice theory for how to play it perfectly. Nim is solved in the strong sense which mean that we know how to play the game perfectly from every possible position.

Some games are weakly solved. Weakly solved means that a player can win the game if the game is played from it's starting position. Played in this way many positions never arise and can still be unknown.

There exists some games were it's known who will win the game but no one knows how to play it that way, Hex is such a game. These are called ultra-weakly solved.

How do you go about solving a game? One way is to list all possible positions and just test them if they are winning, loosing or draws. This technique only works on very simple games as harder games contain just too many possible positions. Solving harder games you need to search the game tree.

So, how do you search a game tree effectively. You need to prune the tree as you go along. There is the common alpha-beta search method which has the advantage that it does not take much memory. It is also fairly good at pruning the tree. You should also take advantage of how the game is structured. In the game of Qubic for example there are lots of forcing sequences. For this type of games the Proof Number(PN) search method is very rewarding.

Since these search algorithms were derived computers have become faster and we have almost solved Checkers and Othello by using the same techniques. But what is needed to go further. Chess seems out of reach and Go is not even on the horizon. When Victor Allis solved Go-Muko and Connect 4 he incorporated a great amount of knowledge into the algorithm. For harder games this is too troublesome, there is just too much knowledge needed.

I think game solving could actually teach us about what we mean by knowledge. Somehow we must make the computer gather this knowledge as he runs through the game tree and we must provide algorithms where this is possible. Ideally the algorithm is independent of the problem. PN-Search is very close. It tries to prove nodes. At every moment it chooses the most proving node and tries to prove it. If that fails it reevaluates the tree and possibly chooses another node to prove.

Here I see a parallel to how mathematics works. You set up definitions and prove theorems. The theorems sometimes lead to dead ends, mathematics which never get used. Sometimes several theorems from different branches of mathematics converge and you can prove something new, the recent proof of Fermat's Last Theorem is a good example of this. To prove something it's not always best to go straight for he solution, actually taking side paths is sometimes beneficial. Who decides which proofs we should go after? Some conjectures are deemed more important than others, like the Riemann hypothesis. Why is this hypothesis important? Because even as it's not proven, mathematics has continued to develop assuming it is true. As time passes more and more conjectures are depending on it. Why have the Riemann hypothesis been given this treatment? Because it is very likely true, and it is powerful. Maybe this technique could be something to consider designing a new tree search algorithm?