Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

mhadi

A Distribution Algorithm

This topic is 5229 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have got a scenario a user gives input of many no of slots and numbers for each slot and tells to distribute it in three partitions such that the weight of all three partition will remains the same or must not exceed to a trheshold for example user gives 1200 500 200 600 1300 and so on ... and i have to ditribute it in A,B,C such that sum of all slots for A=sum of all slots for A=sum of all slots for A or may differ to a threshold of say 300 then the distribution will be 1200-A 1300-B 500+200+600=1300-C therefore threshold not exceeding 300 waiting for quick reply mhadi Trying For The Best Mhadi

Share this post


Link to post
Share on other sites
Advertisement
Well Zahlman thanx for ruining my "EVIL" plans!!
As for for your satisfaction I am not discussing a home work it is a scenario from An Electrical Consultation Company and they want a software that can distribte the load over three phases R,Y And B!! Where as the slots are the circuit breakers having specific load on each breaker!!

I think it would seem easiar to you so please try to help or stop making fun.

Now about the impleamentation logic could this be a better approach:
1. sort the slots and assign the largest three slots into the phases
e.g
1200,1300,1100,200,300,100
sorted to
1300,1200,1100,300,200,100
1300 was assinged to R
1200 to B
1100 to C
then select the next three slots and assing them to reverse i.e
100 to R
200 tp B
and 300 to c
which will make 1400 each!!

waiting for som serious help!!
mhadi
(hope you dont mind sorry for my harsh words)

Share this post


Link to post
Share on other sites
is it important that each partition has the same number of slots in it? if not, you could start like you did (putting the three largest into each one)... then go through the rest in largest-to-smallest order, and assign each to the partition with the lowest total. this will help out if there are more than six that happen to work out nicely, and if there is a large variance between the largest and smallest ones.

[edited by - krez on February 26, 2004 10:43:43 PM]

Share this post


Link to post
Share on other sites
You can add all the numbers, divide by 3 and thats aproximately how much you have to put in every slot...
Then, if you have the numbers sorted you start with the bigger one in one slot, then add to it the bigger one you can without passing the 1/3 of the total (or the 1/3 + threshold)
Then you repeat the procedure for the other two slots...
An example: 1300 + 1200 + 1000 + 800 + 500 + 400 + 200 = 5400
5400 / 3 = 1800
Slot 1 : 1300, then you add 500 = 1800 -> OK
You have left 1200, 1000, 800, 400, 200
Slot 2 : 1200, 400, 200 = 1800 -> OK
You have left 1000, 800
Slot 3 : 1000, 800 = 1800 -> OK

I come up with this solution as I was reading, but I think is a good one...

Share this post


Link to post
Share on other sites
This should be better in the math forum I suppose.

Well the best algorithm and its complexity heavily depends on :
n : number of elements
N : number of slots
and the repartition of the values.

In the small cases you mentionned, then most of the simple algos others have given should work.

If n is small then you can test exhauslively all the combinations. I suppose with some sort of recursive function. Complexity is < n!
You can certainly accelerate the search as you did, ordering values first.

If N/n is small then you can probably state that each slot has a max size. klez algo will be alright in most cases, but will be certainly non optimal or even fail in some cases. I could also show an example where mompox fails. But the idea of the average is a good one. For instance the variance around this average could make a good measure of fitness for a genetic algorithm.

Proof:

For instance (1) :
max capacity : 1500
Slot1 : 1000 + 400
Slot2 : 900 + 500

And you still have 200, you can't put it anywhere.

But a solution exists (2) :
Slot1 : 1000 + 500
Slot2 : 900 + 400 + 200

With big N and bigger n, then probably genetic algorithm would be efficient. But they can still miss in cases similar to (2) but bigger, when the average of the slots is close to the max capacity.


[edited by - Charles B on February 27, 2004 7:52:53 AM]

Share this post


Link to post
Share on other sites
Thanks for the reply Charles
It is going a bit over whelming for me

there are also some misconseptions about terms i used in my first post. There are circuit breakers termed as slots in my post and elements in charles reply also there are electrical phases which were termed A,B,C and then termed as R,Y,B were termed slots in charles reply.

Now I should make it simple there can be many elements(Ckt Breakers) with having numbers(Load in Watt) to be divided in Three phases(R,Y and B) such that
sum of weights of elements for phase R = sum of weights of elements for phase Y = sum of weights of elements for phase C

So charles the no. of elements can range from 3 to infinity(there may be some limitation in electrical field) as you suggent the gentic algorithm there are some considerations:

What could be the equation that could fit this scenarion so that the variables can be the member of chromosome?

I have just read the example of Diophantine Equation Solver
at generation5.com there eqution was a+2b+3c+4d=30

I think we could have a similar equation or may be three equations (OH! Boy!)
lets say
"e1,e2,e3,e4......en" are our elements and "e1.load,e2.load,e3.load....en.load" will be their respective weights
then "n" will be total no of elements and
"Ten.load" will be the total weight
now "Ten.load/3=Aloadpp" (Average load per phase)
and let "thr" will be threshhold

