stephenbrooks.orgForumMuon1Generalmore efficient algorithm possible
Username: Password:
Search site:
Subscribe to thread via RSS
De Bug
2002-11-22 08:16:20
The idea is as follows:
the beam of particles goes through the tube
zsrc,rotsrc,s1f,s1l, .... ,d33l,s34f,s34r,s34l,d34l
is that right ?
why not to fix the whole state of the beam at entering say s34l
then calculate it with one value for d34l then come back to the saved state and recalculate with a different value of d34l ? 

Why not take for example binary tree of calculations:
1) fix zsrc,rotsrc,s1f,s1l, .... ,d33l,s34f,s34r,s34l and calculate for two differnt values of d34l (Total is 2 results)
2) then return back at fixed zsrc,rotsrc,s1f,s1l, .... ,d33l,s34f
and take another s34r (Total is 4 results)
for that s34r again take two different d34l
3) take zsrc,rotsrc,s1f,s1l, .... ,d33l,
and recalculate for twice each of the s34f,s34r and s34l (Total is 8 results)
and so on

--
De Bug
Stephen Brooks
2002-11-22 09:06:47
Works very well for the end of the accelerator but not much good for optimising the components near the beginning.


"As every 11-year-old kid knows, if you concentrate enough Van-der-Graff generators and expensive special effects in one place, you create a spiral space-time whirly thing, AND an interesting plotline"
De Bug
2002-11-22 09:17:30
You're right but it still saves a lot of computation power.
It works like optimizing the tube from the end to the beginning
and doing much effort on optimizing the end of the tube, but yeah i understand that the beinning of tube is most promising part of the optimization.

Do you think it would be beneficial to the project to implement such a technique
and if "yes", how much work it is to rework the source code ?

--
De Bug
Stephen Brooks
2002-11-22 09:47:33
This would be a fair amount of work to implement.  (Remember currently I'm not even employed doing this project, so it's purely done in free time).

The next thing on the list is putting in a queue of results so that the program will re-check the high ones by itself.

Seeing as the accelerator is a linear thing, your idea is not too bad - I'm just wondering how I can integrate it with the current system.  Perhaps each run could be saved at some random points through it, and if the entire run turns out to be a very good percentage, more "semi-runs" will be done just optimising the end-section.


"As every 11-year-old kid knows, if you concentrate enough Van-der-Graff generators and expensive special effects in one place, you create a spiral space-time whirly thing, AND an interesting plotline"
Chuck Coleman
2002-11-22 11:20:59
This is known as the Gauss-Seidel algorithm, a fine global optimization algorithm.  It consists of holding all but one parameter constant and optimizing the last parameter.  Then, that parameter is held constant and another parameter varied.  This is done until all parameters have been individually optimized.  Then, it starts over and repeats (fancy term: iterates) until convergence.

For this project, I would start with the medians of the best250. Each parameter can take on 1000 values.  Each simulation should use something like 1,000,000, if not more, particles.  I don't think this can be done properly, even if simulations are broken down and distributed.  To cut the size, you could only simulate a few values in each dimension.  You can use the best250 to restrict the range of some parameters, but not all of them.  The problem, again, is that we don't know the objective function and can only estimate it by computationally-intensive simulation.

"Sorry, no concluding witticism"
Stephen Brooks
2002-11-23 07:01:51
Interestingly the "mutation" step in the genetic algorithm does effectively this.  It does not often vary all the parameters uniformly - instead it usually only varies a few, so in effect the Muon program is already performing a randomised form of this method because it will take one of the best results so far and then vary a parameter (sometimes more than one) and if the new design is better, that will then form the basis for new variations.


"As every 11-year-old kid knows, if you concentrate enough Van-der-Graff generators and expensive special effects in one place, you create a spiral space-time whirly thing, AND an interesting plotline"
Chuck Coleman
2002-11-26 13:47:36
quote:
Originally posted by Stephen Brooks:
Interestingly the "mutation" step in the genetic algorithm does effectively this.  It does not often vary all the parameters uniformly - instead it usually only varies a few, so in effect the Muon program is already performing a randomised form of this method because it will take one of the best results so far and then vary a parameter (sometimes more than one) and if the new design is better, that will then form the basis for new variations.



I disagree.

1. GA varies 1 or more parameters, but does not do so exhaustively like the G-S Algorithm.

2. Although I have argued that the 'best' file provides a good proxy for the best designs, as the extreme values are correlated with the means, it does not follow that a "better" design arising from mutation is truly better.  This "better" design is another extreme value and may represent a better design.

Given my finding using John Kitchen's data that efficiencies of the designs he examined are not statistically distinguishable from 2.95, the G-S Algorithm looks like a good choice to find the peak sticking out from the 2.95 plain.  I would vary parameters in reverse order.  Do an exhaustive search on each of the 1000 designs: at least 1,000,000 particles each.  The number of particles has to be held constant to avoid heteroscedasticity.  After each dimension has been varied, use one or more nonparametric density estimators to estimate the peak value for that dimension.  Then, repeat the process for the next dimension.  Keep repeating the process for all dimensions until convergences.

The G-S Algorithm has two requirements:

1. The starting point should ideally be near the peak.  Again, I think the median of the best250 is a good starting point.

2. The derivatives should be well-behaved.  Negative derivatives could actually push the algorithm away from convergence.

I've personally used the G-S Algorithm to solve deterministic models of the U.S. macroeconomy of about the same dimensionality.  One thing I noticed was the possibility of false convergence: the algorithm sometimes converges at a point that did not solve the system.  So, I always ran it twice.

"Sorry, no concluding witticism"
Stephen Brooks
2002-11-26 20:08:00
Very few people are going to want to run 1 million particle workunits, and the difference between the simulation and the engineering reality is sufficient that there's no point going into much further detail.  We got the big 150% or so increase over the original design, and that's the interesting part.  When I submit the final figures I'll probably do some simple analysis to find out roughly where the "top" of the plateau area is (smooth the data a bit and then look for the peak).

quote:
One thing I noticed was the possibility of false convergence: the algorithm sometimes converges at a point that did not solve the system.  So, I always ran it twice.


Oh, it'll do that, and there are examples that crop up where you have to run it 100s of times.  These tend to be a real pain for numerical analysts in other optimisation problems.  Basically even if your maximum is a perfect elliptical hill, if the ellipse is long and thin and pointing in a direction that's not aligned with one of your axes, G-S and steepest ascent both take ages to converge.  Something called "conjugate gradient" fixes this for problems of a quadratic nature, though I'd not trust it for data like this.


"As every 11-year-old kid knows, if you concentrate enough Van-der-Graff generators and expensive special effects in one place, you create a spiral space-time whirly thing, AND an interesting plotline"

[This message was edited by Stephen Brooks on 2002-Nov-27 at 4:34.]
: contact : - - -
E-mail: sbstrudel characterstephenbrooks.orgTwitter: stephenjbrooksMastodon: strudel charactersjbstrudel charactermstdn.io RSS feed

Site has had 25162896 accesses.