Диплом.tex

\documentclass[utf8,a5paper,portrait,10pt]{eskdtext}
\usepackage{eskdplain}

\usepackage[T2A]{fontenc}
\usepackage{pscyr}

\usepackage{pstricks}
\usepackage{tikz}

\renewcommand{\ESKDtitleFontI}{\ESKDfontIIsize}
\renewcommand{\ESKDtitleFontIII}{\fontsize{8pt}{8pt}}
\renewcommand{\ESKDtitleFontIV}{\fontsize{14pt}{14pt}}
\renewcommand{\ESKDtitleFontVIII}{\fontsize{12pt}{12pt}}
\renewcommand{\ESKDtitleFontX}{\ESKDfontII\upshape}

\setcounter{tocdepth}{2}

\begin{document}

\ESKDdepartment{Санкт-Петербургский Государственный Политехнический
                Университет}
\ESKDcompany{Факультет Технической Кибернетики}
\renewcommand{\ESKDapprovingName}{Работа допущена к защите}
\ESKDtitleApprovedBy{Зав. кафедрой}{И. Г. Черноруцкий}
\ESKDtitle{Дипломная работа}
\ESKDdocName{Тема «Использование генетических алгоритмов
для автоматизированного написания программ»}

\renewcommand{\ESKDtheTitleFieldVIII}{
\begin{flushleft}
Направление: 230100 — Информатика и вычислительная техника.\\
Специальность: 230105 — Программное обеспечение вычислительной техники
и автоматизированных систем.

\vspace{10mm}
Исполнитель: \hfill Ситник Андрей Андреевич \\
Научный руководитель: \hfill  Амосов Владимир Владимирович \\
Рецензент: \hfill \\
\end{flushleft}}

\renewcommand{\ESKDtheTitleFieldX}{Санкт-Петербург 2001}

\maketitle

\tableofcontents

\newpage
\section{Актуальность темы}

\subsection{Авто-написание программы}

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

Но есть области информационных технологий, где создание программы невероятно
сложно, а описание требований к ней — относительно простое:
\begin{itemize}
  \item Программирование сложных систем, состоящих из автономных объектов
        взаимодействующих друг с другом. Например, группировка простых
        спутников. Такие сложные системы очень надёжны (выход одного элемента
        лишь немного уменьшает мощность множества) и эффективны (из-за
        параллельной работы).
  \item Поиск оптимальных стратегий для теории игр, макроэкономики и
        эволюционной биологии.\cite{communication}
\end{itemize}

Поиск решений для данных задач довольно трудоёмок и сейчас слишком похож на
метод проб и ошибок. Например, чтобы найти оптимальную стратегию в Повторяющейся
дилемме заключённого, её автор, Роберт Аксельрод, просто пригласил знакомых
коллег со всего мира предложить своё решение и выбрал лучшее.\cite{dilemma}

Автоматическая разработка программ способна заменить человека в этом сложном,
долгом и не интересном поиске.

Поскольку сложные системы, теория игр, макроэкономика и эволюционная биология
являются очень востребованными областями науки, то и инструмент для них будет
очень актуален.

\subsection{Саморазвитие программы}

В данный момент изменения в алгоритм программы вносит её разработчик. Тогда,
когда это экономически неоправданно или невозможно, алгоритм делают зависимым
от констант и конечные пользователи или автоматика меняют эти настройки.

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

Саморазвитие программ будет очень актуально для:
\begin{itemize}
  \item Защиты от спама, чтобы автоматически подстраиваться под новые уловки,
        когда пользователь отмечает письмо как рекламное.
  \item Алгоритмов противника в компьютерных играх, чтобы подстраиваться под
        способности и навыки игрока.
  \item Автоматических роботов, чтобы изменять программу управления при
        поломках и других непредвиденных ситуациях.\cite{damage} Это особенно
        полезно в областях, где человек не может прийти ему на помощь, а связь
        затрудненна, например, в космосе.
\end{itemize}

\newpage
\section{Постановка задачи}
Разработчик формулирует требование к алгоритму $a$ в виде оценочной
функции $T$, так чтобы более подходящий для задачи алгоритм давал больший
результат $T(a)$. Разработчик также предоставляет функцию останова $F$, такую,
что $F(T(a))$ вернёт 1, если алгоритм $a$ полностью подходит и цель разработки
достигнута.

Цель данной работы, предоставить инструментарий для разработчика, реализующий
операцию $G(T, F) = a$, которая генерирует алгоритм $a$, получающий максимальное
значение в оценочной функции $T$ и удовлетворяющий критерию останова $F$.

Инструментарий будет использоваться для изучения генетических алгоритмов, так
что важно, чтобы итоговый алгоритм был понятен человеку и весь процесс его
генерации можно было наглядно представить и проанализировать.

\newpage
\section{Генетические алгоритмы}

\begin{figure}
  \centering
  \input{./images/evolution.tex}
  \caption{Генетический алгоритм}
\end{figure}

Как мы видим, задача сводится к оптимизации функции $T(a)$. Однако характер этой
функции неизвестен. Для подобных задач оптимизации весьма эффективны
генетические алгоритмы.\cite{reinforcement}

Генетический алгоритм $G_{ga}$ работает сразу с множеством кандидатов на решение
(популяцией) $A = [a_1, a_2, …, a_n]$. Это итерационный процесс и каждый шаг
$A_i = G_{ga}(A_{i-1})$ немного улучшает оценочную функцию (за значение
оценочной функции популяции, принимается оценочная функция лучшего члена
популяции).

Каждая итерация $G_{ga}(A) = S(Mi(Mu(R(A))))$ состоит из\\
операций:\cite{reinforcement}
\begin{enumerate}
  \item Размножения $R(A)$ — увеличения популяции простым копированием.
        Поскольку последующий отбор уменьшит популяцию, размножение поддерживает
        её размер на каждом шаге.
  \item Мутации $Mu(A)$ — случайного изменения элементов.
  \item Смешивания $Mi(A)$ — объединения двух элементов со случайным выбором
        частей из каждой половины.
  \item Отбора $S(A)$ — удаление наименее подходящих кандидатов: для каждого
        элемента популяции вычисляется оценочная функция и элементы с
        наименьшим её значением изымаются из множества.
\end{enumerate}

В конце каждой итерации с помощью функции останова $F(A)$, которую задаёт
разработчик, определяется нужно ли остановить цикл.

\section{Анализ проблемы}

В данным момент, при создании программы, разработчики представляют алгоритм в
виде иерархического дерева команд на одном из множества языков программирования.
Компилятор транслирует исходный текст в машинный код — список команд с условными
переходами.

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

\newpage
\section{Обзор имеющихся решений}

\subsection{Нейронная сеть}

В исследованиях эволюции\cite{communication} довольно часто поведение объекта 
кодируют с помощью нейронной сети:\cite{neural}
\begin{itemize}
  \item Обработка происходит в множестве простых элементов, нейронов.
  \item Сигналы передаются между нейронами через связи.
  \item Каждая связь характеризуется весом, в зависимости от знака которой
        передаваемый сигнал увеличивается или уменьшается.
  \item Каждому нейрону соответствует активационная функция, которая определяет 
        зависимость выходного сигнала от комбинации входящих сигналов.
\end{itemize}

Несмотря на то, что элементы нейронной сети имеют очень ограниченные
вычислительные способности, вся сеть в целом, объединяя большое число таких
элементов, оказывается способной выполнять весьма сложные задачи.

Нейронная сеть представляется в виде матрицы весов $X$, так что элемент
$x_{ij}$ соответствует весу связи от нейрона $i$ к нейрону $j$. Мутация
вносит случайные изменения в веса и, с небольшой вероятностью, добавляет или
удаляет новый нейрон. Смешивание либо усредняет веса между двумя матрицами, либо
случайным образом выбирает ячейки из матриц-«родителей».

К сожалению, человек не может понять алгоритм нейронной сети при беглом взгляде
на матрицу или граф, что требуется в поставленной задаче.

\subsection{Конечные автоматы}

В рамках развития идей А. А. Шалыто о автоматном программировании
рассматривается генерация конечного автомата с помощью генетических
алгоритмов.\cite{shalyto}

Конечный автомат характеризуется множеством состояний и матрицей переходов $X$,
где $x_{ji}$ содержит дискретный код условия при котором автомат перейдёт из
состояний $i$ в состояние $j$.

Матрица состояний преобразуется в битовую строку, с которой генетический
алгоритм и работает: мутация случайно изменяет биты, смешивание объединяет две
строки в одну, случайно выбрав символы из каждой.

К сожалению, для поставленной задачи автоматы имеют ряд недостатков:
\begin{itemize}
  \item Они не полны по Тьюрингу, что несколько ограничивает их гибкость.
  \item Чтобы быть понятными разработчику их надо представить в виде графа, а
        работа с графикой сложнее, чем с обычным текстом.
\end{itemize}

\newpage
\section{Обзор языка $D^2NA$}

\subsection{Анализ}

Поскольку целью работы является создания понятного и удобного представления
алгоритма для человека, то за основу возьмём современный высокоуровневый язык
программирования.

Первая проблема, которая усложняет случайные изменения в алгоритме —
иерархичность. Уберём её, представив программу в виде набора
условных операторов (\texttt{if}) внутри одного большого постоянного цикла
(\texttt{while}):

\begin{verbatim}
while (true) {
  if (…) {
    …
  }
  if (…) {
    …
  }
}
\end{verbatim}

Будем создавать \texttt{if}-оператор для каждого возможного условия. Чтобы
условных операторов было слишком много, ограничим возможные условия проверки:
\begin{itemize}
  \item поступление внешнего сигнала;
  \item переменная имеет значение больше нуля;