then our equation will be
e1.load + e2.load + e3.load....X= aloadpp+thr
X can be some extent to which load can be added :o)
noooooooo

ok this
ea.load+eb.load+ec.load......=aloadpp+thr
where a,b,c... are variables(1,2,3........n)
i think it is near but not complete

ok let say
ea.load+eb.load+ec.load......e(n/3).load=aloadpp+thr
e(n/3).load is total no of elements divided into three but damn thats pretty hard range of elemnts per phase are not required to be same!!

please hlp me out!!!
waiting for quick rescue!! (SOS)
mhadi

p.s. how cold i relate this post to math fourom?

Share this post


Link to post
Share on other sites
I suppose the mods could move this thread.

It's a problem of combinations.

Example : (with the solution)
Subset 1: 1100,400
Subset 2: 1000,500
Subset 3: 900,400,200

How can you encode this combination ? That's simple, since you have n=7 elements and 3 subsets, it's something like that :


Elements (ordered) : 1100,1000,900,500,400,400,200
Subset : 1, 2, 3, 2, 1, 3, 3


So you have exactly N=3 power n combinations (my prev n! was just plain wrong). For N=3 and n=7, it's possible to test each combination. A (here the) solution is thus combination (or chromosom if you want) : 1,2,3,2,1,3,3

Now I must think a bit to find a valid algo. All I pointed is that "natural" intuitive algos can fail. It's probably more complex than what's suggested at first glance.

Exhaustive search : Brute force can certainly be highly accelerated. It's certainly the way to go, even if the algorithmic complexity (processing time) of the brute force is quite dissuasive. As shown in my example, it's possible that only one combination works, so exhaustive means reliable, other algorithm can fail.

This will be done with a recursive function of this kind :


void examine(int iElt, int iSubset)
{
int isValid;
g_Load[iSubset]++;

isValid=...; // control the max load of the subsets, etc ...
if( !isValid )
return; // Stop an unvalid branch

if( g_bFoundSolution )
return; // Ends recursion

if( iElt==0 )
return; // Leaf of the recursion reached.

examine( iElt-1, 0 );
examine( iElt-1, 1 );
examine( iElt-1, 2 );
}


Genetic algo (GA) : May miss the only valid solution (if only one exists). Probably an encoding of the permutation could constitute the chromosomes. I have already coded smthg like that, but that was 2 years ago. It's very hard to tell if a GA can reach the optimal solution. The problem is to define a good fitness.


[edited by - Charles B on February 29, 2004 6:07:59 PM]

Share this post


Link to post
Share on other sites
Thanx Charles for the solution

About algorithm I have an implementation in mind.

What we can do is generate a random chromosome assign to random elements make total of all the elements and divide it with 3 will make a fitness vector(or reference) now cross over the chromosomes(50 or so) add all the values and find the percentages

e.g.
These are our elements
1200,400,1800,900,500,100

Assign following randomly generated chromosome
1,3,2,1,3,2

Similarly make 50 of them (what could be optimal the optimal no.?)

Make crossovers for example we have got an offspring as (3,2,1,2,1,3)

Then our fitness vector will be (calculated at earlier stage)
1200+400+1800+900+500+100=round (1633.33)=1633
Fitness vector=(1633,1633,1633)for 1,2,3 respectively

Now add all values for 1,all values for 2 and all values for 3

Make out the difference and find the percentages

In our case
For 1 we got 1800+500=2300
For 2 we got 400+900=1300
For 3 we got 1200+100=1300

For 1 = |2300-1633|/smi=% for 1
For 2 = |1300-1633|/smi=% for 2
For 3 = |1300-1633|/smi=% for 3
smi=sum of multiplicative inverses of fitness values

1.Could we add up all th %ages or leave it here?
2.Where we could make use of threshold?
3.Is there is any other sort of implementations or somebody still suggest me to brute force?

I think if the thresh hold is a escape from the unavailibility of exact solution we could force the user to modify it also but greater than 200-500 will be inefficent.

thanx for those who help is anticipated
mhadi


[edited by - mhadi on February 29, 2004 9:45:55 PM]

Share this post


Link to post
Share on other sites
Before testing a GA, I suggest you code brute force first since it's 20-30 lines of code I suppose. And it's very easy to debug.

Note that the code sample I gave is not really brute force anymore. It remains exhaustive but I am sure that :

if( !isValid )
{
g_Stats[INVALID]++; // (*)
return; // Stop an unvalid branch
}

will cut more than 99% of the branches early. See the algo as a tree with 3 branches at each node. It's clear that if only a few solutions exist many branches are invalid at a certain level and quite early. Else if many solutions exist, the algo won't have to scan the whole tree. So only a small ratio of the combinations will be scanned.

Conclusion : exhaustive search should work in far less than one second with n up 20 ( 3^20 < 2^30 < 2*10^9 ).

So if you code I'd be curious you add stats (*) and send em me on my e-mail here (I will change it in my profile right now).


[edited by - Charles B on March 1, 2004 6:10:09 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!