1
$\begingroup$

The short version of my question is: I designed this algorithm for finding a solution for an inverse problem. Based on my research it is a new algorithm, does anyone know a similar algorithm?

My algorithm: Suppose we are looking for a solution (or a model) for an inverse problem. The solution has M parameters.

1) I start with N random solutions (again each of them has M parameters).

2) Each solution with interact with another solution. For example solution A interacts with solution B. When these two solutions interact solution A borrows a parameter (for example the third parameter) from solution B. With the new parameter solution A measures its RMS error (based on the objective/error function that is defined for this problem) and compare it to its original RMS error (before borrowing the parameter from solution B).

3) If the RMS error after borrowing is improved the solution A give +1 score to solution B, otherwise it will give -1 score to solution B.

4) The same interaction happens between solution B and A (now B borrows a parameter and gives score to A).

5) The same interaction happens between all other N solutions (therefore total interactions = N^2).

6) The interaction is just borrowing and scoring. After scoring, each solution will go back to its original parameters.

7) After all solutions interacted with each other, solution with the lowest score will be removed and replaced by another random solution.

8) Also, solution with the highest score randomly gives one of its parameters to each solution.

9) Steps 1-8 will repeat again.

10) The process continues for P times or until the error of one of the solutions reaches below a threshold value.

I tested this algorithm for a problem and it converges quickly (please look at the link at the end). I just want to see if there is any similar or same algorithm. Do you know any similar algorithm for the solution of inverse problems?

RMS Error Plot (click here)

$\endgroup$
  • 4
    $\begingroup$ Sounds like a simple genetic algorithm. $\endgroup$ – Rahul Dec 29 '16 at 18:17
  • 2
    $\begingroup$ I think you should make the question more specific, at least include something like " do you know any similar algorithm for the solution of inverse problems". Right away people would know what the question is about and those with an interest in inverse problems will most likely answer your question. $\endgroup$ – user25406 Dec 29 '16 at 20:22
  • 2
    $\begingroup$ I agree with Rahul that this feels like a genetic algorithm (or a small variant thereof). How big is your solution space for your sample problem that converged quickly? This seems like it would take a while to converge if the solution space is very large, or if the behavior is highly non-linear. $\endgroup$ – Brian Tung Dec 29 '16 at 20:58
  • 1
    $\begingroup$ @Rahul I agree with you. However, there are differences that I didn't know if they exist in other algorithms. For example, in GA, the fitness function (which leads to elimination of some of the solutions) is individual base. Here the fitness depends on the other solutions. $\endgroup$ – N. Tamimi Dec 29 '16 at 21:04
  • 1
    $\begingroup$ @BrianTung The population is 300 solutions. The problem is also a very simple linear inverse problem. $\endgroup$ – N. Tamimi Dec 29 '16 at 21:07

Your Answer

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

Browse other questions tagged or ask your own question.