Совместное применение генетического программирования и верификации для построения автоматов управления системами со сложным поведением
Ключевые слова:
генетическое программирование, машинное обучение, верификация моделей, автонматное программированиеАннотация
Предлагается метод машинного обучения, основанный на совместном применении генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением на основе обучающих примеров. Приводится описание структуры хромосом, генетического алгоритма, операций мутации и скрещивания. Изложены результаты экспериментального исследования на задаче построения конечного автомата управления дверьми лифта.Литература
Поликарпова Н.И., Шалыто А.А Автоматное программирование. СПб: Питер, 2009.
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, свободный, язык – английский, последнее обращение – 17.06.2010.
Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System. 1992. [Электронный ресурс]. Режим доступа: http://www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html, свободный, язык – английский, последнее обращение – 17.06.2010.
Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. V. III. CRC Press, 1999.
Царев Ф.Н. Метод построения автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования / Материалы международной научной конференции «Компьютерные науки и информационные технологии». Саратов: СГУ. 2009, с. 216–219.
Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академии Наук СССР. 1963. № 4, с. 845–848.
Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. M.: МЦНМО, 2002.
Gerth R., Peled D., Vardi M. Y., Wolper P. Simple On-the-fly Automatic Verification of Linear Temporal Logic / Proc. of the 15th Workshop on Protocol Specification, Testing, and Verification, Warsaw, 1995, pp. 3–18.
Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода. Второй этап. СПбГУ ИТМО, 2007. [Электронный ресурс]. Режим доступа: http://is.ifmo.ru/verification/_2007_02_report-verification.pdf, свободный, язык – русский, последнее обращение – 17.06.2010.
Егоров К.В., Шалыто .А. Методика верификации автоматных программ // Информационно-управляющие системы. 2008, № 5, с. 15–21.
11. Lucas S., Reynolds T. Learning Finite State Transducers: Evolution versus Heuristic State Merging // IEEE Transactions on Evolutionary Computation. V. 11, Issue 3, June 2007, pp. 308–325.
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, свободный, язык – английский, последнее обращение – 17.06.2010.
Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System. 1992. [Электронный ресурс]. Режим доступа: http://www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html, свободный, язык – английский, последнее обращение – 17.06.2010.
Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. V. III. CRC Press, 1999.
Царев Ф.Н. Метод построения автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования / Материалы международной научной конференции «Компьютерные науки и информационные технологии». Саратов: СГУ. 2009, с. 216–219.
Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академии Наук СССР. 1963. № 4, с. 845–848.
Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. M.: МЦНМО, 2002.
Gerth R., Peled D., Vardi M. Y., Wolper P. Simple On-the-fly Automatic Verification of Linear Temporal Logic / Proc. of the 15th Workshop on Protocol Specification, Testing, and Verification, Warsaw, 1995, pp. 3–18.
Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода. Второй этап. СПбГУ ИТМО, 2007. [Электронный ресурс]. Режим доступа: http://is.ifmo.ru/verification/_2007_02_report-verification.pdf, свободный, язык – русский, последнее обращение – 17.06.2010.
Егоров К.В., Шалыто .А. Методика верификации автоматных программ // Информационно-управляющие системы. 2008, № 5, с. 15–21.
11. Lucas S., Reynolds T. Learning Finite State Transducers: Evolution versus Heuristic State Merging // IEEE Transactions on Evolutionary Computation. V. 11, Issue 3, June 2007, pp. 308–325.
Опубликован
2010-12-01
Как цитировать
Шалыто, А. А., Царев, Ф. Н., & Егоров, К. В. (2010). Совместное применение генетического программирования и верификации для построения автоматов управления системами со сложным поведением. Труды СПИИРАН, 4(15), 123-135. https://doi.org/10.15622/sp.15.7
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
