Evolutionary algorithm in stochastic environment
I'd go with option 1.

A dynamic training environment is a good way to produce a robust solution (after all natural evolution, which is the inspiration for EA, is always dynamic).

Moreover "take some statistics over the solutions" can be a very hard problem (you shouldn't take for granted that there is a meaningful way to combine / extract information from multiple solutions).

Indeed there are some important aspects to consider:


population diversity have to be carefully monitored. Often EAs are designed for a static optimization problem and the quick loss of diversity can be a problem in a dynamic environment;
it seems that you have a system in which environmental change occurs rapidly. Try to slow down the environment: do not draw a new interaction environment after every mutation but wait for a sequence of mutations (in Genetic Programming this is the approach taken in Dynamic Training Subset Selection{1}). I'm not sure this will work, but it's worth a try;
supply the EA with an explicit memory (sometimes called Valhalla) so that the EA can recall useful information from past generations (e.g {5}).




This is small compendium of interesting papers.

Looking for further resources, consider that there are many kinds of dynamic environments: e.g. noisy fitness functions, environments with optimum changing over time... they are somewhat different problems but share many interesting techniques.

Also it seems to me that you're describing a so called co-adaptive environment (each individual's evolution drives other individuals evolution and individuals change their fitness landscape evermore). You may find interesting techniques in papers about co-evolution.


Dynamic Training Subset Selection for Supervised Learning in Genetic Programming by Chris Gathercole, Peter Ross (1994).
Genetic Algorithm for Adaptation to Dynamic Environments - A survey by Naoki Mori, Hajime Kita (2000).
Evolutionary Dynamic Optimization - A survey of the state of the art by Juergen Branke, Trung Thanh Nguyen, Shengxiang Yang (2012).
An evolutionary approach for time dependant optimization by Philippe Collard, Cathy Escazut, Alessio Gaspar (1997).
"Memory enhanced evolutionary algorithms for changing optimization problems" by Juergen Branke (1999).
Evolutionary Algorithms and Dynamic Optimization Problems by Karsten Weicker (2003).