4
3

What techniques are appropriate when the objective function cannot be expressed as a math program, but is the output of a simulation? Obviously, standard math programming algorithms can't be used.

My background inclines me towards search heuristics, such as Genetic Algorithms and Tabu Search. These methods still work well when the objective function is a "black box". Are there any other techniques I should be aware of? Are there any software packages that solve this sort of problem (and how do they do it)?

asked 27 Oct '10, 03:54

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
accept rate: 5%


12next »

Here is an idea that is somewhat uncommon; try a Design of Experiments approach. Essentially, you have to think of your simulation as a real physical system where observations can be made but for which analytical gradients are unavailable. Thus, you'd be like an experimentalist in a lab, collecting data in each run.

You can then use response surface methods (but in the reduced subspace given by multivariate methods like PCA or PLS); these maximize the amount of information you get in each function evaluation. Using this information, you can perturb your decision variables in directions of maximum covariance and move your current decision variables in the direction that optimizes your objective. Essentially what you would be doing is optimizing and modeling the space at the same time.

In my opinion, DFO (Derivative Free Optimization) methods like Nelder-Mead simplex or even heuristic algorithms like Differential Evolution, GAs, SAs etc. are only good if your objective is cheap to evaluate and all your decision variables are independent. However, if your decision variables are correlated (as is often the case), DFO methods may waste iterations banging around the same subspace with little progress -- this is why it is important to work in the reduced subspace.

See this thread: http://mathoverflow.net/questions/36926/robust-black-box-function-minimization-with-extremely-expensive-cost-function

link

answered 27 Oct '10, 19:31

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 27 Oct '10, 21:50

You may try using some derivative-free solvers: NMSMAX, APPSPACK, NEWUOA, DFO ...

http://www.mcs.anl.gov/~more/dfo/shootout.html

link

answered 27 Oct '10, 14:33

anonymous's gravatar image

anonymous
691311
accept rate: 8%

I will second the answer about DOE. I do simulation analysis pretty much full time, and we often encounter 5-20 independent variables. We usually perform a small simple experiment (a fractional 2^k, or plackett-burman etc) with fewer replications than would be needed for a precise CI on the response. subsequent anova identifies which decision variables (main effects) wield measurable influence over the response, and in most cases we reduce the size of the decision space significantly.

A follow on experiment on the variables of interest may be a more complicated higher resolution design, with more replications per run.

If your simulation is set up for random number synchronization i suggest implementing common random numbers using a baseline case as a control, and measure the difference between experimental runs and that control. In most cases this will drastically reduce the number of replications necessary for a desired precision and help keep your run times manageable.

I've used Opt-Quest that comes with ARENA simulation software and my experience is that for more than just a few decision variables the amount of time required to approach optimality becomes prohibitive (but that experience is pretty limited--it may have been our particular problem).

Best, Jon

link

answered 29 Dec '10, 16:47

Jon%20Davis's gravatar image

Jon Davis
1564
accept rate: 16%

I don't know how big of a problem you got but you might wanna check out Neural Networks. Since wikipedia has a better definition on them I will just quote..

"The utility of artificial neural network models lies in the fact that they can be used to infer a function from observations."

You can still use your heuristics in the training of the net. However AFAIK you have to write the whole network algorithm yourself, but it's relatively easy.

link

answered 27 Oct '10, 05:57

Buxley's gravatar image

Buxley
5641614
accept rate: 9%

Neural networks are indeed a good way of estimating a function from observations. Unfortunately they aren't suitable in this case. I don't HAVE observations, and the objective function isn't a "function" I need to estimate (in the sense of a combination of inputs), it's the output of a real-world process that I can simulate.

(27 Oct '10, 07:33) DC Woods ♦

I think the problem(blakbox) can be seen as a regression problem. Given some inputs we receive an output (in this case the output of the simulation) and there is no known equation between inputs and the output and we try to estimate the relation between inputs and the output. For this purpose, the outputs of a series of simulations can be considered as training and validation data. Then there are different methods and models to choose and neural network is one of them.

link

answered 27 Oct '10, 09:03

Arman's gravatar image

Arman
3292714
accept rate: 0%

I read an article about wing shape optimization for aircraft. The authors used Genetic Algorithm to determine the optimal parameter set. In an evaluation for each parameter set, aerodynamic simulation was executed. They used a lot of blade computers to execute the simulation....

link

answered 27 Oct '10, 12:12

yonezat's gravatar image

yonezat
411
accept rate: 0%

Yes, this is the type of problem, where even a tiny change in one parameter of the solution can result in the the result becoming very different.

(27 Oct '10, 21:00) DC Woods ♦

I've also read about GAs and Genetic Programming being used to "reinvent" the dyson vacuum cleaner, and some other amazing things.

(27 Oct '10, 21:01) DC Woods ♦

You can find a blackbox optimization package here : http://www.gerad.ca/nomad/Project/Home.html

link

answered 28 Oct '10, 14:54

Pascal's gravatar image

Pascal
111
accept rate: 0%

If your model is a discrete event simulation model, most of the leading discrete event simulation packages have optimization engine add-ons that you could use to optimize using the simulation outputs and inputs as your objective function and controls. For example, OptQuest for Arena/Promodel or SimRunner.

link

answered 28 Oct '10, 17:46

dcope's gravatar image

dcope
311
accept rate: 0%

Have you checked out How to Solve It: Modern Heuristics or a similar book? How to Solve It is a very good book in my experience, but perhaps a better one has been published since I last looked.

Without knowing anything about the characteristics/nature of your problem it's hard to say which methodology makes the most sense. There are quite a few approaches though (it only takes a quick look at wikipedia for "Metaheuristic", "Particle Swarm Optimization", "Hill Climber" and following a few of the numerous links to appreciate how varied the options are).

I've used simulated annealing (and hill climbing on simple cases) successfully in a past project. But really, it depends on the character of your problem.

From what you've written in the comments ("a tiny change in one parameter of the solution can result in the the result becoming very different") I think an issue that you'll need to address is how define neighbors of your current solution in such a way that a "neighbor" doesn't have a dramatically different output. This may seem obvious, but if "neighbors" have wildly different results, maybe your simulation is somewhat volatile; if so, I would suggest increasing trial count and averaging.

link

answered 06 Jan '11, 14:00

danhs's gravatar image

danhs
111
accept rate: 0%

As part of Crystal Ball software suite, we routinely solve simulation optimization problems. The definition we use is broader than what you mention: we can have some of the constraints coming from simulation as well. We use OptQuest to solve the optimization problem (Crystal Ball provides the simulation results within the optimization framework), which internally uses tabu search for solving. So, again, a meta-heuristics solver is getting used.

link

answered 26 Aug '11, 13:15

Samik%20R.'s gravatar image

Samik R.
1.2k1920
accept rate: 2%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×79
×58

Asked: 27 Oct '10, 03:54

Seen: 5,416 times

Last updated: 28 Aug '11, 07:59

OR-Exchange! Your site for questions, answers, and announcements about operations research.