\end{itemize}

\newpage
\begin{verbatim}
while (true) {
  if (on_siganl('Input')) {
    …
  }
  if (on_siganl('Input') && a > 0) {
    …
  }
  if (a > 0) {
    …
  }
}
\end{verbatim}

Чтобы упростить внесение случайных изменений, уменьшим количество возможных
команд:
\begin{itemize}
  \item увеличение переменой на единицу;
  \item уменьшение переменой на единицу;
  \item отправка исходящего сигнала;
\end{itemize}

\begin{verbatim}
while (true) {
  if (on_siganl('Input')) {
    a += 1;
  }
  if (on_siganl('Input') && a > 0) {
    send('Output');
    a -= 1;
    a -= 1;
  }
  if (a > 0) { }
}
\end{verbatim}

\subsection{Описания языка}

В рамках данной работы был создан особый язык программирования $D^2NA$.

Программа на $D^2NA$ с внешним миром общается с помощью входящих и исходящих
сигналов. Они характеризуются только именем и не имеют параметров и
продолжительности. Количество и имена сигналов напрямую зависят от задачи и
задаются разработчиком. Имя сигнала должно начинаться с двоеточия и заглавной
буквы и может состоять из букв, цифр и знака подчёркивания (например,
\texttt{:Input}).

Существует особый сигнал \texttt{:Init}, которые посылается в программу при её
запуске. Он является своего рода конструктором.

Программа может хранить внутреннее состояние в знаковых целочисленных
переменных. Генератор может автоматически добавлять или удалять их. Имя
переменной должно начинаться с двоеточия и прописной буквы и может состоять из
букв, цифр и знака подчёркивания (например, \texttt{:a}).

Программа состоит из списка правил. Правило характеризуется условием выполнения
и списком команд (правило можно представить в виде оператора if). Условие может
быть двух видов: поступление определённого сигнала и значение определённой
переменной больше 0. Поскольку имена сигналов и переменных отличаются и для
них возможна только одна проверка, то условие записывается как \texttt{on} с
последующими именами сигналов или переменных, разделёнными запятыми (например,
\texttt{on~:Input, :a}).

Команды в правиле будут выполнены только если все проверки условия будут
истинными. Команды записываются между \texttt{do} и \texttt{end} и могут быть
трёх видов: послать исходящий сигнал (\texttt{send X}), увеличить
(\texttt{up~x}) или уменьшить (\texttt{down x}) значение переменной.

\subsection{Пример программы на $D^2NA$}
\begin{verbatim}
on :Init do
  up :ping
end

on :Print, :ping do
  send :Ping
  down :ping
  up :pong
end

on :Print, :pong do
  send :Pong
  down :pong
  up :ping
end
\end{verbatim}

Данная простая программа посылает поочерёдно \texttt{:Ping} или \texttt{:Pong}
при каждом входящем сигнале \texttt{:Print}. Чтобы помнить, какой сигнал нужно
послать следующим используются две переменные \texttt{:ping} и \texttt{:pong}.

При запуске программы (при системном сигнале \texttt{:Init}) переменная
\texttt{:ping} увеличивается до значения 1. Далее, когда пришёл сигнал
\texttt{:Print} и значение \texttt{:ping} больше нуля, посылается сигнал
\texttt{:Ping}, \texttt{:ping} уменьшается до 0, а \texttt{:pong}, наоборот,
увеличивается до 1.

При сигнале \texttt{:Print} и положительном значении \texttt{:pong}, посылается
сигнал \texttt{:Pong} и происходит обратная процедура.

\subsection{Генерация программы на $D^2NA$}
Программа на $D^2NA$ представляет из себя просто список списков, которые
генетическому алгоритму удобно смешивать и переставлять.

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

Смешивание просто объединяет переменные и случайно выбирая половину правил из
«родителей», формирует новую программу.

Код программы $D^2NA$ представляется из себя обычный текст и очень похож на
современные языки программирования. Его легко понять понять разработчику,
и к нему легко применять множество инструментов для анализа текста (например,
смотреть различия с помощью UNIX-программы \texttt{diff}).

\newpage
\section{Архитектура генератора}

\begin{figure}
  \centering
  \input{./images/architecture.tex}
  \caption{Архитектура генератора}
\end{figure}

Инструментарий для $D^2NA$ состоит из двух пакетов:
\begin{itemize}
  \item виртуальной машины \texttt{d2na/vm} для запуска уже готовых программ на
        $D^2NA$;
  \item генератора \texttt{d2na/evolution}, который с помощью генетических
        алгоритмов создаёт новую программу на $D^2NA$;
\end{itemize}

Такой ход позволит упростить разделение разработки программы и её использования.
Например, на сервер, где программа на $D^2NA$ будет выполняться можно поставить
только виртуальную машину, а на компьютер разработчика, который будет задавать
оценочную функцию и следить за ходом генерации, нужно поставить и генератор и
виртуальную машину.

\subsection{Виртуальная машина}

Виртуальная машина \texttt{d2na-vm} выполняет код на языке $D^2NA$ и позволяет
ему общаться с внешним миром с помощью входящих/исходящих сигналов.

Код на языке $D^2NA$ можно выполнять двумя способами:
\begin{itemize}
  \item независимой программой, передав ей файл с $D^2NA$-кодом;
  \item библиотекой для запуска $D^2NA$-кода внутри другого приложения на языке
        программирования Ruby;
\end{itemize}

\subsubsection{Программа интерпретатора}

Программа интерпретатора предназначена для работы с $D^2NA$-кодом человеком или
другой программой, написанной не на языке программирования Ruby.

Управлением программой \texttt{d2na-vm} сделано согласно рекомендация для
UNIX:
\begin{itemize}
  \item Программа предназначена для запуска их текстового терминала и общается
        с внешним миром простым текстом.
  \item При запуске можно указать аргументы. Они могут быть либо однобуквенные,
        и перед ними должен быть дефис (например, \texttt{-h}), или полным
        названием команды с двумя дефиса вначале (например, \texttt{-help}).
\end{itemize}

\newpage
Чтобы вызвать интерпретатор, нужно в текстовом термина набрать команду вида:

\texttt{d2na-vm} опции файл

Опции могут быть:

\begin{itemize}
  \item \texttt{-p} или \texttt{--prompt} — показывать перед исходящими
        сигналами \texttt{>}, а перед входящими \texttt{<}. Это упрощает работу
        с программой оператору человеку.
  \item \texttt{-c} или \texttt{--color} — показывать перед исходящими
        сигналами красную стрелку \texttt{>}, а перед входящими зелёную стрелку
        \texttt{<}. Это упрощает работу с программой оператору человеку, но
        требует поддержки цветного вывода у текстового терминала.
  \item \texttt{-h} или \texttt{--help} — вывести информацию о опциях и способе
        работы с интерпретатором.
\end{itemize}

После запуска интерпретатор загружает переданный ему файл с $D^2NA$-кодом и
сам посылает ему стартовый входящих сигнал \texttt{:Init}. Если загруженная
$D^2NA$-программа посылает исходящий сигнал, он выводит его в стандартный выход
(\texttt{STDOUT}). Исходящие сигналы разделяются переводом строки.

После загрузки интерпретатор ожидает входящих сигналов со стандартного входа
(\texttt{STDIN}), которые должны оканчиваться переводом строки.
Если входящий сигнал начинается с прописной буквы, то интерпретатор сам
делает первую букву заглавной. При поступлении новых входящих сигналов,
\texttt{d2na-vm} отправляет их загруженной программе на $D^2NA$ и выводи её
ответные исходящие сигналы.

Программа перестаёт работать получив со стандартного входа (\texttt{STDIN}) код
\texttt{ETX} об окончании текста. Его можно ввести нажав \texttt{Ctrl+C}.

\newpage
Рассмотрим пример работы с виртуальной машиной человеком:
\begin{verbatim}
~$ d2na-vm -p ping-pong.d2na
< Print
> Ping
< Print
> Pong
< Print
> Ping
< ^C
~$
\end{verbatim}

С помощью виртуальной машины код на $D^2NA$ может вызывать приложение на любом
языке и платформе. Её надо лишь запустить программу \texttt{d2na-vm}, передав ей
путь к файлу с $D^2NA$-кодом, и передавать/принимать сигналы через текстовый
канал (\texttt{pipe}):

\begin{verbatim}
IO.popen('d2na-vm ping-pong.d2na') do |io|
  io << 'Print'
  io.read #=> "Ping\n"
  io << 'Print'
  io.read #=> "Pong\n"
  io << 'Print'
  io.read #=> "Ping\n"
end
\end{verbatim}

\newpage
\subsubsection{Библиотека интерпретации}

Хоть программа-интерпретатор и позволяет работать с $D^2NA$-кодом и человеку,
и любой другой программе, но запуск отдельного процесса и взаимодействие с ним
через канал (\texttt{pipe}) — не самый эффективный способ. Тем более, если
$D^2NA$-код должен быть запущен из приложения на языке программирования Ruby,
то интерпретатор загрузит ещё одну виртуальную машину Ruby, что не имеет смысла.

Поскольку при генератор будет очень часто запускать $D^2NA$-код, то было решено
сделать более быстрый способ запуска $D^2NA$-программ из приложений на языке
программирования Ruby.

