Welcome to MilkyWay@home

Started Particle Swarm Searches

Message boards : Number crunching : Started Particle Swarm Searches
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile Travis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
Message 869 - Posted: 2 Dec 2007, 3:40:00 UTC

If you've noticed that some of the workunits start with "ps" those are for the new particle swarm search that we just got working. With the last update to the binaries the resulting work units return a lot more information about what kind of search they were run from, when they were generated and how they were generated, so we're going to be able to really start studying whats going on in depth now :)

As to what we're going to be working on while getting these new results, the plan is:

1. fix the remaining memory leaks in the astronomy code
2. Nate is going to be updating the code with the "convolution" which will make work units a bit longer but more accurate
3. i'm going to be implementing adaptive simulated annealing and maybe parallel tempering and stochastic tunneling search methods
4. we'll be doing a lot of data analysis about the particle swarm searches and comparing those to the asynchronous genetic search
5. there's an upcoming genetic/evolutionary algorithms conference (paper submissions due by mid january) and we're hoping to submit the results for genetic search (and particle swarm if we have enough) to that.

thanks again everyone for crunching our numbers and putting up with all the server troubles last week. :D
ID: 869 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
cwhyl

Send message
Joined: 11 Nov 07
Posts: 41
Credit: 1,000,181
RAC: 0
Message 879 - Posted: 2 Dec 2007, 14:39:06 UTC

Nice :)
These new "ps" units seem to be rather fast.
Could you up the limit of 20 WUs a little bit?
My linux quad runs them faster than 20 minutes.
ID: 879 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Rapture
Avatar

Send message
Joined: 8 Nov 07
Posts: 12
Credit: 144,067
RAC: 0
Message 881 - Posted: 2 Dec 2007, 15:28:14 UTC - in response to Message 869.  

I did not notice the difference in the workunit names until you mentioned this in your posting. I can see that there is alot going on here in this project even though most of it is transparent to the users. By the way, what is the difference between genetic search and particle swarm search?
ID: 881 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Odysseus

Send message
Joined: 10 Nov 07
Posts: 96
Credit: 29,931,027
RAC: 0
Message 891 - Posted: 2 Dec 2007, 20:27:15 UTC - in response to Message 869.  

5. there's an upcoming genetic/evolutionary algorithms conference (paper submissions due by mid january) and we're hoping to submit the results for genetic search (and particle swarm if we have enough) to that.

It will be very gratifying to see some results, even preliminary ones, published so soon. AFAICT not many BOINC projects have done so.

ID: 891 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Travis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
Message 897 - Posted: 3 Dec 2007, 8:58:54 UTC - in response to Message 879.  

Nice :)
These new "ps" units seem to be rather fast.
Could you up the limit of 20 WUs a little bit?
My linux quad runs them faster than 20 minutes.


I think the ps_1 and ps_2 swarms weren't working quite right. I've stopped those early and added ps_3, ps_4 and ps_5. Hopefully these will take longer. If not let me know and i'll bump up the limit some more.
ID: 897 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Travis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
Message 898 - Posted: 3 Dec 2007, 9:14:05 UTC - in response to Message 881.  

I did not notice the difference in the workunit names until you mentioned this in your posting. I can see that there is alot going on here in this project even though most of it is transparent to the users. By the way, what is the difference between genetic search and particle swarm search?


