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

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

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

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

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

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