Игнаси Белда - Том 33. Разум, машины и математика. Искусственный интеллект и его задачи

Метод селекции, основанный на принципе колеса рулетки, достаточно прост. Он заключается в том, что каждая особь может быть выбрана с вероятностью, пропорциональной ее приспособленности по отношению к приспособленности остальных особей. Следовательно, если нужно отобрать 10 особей, колесо рулетки потребуется вращать 10 раз.

В примере на рисунке представлено восемь особей и значения их функции приспособленности в процентах от целого. Как вы можете догадаться, при каждом вращении рулетки вероятность выбора определенной особи будет пропорциональной отношению ее значения функции приспособленности к целому. Метод рулетки не исключает возможность выбора менее приспособленных особей — они всего лишь будут выбираться с меньшей вероятностью. Если мы будем вращать колесо рулетки 10 раз, то несколько раз обязательно выберем приспособленных особей, но также вероятно, что несколько раз выбранные особи будут не самыми конкурентоспособными. Именно возможность выбора неконкурентоспособных особей делает генетические алгоритмы столь мощными: это позволяет следовать несколькими путями одновременно, открывать другие варианты, выявлять множество различных максимумов, а в долгосрочной перспективе — находить хорошее локальное решение, а в лучшем случае — глобальный максимум.

Еще одна стратегия отбора, пригодная для решения сложных задач, — это ранговая селекция. При ее использовании отбирается nкопий наиболее приспособленной особи, n — 1 — второй по порядку и так далее до n= 0. Эта стратегия исключает вероятность того, что некая «сверхособь» снизит вероятность отбора прочих особей.

(«Сверхособью» называется особь, далекая от оптимальной, но намного превышающая по своим параметрам прочих особей из своего поколения.) Наличие сверхособей приводит к тому, что популяция оказывается скученной возле нее, и улучшить результаты становится невозможно.

Третья стратегия, турнирная селекция, заняла монопольное положение среди стратегий отбора, используемых при решении реальных задач, благодаря выгодным математическим свойствам и высокой гибкости при моделировании давления отбора. При турнирной селекции используется тот же принцип, что и при объединении спортивных команд в пары при игре на выбывание. Особи отбираются попарно случайным образом, и оптимальной считается та особь, которая побеждает в этом воображаемом турнире. Следовательно, при турнирной селекции необходимо отобрать столько пар, сколько особей необходимо выбрать. Почему эта стратегия считается очень гибкой при моделировании давления отбора? Что произойдет, если мы будем организовывать «турниры» не между двумя, а между nособями? Что если в турнире будет одерживать верх не одна, а mособей? В таком случае говорят, что проводится турнир n: m. С увеличением nдавление отбора будет повышаться, с увеличением m— понижаться.

Чтобы лучше понять схему проведения турнира, представьте себе начальные этапы футбольной Лиги чемпионов. Они проводятся по схеме 4:2 — футбольные команды объединяются произвольным образом в группы по четыре, а две лучшие переходят в следующий этап. Конечно, в примере с Лигой чемпионов нельзя говорить о действительно случайном турнире, так как при формировании групп учитываются определенные критерии — так, в одну группу не могут попасть две команды из одной страны. Однако мы тоже можем вводить свои правила при использовании эволюционных алгоритмов, что будет определять тот или иной тип эволюции.

Часто используется правило, согласно которому в одном турнире соперничают максимально похожие особи. Алгоритм способен находить оптимальные значения функции со множеством оптимумов.

Эти роботы-крабы определяют участки с максимальной освещенностью. У одного из этих роботов нет ног, у другого их сразу четыре. Создатель роботов, Джош Бонгардиз Вермонтского университета, описал их поведение с помощью эволюционного генетического алгоритма и смог показать, что они действовали лучше, чем классические роботы, созданные с той же целью.

После отбора особей, которые оставят потомство, наступает этап размножения.