Genetic Algorithm Improves Shellsort

gstover writes "As a personal programming project recently, I used a genetic algorithm to find a better sequence of increments for Shellsort. It found at least one sequence that out-performs the best previously known by about 5 percent. Here is an article about it (also here). I believe this is the first time a genetic algorithm has actually improved Shellsort."

Comments

efficency vs proof - Do we want this?

[acomj]

Genetic algorithms are interesting in that they can become more efficient and modify themselves. I don't mean to sound like a ludite but is this a good way to develop algorithms?

Is the efficiency gained worth the difficulty in proving the new genetical enhanced algorithm works?

Its hard enough with vigorous testing to prove simple programs work without fail without introducing some random "Genetic" changes that may break the algorithm for some input cases.

One of the problems with AI and self modifing algorithms is that as it learns /evolves you don't get the same output from the same input.. I guess thats the point, but I don't want my programs running like that.

Re:Nice and all

[Kynde]

I guess it's a nice thing that shellsort is getting improved, and I do realize that this is great for genetic research, but, pardon me for being an uneducated ignorant bastard, does it have any practical value, seeing as quicksort is much faster than shellsort? Or am I wrong?

Shell sort has better worst-case running-time than quick sort does.

Most programming these days is all about the common case, but in real-time programming it's all about predictability. Thus there the mergesort is the standard choice over quicksort.