1
$\begingroup$

I'm currently revising my optimization algorithm for a specific part of a problem. I have trouble in wrapping my head around a new approach and my mind is having this tunnel-vision of ideas. I could really use some fresh perspectives.

I'll try my best to simply the explanation.

(Please see attached file "Example-1.png" and "Example-2.png")


Say, we are given 3 distinct persons.

Each of these person have a specific Supply (an item that he/she possess) and a Need (an item that needs to be acquired). Now, if these Supply-Need is reversed, and their reverse can be found in another person, they can be traded.

Moreover, the pairs have a numerical value called Gravity that specifies the importance of the pair to the person. We can treat it as a weight on how much a person can be "satisfied" if the Supply-Need pair is met. Each person can only allocate and distribute 100-points of Gravity among all of his/her Supply-Need pairs.

Now, the Total Satisfaction of this process can be computed by getting the sum of all the Persons' individual satisfactions.

The objective is to have the group of Persons trade their Supply-Need pair/s in different combinations such that we can acquire the largest Total Satisfaction as possible.


In PSO, each Particle represents a candidate solution based on its location in the Search Space.

Given the attached examples in this post, we can say that Example-1.PNG is a distinct candidate solution to this problem, as well as Example-2.PNG.


What's the best approach in how this problem can be represented and evaluated by a Fitness/Objective Function?

How would you characterize this problem in PSO?

Do you have any recommendations of published work with the same problem as this?

Cheers!

EXAMPLE-1.PNG

Example-1.png

EXAMPLE-2.PNG Example-2.png

$\endgroup$
  • 1
    $\begingroup$ I guess I'm confused by your problem. Can you express it mathematically as some sort of nonlinear program? Why do you need to use PSO? $\endgroup$ – Geoff Oxberry Dec 8 '14 at 19:57
  • $\begingroup$ I'm trying have PSO to treat my problem as a black box, given its meta-heuristic nature . Also, I need PSO since it provides fair solutions (not necessarily the optimum) in just a short span of time. $\endgroup$ – Kevin Lloyd Bernal Dec 8 '14 at 20:14
2
$\begingroup$

Maybe a dynamic programming approach would fit as it it seems to be close to the knapsack problem.

If you go for the PSO, I think you could express the quantity each person gets from a particular supply as a variable to your problem. Then you'll have to express your constraints and your objective function. You should have an ILP

After that you could use the PSO algorithm to search for good solutions. Here is a paper found from google scholar (is seems to be cited many many times)

www.computer.org/csdl/proceedings/wcci/2002/7282/02/01004478.pdf

$\endgroup$

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.