<p>
	ПРИМЕНЕНИЕ НАПРАВЛЕННОЙ МУТАЦИИ ДЛЯ ГЕНЕРАЦИИ КЛЕТОЧНЫХ АВТОМАТОВ</p>

Тихомиров Андрей Владимирович, Шалыто Анатолий Абрамович

2014 , ТОМ 14, НОМЕР 2 ( МАРТ-АПРЕЛЬ )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

УДК 004.4'242

ПРИМЕНЕНИЕ НАПРАВЛЕННОЙ МУТАЦИИ ДЛЯ ГЕНЕРАЦИИ КЛЕТОЧНЫХ АВТОМАТОВ

Тихомиров А.В., Шалыто А.А.

Читать статью полностью

Аннотация

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

Ключевые слова: клеточные автоматы, генетические алгоритмы

Список литературы

1. Frisch U., d'Humières, D., Hasslacher B. et. al. Lattice gas hydrodynamics in two and three dimensions // Complex Systems. 1987. V. 1. N 4. P. 649–707.

2. Wolfram S. Cellular automation fluids 1: Basic theory // Journal of Statistical Physics. 1986. V. 45. N 3–4. Р. 471–526.

3. Vose M.D., Wright A.H. Simple genetic algorithms with linear fitness // Evolutionary Computation. 1994. V. 2, N 4. P. 347-368.

4. Vose M.D. A critical examination of the schema theorem. Technical Report UT-CS-93212. University of Tennessee, 1993. [Электронный ресурс]. Режим доступа: http://citeseer.ist.psu.edu/129900.html, свободный. Яз. англ. (дата обращения 20.02.2014).

5. Vose M.D., Wright A.H. The simple genetic algorithm and the Walsh transform. Part I. Theory // Evolutionary Computation. 1998. V. 6. N 3. P. 253–273.

6. Das R., Crutchfield J.P., Mitchell M., Hanson J.E. Evolving Globally synchronized cellular automata // Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, USA: 1995. P. 336–343.

7. Psakhie S.G., Horie Y., Ostermeyer G.P. et. al. Movable cellar automata method for simulating materials with mesostructure // Theoretical and Applied Fracture Mechanics. 2001. V. 37. P. 311–334.

8. Скаков П.С. Классификация поведения одномерных клеточных автоматов. Магистерская диссертация. СПбГУ ИТМО, 2007. [Электронный ресурс]. Режим доступа: http://is.ifmo.ru/papers/_skakov_master.pdf, свободный. Яз. рус. (дата обращения 20.02.2014).

9. Панченко Е.В., Ульянцев В.И. Применение методов решения задачи о выполнимости квантифицированной булевой функции для построения управляющих конечных автоматов по сценариям работы и темпоральным свойствам // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 4 (86). C. 151–153.

10.Бедный Ю.Д. Применение генетических алгоритмов для построения клеточных автоматов [Электронный ресурс]. – Режим доступа: http://is.ifmo.ru/papers/genalgcelaut.pdf, свободный. Яз. рус. (дата обращения 20.02.2014).

11.Царев Ф.Н., Шалыто А.А. Применение генетического программирования для генерации автомата в задаче об «умном муравье» [Электронный ресурс]. Режим доступа:http://is.ifmo.ru/genalg/_ant_ga.pdf, свободный. Яз. рус. (дата обращения 20.02.2014).

12.Тихомиров А.В., Шалыто А.А. Применение адаптивного генетического алгоритма для генерации клеточных автоматов // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 1 (77). С. 100–105.

13.Тихомиров А.В., Шалыто А.А. Применение генетического подхода для генерации клеточных автоматов // Научно-технический вестник СПбГУ ИТМО. 2011. № 2 (72). С. 62–66.

14.Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991. 280 с.

15.Фон Нейман Дж. Теория самовоспроизводящихся автоматов: Пер. с англ. М.: Мир, 1971. 384 с.

16.Наумов Л.А. Метод введения обобщенных координат и инструментальное средство для автоматизации проектирования программного обеспечения вычислительных экспериментов с использованием клеточных автоматов.Äèñ канд. техн. наук: 05.13.12. СПб, 2007. 283 с.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License