I have a real system for which I have built a simulation that can express its certain characteristics. This real system can be in very large amount of configurations which can also be represented within simulation environment. Evaluation of each configuration on real system takes couple of hours, where evaluation within simulation takes couple of minutes.
I developed an optimization algorithm which finds a Pareto set of configurations that minimize (maximize) several objectives.
To solve this, I have built a genetic algorithm which uses simulator to obtain a Pareto set that will further be evaluated on real system.
I am wondering what approach to take on evaluating such two-step optimization heuristic? Evaluating all candidates on real system is infeasible.
So far I have think of this:
- compare results with randomly selected configurations
- compare worst and best results to see if they are distant enough (e.g. in separated cluster)
Any thoughts?
It sounds to me as if you are not concerned with comparing your GA with other state of the art because it is just not possible (function evaluations are expensive).
Other than the heuristic that you have mentioned you can also try these:
- Record how the mean objective values change. Check Fig 16 of "GALE: Geometric Active Learning for Search-Based Software Engineering"
- Cluster the resulting approx pareto front and sample one point from each cluster and run it in actual system.
All this aside how are you going to prove that the simulation that you have created is close to the actual system.
BTW: You are moving towards something called as surrogate modeling. Check out the literature there are some good survey papers:
- http://www.southampton.ac.uk/~aijf197/RecentAdvancesInSurrogateBasedOptimizationCorrectedPrePrint.pdf
- http://ojs.library.queensu.ca/index.php/PCEEA/article/download/3940/3929
On a side note to Dr. Chiang: when the actual frontier is not known, how can one use IGD? Is there a rule of thumb for such situations?
Dear Nikola,
As you may well expose your problem, it seems to me that before making the decision to choose a particular path it is necessary to gather information. This is why I suggest these links and files attachén, good luck.
-Monte Carlo method - Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Monte_Carlo_method
-One-hour-ahead wind power forecast using hybrid grey models
www.inderscience.com/info/.../forthcoming.php?jcod...
Best regards
Dear Nikola Tanković,
The well-known congress on evolutionary computation (CEC) introduced several benchmarks to do so. Please see the link.
http://dces.essex.ac.uk/staff/zhang/MOEAcompetition/cec09testproblem0904.pdf
Article Multiobjective optimization Test Instances for the CEC 2009 ...
Perhaps some non-parametric statistics could help. It would show well how your GA works against the state of the art.
Hi Nikola,
It seems that you are addressing a multiobjective optimization problem with expensive evaluation by simulation. If you focus only on dealing with multiobjective optimization, you may consider comparing your algorithm with some well-known MOEAs such as MOEA/D and NSGA-III in terms of common metrics such as hypervolume and inverted generational distance (IGD). If you want to address both multiobjective optimization and expensive optimization, ParEGO and MOEA/D-EGO might be candidates for the benchmark algorithms.
MOEA/D: http://dces.essex.ac.uk/staff/zhang/webofmoead.htm
NSGA-III: http://dx.doi.org/10.1109/TEVC.2013.2281535
ParEGO: https://www.cs.bham.ac.uk/~jdk/parego/
MOEA/D-EGO: http://dx.doi.org/10.1109/TEVC.2009.2033671
It sounds to me as if you are not concerned with comparing your GA with other state of the art because it is just not possible (function evaluations are expensive).
Other than the heuristic that you have mentioned you can also try these:
- Record how the mean objective values change. Check Fig 16 of "GALE: Geometric Active Learning for Search-Based Software Engineering"
- Cluster the resulting approx pareto front and sample one point from each cluster and run it in actual system.
All this aside how are you going to prove that the simulation that you have created is close to the actual system.
BTW: You are moving towards something called as surrogate modeling. Check out the literature there are some good survey papers:
- http://www.southampton.ac.uk/~aijf197/RecentAdvancesInSurrogateBasedOptimizationCorrectedPrePrint.pdf
- http://ojs.library.queensu.ca/index.php/PCEEA/article/download/3940/3929
On a side note to Dr. Chiang: when the actual frontier is not known, how can one use IGD? Is there a rule of thumb for such situations?
Thank you Vivek, your answer is in good direction I think. The simulation I have created together with the GA is the object of my evaluation. I must evaluate the goodness of results obtained that way. So evaluating the GA itself is linked with evaluation of simulation. For example, if my GA+simulation obtains certain results, I must prove on real system that indeed these results are good and close to optimal somehow.
Hi Vivek,
For your question, the common way I know is to take (or sample some of) the non-dominated solutions from the union of solutions obtained by all tested algorithms as the reference front.
Consider the reserach of Christian Jacob, who used genetic descriptions as the subject elements of an evolutionary programming environment. Hope this helps.
url pages.cpsc.ucalgary.ca/~jacob/Lectures/Lectures.html
- Badges
- Science method