reduce time for a specific code
Theodora
you the general idea of the code, there is an electrical
network which has 18 switches. Using GA, the program tests
several topologies (combination of open and closed
switches)in order to find the best topology so that the
network runs more economically. The representation of the
opened and closed switches is done by using 1 and 0
respectively.
In order to improve the CPU time, I thought that the program
should use two matrices: one to store every valid (according
to some criteria) topology and the cost associated with it,
and the other to store the invalid topologies. Therefore,
for every topology that the GA produces, those matrices are
going to be checked first before the actual test takes place
in order to save some time.
What do you think of that? Will it be efficient? And how
should I store the values in the matrices? Will it be faster
if I turn each topology into a decimal number, or it would
be the same?
Any other suggestions are also welcome!
Rune Allnor
The first step is to forget about GAs. After that it is
a matter of convenience whether to choose a graph flow
computation algorithm (Dijkstra's algorithm?) or a brute
search. Graph flow analysis is a bit trickier to implement,
but will run the fastest. Brute searches are easy to
implement but will take the longest to run.
You have 18 swithches, each will be open or closed, meaning
there are 2^18 = 250000 combinations all in all. That's not
an awful lot, these days. Assuming that it takes less than
10 ms to compute the fitness of one topology, the brute
search will take less than an hour.
Rune
Theodora
<b1982b98-7308-4a98...@w7g2000hsa.googlegroups.com>...
Thanks a lot! Since I don't have experience in any of them I
have to read about them and see if they can be applied to
the problem. However, the small search I did in wikipedia,
the Dijkstra's algorithm don't seem the right one.
Rune Allnor
> RuneAllnor<all...@tele.ntnu.no> wrote in message
>
> <b1982b98-7308-4a98-9f58-d06219f1c...@w7g2000hsa.googlegroups.com>...
There might be some specialized algorithm available in
the field where your network originates. You might want to
run some tests and see how long it takes to do the computations
for one case, to see how long a brute search will take.
Try and take the time of a loop which computes 100 or 1000
cases, and compute the per case average.
Rune
Theodora
Well, the 2^18 cases are actually much more, because for
each case, in order the topology to be valid, adjustments to
39 transformers can be made. Those adjustments are discrete
of +/- 8 steps, which means 17 possible changes for each
transformer. For this part of the code GA is also used in
order to find the best adjustment. Now I think it's clear
that it is not possible to test all the topology candidates
and why GA was selected.
Rune Allnor
> Well, the 2^18 cases are actually much more, because for
> each case, in order the topology to be valid, adjustments to
> 39 transformers can be made. Those adjustments are discrete
> of +/- 8 steps, which means 17 possible changes for each
> transformer. For this part of the code GA is also used in
> order to find the best adjustment. Now I think it's clear
> that it is not possible to test all the topology candidates
> and why GA was selected.
Then you need to profile the code and see where it spends the
most time. Mind you, I've seen GAs run literally for weeks without
producing useful results, so it is always the question when
to abort the GA - maybe it will find the ideal solution if it
is allowed to run for another hour. Or day. Or month.
There is just no way to know.
Rune