Both genetic search and particle swarm are monte carlo algorithms (basically global search methods using randomization: http://en.wikipedia.org/wiki/Monte_Carlo_method ).

Wikipedia isn't bad for information on either of these:
http://en.wikipedia.org/wiki/Particle_swarm_optimization
http://en.wikipedia.org/wiki/Genetic_algorithm

But in a nutshell, what we're trying to do is fit a model of the milkyway galaxy to different 'wedges' of stars observed with the SLOAN digital sky survey ( http://www.sdss.org/ ). This model has a bunch of input parameters which specify where stars should be observed. What a workunit does is take a set of input parameters and calculate the model over the given star set, and what it sends back is an estimated fitness, or likelihood that this parameter set is a good one. What we're trying to do is find the best fitness or likelihood for the model of the milkyway.

Particle swarm and genetic search just do this in different ways. With genetic search, we calculate an initial set of random parameters and use this to generate an initial population (ranked by fitness). After this, we generate work units by using different parameter production methods that simulate evolution, ie. , reproduction - take two parameter sets and generate a child thats a combination of the two (for this we use three different methods of generating a child, the average of the two parents, a point outside the more fit parent, and a point outside the less fit parent -- theres more about this in our eScience paper linked on the front page), and mutation - take a parameter set and mutate one parameter randomly to generate a new set. When we get results back, we update the population by inserting new parameter sets that will improve the overall fitness of the population. This eventually converges around a single set of parameters and when that happens we've found our result :) Genetic search is also nice in that if there are multiple minima (a few different areas where the parameter sets are good), the population will usually converge to both, so if we look over the entire population it will be grouped around the minima.

Particle swarm works a bit differently, it generates an initial set of particles each with their own random velocity. As the search progresses, the location of a particle is a set of parameters, and the velocity of that particle is the difference in the parameter set from the particles previous location. New parameters sets (the particles next position) are generated by having it continue to move by a random amount of the previous velocity, but also by having the particle pulled by a random amount towards the globally best found parameter set, and the particles locally best found parameter set. In this way, the particles swarm around pulling themselves towards the best found parameter sets until they converge.

Both searches move through the search space differently, so it will be interesting to see which works better. Also, there's a lot of variations on each that we can test which can improve performance. It also might be the case that for one set of stars one search may be better than the other. We might also be able to blend them or adaptively choose one or the other based on how the search is running. Theres a lot of interesting stuff to look into :) It's also nice because BOINC is a radically different computing architecture than what these searches have been previously used on, so we've had to make our own asynchronous versions that work on BOINC. This also lets us compare our asynchronous searches on BOINC to synchronous searches on more traditional architectures (ie, the supercomputer at RPI and the grid of clusters we have access to at RPI).
ID: 898 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Travis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
Message 900 - Posted: 3 Dec 2007, 9:19:44 UTC - in response to Message 891.  

5. there's an upcoming genetic/evolutionary algorithms conference (paper submissions due by mid january) and we're hoping to submit the results for genetic search (and particle swarm if we have enough) to that.

It will be very gratifying to see some results, even preliminary ones, published so soon. AFAICT not many BOINC projects have done so.



Theres a lot of interesting computer science research we're doing here and AFAIK researching how different global optimization techniques can work on massively large-scale, massively heterogeneous, and rather volatile computing environments is a really new area so it gives us lots of opportunities for publications.

This isn't to mention the fact that the results that we get of our searches are being used by the astronomers to test new models much faster than before. I think they're submitting a publication shortly that has a little bit about this work here. Whe Nate updates the astronomy binaries with the convolution code they'll be getting even more interesting results. So hopefully we'll be seeing publications on both the computer science and the astronomy side :)
ID: 900 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
rbpeake

Send message
Joined: 29 Aug 07
Posts: 21
Credit: 1,050,702
RAC: 0
Message 910 - Posted: 3 Dec 2007, 14:25:46 UTC - in response to Message 898.  

Both genetic search and particle swarm are monte carlo algorithms (basically global search methods using randomization: http://en.wikipedia.org/wiki/Monte_Carlo_method ).

Wikipedia isn't bad for information on either of these:
http://en.wikipedia.org/wiki/Particle_swarm_optimization
http://en.wikipedia.org/wiki/Genetic_algorithm

Theres a lot of interesting stuff to look into :)


Thanks very much for the very informative update! :)

For me BOINC has been a great way to learn about all these fascinating topics! A number of other BOINC projects utilize Monte Carlo optimizations as well as I am sure you are aware, and it is fascinating to see how these methods are used and improved on by the various projects each according to their needs. Thanks again, I am very much looking forward to helping you guys! :)

