Генетические алгоритмы

Исследование генетических алгоритмов (genetic algorithms) заключается в попытках применения нашего понимания естественной эволюции к решению задач. Этот подход подразумевает соединение лучших представителей из набора предложенных решений для получения решений следующего поколения, обладающих преимуществами по сравнению с исходным набором. Повторяя этот процесс снова и снова, можно имитировать процесс эволюции и в итоге получить подходящие решения актуальной проблемы.

В качестве примера предположим, что вы играете в покер с одними и теми же друзьями каждую среду и хотите разработать стратегию увеличения ваших шансов на выигрыш. Эволюционный подход к этой задаче начинается с выявления различных ситуаций, которые могут произойти во время игры в покер, и потенциальных ответов на каждую из них. Это, конечно же, самая объемная часть решения, так как рассмотреть придется множество ситуаций. После завершения анализа мы можем сконструировать стратегию игры в покер, задав определенную реакцию на каждую ситуацию. Любую стратегию можно представить в виде списка в форме S,R1? S2R2, -, SnRn, где буквой S обозначаются потенциальные ситуации, a R — это ответ на данную ситуацию. Представления различных стратегий состоят из одинаковых последовательностей ситуаций, но за этими ситуациями следуют разные реакции. Чтобы применить определенную стратегию, необходимо просто найти подходящую ситуацию в списке и воспроизвести соответствующий ей ответ.

Следующий шаг в нашей задаче — это выбор исходного набора стратегий и применение их во время игры в покер, причем необходимо регистрировать выигрыши, полученные при применении каждой стратегии. Основываясь на этом анализе, мы затем выберем наилучшие из исходных стратегий и сгруппируем выбранные стратегии попарно. Из каждой такой пары мы создадим две новые стратегии; для этого разделим списки, соответствующие двум стратегиям, на две части и присоединим начало одного списка к концу другого (рис. 10.24). Получившийся набор новых стратегий проверим на следующей неделе. Так, каждую неделю мы будем снова выбирать наилучшие стратегии и из них создавать новое поколение стратегий для проверки на очередной неделе. Таким образом, с ходом времени наш процесс будет имитировать естественный эволюционный процесс, в котором выжившие представители каждого поколения порождают следующее поколение. В действительности мы можем даже имитировать мутации, случайным образом изменяя по одному ответу в каждой стратегии за один раз.

К сожалению, наш пример с покером не слишком реалистичен, так как проверить большой набор стратегий за один вечер невозможно. Однако если автоматизировать процесс игры, как это можно сделать со многими другими приложениями, эволюционный подход вполне применим. Например, этот процесс предлагается для исследований генетических алгоритмов. Сначала ищется способ представления возможных решений в виде строк символов. Затем создается и проверяется набор потенциальных решений. Наилучшие экземпляры из этого набора скрещиваются для формирования нового поколения возможных решений, которые, в свою очередь, также проверяются и формируют следующее поколение. Во время процесса скрещивания иногда можно применять случайные мутации.

Эволюционный подход применяется во многих областях с весьма обнадеживающими результатами. Например, проектирование конфигураций искусственных нейронных сетей. Предположим, что мы хотим решить какую-либо задачу при помощи искусственной нейронной сети, состоящей из предопределенного количества блоков обработки данных. Перед тем как мы начнем обучать сеть, необходимо решить, каким образом будут соединены блоки. Пусть конфигурации искусственной нейронной сети обозначаются строками, состоящими из нулей и единиц, расположенных в соответствии с определенной системой. Предполагая, что в системе будет пять блоков обработки данных, пометим их цифрами от 1 до 5 (рис. 10.25, а). Затем построим квадратную таблицу из пяти строк и пяти столбцов (рис. 10.25, 6). На пересечении i-й строки и j-ro столбца мы помещаем единицу, если в нашей сети выход i-ro блока соединен с входом j-vo блока обработки данных. Во все остальные ячейки таблицы мы помещаем 0. Затем последовательно записываем строки таблицы в одну большую строку (рис. 10.25, в).

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

Такой подход успешно применяется в разработке простых искусственных нейронных сетей.

Техника генетических алгоритмов также применяется при проектировании программ; эта область называется эволюционным программированием (evolutionary programming). Цель исследований — научиться создавать программы, позволяя им самостоятельно эволюционировать, а не просто писать их. Важный шаг в этом исследовании — поиск путей взаимодействия частей программ и создания новых осмысленных программ. Парадигму функционального программирования составляют вложенные функции, где выход одной функции используется как вход для другой. Таким образом, можно поменять местами функции из двух программ, не разрушая структуру этих программ.

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

Область исследования эволюционного программирования находится еще в зачаточном состоянии. Успех достигнут только для простейших случаев. Например, эволюционные техники применялись для создания программ, рассчитывающих свойства простых геометрических фигур, например площади квадрата или длины окружности. Основная проблема заключается в выявлении среди группы программ, ни одна из которых не кажется близкой к желаемому результату, «наилучших представителей». Такая же ситуация и в других областях генетических алгоритмов; смогут ли рассматриваемые техники развиться настолько, чтобы суметь решить важные, значительные проблемы? В любом случае, генетические алгоритмы ярко иллюстрируют, с каким творчеством и воображением подходят к "исследованиям информационных технологий сегодняшние ученые.