Hello,
Since FET is quite in a stable state, I would like to think of other algorithms. Maybe you have some suggestions.
I tried applying the FET recursive swapping algorithm to the 3-satisfiability problem, but it fails miserably compared to other very fast methods, like gnovelty+, which is based on a simple algorithm. I am sure, looking at many FET users, that FET algorithm is very efficient. I also tried simple methods before in FET, but they failed by far.
I would like to have a longer discussion here, on useful things for me to do, as I am stalling.
general : every problem requires a specific algorithm .
if an algorithm successful to solve a problem , it is not necessary that he managed to solve else!
that is wrong. every mathematic do that.
mainly because of 2 reasons:
a) proof that the old algorithm and/or solution is correct
b) check if the other algorithm is faster.
thank you Mr. volker for your quick reply. there is a malentedu, I have not talked about the accuracy of the algorithm, but its convenience in relation to the problem.
example: the genetic algorithm is corect, but has proven its limits for the problem of the time table; it is slow, it is the main reason it is replaced by the heuristic algorithm.
yes, but there are many other possible algorithms we didn't checked yet.
also we didn't proof that the current one is correct. maybe there is still a bug and it can find only 99.9999% of all possible solutions.
in normal case not critical, but in wost case we might skip possible solution and we will never find a solution with this algorithm even there is one.
i think Liviu also talked a bit more general. so not only timetabling algorithms.
Quote from: Volker Dirr on May 21, 2016, 04:26:55 PM
yes, but there are many other possible algorithms we didn't checked yet.
also we didn't proof that the current one is correct. maybe there is still a bug and it can find only 99.9999% of all possible solutions.
in normal case not critical, but in wost case we might skip possible solution and we will never find a solution with this algorithm even there is one.
i think Liviu also talked a bit more general. so not only timetabling algorithms.
I have read somewhere that timetabling belongs to the class of problems which are "NP complete" (or "NP hard"?) In other words, there is no algorithm which is guaranteed to find a solution, or which can guarantee that there is no solution with the given data, except for brute force. There are only heuristic algorithms, some of which work better than others.
However, I am not a computer scientist or engineer, so I think that the present algorithm which introduces an element of randomness to the search path works quite well. If one generation takes too long, you can cancel it and try again. The random ordering should make it possible to find a solution quickly (if there is one).
Yes, indeed, Bob :)
Dear Mr Liviu,
I'm research about FET. So can you tell me what is exactly algorithms that you use in FET?
Hopefully, I can get your information as soon as possible.
Thanks so much!
Please see http://lalescu.ro/liviu/fet/doc/ , "Timetable generation algorithm".
There are also some other topics here on the forum about the algorithm, you may search the forum.
Mr Liviu Thanks for your quickly reply. Next time I will read document first before ask you :)
No problem :)