Москва 2008 предисловие

Генетические алгоритмы. Генетические алгоритмы — популяр­ный вариант эволюционных алгоритмов. Они являются прежде всего средством решения разнообразных комбинаторных задач и задач оптимизации, но входят также и в стандартный набор инст­рументов Data Mining. Основой для создания генетических алго­ритмов считается модель биологической эволюции и методы случайного поиска; производится имитация механизмов наслед­ственности, изменчивости и естественного отбора в живой при­роде. Генетические алгоритмы работают со специально закодирован­ными данными решаемой задачи — хромосомами (строками), состоящими из элементарных логических высказываний (генов). Все множество таких комбинаций называют популяцией хромо­сом. Для поиска оптимального решения вводится способ сопос­тавления хромосом — функция жизнеспособности, определяю­щая показатель качества, ценность строки (хромосомы). Вся рабо­та генетического алгоритма направлена на поиск строки с макси­мальной жизнеспособностью, которая и станет решением задачи.
Популяция обрабатывается с помощью процедур репродукции, изменчивости (мутаций), генетической композиции. Наиболее важными среди этих процедур являются случайные мутации в индивидуальных хромосомах, обмен генами между хромосомами (кроссинговер) и рекомбинация генетического материала инди­видуальных родительских хромосом (аналогично гетеросексуаль­ной репродукции), миграции генов. Мутация состоит в том, что у случайно выбранной хромосомы изменяется один или несколько генов, в результате чего изменяются свойства всей хромосомы. Отбор заключается в выборе пары «родителей» для последующего скрещивания. В ходе совершения процедур на каждой стадии эво­люции получается популяция со все более совершенными инди­видуумами, пока не будут выполнены заданные условия.
Генетические алгоритмы привлекательны тем, что их удобно распараллеливать. Например, можно разбить «поколение» на не­сколько групп и работать с каждой из них независимо, обеспечи­вая время от времени межгрупповой обмен несколькими хромо­сомами. Однако генетические алгоритмы имеют ряд серьезных не­достатков. В частности, процесс создания исходного набора хро­мосом, критерии отбора хромосом и используемые процедуры являются эвристическими и не гарантируют нахождения «лучшего» решения. Как и в живой природе, эволюция может «заклиниться» на какой-либо непродуктивной ветви. И наоборот, два неперс­пективных «родителя», который будут исключены из эволюции генетическим алгоритмом, могут оказаться способными через несколько итераций произвести высокоэффективного потомка. Это особенно заметно при решении высокоразмерных задач со слож­ными внутренними связями. Генетические алгоритмы «капризны» в настройке и трудоемки при решении задач поиска логических закономерностей в данных. Генетические алгоритмы не составля­ют серьезной конкуренции деревьям решений и алгоритмам огра­ниченного перебора при решении задач поиска логических зако­номерностей в данных, несмотря на то, что оба последних метода тоже имеют свои принципиальные недостатки.