Круг практических задач, решаемых компьютерами, постоянно расширяется. Компьютер может составить расписание деловых встреч, удобный график работы сменных экипажей автобусов, научить вас играть на пианино, а иногда и заставить задуматься, способны ли вы вообще научиться игре в шахматы. Однако это возможно лишь при одном маленьком, но неприятном условии: какой-то несчастный должен написать программу, которая будет все это делать. Как жаль, что мы не можем просто перечислить, что хотелось бы получить от программы, а все скучные детали того, как именно она это сделает, предоставить самой машине! Генетические алгоритмы, конечно, не претендуют на роль эдакого "святого Грааля" в сфере программирования, но в ряде приложений они способны на нечто довольно близкое.

Рис.1.Эффективный и неэффективный маршруты в задаче коммивояжера (ЗКВ).

   Давайте для примера посмотрим, как можно использовать генетические алгоритмы для решения "задачи коммивояжера" (ЗКВ). ЗКВ состоит в том, чтобы по данному списку городов определить, в каком порядке коммивояжер должен посетить каждый из них по одному разу, чтобы получившийся маршрут был кратчайшим из возможных или хотя бы близким к таковому. На рис. 1 показаны два маршрута для одной задачи ЗКВ - эффективный и менее эффективный (то есть более длинный).

   Генетические алгоритмы решают задачи, работая с популяцией из некоторого числа наугад взятых решений (обычно их несколько сотен; далее для определенности примем величину 500). При этом должны быть указаны правила, по которым решения, по аналогии с дарвинской "борьбой за существование":

  скрещиваются (crossover; в русской биологической литературе эта операция традиционно называется кроссинговер),

  порождают разнообразных "детей",