Для этого был сделан Ruby-класс \texttt{D2NA::Code} с методами:
\begin{itemize}
  \item \texttt{new(\&block)} — загружает $D2NA$-код переданный в переменной
        \texttt{block}.
  \item \texttt{{<}< singal} — послать входящий сигнал из переменной
        \texttt{signal}.
  \item \texttt{listen(*singals, \&block)} — код в переменной \texttt{block} будет
        вызван, когда загруженный код пошлёт исходящий сигнал, содержащийся в
        массиве \texttt{singals}. Если массив \texttt{singals} пустой, то код из
        \texttt{block} будет вызываться при любом исходящем сигнале.
  \item \texttt{delete\_listeners!} — удаляет все коды, добавленные через метод
        \texttt{listen}.
  \item \texttt{reset!} — обнуляет все переменные загруженного кода
        (переводит его в начальное состояние).
\end{itemize}

При получении первого входящего сигнала библиотека сама отправит загруженному
коду стартовый сигнал \texttt{:Init}. После вызова метода \texttt{reset!} и
обнуления переменных стартовый сигнал \texttt{:Init} будет снова послан
автоматически.

Пример работы с библиотекой:
\begin{verbatim}
require 'd2na/vm'

code = D2NA::Code.new do
  on :Init do
    up :ping
  end

  on :Print, :ping do
    send :Ping
    down :ping
    up :pong
  end

  on :Print, :pong do
    send :Pong
    down :pong
    up :ping
  end
end

code.listen { |signal| puts signal }

code << :Print # Выведет Ping
code << :Print # Выведет Pong
code << :Print # Выведет Ping

code.reset!
code.listen { |signal| puts signal }
code << :Print # Выведет Ping
\end{verbatim}

Очень часто программа работающая с $D^2NA$-кодом должна просто складывать
исходящие сигналы в массив. Поэтому в библиотеке есть специальный класс
\texttt{D2NA::Recorder} для этого. Он расширяет класс массива \texttt{Array},
но позволяет в конструкторе передать код, сигналы с которого он будет
записывать:
\begin{verbatim}
require 'd2na/vm'

code = D2NA::Code.new do
  on :Input do
    up :a
  end
  on :Inpit, :a do
    send :Output
  end
end

out = D2NA::Recorder.new(code)

code << :Input
code << :Input
code << :Input
out #=> [:Output, :Output]
\end{verbatim}

\newpage
\subsection{Генератор}
Разработчик указывает требования к новой программе с помощью оценочной функции и
функции останова, с помощью которых генератор создаёт новый $D^2NA$-код
множеством итерация из трёх шагов:
\begin{enumerate}
  \item Простое копирование $D2NA$-кода, чтобы получить множество нужного
        размера.
  \item Внесение случайных изменений в каждый экземпляр $D2NA$-кода.
  \item Проверка результата оценочной функцией и удаление программ, набравших
        минимум баллов.
\end{enumerate}

Пакет генератора требует установки виртуальной машины для $D2NA$ и работает с
ней через её библиотеку для языка Ruby.

Генератор можно разделить на четыре независимые части:
\begin{itemize}
  \item \textbf{Evolution} — установка настроек генератора и управление
        процессом создания новой программы.
  \item \textbf{MutableCode} — изменение $D2NA$-кода, в том числе внесение
        случайных изменений.
  \item \textbf{Tests} — макоязык (DSL, Domain-Specific Language) для записи
        оценочной функции и тестирование промежуточного $D2NA$-кода.
  \item \textbf{Population} — упорядоченное хранение промежуточных программ и
        удаление на каждом шаге $D2NA$-кода получившего минимальную оценку в
        оценочной функции.
\end{itemize}

\subsubsection{Настройка генератора}
Настройка генератора осуществляется с помощью специального макроязыка
(DSL, Domain-Specific Language) — библиотеки с набором методов для языка
программирования Ruby.

Основа генератора — класс \texttt{D2NA::Evolution}. Чтобы описать задание для
генератора нужно написать программу на языке Ruby, подключить библиотеку
\texttt{d2na/evolution} и создать в ней экземпляр этого класса:

\begin{verbatim}
require 'd2na/evolution'
e = D2NA::Evolution.new do
  # Настройки генератора и оценочная функция
end
\end{verbatim}

Поскольку Ruby — интерпретируемый язык программирования, то инструкции
генератору можно писать с помощью простого текстового редактора и запуска
текстовый файл в программе \texttt{ruby} версии 1.9.1:

\begin{verbatim}
~$ ruby evolution.rb
\end{verbatim}

Класс \texttt{D2NA::Evolution} имеет набор методов для настройки эволюции:
\begin{itemize}
  \item \texttt{protocode(code)} — задаёт \texttt{code} как первое поколение
        программы для начала итераций. В основном разработчик в первом поколении
        задаёт только имена входящих и исходящий сигналов.
        Вызванный без параметров возвращает текущее значение.
  \item \texttt{min\_population(count)} — задаёт \texttt{size}, как минимальное
        количество программ-кандидатов после каждой итерации. На первый итерации
        $D^2NA$-код, заданный в \texttt{protocode}, клонируется до размера
        минимальной популяции.
        Вызванный без параметров возвращает текущее значение.
  \item \texttt{worker\_count(count)} — задаёт \texttt{size}, как количество
        потоков, которые будут генерировать новую программу. Чтобы полностью
        использовать потенциал современных многоядерных процессоров при
        мутация и тестировании кода в многопоточном режиме.
        Вызванный без параметров возвращает текущее значение.
  \item \texttt{selection(description, options, \&block)} — добавляет
        \texttt{block} как оценочную функцию, которой конечный $D^2NA$-код
        должен соответствовать. Аргумент \texttt{description} может содержать
        описание оценочной функции, а \texttt{options} — хеш с параметром
        \texttt{priority}, в котором содержится цифровой приоритет этой
        оценочной над другими.
  \item \texttt{end\_if(\&block)} — задаёт \texttt{block}, как функцию
        остановка. Переданный код будет вызываться в конце каждой итерации, и,
        если он вернёт истинное значение, процесс генерации будет остановлен,
        так как цель разработчика достигнута. Для разработчик имеется набор
        функций, упрощающих задание функции останова:
        \begin{itemize}
          \item \texttt{success} — возвращает истинное значение, если все
                требований оценочной функции выполнены.
          \item \texttt{stagnation > }\textit{count} — возвращает истинное
                значение, если значение оценочной функции не было улучшено за
                последнее \textit{count} шагов.
        \end{itemize}
        Разработчик может объединять функции, например:
        \texttt{success and stagnation > 10}.
  \item \texttt{stagnation\_limit(maximum)} — задаёт \texttt{maximum}, как
        максимальное количество шагов простоя. Если значение оценочной функции
        не было улучшено за максимальное количество шагов простоя, то генерация
        останавливается, поскольку генератор не способен создать требуемый код.
        Вызванный без параметров возвращает текущее значение.
\end{itemize}

\newpage
Так же класс \texttt{D2NA::Evolution} содержит методы для управления ходом
генерации:
\begin{itemize}
  \item \texttt{step!} — делает следующую итерацию написания программы.
  \item \texttt{next\_step?} — возвращает истинное значение, если функция
        останова показала, что цель генерации ещё не достигнута и требуются ещё
        итерации.
  \item \texttt{step} — возвращает количество уже выполненных итераций.
  \item \texttt{stagnation} — возвращает количество последних шагов, за которые
        не удалось улучшить результат оценочной функции.
  \item \texttt{population} — возвращает популяцию программ, сгенерированных на
        текущем шаге.
  \item \texttt{old\_population} — возвращает популяцию программ, полученных на
        предыдущем шаге.
\end{itemize}

\newpage
В итоге типичная настройка генератора будет выглядеть как:
\begin{verbatim}
require 'd2na/evolution'

e = D2NA::Evolution.new do
  worker_count 4
  
  min_population 10
  protocode do
    # Входящие/исходящие сигналы согласно
    # условиям задачи
    input :Print
    output :Ping, :Pong
  end
  
  selection "First" do
    # Первая оценочная функция
  end
  selection "Second", priority: 2 do
    # Вторая оценочная функция,
    # более приоритетная
  end
  
  end_if { success and stagnation > 10 }
  
  stagnation_limit 20
end

while e.next_step?
  e.step!
  # Выводим «!» при улучшении результата
  # оценочной функции, иначе количество
  # выполненных шагов.
  0 == e.stagnation ? putc('!') : e.step
end
\end{verbatim}

\subsubsection{Мутатор}

Чтобы вносить в уже созданный код изменения, в пакете генератора есть класс
\texttt{D2NA::MutableCode}, который расширяется класс \texttt{D2NA::Code} из
виртуальной машины, добавляя в него методы:
\begin{itemize}
  \item \texttt{modify(\&block)} — вносит набор изменений в код, указанные в
        коде \texttt{block}, после чего восстанавливает кеши и компилирует
        $D2NA$-код.
  \item \texttt{clone} — возвращает полную копию объекта с данным $D^2NA$-кода.
  \item \texttt{mutate!} — вносит случайные изменения в текущий $D^2NA$-код.
        Параметры случайных изменений можно задать аргументов как хеш или
        задать глобальной для всех вызовов \texttt{mutate!} с помощью свойства
        объекта \texttt{mutation\_params}.
  \item \texttt{to\_ruby} — возвращает текстовое представление загруженного
        $D^2NA$-кода для сохранения в файл.
\end{itemize}

Поскольку, каждое изменение $D^2NA$-кода требует ресурсов на компилияцию и
пересоздание кешей, то несколько изменений можно объединить в один блок, передав
их методу \texttt{modify}. Возможные команды изменения программы:
\begin{itemize}
  \item \texttt{add\_command(rule, command, param)} — вставляет в
        правило с номером \texttt{rule} команду с именем
        \texttt{command} для переменной или исходящего сигнала
        \texttt{param}.
  \item \texttt{remove\_command(position, rule)} — удаляет команду. Либо по
        порядковому номеру \texttt{position} во всём коде (если \texttt{rule}
        не задан), либо в правиле с указанным в \texttt{rule} номером.
  \item \texttt{add\_states(*states)} — добавляет в $D^2NA$-код переменные с
        указанными в массиве \texttt{states} именами.
  \item \texttt{remove\_state(name)} — удаляет из кода переменную с именем,
        указанным в \texttt{name}, и все команды связанные с ней.
