Author Topic: Algorithms  (Read 1767 times)

0 Members and 1 Guest are viewing this topic.

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5163
  • FET author and forum moderator
    • View Profile
    • Homepage
Algorithms
« on: June 28, 2013, 09:04:39 AM »
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.

Benahmed Abdelkrim

  • Level 5
  • *****
  • Posts: 715
  • The most beautiful is the simple
    • View Profile
Re: Algorithms
« Reply #1 on: May 21, 2016, 07:51:56 AM »
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!
« Last Edit: May 21, 2016, 07:54:23 AM by Benahmed Abdelkrim »
B.A/krim

Volker Dirr

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 1892
    • View Profile
Re: Algorithms
« Reply #2 on: May 21, 2016, 08:11:48 AM »
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.
 

Benahmed Abdelkrim

  • Level 5
  • *****
  • Posts: 715
  • The most beautiful is the simple
    • View Profile
Re: Algorithms
« Reply #3 on: May 21, 2016, 09:01:11 AM »
 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.
« Last Edit: May 21, 2016, 09:06:36 AM by Benahmed Abdelkrim »
B.A/krim

Volker Dirr

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 1892
    • View Profile
Re: Algorithms
« Reply #4 on: May 21, 2016, 09:26:55 AM »
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.

Bob Hairgrove

  • Level 1
  • *
  • Posts: 25
    • View Profile
Re: Algorithms
« Reply #5 on: August 10, 2016, 08:46:22 AM »
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).

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5163
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Algorithms
« Reply #6 on: August 10, 2016, 08:51:15 AM »
Yes, indeed, Bob :)

canhathuongnhau

  • Level 1
  • *
  • Posts: 19
    • View Profile
Re: Algorithms
« Reply #7 on: December 02, 2016, 09:18:23 PM »
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!
« Last Edit: December 02, 2016, 09:37:58 PM by canhathuongnhau »

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5163
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Algorithms
« Reply #8 on: December 03, 2016, 12:56:19 AM »
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.
« Last Edit: December 03, 2016, 04:27:46 AM by Liviu Lalescu »

canhathuongnhau

  • Level 1
  • *
  • Posts: 19
    • View Profile
Re: Algorithms
« Reply #9 on: December 03, 2016, 11:12:51 AM »
Mr Liviu Thanks for your quickly reply. Next time I will read document first before ask you :)

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5163
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Algorithms
« Reply #10 on: December 03, 2016, 11:20:56 AM »
No problem :)