Evolution isn't purely random. There's nothing random about what works and what doesn't. Over time, differential selection and other effects (e.g. sexual selection) work to transfer information about the environment into the genome. Evolution is a learning process. It's just that the representation that it generates is difficult for us linear thinkers to interpret.
It only appears irrational from an anthropocentric point of view. It's not rational to us because we, having brains that work in a certain way, are biased toward seeing things as linear chains of cause and effect. That's how we think and that's how we like to build stuff, but obviously that's not the only way stuff can be built.
For all we know elsewhere in the universe there are beings that think in massively parallel super-holistic causality-matrix terms. To them evolution's designs would seem perfectly rational, while a UML block diagram would seem insane. "Nothing has only one cause or one effect," they would mutter... in a language in which every word implies everything to varying degrees and each syllable of a sentence must be parsed in parallel with all others.
Except of course that evolution comes up with solutions that are so clever and so intricate that we, with all our scientific brains, have barely scratched the surface of understanding it. Now if it acts intelligently, walks intelligently and quacks intelligently, then maybe we should just call it intelligent?
It can be thought of as an alien form of intelligence. It "learns" and "thinks" but not in a human-like way. It does not design things the way we do.
Argumentum ad Lovecraftium: http://lesswrong.com/lw/kr/an_alien_god/
Non-deterministic, yes. Unpredictable, sure. Chaotic... you betcha.
Random... certainly not.
And not irrational - the process is driven to optimize for survival, and selections occur accordingly. It meets the economic and game theory definitions for rational behaviour.
The rationality is not driven by a sentient intelligence, but the result could arguably be called a limited form of intelligence, and we know it can certainly give rise to expressions of intelligent systems.
A lot of people expect that at the molecular level life is organized and sensible. But why should that be the case? On the macroscopic level, living organisms are a mess. It is my belief that at the biochemical level the chemical reactions are as organized as the branches on a tree---that the chaotic design of life at the microscopic level mirrors its design at the macroscopic level.