Генетические алгоритмы в МиниБоте
Генетические алгоритмы: почему они работают? когда их применять?
РОСС КЛЕМЕНТ, Опубликовано: 16.3.1999
взято от сюда http://www.mnogosmenka.ru/drugoe/genetitiskie.htm
© 2002, Издательский дом «КОМПЬЮТЕРРА» | http://www.computerra.ru/
Журнал «Компьютерра» | http://www.computerra.ru/
Этот материал Вы всегда сможете найти по его постоянному адресу: http://www.computerra.ru/offline/1999/289/2523/
XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..
Росс Клемент (Ross Clement; R.P.Clement@westminster.ac.uk) окончил Оклендский университет (Новая Зеландия) по специальности "Компьютерные науки". Защитил диссертацию и получил степень "Doctor of Engineering" в Техническом университете Тойохаши (Toyohashi University of Technology) в Японии. В 1991-93 годах занимался приложениями генетических алгоритмов к задачам составления расписаний. С 1993 года - лектор в Школе компьютерных наук в Харроу, в Университете Вестминстера (Лондон). Научные интересы: генетические алгоритмы, интеллектуальные агенты, фрактальная музыка.
Рис. 1.Эффективный и неэффективный маршруты в задаче коммивояжера (ЗКВ).
Круг практических задач, решаемых компьютерами, постоянно расширяется. Компьютер может составить расписание деловых встреч, удобный график работы сменных экипажей автобусов, научить вас играть на пианино, а иногда и заставить задуматься, способны ли вы вообще научиться игре в шахматы. Однако это возможно лишь при одном маленьком, но неприятном условии: какой-то несчастный должен написать программу, которая будет все это делать. Как жаль, что мы не можем просто перечислить, что хотелось бы получить от программы, а все скучные детали того, как именно она это сделает, предоставить самой машине! Генетические алгоритмы, конечно, не претендуют на роль эдакого "святого Грааля" в сфере программирования, но в ряде приложений они способны на нечто довольно близкое.
Давайте для примера посмотрим, как можно использовать генетические алгоритмы для решения "задачи коммивояжера" (ЗКВ). ЗКВ состоит в том, чтобы по данному списку городов определить, в каком порядке коммивояжер должен посетить каждый из них по одному разу, чтобы получившийся маршрут был кратчайшим из возможных или хотя бы близким к таковому. На рис. 1 показаны два маршрута для одной задачи ЗКВ - эффективный и менее эффективный (то есть более длинный).
Генетические алгоритмы решают задачи, работая с популяцией из некоторого числа наугад взятых решений (обычно их несколько сотен; далее для определенности примем величину 500). При этом должны быть указаны правила, по которым решения, по аналогии с дарвинской "борьбой за существование":
- скрещиваются (crossover; в русской биологической литературе эта операция традиционно называется кроссинговер),
- порождают разнообразных "детей",
- соперничают за ограниченные ресурсы,
- мутируют
- и, в конечном счете, умирают.
Рис. 2. Схема работы генетического алгоритма.
Схема типичного генетического алгоритма представлена на рис. 2. В статье мы обсудим, как работают различные блоки из этой схемы.
Разработка генетического алгоритма начинается с конструирования двоичной хромосомы, представляющей возможные решения этой задачи. Традиционно генетические алгоритмы используют для этого двоичные строки фиксированной длины. Например, для нашей ЗКВ с четырьмя городами, которые надо поочередно посетить, проще всего было бы выделить по 2 бита на каждый город, получив 8-битовую хромосому. Рисунок 3 поясняет, как записывается информация на такую хромосому. Можно построить множество случайных строк из 8 бит, интерпретируя их как маршруты объезда городов.
