I would agree that genetic algorithms (GA) is good way to go. In short, these types of algorithms simulate Darwinian evolution. In general, GA is not very computationally intensive.
You'll need to come up with a set of parameters (genes) that guide an AI's behavior. The first AIs that a player encounters will have these parameters set to values that provide descent behavior. The parameters for each instance of the AI in this first generation should vary a bit.
Next, you'll need to come up with a function which scores how well a particular AI performs. This score might take into account how much damage the AI caused the player, and if the AI survived the round. This score is known as the "objective function" in GA.
After each round, the genes for the best scoring AIs are mated to create a new generation of AIs. There are many ways to mate individuals, and will depend upon the genes, and the tradeoff between how quickly you want the AIs to evolve, and how much the game can tolerate malfunctioning AIs.
Check out some of the resources on GA, and write back if you want to discuss more.
This is sort-of what I should have expected to hear
Genetic programming and algorithms seems like something that would be a good base, especially for intelligent aspects of mutation, or varaiables that can chage by vectors or scalar values (motor movements, for example). I was more wondering if there's anything a little more specific to physical mutations in enemies, not so much the way they think; I know genetic algorithms can do this, but how...does anyone have an idea on how I could rate the fitness of a physical mutation on an enemy? Or how I can define changes to the physical structure or animations? I'm trying to figure out how to define physical mutations to their bodies...Hence the change in physical attributes, weapons (claws vs. fangs, or poison, etc.), and other less...mental attributes.
I can picture how to define motor movement using genetic algorithms, and rating their fitness to, say, how fast they move. They just change the vales for forces, torque, and speed of the moving limbs. But how would one define the fields that can change for physical mutations? Just a thought deeper into the process...
GA works well for physical structures, and weapons as well. See videos for "evolved virtual creatures" or "Karl Sims".