The problem with true random changes to the algorithm is that most of the resultant mutated algorithms have some deadly fault that makes it unsuitable as a proof of work.
I was thinking about that too, but maybe it's not a big deal that sometimes there will exist 'shortcuts'?
Most weaknesses in algorithms are discovered by humans, and if a human can find a flaw within the 10-minute blocktime, that's no problem at all, because human PoW beats every other distribution scheme, so they deserve the block-reward.
But even if that analysis could be automated: it becomes PoW on itself. Miners still have to choose between how much CPU power (and time) they spend on analyzing it first, as all the 'dumb' miners already started mining that block. Maybe that would cause some kind of race between the two, and as long as that race lasts 10 minutes on average, all will be fine.
Also it may lead to people trying to steer the next function into functions it can do better than competition.
If the choice for the algorithm depends on the hash of the previous block, I cannot see how anyone could steer the next function?