\end{itemize}

В итоге, измение загруженного $D^2NA$-код будет выглядеть как:
\begin{verbatim}
code = D2NA::Code.new do
  on :Input do
    up :a
    send :Wrong
  end
end

code.modify do
  remove_command 2
  add_command 1, :send, :Right
end
\end{verbatim}

Параметры доступные в свойстве объекта \texttt{mutation\_params} для управления
случайными изменениями в программе:

\begin{itemize}
  \item \texttt{max\_actions} — максимальное количество изменений при мутации.
        Количество действий мутатора выбирается с помощью случайной величины
        равномерно распределения.
  \item \texttt{min\_actions} — минимальной количество изменений при мутации.
  \item \texttt{max\_state\_actions} — максимальное количество внесённых
        случайных команд с новой переменной после её добавления. Количество
        выбирается с помощью случайной величины равномерно распределения.
  \item \texttt{min\_state\_actions} — минимальное количество внесённых
        случайных команд с новой переменной после её добавления.
  \item \texttt{add} — вероятность добавления новой команды.
  \item \texttt{remove} — вероятность удаления существующей команды.
  \item \texttt{add\_state} — вероятность добавления новой переменной. После
        добавления новой переменной будет добавлено случайное количество
        команд её использующих.
  \item \texttt{remove\_state} — вероятность удаления существующей переменной и
        всех команд её использующих.
\end{itemize}

Разработчик может задать параметры мутации, с помощью метода \texttt{protocode}
объекта \texttt{D2NA::Evolution}:

\begin{verbatim}
e = D2NA::Evolution.new do
  protocode do
    mutation_params[:max_actions] = 6
    mutation_params[:min_actions] = 4
    …
  end
  …
end
\end{verbatim}

\subsubsection{Оценочная функция}

Задание оценочной функции — наиболее сложная задание для разработчика при
использовании автоматической генерации программ с помощью генетических
алгоритмов.

К сожалению, нельзя использовать имеющиеся инструменты для автоматического
тестирования, потому что они возвращают только два возможных значения: программа
соответствует тестам или нет. Для генетического алгоритма, оценочная функция
должна возвращать число, чтобы понять, что программа стала чуть больше 
соответствовать тесту, даже если полностью его не проходит.

Например, если нам нужно чтобы программа возвращала $1$, но одна программа в
ответе вернула $0$, а другая — $-1$, то тесты должны показать, что первая
программа больше соответствует описанными нами условиям.

Исходя из описанных требований, в пакете генератора для $D^2NA$-кода есть набор
удобных инструментов для задания оценочной функции в виде макроязыка (DSL,
Domain-Specific Language).

Для добавления оценочной функции в классе \texttt{D2NA::Evolution} есть метод
\texttt{selection(description, options, \&block)}, который принимает описание
теста, его настройки и код тестирования.

При автоматическом написании программы, генератор может использовать несколько
оценочных функция сразу. Разработчик может задать им разное описание, чтобы
отличать их, и разный приоритет в настройках теста с помощью ключа
\texttt{priority}, например:

\begin{verbatim}
e = D2NA::Evolution.new do
  …
  selection "Первая" do
    # Код первой оценочной функции
    …
  end
  selection "Первая", priority: 2 do
    # Код второй оценочной функции,
    # более приоритетной.
    …
  end
end
\end{verbatim}

Код оценочной функции — это обычная программа на языке программирования Ruby.
Проверки и требования для генерируемого кода, задаются с помощью набора методов:
\begin{itemize}
  \item \texttt{send(signals)} — посылает в тестируемый код все входящие сигналы
        из массива \texttt{signals}.
  \item \texttt{out} — возвращает массив исходящих сигналов, посланных текущим
        тестируемым кодом.
  \item \texttt{clear\_out!} — очищает буфер исходящих сигналов, возвращаемый
        методов \texttt{out}.
  \item \texttt{should(value)} — проверяет, чтобы значение \texttt{value} было
        истинным, например, вызов \texttt{should out.length == 2} проверяет,
        что тестируемая программа послала 2 исходящих сигнала (после начала
        теста или последнего вызова \texttt{clear\_out!}).
  \item \texttt{max(value)} — требует, чтобы тестируемая программа имела
        максимальное значение \texttt{value}. То есть, программа с максимальное
        значение \texttt{value} получить максимальную оценочную функцию, чтобы
        остатся в следующущуй итерации.
  \item \texttt{min(value)} — требует, чтобы тестируемая программа имела
        минимальное значение \texttt{value}. Например, вызов\\
        \texttt{min(out.length)} требует, чтобы $D^2NA$-код посылал минимум
        исходящих сигналов.
\end{itemize}

Для упрощения работы разработчика, библиотека тестов имеет ряд методов,
объединиящих вызов \texttt{should}, \texttt{min} и \texttt{max} для решения
распространённых задач:
\begin{itemize}
  \item \texttt{out\_should\_be\_empty} — требует, чтобы тестируемая программа
        не посылала ни один исходящий сигнал в начала теста или с последнего
        вызова \texttt{clear\_out!}.
  \item \texttt{out\_should(signals)} — принимает хеш имеющий в ключах имена
        исходящих сигналов и в значения — их количество и проверяет, чтобы
        в буфере исходящих сигналов \texttt{out} содержалось только указанные в
        \texttt{signals} исходящие сигналы и только в указанном количестве.
  \item \texttt{out\_should\_has(signals)} — нестрогий аналог\\
        \texttt{out\_should}. Он принимает хеш имеющий в ключах имена
        исходящих сигналов и в значения — их количество и проверяет, чтобы
        в буфере исходящих сигналов \texttt{out} содержалось указанные в
        \texttt{signals} исходящие сигналы и только в указанном количестве.
        То есть, если тестируемая программа посылала исходящие сигналы не
        указанные в \texttt{signals}, то это не будет считаться ошибкой.
  \item \texttt{out\_should\_hasnt(signals)} — проверяет, чтобы в буфере
        исходящих сигналов \texttt{out} не содержались сигналы указанные в
        массиве \texttt{signals}.
\end{itemize}

Пример, оценочной функции для программы-сумматора, которая посылает исходящих
сигналов \texttt{:C} столько, сколько в сумме пришло входящих сигналов
\texttt{:A} и \texttt{:B}:

\begin{verbatim}
selection "Сумматор" do
  out_should_be_empty
  
  send :A, :A
  out_should :C => 2
  
  send :B, :B, :B
  out_should :C => 5
end
\end{verbatim}

Каждый метод проверки (\texttt{should}, \texttt{min}, \texttt{max}, \\
\texttt{out\_should}, \texttt{out\_should\_has}, \texttt{out\_should\_hasnt},\\
\texttt{out\_should\_be\_empty}) может принимать приоритет проверки с помощью
ключа \texttt{priority}.

Например, в данном тесте, код посылающий лишний сигнал \texttt{:B} будет иметь
меньшее значение оценочной функции, чем код, не посылающий нужный сигнал
\texttt{:A}.

\begin{verbatim}
out_should_has   :A => 1
out_should_hasnt :B, priority: 2
\end{verbatim}

Тест считается пройденным, только если выполнены все условиях в проверках
\texttt{should}. Проверки \texttt{min} и \texttt{max} не учитываются в вызове
метода \texttt{success} класс \texttt{D2NA::Evolution}, но по их результата
тест может считаться пройденным лучше или хуже.

\subsubsection{Популяция}

На каждой итерации, после клонирования и случайного изменения, программы на
$D^2NA$ должны складывать в специальный массив-популяцию вместе со своими
результатами оценочной функции.

Хранится они должны по слоям — программы с одинаковыми результатом оценочной
функции должны иметь один слой.


\begin{figure}
  \centering
  \input{./images/population.tex}
  \caption{Пример обрезки популяции}
\end{figure}

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

\begin{enumerate}
  \item Максимальный размер первого слоя (с наилучшему результатами оценочной
        функции) вычисляется по формуле:\\
        $L_0 = min\_population + (stagnation * stagnation\_grow)$.\\
        Максимальный размер каждого последующего слоя равен половине от
        предыдущего: $L_{x} = L_{x-1} / 2$
  \item На каждом слое программы размещаются по уменьшению длины кода — самые
        короткие в начале.
  \item Программы не помещающиеся в максимальный размер слоя удаляются с конца
        списка.
\end{enumerate}

В начале каждый итерации старая популяция копируется в переменную
\texttt{old\_population}, в в переменной \texttt{population} создаётся новая.

Чтобы в результате случайных изменений не ухудщить результат, перед итерацией
$D^2NA$-код набравший максимальное значение оценочной функции и имеющий
минимальный размер исходного кода без изменений копируется в новую популяцию.

Текущая популяция находится в свойстве \texttt{population} класса
\texttt{D2NA::Evolution} и имеет набор методов:
\begin{itemize}
  \item \texttt{best} — возвращает лучший код с максимальным значение оценочной
        функции и минимальный размером исходного кода (первый элемент первого
        слоя).
  \item \texttt{best\_result} — возвращает лучшее значение оценочной функции
        (полученное для всех элементов первого слоя).
\end{itemize}

\newpage
\section{Программная реализация}

