Эволюционное программирование.
Современное состояние данного подхода иллюстрирует пример системы PolyAnalyst. Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа — методе группового учета аргументов — МГУА (см. разд. 3.4) зависимость ищут в форме полиномов.
В настоящее время из продающихся в России систем МГУА реализован в системе NeuroShell.
Генетические алгоритмы.
Data Mining — не основная область применения генетических алгоритмов. Их нужно рассматривать скорее как мощное средство решения разнообразных комбинаторных задач и задач оптимизации. Тем не менее генетические алгоритмы (см. разд.3.6) вошли сейчас в стандартный инструментарий методов Data Mining.
Первый шаг при построении генетических алгоритмов — это кодировка исходных логических закономерностей в базе данных, которые именуют хромосомами, а весь набор таких закономерностей называют популяцией хромосом. Далее для реализации концепции отбора вводится способ сопоставления различных хромосом. Популяция обрабатывается с помощью процедур репродукции, изменчивости (мутаций), генетической композиции. Эти процедуры имитируют биологические процессы. Наиболее важные среди них: случайные мутации данных в индивидуальных хромосомах, переходы (кроссинговср) и рекомбинация генетического материала, содержащегося в индивидуальных родительских хромосомах (аналогично гетеросексуальной репродукции), и миграции генов. В ходе работы процедур на каждой стадии эволюции получаются популяции со все более совершенными индивидуумами.
Примером может служить система GcncHuntcr.
С чем связано направление эволюционного программирования
Эволюционное программирование
Проиллюстрируем современное состояние данного подхода на примере системы PolyAnalyst — отечественной разработке, получившей сегодня общее признание на рынке Data Mining. В данной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход немного похож на генетические алгоритмы). Когда система находит программу, более или менее удовлетворительно выражающую искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных дочерних программ те, которые повышают точность. Таким образом система «выращивает» несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Специальный модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и пр).
Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа — методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов. В настоящее время из продающихся в России систем МГУА реализован в системе NeuroShell компании Ward Systems Group.
Стоимость систем до $ 5000.
Генетические алгоритмы
Data Mining не основная область применения генетических алгоритмов. Их нужно рассматривать скорее как мощное средство решения разнообразных комбинаторных задач и задач оптимизации. Тем не менее генетические алгоритмы вошли сейчас в стандартный инструментарий методов Data Mining, поэтому они и включены в данный обзор.
Первый шаг при построении генетических алгоритмов — это кодировка исходных логических закономерностей в базе данных, которые именуют хромосомами, а весь набор таких закономерностей называют популяцией хромосом. Далее для реализации концепции отбора вводится способ сопоставления различных хромосом. Популяция обрабатывается с помощью процедур репродукции, изменчивости (мутаций), генетической композиции. Эти процедуры имитируют биологические процессы. Наиболее важные среди них: случайные мутации данных в индивидуальных хромосомах, переходы (кроссинговер) и рекомбинация генетического материала, содержащегося в индивидуальных родительских хромосомах (аналогично гетеросексуальной репродукции), и миграции генов. В ходе работы процедур на каждой стадии эволюции получаются популяции со все более совершенными индивидуумами.
Генетические алгоритмы удобны тем, что их легко распараллеливать. Например, можно разбить поколение на несколько групп и работать с каждой из них независимо, обмениваясь время от времени несколькими хромосомами. Существуют также и другие методы распараллеливания генетических алгоритмов.
Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и используемые процедуры являются эвристическими и далеко не гарантируют нахождения «лучшего» решения. Как и в реальной жизни, эволюцию может «заклинить» на какой-либо непродуктивной ветви. И, наоборот, можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции генетическим алгоритмом, оказываются способными произвести высокоэффективного потомка. Это особенно становится заметно при решении высокоразмерных задач со сложными внутренними связями.
Примером может служить система GeneHunter фирмы Ward Systems Group. Его стоимость — около $1000.
Эволюционное программирование.
Проиллюстрируем современное состояние данного подхода на примере весьма распространенной системы Poly Analyst. В данной системе гипотезы о виде зависимости целевой переменной от других переменных формулируются в виде программ на некотором внутреннем языке программирования. Процесс построения программ строится как эволюция в мире программ (этим подход похож на генетические алгоритмы, см. далее). Когда система находит программу, достаточно точно выражающую искомую зависимость, она начинает вносить в нее небольшие изменения и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Так система «выращивает» несколько генетических линий программ, которые конкурируют между собой в точности выражения искомой зависимости. Специальный транслирующий модуль системы PolyAnalyst переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и проч.), из-за чего они становятся легкодоступными. Для того чтобы полученные результаты были еще понятнее для пользователя- нематематика, имеется богатый арсенал разнообразных средств визуализации обнаруживаемых зависимостей. Для контроля статистической значимости выводимых зависимостей применяется набор современных методов, например рандомизированное тестирование.
Другое направление эволюционного программирования связано с поиском зависимости целевых переменных от остальных в форме функций какого-то определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа — методе группового учета аргументов — зависимость ищут в форме полиномов.
Генетические алгоритмы нужно рассматривать как мощное средство решения разнообразных комбинаторных задач и задач оптимизации. В то же время генетические алгоритмы вошли в стандартный инструментарий методов Data Mining.
Пусть нужно найти решение задачи, оптимальное с точки зрения некоторого критерия, и пусть каждое решение полностью описывается некоторым набором чисел или величин нечисловой природы. Скажем, если нужно выбрать совокупность фиксированного числа параметров рынка, наиболее выраженно влияющих на его динамику, это будет набор имен этих параметров. Об этом наборе можно говорить, как о совокупности хромосом, определяющих качества индивида — данного решения поставленной задачи. При этом значения параметров, определяющих решение, целесообразно называть генами, а поиск оптимального решения будет похож на эволюцию популяции индивидов, представленных их наборами хромосом. В этой эволюции действуют три механизма:
1) отбор сильнейших — наборов хромосом, которым соответствуют оптимальные решения; 2) скрещивание — производство новых индивидов при помощи смешения хромосомных наборов отобранных индивидов; 3) мутации — случайные изменения генов у некоторых индивидов популяции. В результате смены поколений в конце концов вырабатывается такое решение поставленной задачи, которое уже не может быть далее улучшено.
Генетические алгоритмы имеют ряд недостатков. Критерий отбора хромосом и сама процедура являются эвристическими и вовсе не гарантируют нахождения лучшего решения. Как и в реальной жизни, эволюцию может «заклинить» на какой-либо непродуктивной ветви. В то же время можно привести примеры, как два неперспективных родителя, которые будут исключены из эволюции генетическим алгоритмом, оказываются способными произвести высокоэффективного потомка. Это становится особенно заметно при решении высокоразмерных задач со сложными внутренними связями.
Алгоритмы ограниченного перебора были предложены в середине 1970-х гг. М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.
Эволюционные алгоритмы
Эволюционные алгоритмы — направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует процессы естественного отбора.
Виды алгоритмов
- генетические алгоритмы — эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров;
- генетическое программирование — автоматическое создание или изменение программ с помощью генетических алгоритмов;
- эволюционное программирование — аналогично генетическому программированию, но структура программы постоянна, изменяются только числовые значения;
- программирование экспрессии генов
- эволюционные стратегии — похожи на генетические алгоритмы, но в следующее поколение передаются только положительные мутации;
- дифференциальная эволюция;
- нейроэволюция — аналогично генетическому программированию, но геномы представляют собой искусственные нейронные сети, в которых происходит эволюция весов при заданной топологии сети, или помимо эволюции весов также производится эволюция топологии;
- системы классификаторов;
Все они моделируют базовые положения в теории биологической эволюции — процессы отбора, мутации и воспроизводства. Поведение агентов’ определяется окружающей средой. Множество агентов принято называть популяцией. Такая популяция эволюционирует в соответствии с правилами отбора в соответствии с целевой функцией, задаваемой окружающей средой. Таким образом, каждому агенту (индивидууму) популяции назначается значение его пригодности в окружающей среде. Размножаются только наиболее пригодные виды. Рекомбинация и мутация позволяют изменяться агентам и приспособляться к среде. Такие алгоритмы относятся к адаптивным поисковым механизмам.
Эволюционные алгоритмы успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на математическом языке.
Отрасли использования
Эволюционные алгоритмы используются при комбинаторной оптимизации, в частности при решении классических NP-полных проблем, таких как задача коммивояжера, задача упаковки ранца, разбитие чисел, максимально независимое множество и зарисовка графов.