The problem of the Smart Ant-3
The problem of the Smart Ant-3

4.4. Автоматы и генетическое программирование

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

automata-and-genetic-programming

В других случаях построенный автомат бывает неоптимальным. Возможное решение всех этих проблем — перепоручить построение управляющего автомата компьютеру. Одним из наиболее эффективных методов автоматизированного конструирования программ является генетическое программирование. Основная идея генетического программирования состоит в построении программ путем применения генетических алгоритмов к некоторой модели вычисления. При этом разработчику программы остается лишь задать оценочную функцию, определяющую для каждого результата вычисления в выбранной модели численное значение, называемое его приспособленностью. Генетические алгоритмы — это метод оптимизации, основанный на концепциях естественной эволюции. Он оперирует поколениями, состоящими из особей. Первое поколение заполняется особями, сгенерированными случайным образом. Каждое последующее поколение формируется из особей предыдущего поколения в зависимости от их приспособленности путем перенесения их без изменений либо применения к ним с некоторыми вероятностями генетических операторов: мутации и скрещивания. Результатом оптимизации считается особь с максимальной оценкой из последнего поколения. Для того чтобы применение генетического программирования для оптимизации автоматизированных объектов управления стало возможным, необходимо разработать представление автомата в виде особи, определить операции мутации и скрещивания автоматов и подобрать параметры генетического алгоритма, подходящие для автоматов. После этого для каждой задачи остается только реализовать объект управления и определить функцию приспособленности. Значение приспособленности автоматизированного объекта управления целесообразно задавать как функцию вычислительного состояния объекта управления после заданного числа тактов работы автомата. Обычно в качестве моделей вычислений в генетическом программировании используют деревья, графы, команды процессора — «низкоуровневые» модели, имеющие ограниченный набор элементарных операций (таких, как, например, запись и чтение ячеек памяти, арифметические операции, вызовы подпрограмм и т. д.). Достоинство низкоуровневых моделей состоит в их универсальности: с их помощью можно построить любую программу целиком, единообразно, вне зависимости от специфики решаемой задачи. Однако такие модели обладают и серьезными недостатками. Во-первых, построенная программа из-за отсутствия высокоуровневой структуры редко бывает понятна человеку, что исключает возможность ее дальнейшей модификации вручную, обобщения полученного решения и т. п. Во-вторых, из-за того, что пространство допустимых программ в этом случае очень велико, генетическая оптимизация требует длительного времени и может использоваться только для небольших задач. С другой стороны, если использовать в качестве модели вычислений автоматизированный объект, причем реализацию объекта управления производить вручную, пространство поиска значительно сокращается и генетический подход становится реалистичным. При этом используется разумное разделение труда: компьютер выполняет ту часть работы, которая лучше всего получается у него, а человек — то, что под силу только ему. Первые работы в области генерации конечных автоматов с помощью генетических алгоритмов были выполнены около 40 лет назад Однако в этой работе автоматы рассматривались как одна из моделей человеческого интеллекта. Эта модель оказалась непродуктивной (по крайней мере, при существовавшем в то время уровне развития вычислительной техники), и исследования в этом направлении почти прекратились. Они возобновились только через 20 лет При этом круг рассматриваемых задач расширился. В частности, стали изучаться задачи управления, однако в большинстве этих задач управляющие автоматы имели только одну входную переменную (см. пункт 4.4.1). С развитием автоматного программирования стала актуальной задача генерации управляющих автоматов с большим числом входных переменных (см. пункт 4.4.2).

4.4.1. Задача об Умном муравье

1.8.1.3.Тип матрицы монитора

Программирование логических контроллеров ПЛК-автоматов