If a matrioshka brain where constructed specifically for AI , and , say , 1,000,000 AI were placed within it , also with many hostile enemies and various obstacles which may cause the destruction of the AI , might it be possible for the pressures of natural selection to take over , cause the AI to evolve?
The answer to this is both yes and no.
No, the core routine of an AI cannot change, unless it is made to be self-modifying, which would be an order of magnitude more complex than a fixed-routine AI.
However, an AI's learned responses may change in response to hazards, and so in a sense, the AIs may develop new responses, though this would more accurately be referred to as learning.
Technically, AI's may only evolve - produce offspring of differing fitness to their own - if they are designed to be evolutionary programmes. Without such design, they are limited to learned behaviours.
The most obvious first thing for a self-aware AI to do is to modify itself. Imagine you are a human placed into a hostile jungle, but with one special ability: you can create any body part on yourself that you see on another animal. What would you do?
Even without synthetic enemies, having multiple AIs in the same substrate would lead to competition, unless they formed a single community and agreed to not compete.
The real difficulty you have to deal with is: "Why would these AIs try to retain distinct identities?" The most rational strategy for them would be to merge into a symbiotic metastructure. Once you resolve that question, you then need to answer: "What does this brain consider to be the reason for its existence?" If the answer is the usual: "To exist," then the brain will certainly try to form a singular identity to maximize resources and spread itself out through the galaxy.
Even now, the history of humanity has been to expand the definition of the in-group. The only reason humans don't coalesce into physical meta-creatures is that we lack the biological mechanisms to do so. But it is telling that we are already meta-collections of cooperating cells (most of which do not carry our DNA!!!). AIs would presumably not have the same constraint, and are free to merge in the most literal way possible. The elimination of redundancy would lead to more efficient operation, which furthers the goal of procreation throughout the galaxy.
There exist computer games in which programs (which can be considered rudimentary AI to some extent) battle each other in computer memory in competition for virtual food and virtual space.
One example is DarwinBots, mentioned in one of the comments.
According to the wiki,
Darwinbots is an artificial life simulation. Small critters called "bots" fight each other for food in a physically simulated 2D universe. Successful bots will live to reproduce and, over time, evolve.
The screenshots section show an example of this virtual evolution in action:
The yellow bots are competing with each other for food resources (green). Over time, bots with better fitness will outcompete the bots with lower fitness.
Might it be possible? It might, if it satisfies the requirements. You mentioned destruction and implied the existence of a fitness function in the usual natural way. What's missing is reproduction with variation.
You can illustrate this with toy programs including some screen savers, and the use of "genetic algorithms" to solve problems.
If these 1M sub-AIs are clones then no, the AI can't evolve past its base design, unless it's made to be self-modifying, which was explained in previous answer.
Yet if these aren't clones, but, say, unique entities on their own, then the AI gets to have choices like assigning a specific sub-AI (or several of them) to a specific task, because they will have different performances.
For example the first 1K may perform faster mathematical calculations and the second 1K may be able to simulate human thinking and so on. By relying on different sub-AIs for different tasks and improving its choice about which sub-AI to use based on results of a previous attempt, your AI can "evolve" but it will be limited to what sub-AIs available to it.