УДК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 с.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2019 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика