Выводы по главе 3
Предложен новый метод совместного применения генетического и автоматного программирования – метод построения конечных автоматов на основе тестов.
Предложен алгоритм генетического программирования, осуществляющий построение автомата управления системой со сложным поведением на основе построения его структуры и алгоритма расстановки пометок.
Предложен метод скрещивания описаний конечных автоматов, учитывающий поведение автоматов на тестах.
Приведен пример применения предложенного метода и алгоритма генетического программирования для построения конечного автомата управления часами с будильником.
Заключение
В работе предложен метод построения автоматов управления системами со сложным поведением на основе тестов. Описано программное средство для поддержки этого метода. Приведен пример применения этого метода для построения автомата управления часами с будильником.
В работе также предложен метод представления функции переходов управляющего конечного автомата с помощью конечных распознавателей. Приведен пример применения этого метода для построения конечного автомата в задаче «Умный муравей–3». Выполнено сравнение предложенных методов с существующими.
Сформулированы направления дальнейшего исследования по применению генетических алгоритмов для построения конечных автоматов управления системами со сложным поведением:
совместное применение метода построения автоматов на основе тестов и метода сокращенных таблиц переходов;
совместное применение метода построения автоматов на основе тестов и метода представления автоматов деревьями решений;
изучение возможности применения методов верификации на моделях (Model checking) [8] при вычислении функции приспособленности.
По теме работы сделан доклад на IV межвузовской конференции молодых ученых (14–17 апреля 2009 года, СПбГУ ИТМО) и на научно-практической конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009, 26–27 мая 2009 года, г. Коломна). Кроме этого, поданы материалы на XII международную конференцию по мягким вычислениям и измерениям (SCM 2009, 25–27 июня 2009 года, СПбГЭТУ (ЛЭТИ) им. В. И. Ульянова-Ленина, Санкт-Петербург, Россия).
Источники
Бедный Ю. Д., Шалыто А. А. Применение генетических алгоритмов для построения автоматов в задаче «Умный муравей». СПбГУ ИТМО. 2007. http://is.ifmo.ru/works/ant/
Бек К. Экстремальное программирование: разработка через тестирование. СПб: Питер, 2003.
Воронин О., Дьюдни А. Дарвинизм в программировании //Мой компьютер. 2004. № 35. http://www.mycomp.kiev.ua/text/7458
Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит. 2006.
Гуров В. С., Мазим М. А., Нарвский А. С., Шалыто А. А. UML. SWITCH-технология. Eclipse // Информационно-управляющие системы. 2004, № 6, c.12–17.
Данилов В. Р. Метод представления автоматов деревьями решений для использования в генетическом программировании //Научно-технический вестник СПбГУ ИТМО. Выпуск 53. Автоматное программирование, с. 103-108.
Данилов В. Р. Технология генетического программирования для генерации автоматов управления системами со сложным поведением. СПбГУ ИТМО. Бакалаврская работа. 2007.
Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. М.: Издательство МЦНМО. 2002.
Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академии Наук СССР 163.4, с. 845–848.
Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о «Флибах» / Сборник докладов 4-й Всероссийской научной конференции «Управление и информационные технологии» (УИТ-2006). СПбГЭТУ «ЛЭТИ». 2006. с.144–149. http://is.ifmo.ru/works/flib
Мазин М. А. Парфенов В. Г., Шалыто А. А. Разработка интерактивных приложений Macromedia Flash на базе автоматной технологии. Проектная документация. СПбГУ ИТМО. 2003. http://is.ifmo.ru/projects/flash/
Непейвода Н. Н. Стили и методы программирования. М.: Интернет-Университет Информационных технологий, 2005.
Николенко С. И. Лекции по генетическим алгоритмам. http://logic.pdmi.ras.ru/~sergey/teaching/ml/
Норенков И. П., Арутюнян Н. М. Метагенетический алгоритм оптимизации и структурного синтеза проектных решений //Информационные технологии. 2007. № 3.
Поликарпова Н. И., Точилин В. Н., Шалыто А. А. Применение генетического программирования для генерации автоматов с большим числом входных переменных //Научно-технический вестник СПбГУ ИТМО. Выпуск 53. Автоматное программирование, с. 24-42.
Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб: Питер, 2009.
Промежуточный отчет по этапу III «Экспериментальные исследования поставленных перед НИР задач». http://is.ifmo.ru/genalg/_2007_03_report-genetic.pdf
Промежуточный отчет по этапу IV «Обобщение и оценка результатов исследований». http://is.ifmo.ru/genalg/_2007_04_report-genetic.pdf
Рассел С., Норвиг П. Искусственный интеллект. Современный подход. М.: Вильямс. 2006.
Сайт по генетическому программированию. www.genetic-programming.com
Туккель Н. И., Шалыто А. А. Система управления дизель-генератором (фрагмент). Программирование с явным выделением состояний. Проектная документация. http://is.ifmo.ru/projects/dg/
Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.
Царев Ф. Н. Разработка метода совместного применения генетического программирования и конечных автоматов на примере игры «Летающие тарелки». СПбГУ ИТМО. Бакалаврская работа. 2007.
Царев Ф. Н. Совместное применение генетического программирования, конечных автоматов и искусственных нейронных сетей для построения системы управления беспилотным летательным аппаратом //Научно-технический вестник СПбГУ ИТМО. Выпуск 53. Автоматное программирование, с. 42–60.
Царев Ф. Н., Шалыто А. А. Применение генетических алгоритмов для построения автоматов с минимальным числом состояний для задачи об «Умном муравье» /Труды научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях». СПб.: СПбГПУ. 2008, с.209-215.
Шалыто А. А. Switch-технология. Алгоритмизация и программирование задач логического управления СПб.: Наука, 1998.
Angeline P., Pollack J. Evolutionary Module Acquisition / Proceedings of the Second Annual Conference on Evolutionary Programming. Cambridge: MIT Press. 1993, pp.154–163. http://www.demo.cs.brandeis.edu/papers/ep93.pdf
Armstrong, D. A programmed algorithm for assigning internal codes to sequential machines // IRETransactions on Electronic Computers, EC.11. 1962. I.4, pp.466–472.
Axelrod R. The Evolution of Cooperation. NY: Basic Books, 1984.
Axelrod R. The Evolution of Strategies in the Iterated Prisoner's Dilemma / In Genetic Algorithms and Simulated Annealing. London: Pitman, 1987. pp. 32−41. http://www-personal.umich.edu/~axe/research_papers.html
Belz A., Eskikaya B. A Genetic Algorithm for Finite State Automata Induction with Application to Phonotactics / Proceedings of the ESSLLI-98 Workshop on Automated Acquisition of Syntax and Parsing, Saarbruecken, 1998, pp. 9–17. http://www.itri.brighton.ac.uk/~Anja.Belz/Publications/A_GA_for_FSA_induction_with_an_application_to_phonotactics.ps
Benson K. Evolving Finite State Machines with Embedded Genetic Programming for Automatic Target Detection. http://ieeexplore.ieee.org/iel5/6997/18853/00870838.pdf
Brave S. Evolving Deterministic Finite Automata Using Cellular Encoding / Proceeding of First Annual Conference (Genetic Programming-1996), pp. 39−44. http://citeseer.ist.psu.edu/131538.html
Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. Volumes I. II, III. CRC Press, 1999.
Das R., Mitchell M., Crutchfield J.P. A genetic algorithm discovers particle-based computation in cellular automata // Lecture Notes in Computer Science. 1994. www.santafe.edu/research/publications/workingpapers/94-03-015.pdf
Fogel D. The Evolution of Intelligent Decision Making in Gaming // Cybernetics and Systems. 2001. 22, pp. 223−236.
Fogel L. Autonomous Automata // Industrial Research. 1962. V.4, pp. 14–19.
Fogel L., Owens A., Walsh M. Artificial Intelligence through Simulated Evolution. NY: Wiley. 1966.
Ghnemat R., Khatatneh K., Oqeili S., Bertelle C., Duchamp G. Automata-based adaptive behavior for economic modeling using game theory. 2005. http://arxiv.org/abs/cs/0510089
Gold E. M. Complexity of automaton identification from given data. // Information and Control, 1978, № 37, pp. 302−320.
Goldberg D. A Note on Boltzmann Tournament Selection for Genetic Algorithms and Population-Oriented Simulated Annealing // Complex Systems. 1990. V. 4, I. 4, pp. 445−460.
Hamming R. Error detecting and error correcting codes. Bell System Technical Journal 29 (2), pp. 147–160.
Hillis W. Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure / In Artificial Life II. MA: Addison-Wesley, 1992. pp. 313−324.
Holland J. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System: Evolution as a Theme in Artificial Life /Proceedings of Second Conference on Artificial Life. MA: Addison-Wesley. 1992, pp.549–578. www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html
Juillie H., Pollack J. Coevolving the "Ideal" Trainer: Application to the Discovery of Cellular Automata Rules. 1998. http://citeseer.ist.psu.edu/16712.html
Koza J. Genetic Evolution and Co-Evolution of Computer Programs / Proceedings of Second Conference on Artificial Life. Redwood City, CA: Addison-Wesley. 1992. pp. 603−629. http://citeseer.ist.psu.edu/177879.html
Koza J. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA: The MIT Press, 1998.
Levy S. Artificial Life: The Quest for a New Creation. New York: Pantheon, 1992. 380 p.
Lucas S., Reynolds T. Learning DFA: Evolution versus Evidence Driven State Merging.
Lucas S., Reynolds T. Learning Finite State Transducers: Evolution versus Heuristic State Merging. IEEE Transactions on Evolutionary Computation
Volume 11, Issue 3, June 2007, pp. 308–325.
Lucas S., Reynolds T. Learning Deterministic Finite Automata with a Smart State Labelling Evolutionary Algorithm. IEEE Transactions on Evolutionary Computation
Volume 27, Issue 7, June 2005.
Miller J. The Coevolution of Automata in the Repeated Prisoner's Dilemma. Working Paper. Santa Fe Institute. 1989 // Journal of Economic Behavior & Organization. 1996. V. 29, I. 1, pp. 87–112.
Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996.
Mitchell M., Crutchfield J. P., Hraber P. T. Evolving cellular automata to perform computations. Physica D. 75, pp. 361–391, 1993. http://web.cecs.pdx.edu/~mm/mech-imped.pdf
Naidoo A., Pillay N. The Induction of Finite Transducers Using Genetic Programming / Proceedings of Euro GP. Springer. 2007. http://saturn.cs.unp.ac.za/~nelishiap/papers/eurogp07.pdf
Nedjah N., Mourelle L. Mealy Finite State Machines: An Evolutionary Approach // International Journal of Innovative Computing, Information and Control. 2006. V.2, I. 4.
Reynolds C. W. Competition, Coevolution and the Game of Tag / Proceedings of Artificial Life IV. Cambridge. MA: MIT Press, 1994. pp. 59−69. http://www.red3d.com/cwr/papers/1994/alife4.html
Tu M., Wolff E., Lamersdorf W. Genetic Algorithms for Automated Negotiations: A FSM-based Application Approach /Proceedings of the 11-th International Conference on Database and Expert Systems. 2000. http://ieeexplore.ieee.org/iel5/7035/18943/00875153.pdf
Whitley D. The GENITOR Algorithm and Selective Pressure / Proceedings of the 3rd International Conference on Genetic Algorithms. Colorado State: Morgan Kaufmann, 1989. pp. 116−121. http://www.genalgo.com/index.php?option=com_content&task=view&id=80&Itemid=30
Wolff K., Nordin P. An Evolutionary Based Approach for Control Programming of Humanoids / Proceedings of the 3rd International Conference on Humanoid Robots (Humanoids'03). Karlsruhe: VDI/VDE-GMA. 2003. http://citeseer.ist.psu.edu/641298.html
|
