Введение
1. Автоматное программирование, конечные автоматы, методы генерации конечных автоматов 15
1.1. Автоматное программирование 15
1.2. Метаэвристические алгоритмы
1.2.1. Эволюционные алгоритмы 20
1.2.2. Муравьиные алгоритмы
1.3. Поисковая инженерия программного обеспечения 30
1.4. Методы генерации конечных автоматов
1.4.1. Методы генерации конечных автоматов без учета темпоральных формул 31
1.4.2. Методы генерации конечных автоматов с учетом темпоральных формул 37
1.4.3. Методы на основе AE-парадигмы 40
1.4.4. Метод генерации автоматных моделей программ с инвариантами 43
1.5. О свойствах пространства поиска в одной задаче генерации конечных автоматов 44
1.6. Постановка задачи генерации управляющих конечных автоматов по сценариям работы и темпоральным формулам 47
1.7. Задачи, решаемые в диссертационной работе 49
Выводы по главе 1 51
2. Метод генерации конечных автоматов по сценариям работы и темпоральным формулам на основе муравьиного алгоритма 52
2.1. Функция приспособленности 52
2.2. Способ представления пространства поиска 53
2.3. Выбор начального приближения
2.4. Эвристическая информация 56
2.5. Построение решений муравьями 56
2.6. Обновление значений феромона 59
2.7. Генерация начального решения по сценариям работы с помощью алгоритма на основе решения задачи выполнимости 62
2.8. Вычислительные эксперименты
2.8.1. Подготовка входных данных 62
2.8.2. Сравнение эффективности алгоритмов 64
2.8.3. Настройка значений параметров 65
2.8.4. Пример: генерация автомата управления дверьми лифта.. 67
2.8.5. Генерация автоматов по случайно сгенерированным входным данным 69
2.9. Сравнение с точными методами генерации конечных автоматов по LTL-формулам 71
2.10.Использование предложенного метода MuACO для генерации автоматов управления моделью беспилотного самолета 74
Выводы по главе 2 74
3. Методы генерации конечных автоматов по сценариям работы и темпоральным формулам на основе параллельных муравьиных алгоритмов 76
3.1. Метод генерации конечных автоматов pMuACO 76
3.2. Методы psMuACO и pstMuACO 78
3.3. Вычислительные эксперименты 82
Выводы по главе 3 85
4. Инструментальное средство и библиотека для генерации конечных автоматов 86
4.1. Использование разработанного инструментального средства для генерации конечных автоматов по сценариям работы и темпоральным формулам 88
4.2. Использование разработанного инструментального средства для решения других задач генерации конечных автоматов 91
Выводы по главе 4 92
5. Внедрение результатов работы при генерации автоматной логики для базисных функциональных блоков стандарта IEC 61499 93
5.1. Стандарт IEC 61499 94
5.2. Постановка задачи 96
5.3. Предлагаемый подход 97
5.3.1. Формирование сценариев работы 97
5.3.2. Способ представления диаграммы управления выполнением 98
5.3.3. Операторы мутации 101
5.3.4. Алгоритм расстановки пометок в состояниях 103
5.3.5. Функция приспособленности 105
5.3.6. Упрощение диаграмм управления выполнением 108
5.3.7. Эксперименты 108
5.3.8. Анализ сгенерированных ДУВ 112
5.4. Полиномиальный алгоритм генерации ДУВ специального вида.. 114
5.4.1. Вычисление множества ДУВ-алгоритмов 114
5.4.2. Построение ДУВ по сценариям и известному множеству алгоритмов 116
Выводы по главе 5 119
Заключение 121
Список источников 123
