You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Viliam comments on Open thread, Jul. 11 - Jul. 17, 2016 - Less Wrong Discussion

4 Post author: MrMind 11 July 2016 07:09AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (131)

Comments (131)

You are viewing a single comment's thread. Show more comments above.

Comment author: Thomas 11 July 2016 03:59:38PM *  3 points [-]

Evolution. Schedules are competing for being there. Every second 10000 or so are born and are mostly killed by the control program which let live only the top schedules according to the 30+ criteria set in the script.

Random (but perhaps clever) mutation and non-random selection, that's under the hood.

At first, the top schedule is a random one and not feasible at all. After a million (or a billion, that depends) generations the first feasible one appears and from there on, evolution produces more and more perfect schedules.

For every processor core, at least one evolution is going on. Each at least slightly different one. The program can spread across many computers and there may be as many as 100 or more parallel evolutions going on. They talk occasionally (via internet) and exchange their champions.

It has been 10 years long real life experiment, which went very well. A lot of schools involved, teachers and students and some academic papers published. Now it's time to spread it.

Comment author: Viliam 12 July 2016 07:57:08AM *  0 points [-]

Does the solution space support this? I can imagine a schedule that only violates 1 criterium, but the nearest correct solution is far away from it. (Seems to me the schedules are similar to 3-SAT in this aspect.)

Comment author: Thomas 12 July 2016 07:04:06PM 0 points [-]

Does the solution space support this? I can imagine a schedule that only violates 1 criterium, but the nearest correct solution is far away from it.

This is indeed a big and fundamental problem. If 1 criterium only is violated and this persists for many millions of generations, the control program sees this semi-solution as worse and worse. Much worse than a 2 or 4 criteriums miss. So it's then killed.

It's even more complicated than that. Several such tricks are employed and this problem almost vanishes.

Powered by Reddit Powered by Reddit