Генетический алгоритм. Размещение графа на линейке

Задача минимизации длин ребер графа, размещенного на линейке. Предполагается, что расстояния между вершинами графа одинаковые. Задача решается используя генетический мутационный алгоритм. Мутации - инверсия по k-му элементу. Это означает, что k генов хромосомы не меняются, остальные подвергаются инверсии - просто записываются в обратном порядке. С каждым шагом алгоритма число k растет. На 4-м шаге алгоритм дает почти двукратное уменьшение суммарной длины ребер.

The problem of minimizing the lengths of edges placed on the line. It is assumed that a distance between vertices are equal. The problem is solved using the genetic mutation algorithm. Mutations - inversion for the k-th element. This means that k chromosome genes do not change, remaining are subjected to inversion - simply written in reverse order. With each step of the algorithm the number k increases. At the 4th step, the algorithm provides an almost twofold decrease in the total length of the edges.

Видео Генетический алгоритм. Размещение графа на линейке канала Kirsanov2011