Адаптивные системы управления

Первый вариант скрещивания. Обозначим переход из состояния номер i в автомате P1 по значению входной переменной «Перед муравьем есть еда» как P1(i, 1), а по значению «Перед муравьем нет еды» как P1(i, 0). Аналогичный смысл придадим обозначениям P2(i, 0) и P2(i, 1). Тогда для переходов из состояния с номером i в автоматах-потомках S1 и S2 будет справедливо одно из четырех:

· либо S1(i, 0) = P1(i, 0), S1(i, 1) = P2(i, 1) и S2(i, 0) = P2(i, 0), S2(i, 1) = P1(i, 1);

· либо S1(i, 0) = P2(i, 0), S1(i, 1) = P1(i, 1) и S2(i, 0) = P1(i, 0), S2(i, 1) = P2(i, 1);

· либо S1(i, 0) = P1(i, 0), S1(i, 1) = P1(i, 1) и S2(i, 0) = P2(i, 0), S2(i, 1) = P2(i, 1);

· либо S1(i, 0) = P2(i, 0), S1(i, 1) = P2(i, 1) и S2(i, 0) = P1(i, 0), S2(i, 1) = P1(i, 1).

Все четыре варианта равновероятны.

Второй вариант скрещивания. В автоматах P1 и P2 найдем переходы, которые они выполняют в течение первых сорока ходов по игровому полю. Обозначим множество таких переходов автоматов P1 и P2 как TF(P1) и TF(P2) соответственно. Множество переходов некоторого автомата A обозначим T(A). Возможны два равновероятных варианта:

· либо T(S1) = TF(P1)U(T(P2) \TF(P2)) и T(S2) = TF(P2)?(T(P1) \TF(P1));

· либо T(S2) = TF(P1)U(T(P2) \TF(P2)) и T(S1) = TF(P2)?(T(P1) \TF(P1)).

Формирование следующего поколения. В качестве основной стратегии формирования следующего поколения используется элитизм [7]. При обработке текущего поколения отбрасываются все особи, кроме нескольких наиболее приспособленных. Доля выживающих особей постоянна для каждого поколения и является одним из параметров алгоритма. Эти особи переходят в следующее поколение. После этого оно дополняется до требуемого размера следующим образом: пока оно не заполнено выбираются две особи из текущего поколения, и они с некоторой вероятностью скрещиваются или мутируют. Обе особи, полученные в результате мутации или скрещивания, добавляются в новое поколение.

Кроме этого, если на протяжении достаточно большого числа поколений не происходит увеличения приспособленности, то применяются «малая» и «большая» мутации поколения.

При «малой» мутации поколения ко всем особям, кроме 10% лучших, применяется оператор мутации. При «большой» мутации каждая особь либо мутирует, либо заменяется на случайно сгенерированную.

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

Вычисление функции приспособленности. Функция приспособленности особи (автомата) равна

где F -количество еды, которое съедает за 200 ходов муравей, поведение которого задается этим автоматом, а T - номер хода, на котором муравей съедает последнюю единицу еды. Она вычисляется моделированием и запоминается.

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

Настраиваемые параметры алгоритма. Следующие параметры алгоритма генетического программирования могут быть изменены:

· размер поколения;

· доля особей, переходящих в следующее поколение;

· количество состояний;

· вероятность мутации;

· время до «малой» мутации поколения;

· время до «большой» мутации поколения.

Как показывают вычислительные эксперименты, изменение некоторых из этих параметров может существенно влиять на время поиска автомата, позволяющего муравью съесть всю еду.

3. Результаты

Вычислительные эксперименты проводились с различными значениями параметров алгоритма. При этом в перебираемых автоматах не разрешалось использовать действие «Ничего не делать». Заметим, что это действие, на самом деле, бесполезно. Оно подобно е-переходам в конечных недетерминированных автоматах, используемых для распознания регулярных языков, и может быть устранено алгоритмом, подобным алгоритму е-замыкания [8]. На рис. 3 изображен граф переходов построенного разработанным алгоритмом автомата с семью состояниями, который позволяет муравью съесть всю еду за 190 ходов.

Рис. 3. Автомат, позволяющий муравью съесть всю еду

На рис. 3 используются те же обозначения, что и на рис. 2.

Заключение

Во многих работах, например в [9], генетические алгоритмы применяются для настройки нейронных сетей. Однако нейронная сеть обладает существенным недостатком: после того, как она настроена, ни понять, как она работает, ни изменить ее так, чтобы она стала работать лучше человек не в состоянии. Авторы предполагают, что конечные автоматы этого недостатка лишены, так как они лучше структурированы за счет применения концепции состояний [10]. [3]

Литература

1. Шалыто А.А. Технология автоматного программирования / Труды первой Всероссийской научной конференции "Методы и средства обработки информации" М.: МГУ. 2003. http://is.ifmo.ru/works/tech_aut_prog/

2. Angeline P. J., Pollack J. Evolutionary Module Acquisition // Proceedings of the Second Annual Conference on Evolutionary Programming. 1993. http://www.demo.cs.brandeis.edu/papers/ep93.pdf

3. Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System. 1992. www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html

4. Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. Volume III. CRC Press, 1999.

5. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2006.

6. Koza J. R. Genetic programming: on the programming of computers by means of natural selection. MIT Press, 1992.

7. De Jong K. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis. Univ. Michigan. Ann Arbor, 1975.

8. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.

9. Рассел С., Норвиг П. Искусственный интеллект: современный подход. М.: Вильямс, 2006.

10. SWITCH-технология. Википедия. http://ru.wikipedia.org/wiki/Switch-

%D1%82%D0%B5%D1%85%D0%BD%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%8F

Размещено на Allbest