Программная реализация виртуальной машины и генератора для $D^2NA$-программ
полностью открыта и  вместе с историей изменений опубликована в Интернете по
адресу \texttt{http://github.com/ai/d2na} на условиях свободной лицензии
GNU GPL.

\subsection{Средства разработки}

Разработка велась на операционной системе Linux, поскольку являясь UNIX-подобной
операционной системой она обладает целым набором полезным инструментов для
разработки и позволяет программировать быстро и эффективно. Поэтому $D^2NA$
разрабатывалась в духе идеологии UNIX.

Для разработки $D^2NA$ требовался язык удовлетворяющий следующим критериям:
\begin{itemize}
  \item \textbf{Скорость разработки}. Сначала нужно написать систему грубо и
        максимально быстро для проверки идеи. А потом, в случае успеха, уже
        можно оптимизировать систему и переписывать критические блоки на языки
        более низкого уровня, такие как C или Java.
  \item \textbf{Гибкость.} Цель $D^2NA$ — создание инструмента для изучения и
        экспериментов с генетическими алгоритмами, поэтому язык и платформа
        должна быть гибкой, чтобы вносить изменения максимально быстро и легко.
  \item \textbf{Свободный синтаксис.} Желательно, чтобы синтаксис языка $D^2NA$ был
        просто подсинтаксисом (DSL, Domain-Specific Language) языка разработки
        генератора, чтобы не писать отдельный интерпретатор.
  \item \textbf{Кроссплатформенностью.} Язык разработки не должен быть привязан к
        определённой операционной системе или интегрированной среде разработки.
        Результат работы должен запускаться на любой из распространённой
        операционной системе (Windows, Mac OS X, Linux) без перекомпиляции.
        Желательно, чтобы разработку можно было вести использую обычный
        текстовой редактор и простой набор скриптов.
  \item \textbf{Автоматическое тестирование.} Поскольку в рамках проекта
        разрабатывался набор утилит (а не конечный продукт с графическим
        интерфейсом пользователя), то лучше всего подходит автоматическое
        тестирование, желательно с применение подхода BDD (Behavior Driven
        Development).
\end{itemize}

Для поставленных задач лучше всего подходил язык Ruby версии 1.9.

\newpage
\subsection{Язык программирования Ruby}

\subsubsection{Парадигма}

Ruby — полностью объектно-ориентированный язык. В нём все данные являются
объектами, в отличие от многих других языков, где существуют примитивные типы.
Каждая функция — метод. Переменные Ruby содержат не сами объекты, а ссылки на
них. Присваивание — это не передача значения, а копирование ссылки на
объект\cite{ruby}.

Ruby не поддерживает множественное наследование, но вместо него есть мощный
механизм примесей. Все классы (напрямую или через другие классы) выведены из
класса \texttt{Object}, следовательно, любой объект может использовать
определённые в нем методы (например, \texttt{class}, \texttt{to\_s},
\texttt{nil?}). Процедурный стиль также поддерживается, но все глобальные
процедуры неявно являются закрытыми методами класса \texttt{Object}.

Ruby является мультипарадигменным языком: он поддерживает процедурный стиль
(определение функций и переменных вне классов), объектно-ориентированный
(всё — объект), функциональный (анонимные функции, замыкания, возврат значения
всеми инструкциями, возврат функцией последнего вычисленного значения).
Он поддерживает отражение, метапрограммирование, информацию о типах переменных
на стадии выполнения.

Возможности Ruby \cite{ruby}:
\begin{itemize}
  \item Имеет лаконичный и простой синтаксис, частично разработанный под
  \item Позволяет обрабатывать исключения в стиле Java и Python.
  \item Позволяет переопределять операторы, которые на самом деле являются
        методами.
  \item Полностью объектно-ориентированный язык программирования. Все данные в
        Ruby являются объектами в понимании Smalltalk.
        Единственное исключение — управляющие конструкции, которые в Ruby в 
        отличие от Smalltalk не являются объектами. Например, число \texttt{1} —
        это экземпляр класса \texttt{Fixnum}. Также поддерживается добавление 
        методов в класс и даже в конкретный экземпляр во время выполнения
        программы.
  \item Не поддерживает множественное наследование, но вместо него может
        использоваться концепция «примесей», основанная в данном языке на
        механизме модулей.
  \item Содержит автоматический сборщик мусора. Он работает для всех объектов
        Ruby, в том числе для внешних библиотек.
  \item Создавать расширения для Ruby на C очень просто частично из-за
        сборщика мусора, частично из-за несложного и удобного API.
  \item Поддерживает замыкания с полной привязкой к переменным.
  \item Поддерживает блоки кода (код заключается в \texttt{\{ \ldots \}} или 
        \texttt{do \ldots end}). Блоки могут использоваться в методах или
        преобразовываться в замыкания.
  \item Целые переменные в Ruby автоматически конвертируются между типами
        \texttt{Fixnum} (32-разрядные) и \texttt{Bignum} (больше 32 разрядов) в
        зависимости от их значения, что позволяет производить целочисленные
        математические расчёты с бесконечной точностью.
  \item Не требует предварительного объявления переменных, но для интерпретатора
        желательно, чтобы переменным присваивалось пустое значение \texttt{nil}
        (тогда интерпретатор знает, что идентификатор обозначает переменную, а
        не имя метода). Язык использует простые соглашения для обозначения
        области видимости. Пример: просто \texttt{var} — локальная переменная,
        \texttt{@var} — переменная экземпляра (член или поле объекта класса),
        \texttt{@@var} — переменная класса, \texttt{\$var} — глобальная
        переменная.
  \item В Ruby непосредственно в языке реализованы многие шаблоны
        проектирования, так, например, «одиночка» (Singleton) может быть (хотя и
        не обязан) реализован добавлением необходимых методов к одному
        конкретному объекту.
  \item Может динамически загружать расширения, если это позволяет операционная
        система.
  \item Имеет независимую от ОС поддержку невытесняющей многопоточности.
  \item Перенесён на множество платформ. Он разрабатывался на GNU/Linux, но
        работает на многих версиях Unix, DOS, Microsoft Windows (в частности,
        Win32), Mac OS X, BeOS, OS/2 и т. д.
\end{itemize}

\subsubsection{Пример}

В Ruby все классы являются открытыми, поэтому можно расширить стандартные классы
с помощью дополнительных методов. В следующем примере, мы расширим класс
\texttt{Array} методом \texttt{at\_rand}, который будет возвращать случайный
элемент массива, при этом, если массив \emph{n}-размерный, то в результате
\emph{n} обращений к этому методу, каждый элемент вернется единожды. Данный
метод пригодится как внешний итератор для последовательного случайного перебора
элементов массива.

\begin{verbatim}
  class Array
    def at_rand
      if @not_picked.empty?
        @not_picked = self.sort_by { rand }
      end
      @not_picked.pop
    end
  end  
\end{verbatim}

Следующий пример позволяет значительно упростить добавление методов для высчета
функции и их производных, он будет использоваться для задания функций активации
в программе: 

\begin{verbatim}
module DerivativeFunctions
  def self.create_function(name, function, derivative)
    define_method name do |value|
      y = function.call x
    
      case value
      when :function then y
      when :derivative then derivative.call y
      else
        raise 'Unknown type of function'
      end
    end
  end
end
\end{verbatim}

\newpage
\subsection{Синтаксис $D^2NA$}

Ruby выделяет тем, что обладает довольно гибким синтаксисом:
\begin{itemize}
  \item точка с запятой \texttt{;} необязательна, если команды разделены
        переводом строки;
  \item скобки \texttt{()} необязательна после метода, поскольку в Ruby нельзя
        обращаться к свойствам класса без вызова метода.
\end{itemize}

Так же Ruby обладает рядом удобных инструментов, упрощающих синтаксис:
\begin{itemize}
  \item Методу в качестве аргументов можно передать не только значения, но и
        другой код, заключив его между \texttt{do end} после вызова метода.
  \item Строка начатая с двоеточки \texttt{:} будет хранится в программе, как
        число (Symbol). При этом, строки с одинаковыми значениями будут иметь
        один номер. В итоге, сравнение и хранение Symbol значительно более
        эффективно. Можно сказать, что Symbol является удобной заменой констант
        и Enum из более низкоуровневых языков программирования.
\end{itemize}

В итоге, как можно заметить, синтаксис $D^2NA$ — это просто подсинтаксис
(DSL, Domain-Specific Language) языка программирования Ruby.

Рассмотрим программу на $D^2NA$:
\begin{verbatim}
on :Init do
  up :var
end

on :Input, :var do
  send :Output
  down :var
end
\end{verbatim}

В итоге получается обычный Ruby-код в котором два раза вызывается метод
\texttt{on}:
\begin{enumerate}
  \item В первом случае он получает два аргумента: Symbol-строку «Init» и код,
        в котором выполняется метод \texttt{up} с параметром «var».
  \item Во втором случае метод \texttt{on} получается три аргумента: две
        Symbol-строки «Input» и «var» и код, который вызывает метод
        \texttt{send} с параметром «Output» и \texttt{down} с параметром «var».
\end{enumerate}

\newpage
\subsection{Виртуальная машина}
Виртуальная машина для языка $D^2NA$ представлена набором классов:
\begin{itemize}
  \item \texttt{D2NA::Rule} — одной правил программы, которое в исходном коде
        определяется оператором \texttt{on}. Имеет методы:
        \begin{itemize}
          \item \texttt{conditions} — условие выполнения правила. Массив с
                именами входящих сигналов или переменных.
          \item \texttt{commands} — массив команд, вида\\
                \texttt{[\textit{имя команды}, \textit{переменная или сигнал}]}.
          \item \texttt{compiled} — скомпилированную версию списка команд для
                быстрого выполнения.
          \item \texttt{send(signal)} — добавляет в правило команду, посылающую
                исходящий сигнал с именем из параметра \texttt{signal}.
          \item \texttt{up(state)} — добавляет в правило команду, увеличивающую
                значение переменной из параметра \texttt{state}.
          \item \texttt{down(state)} — добавляет в правило команду, уменьшающую
                значение переменной из параметра \texttt{state}.
        \end{itemize}
  \newpage
  \item \texttt{D2NA::Code} — программа на $D^2NA$. Методы:
        \begin{itemize}
          \item \texttt{rules} — массив правил программы.
          \item \texttt{input\_signals} — массив с именами всех входящих
                сигналов, которые используются в программе.
          \item \texttt{output\_signals} — массив с именами всех исходящих
                сигналов программы.
          \item \texttt{states} — хеш всех переменных, которые используется
                в программе, с именем переменной в ключах и её содержимым в
                значениях хеша.
          \item \texttt{length} — количество всех команд в программе.
          \item \texttt{max\_depth} — максимальное количество циклов для
                педотвращения зацикливания.
          \item \texttt{on(*conditions, \&block)} — добавляет новое правило
                с условиями из массива \texttt{conditions} и командами из блока
                кода \texttt{block}.
          \item \texttt{listen(signals, \&block)} — добавляет код
                \texttt{block}, как подписчика на сигналы из массива
                \texttt{signals}. Если \texttt{signals} пуст, то \texttt{block}
                будет вызван при любом исходящем сигнале.
          \item \texttt{delete\_listeners!} — удаляет всех подписчиков на
                исходяящие сигналы, добавленных через метод \texttt{listen}.
          \item \texttt{<<(signal)} — посылает входящий сигнал с именем
                из параметра \texttt{signal} в код.
          \item \texttt{sind\_out(signal)} — посылает исходящий сигнал с именем
                из параметра \texttt{signal} и оповещает о нём всех подписчиков.
          \item \texttt{state\_up(state)} — увеличивает значение переменной с
                именем из параметра \texttt{state} на единицу.
                именем из параметра \texttt{state} на единицу.
          \item \texttt{start} — посылает входящий сигнал \texttt{:Init} в
                загруженный код.
          \item \texttt{started?} — возвращает истинное значение, если сигнал
                \texttt{:Init} уже был послан в загруженный код.
          \item \texttt{reset!} — возвращает код в исходное состояние, обнуляя
                все переменные.
          \item \texttt{conditions\_cache} — индекс для повышения
                быстродействия. Это хеш в ключах хранит имя переменной или
                входящего сигнала, а в значения — список правил, у которых эта
                переменная или входящий сигнал есть в условии.
          \item \texttt{required} — кеш для повышения быстродействия. Этот хеш
                хранит в ключах правила программы, а в значении — сколько ещё
                условий не удовлетворенно для запуска правила.
        \end{itemize}
  \item \texttt{D2NA::Recorder} — расширенная версия массива, которая
        подключается к загруженному $D^2NA$-коду и помещает в себя все
        исходящие из него сигналы. Служит для отладки, автоматического
        тестирования и используется в макроязыке. Расширяется системный
        Ruby-класс массивов \texttt{Array} добавляя в него методы:
       \begin{itemize}
          \item \texttt{initialize(code)} — меняет у \texttt{Array}
                конструктор, принимая в \texttt{code} загруженный $D^2NA$-код,
                исходящие сигналы которого нужно записывать. При загрузке
                с помощью метод \texttt{listen} класса \texttt{D2NA::Code}
                подключает свой метод \texttt{dispatch} для записи исходящих
                сигналов.
          \item \texttt{dispatch(code, signal)} — метод, которые будет вызывать
                объектом класса \\ \texttt{D2NA::Code}, когда он будет посылать
                исходящий сигнал. В \texttt{code} он передаст ссылку на самого
                себя, а в \texttt{signal} — имя исходящего сигнала.
        \end{itemize}
  \item \texttt{D2NA::Console} — класс программы виртуальной машины. Он
        работает с текстовым терминалом и стандартными входом и выходом
        (\texttt{STDIN} и \texttt{STDOUT}), загружая код из указанного файла,
        считывая введённые пользователем входящие сигналы и печатая исходящие
        сигналы загруженного кода:
        \begin{itemize}
          \item \texttt{code} — загруженный код, объект класса
                \texttt{D2NA::Code}.
          \item \texttt{input} — поток для чтения команд. По умолчанию равен
                \texttt{STDIN}. Переменная служит для того, чтобы во время
                автоматического тестирования сменить проток входящих сигналов.
          \item \texttt{output} — поток для чтения команд. По умолчанию равен
                \texttt{STDOUT}. Переменная позволяет скрипту автоматического
                тестирования сменить поток исходящих сигналов, чтобы проверить
                что программа будет печатать на экран.
          \item \texttt{prompt} — нужно ли печатать префикс: «<» перед
                входящими сигналами и «>» — перед исходящими.
          \item \texttt{color} — должен ли префикс перед входящими сигналами
                печататься зелёным, а перед исходящими — красным.
          \item \texttt{load(string)} — загрузить $D^2NA$-код, который
                содержится в строке \texttt{string}.
          \item \texttt{print(code, signal)} — метод, которые будет вызывать
                объектом класса \texttt{D2NA::Code}, когда он будет посылать
                исходящий сигнал. При получении исходного сигнала в переменной
                \texttt{signal} выведет его в поток указанный в \texttt{output}.
          \item \texttt{read} — прочитать следующий входящий сигнал с потока
                указанного в \texttt{input}. Метод будет ждать, пока во
                входящем потоке не появится перевод строки.
          \item \texttt{help} — вывести текст справки.
          \item \texttt{invalid\_option(option)} — вывести текст о неизвестной
                опции \texttt{option}.
        \end{itemize}
\end{itemize}

\subsubsection{Загрузка кода через библиотеку}

Процесс загрузки $D^2NA$-кода через библиотеку интерпретатора:
\begin{enumerate}
  \item В пакете \texttt{d2na/vm} идёт файл \texttt{d2na-vm.rb}, который
        загружает все классы виртуальной машины:

        \begin{verbatim}
        require 'd2na-vm'
        \end{verbatim}

        Поскольку классы \texttt{D2NA::Recorder} и \texttt{D2NA::Console} не
        обязательно будут использоваться, то они с помощью \texttt{autoload}
        будут загружены только в момент использования.
  \item После загрузки нужных классов виртуальной машины, использующая её 
        программа должна создать экземпляр класса\\ \texttt{D2NA::Code} и
        передать конструктору блок с $D^2NA$-кодом:

        \begin{verbatim}
        code = D2NA::Code.new do
          on :A do
            send :C
          end
          on :B do
            send :C
          end
        end
        \end{verbatim}

  \item Чтобы загрузить $D^2NA$-код объект класса \texttt{D2NA::Code} просто
        вызывает переданный блок кода на себе (с помощью\\
        \texttt{instance\_eval}). В итоге при загрузке вышеуказанного кода, у
        объекта будет два раза вызван метод \texttt{on}.
  \item Метод \texttt{on} после вызова создаёт создаёт новый объект класса
        \texttt{D2NA::Rule} с переданными условиями и передаёт ему блок кода с
        командами нового правила. В данном примере будет создано два объекта
        \texttt{D2NA::Rule} с условиями поступления входящего сигнала
        \texttt{:A} и \texttt{:B}.
  \item Код должен заранее знать список используемых в нём переменных и
        сигналов. Поэтому, правило сразу после создания вызывает метод у
        создавшего его кода метод \texttt{input(signal)} для каждого входящего
        сигнала в условии правила, а все переменные из условия помещает во
        временный массив \texttt{@states}.
  \item Далее правило вызывает на себе переданный ему блок команд. У объекта
        \texttt{D2NA::Rule} есть методы на каждую возможную команду правила.
        После вызова эти методы добавляют соответствующую команду в массив
        \texttt{commands} и сохраняют используемые в команде исходящие сигналы и
        переменные во временных массивах \texttt{@signals} и \texttt{@states},
        соответственно.
  \item После того, как все команды добавлены в правило, у правила есть список
        всех используемых исходящих сигналов и переменных и оно передаёт их
        создавшему правило коду, вызывая у него методы \texttt{output} и
        \texttt{add\_state},соответственно.
  \item Правило компилирует список своих команд в анонимную функцию с помощью
        \texttt{eval}. Анонимная функция для каждой команду будет соответственно
        вызывать методы \texttt{send\_out}, \texttt{state\_up} и
        \texttt{state\_down} у объекта класса \texttt{D2NA::Code}.
  \item Загруженное правило помещает в индекс \texttt{conditions\_cache} исходя
        из своего условия и в кеш \texttt{required} с размером своего списка
        условий.
\end{enumerate}

\subsubsection{Загрузка кода через программу}

Программа интерпретатора находится в файле \texttt{bin/d2na-vm}. Для загрузки
кода она наравне с другими программами использует библиотеку интерпретатора.

При вызове файл \texttt{bin/d2na-vm}:
\begin{enumerate}
  \item Загружает библиотеку интерпретатора.
  \item Создаёт объект класса \texttt{D2NA::Console}.
  \item Анализирует аргументы переданные через текстовой и устанавливает
        соответствующие настройки у объекта класса \texttt{D2NA::Console}.
  \item Если файл с $D^2NA$-кодом не передан или передан аргументы \texttt{-h}
        или \texttt{--help} вызывает метод \texttt{help} длч показа справки.
  \item Если передан неизвестный аргумент, вызывает метод
        \texttt{invalid\_option} для показа сообщения об ошибке.
  \item Если ошибок не было, читает из переданного файла $D^2NA$-код и посылает
        его объекту класса \texttt{D2NA::Console}.
  \item В бесконечном цикле считывает имена входящих сигналов со стандартного
        входа (\texttt{STDIN}).
  \item По закрытию входящего потока (получению с него кода \texttt{ETX} об
        окончании текста) — закрывает программу.
\end{enumerate}

\newpage
\subsubsection{Исполнение кода}

После загрузки кода, объект \texttt{D2NA::Code} посылает сам в себя входящий
сигнал \texttt{:Init} и ждёт поступления новых входящих сигналов.

При поступлении входящего сигнала:
\begin{enumerate}
  \item Код через индекс смотрит все правила с входящим сигналом в условии и
        выполняет те из них, у которых кеш невыполненных условий
        (\texttt{required}) равен единицы.
  \item Выполненные правила вызывают у кода методы \texttt{send\_out},
        \texttt{state\_up} и \texttt{state\_down} для исходящего сигнала,
        повышения и понижения переменных, соответственно:
        \begin{itemize}
          \item При исходящем сигнале код уведомляет о нём всех подписанных
                на соответствующий сигнал через метод \texttt{listen}.
          \item При увеличении переменной, код увеличивает её значение в хеше
                \texttt{states} и добавляет её во временный хеш \texttt{@diff}.
          \item При увеличении переменной, код уменьшает её значение в хеше
                \texttt{states} и добавляет её во временный хеш \texttt{@diff}.
        \end{itemize}
  \item После вызова всех правил, код с помощью временного хеша \texttt{@diff}
        смотрит, какие переменные изменились. Для всех изменённых переменных
        код смотрит правила, содержащие изменённую переменную в условии, и
        уменьшает или увеличивает им кеш невыполненных условий
        (\texttt{required}).
  \item Далее код вызывает все правила, у которых кеш невыполненных условий
        стал равен нулю.
  \item Если \texttt{@diff} показывает, что есть вновь изменённые переменные и
        максимальное количество циклов (\texttt{max\_depth}) не превышено, то
        код возвращается к шагу \textit{в}.
\end{enumerate}

\subsection{Генератор}

Генератор программ на $D^2NA$ состоит из классов:
\begin{itemize}
  \item \texttt{D2NA::TestResult} — класс для хранения результатов оценочной
        функции. Содержит методы:
        \begin{itemize}
          \item \texttt{match(test, priority)} — добавляет проверку с
                приоритетом в \texttt{priority}, что в параметре \texttt{test} —
                истинное значение.
          \item \texttt{max(value, priority)} — добавляет требование с
                приоритетом в \texttt{priority}, чтобы в параметре
                \texttt{value} значение было максимально.
          \item \texttt{min(value, priority)} — добавляет требование с
                приоритетом в \texttt{priority}, чтобы в параметре
                \texttt{value} значение было минимально.
          \item \texttt{success?} — возвращает истинное значение, если все
                проверки, добавленные через \texttt{match} — успешны.
          \item \texttt{<=>(another)} — сравнивает себя с другим результатом
                оценочной функции. Возвращает $-1$, $0$ или $1$, если хуже,
                равен или лучше, соответственно.
        \end{itemize}
  \item \texttt{D2NA::Tests} — класс для хранения оценочных функции. Методы:
        \begin{itemize}
          \item \texttt{tests} — массив с кодом оценочных функций.
          \item \texttt{add(description, priority, \&block)} — добавляет код
                новой оценочной функции из \texttt{block} с описанием из
                \texttt{description} и приоритетом из \texttt{priority}.
          \item \texttt{run(code)} — тестирует объект класса\\
                \texttt{D2NA::Code} из параметра \texttt{code} и возвращает
                результат оценочной функции в объекте класса\\
                \texttt{D2NA::TestResult}.
          \item \texttt{output\_signals} — хеш с именем исходящего сигнала в
                ключах и посланном количестве в значениях.
          \item \texttt{out} — объект класса \texttt{D2NA::Recorder},
                записывающий исходящие сигналы тестируемого кода.
          \item \texttt{clear\_out!} — очищает записанные исходящие сигналы в
                \texttt{out} и \texttt{output\_signals}.
          \item \texttt{out\_should\_be\_empty} — проверяет, что \texttt{out}
                пуст. Создаёт 2 требования в объекте\\
                \texttt{D2NA::TestResult}:\\ \texttt{match(out.length == 1)} и
                \texttt{min(out.length)}.
          \item \texttt{out\_should\_has} —  проверяет, что в \texttt{out}
                содержал сигналы из ключей хеша \texttt{signals} в указаном в
                значениях хеша количестве. Для каждого элемента хеша
                \texttt{signals} создаёт 2 требования:
                \texttt{match(output\_signals[signal] ==\\ value)} и
                \texttt{min((output\_signals[signal] - value).abs)}. Хеш
                \texttt{signals} так же может содержать ключ \texttt{priority} с
                приоритетом теста.
          \item \texttt{out\_should(signals)} — проверяет, что в \texttt{out}
                содержал только сигналы из ключей хеша \texttt{signals} в
                указаном в значениях хеша количестве. Для каждого элемента
                хеша \texttt{signals} создаёт 2 требования:
                \texttt{match(output\_signals[signal] ==\\ value)} и
                \texttt{min((output\_signals[signal] - value).abs)}. Кроме того,
                подсчитывает неуказанные в ключах \texttt{signals} посланные
                сигналы и для них создаёт 2 требования: \texttt{match(0 == bad)}
                и \texttt{min(bad)}. Хеш \texttt{signals} так же может содержать
                ключ \texttt{priority} с приоритетом теста.
          \item \texttt{out\_should\_hasnt(signals, options)} —\\ проверяет,
                чтобы среди посланных сигналов не было исходящих сигналов из
                массива \texttt{signals}. Для каждого сигнала массива
                \texttt{signals} создаёт два требования:
                \texttt{min(output\_signals[i])} и\\
                \texttt{match(output\_signals[i] == 0)}. В \texttt{options}
                может содержаться хеш с ключом \texttt{priority} с приоритетом
                теста.
          \item \texttt{send(*signals)} — посылает в тестируемый код входящие
                сигналы из массива \texttt{signals}.
          \item \texttt{should(value, options)} — создаёт требование\\
                \texttt{match(value)}. В \texttt{options} может содержаться хеш
                с ключом \texttt{priority} с приоритетом теста.
          \item \texttt{max(value, options)} — создаёт требование\\
                \texttt{max(value)}. В \texttt{options} может содержаться хеш
                с ключом \texttt{priority} с приоритетом теста.
          \item \texttt{min(value, options)} — создаёт требование\\
                \texttt{min(value)}. В \texttt{options} может содержаться хеш
                с ключом \texttt{priority} с приоритетом теста.
        \end{itemize}
  \item \texttt{D2NA::Population} — класс для хранения программ по слоям на
        основе результата оценочной функции. Имеет методы:
        \begin{itemize}
          \item \texttt{push(code, result)} — помещает в популяцию код из
                \texttt{code} с объектом класса \texttt{D2NA::Code} и
                соответствующий ему результат оценочной функции из
                \texttt{result} с объектом класса \texttt{D2NA::TestResult}.
          \item \texttt{pop} — возвращает следующий код и удаляет его из
                популяции.
          \item \texttt{best\_result} — возвращает лучший результат оценочной
                функции.
          \item \texttt{best} — возвращает код с наименьшей длинной и получивший
                лучший результат оценочной функции.
          \item \texttt{trim(first, decrease)} — сокращает первый слой для
                размера из параметра \texttt{first}, а последующий слои
                сокращаются до размера\\ $L_i = L_{i-1} / \texttt{decrease}$.
        \end{itemize}
 \item \texttt{D2NA::MutableCode} — расширяет класс \texttt{D2NA::Code},
       добавляя в него методы для изменения, клонирования, печати и мутации:
       \begin{itemize}
         \item \texttt{to\_tuby} — возвращает строку с исходным кодом программы.
         \item \texttt{clone} — возвращает копию объекта и всех его кешей.
               Правила из его свойства \texttt{rules} не копируются, так как они
               будут копироваться, только если одна из копий кода изменит
               правило.
         \item \texttt{modify(\&block)} — выполняет блок кода из \texttt{block}
               на объекте (с помощью \texttt{instance\_eval}), после чего
               перекомпилирует все изменённые правила.
         \item \texttt{conditions\_count} — количество всех возможных условий
               с текущими входящими сигналами и переменными.
         \item \texttt{unused\_conditions} — неиспользованные условия из
               всех возможных условий с текущими входящими сигналами и
               переменными. То есть условия, с которыми ещё нет правил.
         \item \texttt{delete\_rule(rule)} — удаляет правило \texttt{rule} из
               кода и всех его кешей.
         \item \texttt{remove\_state(state)} — удаляет переменную с именем
               \texttt{state}, все правила имеющие эту переменную в условии и
               все команды, работающие с этой переменной.
         \item \texttt{add\_command(rule\_number, command, param)} — добавляет
               команду \texttt{comamnd}, влияющую на переменную или сигнал
               \texttt{param}, в правило с порядковым номером из
               \texttt{rule\_number}. При изменении правила, сначала копирует
               его и меняет уже его копию.
         \item \texttt{remove\_command(position, rule\_number)} — удаляет
               правило с порядковым номером \texttt{position}. При изменении
               правила, сначала копирует его и меняет уже его копию. Если
               \texttt{rule\_number} указан, то порядковый номер отсчитывается
               в указанном правиле, иначе — во всей программе с начала.
         \item \texttt{mutation\_params} — параметры случайных изменений по
               умолчанию.
         \item \texttt{mutate!(params)} — вносит в код случайные изменения
               исходя из параметров объединив \texttt{params} или
               \texttt{mutation\_params}.
       \end{itemize}
  \item \texttt{D2NA::Worker} — класс для многопоточной обработки. Методы:
      \begin{itemize}
        \item \texttt{evolution} — генератор, который создал этот объект.
        \item \texttt{thread} — отдельный процесс, в котором работает это
              объект.
        \item \texttt{tests} — копия оценочной функции, чтобы при её вызове
              не создавать конфликтов с другими работающими объектам класса
              \texttt{D2NA::Worker}.
        \item \texttt{work} — сделать очередную итерацию работы со следующим
              кодом из прошлой популяции.
        \item \texttt{run} — запустить работу объекта в отдельном процессе.
      \end{itemize}
  \item \texttt{D2NA::Evolution} — класс для настройки и управления генерацией
        кода с помощью генетических алгоритмов. Содержит методы:
        \begin{itemize}
          \item \texttt{protocode(code, \&block)} — задаёт объект\\ класса
                \texttt{D2NA::Code} из параметра \texttt{code} как первое
                поколение программы для начала итераций. Если \texttt{code} не
                задан, но передан блок кода, то метод сам создаст пустой
                экземпляр \texttt{D2NA::MutableCode} и вызовет на нём
                \texttt{block} с исходных $D^2NA$-кодом. Вызванный без
                параметров возвращает текущее значение.
          \item \texttt{min\_population(count)} — задаёт \texttt{size}, как
                минимальное количество программ-кандидатов после каждой
                итерации. Вызванный без параметров возвращает текущее значение.
                По умолчанию — 10.
          \item \texttt{stagnation\_grow(count)} — задёт \texttt{count}, как
                увеличение популяции на каждом шаге, когда оценочная функциия
                не была улучшена. Вызванный без параметров возвращает текущее
                значение. По умолчанию — 2.
          \item \texttt{layer\_decrease(count)} — задаёт \texttt{count}, как
                коэффициент уменьшение размера каждого слоя популяции.
                Вызванный без параметров возвращает текущее значение.
                По умолчанию — 2.
          \item \texttt{worker\_count(count)} — задаёт \texttt{size}, как
                количество объект класса \texttt{D2NA::Worker}, которые будут
                загружены для генерации кода и будут работать в независимых
                потоках. Вызванный без параметров возвращает текущее значение.
                По умолчанию — 1.
          \newpage
          \item \texttt{selection(description, options, \&block)} — добавляет в
                объект класса \texttt{D2NA::Tests} оценочную функцию, которой
                конечный $D^2NA$-код должен соответствовать. Аргумент
                \texttt{description} может содержать описание оценочной
                функции, а \texttt{options} — хеш с параметром
                \texttt{priority}, в котором содержится цифровой приоритет этой
                оценочной над другими.
          \item \texttt{tests} — возвращает массив оценочных функций, объектов
                класса \texttt{D2NA::Tests}.
          \item \texttt{end\_if(\&block)} — задаёт \texttt{block}, как функцию
                остановка. Переданный код будет вызываться в конце каждой
                итерации, и, если он вернёт истинное значение, процесс генерации
                будет остановлен, так как цель разработчика достигнута.
                По умолчанию — \texttt{success}, то есть проверяет, чтобы
                требования оценочной функции были выполнены.
          \item \texttt{stagnation\_limit(maximum)} — задаёт\\ \texttt{maximum},
                как максимальное количество шагов простоя. Если значение
                оценочной функции не было улучшено за максимальное количество
                шагов простоя, то генерация останавливается, поскольку генератор
                не способен создать требуемый код. Вызванный без параметров
                возвращает текущее значение. По умолчанию — 1 000.
          \item \texttt{last\_best\_result} — лучший результат оценочной функции
                с прошлой итерации.
          \item \texttt{stagnation} — возвращает количество последних шагов, за
                которые не удалось улучшить результат оценочной функции.
          \item \texttt{success} — возвращает истинное значение, если все
                требований оценочной функции выполнены.
          \item \texttt{step!} — делает следующую итерацию написания программы.
          \item \texttt{step} — возвращает количество уже выполненных итераций.
          \item \texttt{end?} — возвращает значение функция останова.
          \item \texttt{no\_result?} — возвращает истинное значение, если
                цель генерации нельзя достигнуть, то есть максимальное
                количество без улучшения оценочной функции превышено.
          \item \texttt{next\_step?} — возвращает истинное значение, если
                функция останова показала, что цель генерации ещё не достигнута
                и требуются ещё итерации. Генерирует исключение, если количество
                шаг без улучшение результата оценочной функции
                (\texttt{stagnation}) превысил предел\\
                \texttt{stagnation\_limit}.
          \item \texttt{population} — возвращает популяцию программ,
                сгенерированных на текущем шаге.
          \item \texttt{old\_population} — возвращает популяцию программ,
                полученных на предыдущем шаге.
          \item \texttt{workers} — массив созданных объектов класса
                \texttt{D2NA::Worker} для работы в многопоточном режиме.
        \end{itemize}
\end{itemize}

\newpage
\subsubsection{Генерация кода}

Процесс генерации программы на $D^2NA$-коде по оценочной функции:

\begin{enumerate}
  \item В пакете \texttt{d2na/evolution} есть файл \texttt{d2na-evolution.rb},
        который загружает все класс генератора и виртуальной машины:
        \begin{verbatim}
        require 'd2na-evolution'
        \end{verbatim}
  \item После загрузки нужных классов, разработчик создаёт экземпляр класса
        \texttt{D2NA::Evolution} и устанавливает в ней нужные ему настройки,
        имена входящий и исходящих сигналов и оценочные функции:
        \begin{verbatim}
        e = D2NA::Evolution.new do
          protocode do
            input … # Имена входящих сигналов
            ouput … # Имена входящих сигналов
          end
          # Настройки
          selection do
            # Оценочная функция
          end
        end
        \end{verbatim}
   \newpage
   \item Далее разработчик пишет цикл, совершающий итерацию генерации кода,
         пока цель генерации не будет достигнута или застой (количество
         итераций без улучшения оценочной функции) не превысит максимальное
         значение:
         \begin{verbatim}
         while e.next_step?
           e.step!
         end
         \end{verbatim}
  \item Вначале генератор создаёт первое поколение в свойстве\\
        \texttt{population} размером указанным в \texttt{min\_population},
        содержащее точные копии кода переданного в \texttt{protocode}.
  \item До начала итерация генератор создаёт указанное в\\
        \texttt{worker\_count} количество процессов обработки их объектов класса
        \texttt{D2NA::Worker}.
  \item В начале каждой итерации генератор копирует текущую популяцию из
        \texttt{population} в \texttt{old\_population}. В \texttt{population}
        создаётся пустая популяция.
  \item Далее каждый обработчик (объект класса \texttt{D2NA::Worker}) в
        отдельном процессе начинает итерацию:
        \begin{enumerate}
          \item Достаёт следующий код и удаляет его из прошлой популяции\\
                \texttt{old\_population}.
          \item Делает 2 копии кода с помощью метода \texttt{clone} класса
                \texttt{D2NA::MutableCode}.
          \item На каждой копии вызывает случайные изменения с помощью метода
                \texttt{mutate!}.
          \item Каждую копию тестирует заданными разработчиком оценочными
                функциями из свойства \texttt{tests} класса
                \texttt{D2NA::Evolution}.
          \item Каждую копию кода, вместе с полученными результатами оценочной
                функции помещает в новую популяцию \texttt{population}.
          \item Объект класса \texttt{Population} приняв новый код и его
                результат оценочной функции, с помощью бинарного поиска находит
                подходящий слой и сохраняет код там.
        \end{enumerate}
  \item После окончания итерации генератор с помощью\\
        \texttt{last\_best\_result} и \texttt{population.best\_result} смотрит,
        улучшился ли результат оценочной функции, и, если она стал больше,
        обнуляет \texttt{stagnation}, иначе увеличивает на 1.
  \item Далее генератор вычисляет новый размер первого слоя\\
        (\texttt{min\_population + stagnation\_grow * stagnation}) и удаляет из
        популяции программы максимально несоответствующие оценочной функции с
        помощью \texttt{population.trim}.
  \item После чего управление возвращает в цикл генерации и если
        \texttt{stagnation} превысил \texttt{stagnation\_limit}, то генерируется
        исключение \texttt{D2NA::Timeout}, что код нельзя сгенерировать.
        Иначе, с помощью \texttt{end?} проверяется достигнута ли цель генерации,
        указанная в \texttt{end\_if}. Если цель достигнута, то цикл прерывается,
        иначе, возвращается на шаг \textit{е}.
\end{enumerate}

\newpage
\begin{thebibliography}{}

  \bibitem{communication}
    Mitri, S., Hubert, J. and Waibel, M. Social Behavior: From Cooperation to
    Language. — Biological Theory. 2008. — с. 99—102

  \bibitem{dilemma}
    Axelrod R. The Evolution of Cooperation. — Basic Books, 1984

  \bibitem{damage}
    Bongard J., Lipson H. Automated Damage Diagnosis and Recovery for Remote
    Robotics. — ICRA04, 2004

  \bibitem{reinforcement}
    Sutton R., Barto A. Reinforcement Learning. — The MIT Press, 2002

  \bibitem{neural}
    Haykin S. Neural Networks: A Comprehensive Foundation. 2nd Edition. — M.: Prentice Hall, 1998

  \bibitem{shalyto}
    Царев Ф.Н., Шалыто А.А. Применение генетического программирования для
    построения автоматов, управляющих системами со сложным поведением. — 2007
  
  \bibitem{ruby}
      Flanagan D., Matsumoto Y. The Ruby Programming Language. — M.: O'Reilly, 2008

\end{thebibliography}

\end{document}