Это скорее не методы обработки данных, а общий подход к построению моделей, который может использоваться в различных методах. Идея эволюционных методов (ЭМ) заимствована у природы, это именно тот способ, которым природа создала самые высокие свои достижения - живых существ (и человека в том числе). Процесс эволюции в природе основан на трех главных принципах: наследственности, изменчивости и отборе.
Наследственность это сохранение большинства имеющихся признаков, она нужна, чтобы полезные свойства сохранялись и накапливались.
Изменчивость это возможность изменений небольшой части признаков (мутаций), она обеспечивает гибкость и возможность развития.
Отбор это проверка результатов, тот механизм, который позволяет разделить хорошие и плохие свойства.
Рис. 1. Общая схема процесса эволюции
Эти "подсмотренные" у природы принципы можно применить к решению самых разных задач, такой подход называют эволюционным. В самом общем виде схема выглядит так: у нас есть объект или несколько объектов, который мы хотим улучшить. Объектом может быть почти все что угодно: набор чисел, математическая формула, техническое устройство, химический состав, компьютерная программа и т.д. Далее, создается несколько копий исходных объектов, но не абсолютно точных копий, каждая имеет небольшие отличия. Затем надо проверить, какие из полученных объектов лучше всего соответствуют нашим требованиям. Выбрав самые лучшие, опять копируем их с небольшими изменениями и опять выбираем лучшие. Повторив такую операцию много раз мы можем значительно улучшить исходный объект. Идея эта совсем проста, и давно используется людьми, например при выведений сортов растений и пород животных. Но во многих случаях ее применение затруднительно. Процес эволюции может потребовать тысяч поколений, изготавливать и проверять такие количества реальных физических объектов часто просто невозможно и почти всегда нерентабельно. Но развитие компьютеров открыло перед ЭМ совершенно новые возможности. Вместо того, чтобы работать с реальными объектами можно работать с их математическими моделями. В этом случае размножение и проверка моделей легко осуществляются на компьютере, и эволюционные методы очень удобны.
В 70-е годы были опубликованы несколько работ в которых рассматривались методы случайного поиска с применением идей заимствованных из биологической эволюции. А первое последовательное изложение основных идей эволюционных алгоритмов было сделано в 1975 году Дж. Холландом. Его работа «Адаптация в естественных и искусственных системах» ( «Adaptation in Natural and Artificial Systems») привлекла к эволюционным методам всеобщий интерес. Эту работу обычно и считают началом развития ЭМ. Сейчас ЭМ являются одним из самых популярных направлений в соременных технологиях обработки данных.
Хотя ЭМ годятся практически для любой задачи их применение не всегда оправдано. Если мы хотя бы приблизительно можем оценить, как влияют изменения отдельных признаков на качество объекта, то обычно есть более эффективные методы поиска, чем эволюционный. Чем сложнее система и чем меньше известно о влиянии отдельных параметров на поведение системы в целом, тем более полезными могут быть ЭМ. Их ценность именно в том, что совершенно не обязательно знать какими должны быть изменения признаков для улучшения объекта, и эти изменения могут выбираться случайно.
К трем основным принципам эволюционного процесса иногда добавляют четвертый - скрещивание. Хотя скрещивание и не является обязательным для ЭМ, оно позволяет значительно увеличить их эффективность. Идея состоит в том, что разные объекты одного поколения могут независимо накапливать различные полезные признаки. Если для создания объекта потомка берется лишь один объект родитель, то для накопления всех полезных признаков может потребоваться очень много поколений, ведь изменения невелики и случайны. Скрещивание или кроссовер это способ создание объекта потомка, при котором половина свойств берется от одного объекта-родителя, а вторая половина от другого. Это позволяет сразу объединить полезные свойства независимо накопленные обоими объектами-родителями в одном объекте потомке. Методы реализующие эволюционный поиск с использованием скрещивания часто называют генетическими алгоритмами (ГА).
В различных задачах генетические алгоритмы могут различаться вероятностью и величиной мутаций, правилами, по которым делается кроссовер и т.п., но общие принципы одни и те же. Для того, чтобы задачу можно было решать эволюционными методами ее надо представит в виде модели, в которой каждое решение можно представить в виде набора некоторых параметров или свойств. Кроме того должна существовать операция проверки решений, численно оценивающая качество решения.
Какое применение могут найти генетические алгоритмы при анализе числовых лотерей? Непосредственно применить их для выбора номеров нельзя, но если у нас есть какой-нибудь метод выбора номеров с большим количеством неизвестных параметров, то с помощью ГА можно подобрать оптимальные значения этих параметров.
Рассмотрим простейший пример. Пусть у нас есть метод выбора номеров зависящий от ряда параметров, допустим a, b, c, d.... Какие значения должны иметь в идеале эти параметры мы не знаем, но можем выбрать какие -то значения a0, b0, c0, d0. случайно и протестировать метод на некотором массиве тиражей и получить в результате какой-то процент угадываний P0. Эта величина является для нас оценкой "качества" выбранного набора параметров. Теперь сделаем один шаг эволюции. Из исходного набора a0, b0, c0, d0 сформируем новый набор, в котором каждый из параметров с небольшой вероятностью может быть немного изменен. Вероятность и величина изменения должны выбираться для конкретной задачи, это те характеристики, от которых будет зависеть процесс эволюции метода. Сделаем несколько таких наборов, которые немного отличаются от исходного: (a11, b11, c11, d11, ...), (a12, b12, c12, d12, ...), (a13, b13, c13, d13, ...), ... и проверив каждый из них получим для них оценки P11, P12, P13, ... Теперь из этих наборов (включая исходный) выберем тот, для которого оценка наилучшая и используюя его как исходный создадим новые наборы (a21, b21, c21, d21, ...), (a22, b22, c22, d22, ...), (a23, b23, c23, d23, ...), ... и т.д. На каждом шаге мы будем получать набор параметров, которые по крайней мере не хуже предыдущих. Повторяя такую операцию много раз мы рано или поздно придем к набору с самыми лучшими параметрами. Но таких шагов может потребоваться очень много. Если число параметров невелико, то выгоднее использовать другие методы, например, градиентный поиск, при котором изменения параметров на каждом шаге являются не случайными, а расчитываются путем сравнения несколких наборов с близкими параметрами.
Эволюционные алгоритмы часто являются составной частью других комплексных методов анализа, например, в они лежат в основе очень эффективного метода группового учета аргументов (МГУА).