Regards,
Bob P.
ID: 910 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile tahanko

Send message
Joined: 13 Dec 07
Posts: 11
Credit: 1,849,193
RAC: 0
Message 1055 - Posted: 14 Dec 2007, 6:16:41 UTC

hello
I just want to ask if the quota of 20 WU per day will be changed? because my C2D crunches fast and I want to crunch for this project.
thanks in advance
ID: 1055 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile JLDun
Avatar

Send message
Joined: 17 Nov 07
Posts: 77
Credit: 117,183
RAC: 0
Message 1056 - Posted: 14 Dec 2007, 7:54:14 UTC - in response to Message 1055.  

hello
I just want to ask if the quota of 20 WU per day will be changed? because my C2D crunches fast and I want to crunch for this project.
thanks in advance

Isn't it 20 WU's at a time, instead? I'm under the impression that it's:
{(Unstarted WU's)+(WU You're working on)+(Finished WU not yet reported)=20} at any particular time.
ID: 1056 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile tahanko

Send message
Joined: 13 Dec 07
Posts: 11
Credit: 1,849,193
RAC: 0
Message 1058 - Posted: 14 Dec 2007, 10:24:22 UTC - in response to Message 1056.  

Isn't it 20 WU's at a time, instead? I'm under the impression that it's:
{(Unstarted WU's)+(WU You're working on)+(Finished WU not yet reported)=20} at any particular time.

I dont know, because I crunched 20 WUs and I am not getting any other new WUs
ID: 1058 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Irishgeezah
Avatar

Send message
Joined: 10 Nov 07
Posts: 37
Credit: 11,855,733
RAC: 0
Message 1059 - Posted: 14 Dec 2007, 11:06:51 UTC - in response to Message 1058.  

Isn't it 20 WU's at a time, instead? I'm under the impression that it's:
{(Unstarted WU's)+(WU You're working on)+(Finished WU not yet reported)=20} at any particular time.

I dont know, because I crunched 20 WUs and I am not getting any other new WUs


They were having problems with power/internet outages last night so it seems like they've had another overnight, won't be any work for a few more hours most likely.



ID: 1059 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Jayargh
Avatar

Send message
Joined: 8 Oct 07
Posts: 289
Credit: 3,690,838
RAC: 0
Message 1061 - Posted: 14 Dec 2007, 14:26:01 UTC - in response to Message 1055.  

hello
I just want to ask if the quota of 20 WU per day will be changed? because my C2D crunches fast and I want to crunch for this project.
thanks in advance


No,I don't think the quota will be changed anytime soon...however I believe the length of the unit will increase soon thus having the effect you are looking for.
ID: 1061 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Martin P.

Send message
Joined: 21 Nov 07
Posts: 52
Credit: 1,756,052
RAC: 0
Message 1062 - Posted: 14 Dec 2007, 15:40:53 UTC - in response to Message 1059.  
Last modified: 14 Dec 2007, 15:45:33 UTC

Isn't it 20 WU's at a time, instead? I'm under the impression that it's:
{(Unstarted WU's)+(WU You're working on)+(Finished WU not yet reported)=20} at any particular time.

I dont know, because I crunched 20 WUs and I am not getting any other new WUs


They were having problems with power/internet outages last night so it seems like they've had another overnight, won't be any work for a few more hours most likely.


tahanko,

the daily quota is 2,000 work-units, not 20. The 20 only refers to the maximum number of work-units that you can have on your computer at any time. As soon as you finish a few work units they will be transmitted and the missing number of new WUs to 20 will then be transferred to your computer.

ID: 1062 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile tahanko

Send message
Joined: 13 Dec 07
Posts: 11
Credit: 1,849,193
RAC: 0
Message 1066 - Posted: 14 Dec 2007, 18:38:27 UTC

thanks Martin P. for the explanation :)
ID: 1066 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : Number crunching : Started Particle Swarm Searches

©2024 Astroinformatics Group