As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, the precision of grid ergodic searching is the searching step. But what the precision should be using PSO searching. From the position update formula of PSO:

$x_i \leftarrow x_i+v_i$

So, we can assume the precision of PSO searching is the maximum of velocity of particles? Is this right? Generally, we set the maximum of particle velocity is about 10% to 20% of the position scale. But with this setting, we can still obtain a good precision with PSO, which contradicts previous assumption. So the searching precision of PSO is? Or it can be expressed as a function of maximum velocity and other parameters?

It seems that PSO can realize arbitrary precision... Because if there are sufficient particle numbers and iteration times, the PSO can approach to the actual solution.

  • $\begingroup$ Welcome to CS.SE! Can you define what you mean by "searching precision"? When you ask what the precision should be, what are you referring to? The precision of what? What do you mean by precision in this context? Can you edit your question to make these points clearer? $\endgroup$ – D.W. Mar 11 '19 at 17:02
  • $\begingroup$ Cross-posted: mathoverflow.net/q/325109/37212, stackoverflow.com/q/55090656/781723, cs.stackexchange.com/q/105431/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Mar 11 '19 at 17:04
  • $\begingroup$ I think I already presented clearly. The precision here is the difference between the result obtained with PSO and the true value. I dont know if there is other precision in PSO.... $\endgroup$ – Land Mar 12 '19 at 9:38

If by "precision" you mean the error in the result of PSO (i.e., the difference between the value that PSO outputs and the true global optimum), the error can be arbitrarily large. PSO is a heuristic. There are no guarantees that it finds the global optimum, or even that it gets close -- and there is no formula in terms of parameters (like velocity) for how large the error will be. The error depends on the optimization problem you're solving and on the shape of the loss surface.

  • $\begingroup$ Yes, you are right. So I mentioned it may be arbitrary precision. I just wondered if it is possible to provide a quantitative analysis for a given optimization problem. You can add sufficient conditions needed, such as the swarm size, the iteration times, velocity, etc.. Any parameter will be allowed to include, if you can get the formula of precision, or corresponding quantitative analysis, or just the order of precision. $\endgroup$ – Land Mar 12 '19 at 21:29
  • $\begingroup$ @ChenglongLi, in general that might be very difficult. PSO is a heuristic for solving a NP-hard problem. It might be possible for sufficiently simple special cases but for most real-world problems I would not expect you to be able to obtain any such analysis. I wouldn't hold out much hope for it being possible for real-world problems. This is an area that's driven mostly by experiments and trial and error. For your specific question, you haven't told us the specific optimization problem so it's certainly not possible to provide a quantitative analysis for your specific problem. $\endgroup$ – D.W. Mar 12 '19 at 21:33
  • $\begingroup$ Thank you. I get it. $\endgroup$ – Land Mar 12 '19 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.