3.3.Пример применения метода
В настоящем разделе описывается применение предлагаемого метода для построения конечного автомата управления часами с будильником [16]. Эти часы имеют три кнопки (Рис. 26.), которые служат для изменения режима их работы и для настройки текущего времени или времени срабатывания будильника.
|
Внешний вид часов с будильником
|
Если будильник выключен, то кнопки «H» и «M» служат, соответственно, для увеличения на единицу числа часов и минут в текущем времени. Кнопка «A» в этом режиме служит для перехода в режим настройки времени срабатывания будильника. В этом режиме кнопки «H» и «M» служат для увеличения на единицу числа часов и минут во времени срабатывания будильника. Нажатие кнопки «A» в этом режиме приводит к включению будильника. Он срабатывает, как только время срабатывания совпадает с текущим временем. Звонок автоматически выключается через минуту или может быть выключен нажатием кнопки «A», которая также выключает будильник. Кроме кнопок часы содержат таймер, который срабатывает каждую минуту – при каждом его срабатывании текущее время увеличивается на одну минуту.
Отметим, что рассматриваемые часы с будильником являются системой со сложным поведением, так как в ответ на одни и те же входные события (нажатия кнопок) в зависимости от режима работы генерируются различные выходные воздействия.
Эта система со сложным поведением имеет четыре входных события:
H – нажата кнопка «H» на корпусе часов;
M – нажата кнопка «M» на корпусе часов;
A – нажата кнопка «A» на корпусе часов;
T – сработал таймер.
Она также содержит две входные переменные:
x1 – верно ли, что время срабатывания будильника совпадает с текущим временем;
x2 – верно ли, что текущее время превышает время срабатывания будильника ровно на одну минуту.
Кроме этого эта система имеет семь выходных воздействий:
z1 – увеличить число часов текущего времени;
z2 – увеличить число минут часов текущего времени;
z3 – увеличить число часов времени срабатывания будильника;
z4 – увеличить число минут времени срабатывания будильника;
z5 – прибавить минуту к текущему времени;
z6 – включить звонок будильника;
z7 – выключить звонок будильника.
Поведение часов с будильником может быть описано графом переходов конечного автомата, который приведен в [16] и построен вручную (Рис. 27.).
|
Граф переходов конечного автомата управления часами с будильником
|
Начальным состоянием этого автомата является состояние «1. Будильник выключен».
3.3.1.Система тестов
В систему тестов для построения автомата управления часами с будильником включены тесты, описывающие его работу во всех трех режимах. Тесты, описывающие поведение часов с будильником в режиме работы «Будильник выключен» приведены в табл. Таблица 7..
Тесты для режима работы «Будильник выключен»
|
Тест
|
Комментарий
|
Input: T, T, T, T
Answer: z5, z5, z5, z5
|
Описывает обработку часами события «Сработал таймер». При возникновении этого события текущее время должно быть увеличено на минуту.
|
Input: H, H, H, H
Answer: z1, z1, z1, z1
|
Описывает обработку часами нажатия кнопки «H». При нажатии на эту кнопку число часов в текущем времени должно быть увеличено на единицу.
|
Input: M, M, M, M
Answer: z2, z2, z2, z2
|
Описывает обработку часами нажатия кнопки «M». При нажатии на эту кнопку число минут в текущем времени должно быть увеличено на единицу.
|
Input: T, M, H, T, T, T, M, T, H, H, T, M
Answer: z5, z2, z1, z5, z5, z5, z2, z5, z1, z1, z5, z2
|
Описывает обработку событий H, M и T в режиме «Будильник выключен».
|
Input: A, A, A, T, T, T, T
Answer: z7, z5, z5, z5, z5
|
|
Input: A, A, A, H, H, H, H
Answer: z7, z1, z1, z1, z1
|
|
Input: A, A, A, M, M, M, M
Answer: z7, z2, z2, z2, z2
|
|
Тесты, описывающие поведение часов с будильником в режиме работы «Настройка будильника» приведены в табл. Таблица 8..
Тесты для режима работы «Настройка будильника»
|
Тест
|
Комментарий
|
A, T, T, T, T
z5, z5, z5, z5
|
|
A, H, H, H, H
z3, z3, z3, z3
|
|
A, M, M, M, M
z4, z4, z4, z4
|
|
A, T, T, M, H, T, T
z5, z5, z4, z3, z5, z5
|
|
A, T, M, H, T, T, T, M, T, H, H, T, M
z5, z4, z3, z5, z5, z5, z4, z5, z3, z3, z5, z4
|
|
A, A, A, A, T
z7, z5
|
|
A, A, A, A, T, T, T, T
z7, z5, z5, z5, z5
|
|
A, A, A, A, H
z7, z3
|
|
A, A, A, A, H, H, H, H
z7, z3, z3, z3, z3
|
|
A, A, A, A, M
z7, z4
|
|
A, A, A, A, M, M, M, M
z7, z4, z4, z4, z4
|
|
Тесты, описывающие поведение часов с будильником в режиме работы «Будильник включен» приведены в табл. Таблица 9..
Тесты для режима работы «Будильник включен»
|
Тест
|
Комментарий
|
A, A, H, H, H, H
z1, z1, z1, z1
|
|
A, A, M, M, M, M
z2, z2, z2, z2
|
|
A, A, T [!x1 & !x2], T [!x1 & !x2], T [!x1 & !x2]
z5, z5, z5
|
|
A, A, T [!x1 & !x2], T [x1], T [x2]
z5, z5, z6, z5, z7
|
|
A, A, T [!x1 & !x2], T [x1]
z5, z5, z6
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], H
z5, z5, z6, z5, z7, z1
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], M
z5, z5, z6, z5, z7, z2
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], T [!x1 & !x2]
z5, z5, z6, z5, z7, z5
|
|
A, A, T [x1]
z5, z6
|
|
A, A, T [x2]
z5, z7
|
|
A, A, T [x1], T [x2]
z5, z6, z5, z7
|
|
A, A, T [!x1 & !x2]
z5
|
|
A, A, T [!x1 & !x2], M, H, T [!x1 & !x2], T [!x1 & !x2], T [!x1 & !x2], M, T [!x1 & !x2], H, H, T [!x1 & !x2], M
z5, z2, z1, z5, z5, z5, z2, z5, z1, z1, z5, z2
|
|
Кроме тестов, описывающих поведение автомата в каждом из трех режимов, в набор тестов включены тесты, описывающие поведение автомата сразу в нескольких режимах. Эти тесты приведены в табл. Таблица 10..
Тесты, описывающие поведение автомата в нескольких режимах
|
Тест
|
Комментарий
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, H
z5, z5, z6, z5, z7, z7, z1
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, M
z5, z5, z6, z5, z7, z7, z2
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, T
z5, z5, z6, z5, z7, z7, z5
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, A, H
z5, z5, z6, z5, z7, z7, z3
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, A, M
z5, z5, z6, z5, z7, z7, z4
|
|
A, A, T [!x1 & !x2], T [x1], T [x2], A, A, T
z5, z5, z6, z5, z7, z7, z5
|
|
A, A, T [!x1 & !x2], T [x1], A, A, T
z5, z5, z6, z7, z5
|
| 3.3.2.Результаты применения генетического алгоритма
Построение конечного автомата управления часами с будильником проводилось при следующих параметрах алгоритма генетического программирования:
размер поколения – 2000 особей;
доля «элиты» – наиболее приспособленных особей, напрямую переходящих в следующее поколение, – 10 %;
число поколений до малой «мутации поколения» – 100 поколений;
число поколений до большой «мутации поколения» – 150 поколений;
размер автоматов в начальном поколении – четыре состояния.
Цель состояла в том, чтобы построить автомат, содержащий 14 переходов и соответствующий всем тестам (значение функции приспособленности, соответствующее такому автомату – 20.86). В результате работы алгоритма генетического программирования был построен автомат (Рис. 28.), в котором из начального (отмечено «жирной» рамкой) достижимы только три состояния из четырех. Если удалить недостижимое состояние, то этот граф переходов будет изоморфен построенному вручную.
|
Граф переходов автомата, построенного с помощью алгоритма генетического программирования
|
График зависимости максимального значения функции приспособленности от номера поколения приведен на Рис. 29..
|
Зависимость максимального значения функции приспособленности от номера поколения
|
Как видно из графика, автоматы, входящие в начальное поколение, проходят тесты примерно наполовину. Примерно к двухсотому поколению был построен автомат, полностью проходящий все тесты, однако содержащий достаточно большое число переходов. Далее шел процесс уменьшения числа переходов, в процессе которого три раза (в районе 400-го, 1000-го и 1200-го поколений) к популяции применялась операция «большой мутации», в результате которой значение функции приспособленности уменьшалось до примерно десяти. В результате в 1482-ом поколении был построен автомат, полностью проходящий все тесты и содержащий 14 переходов.
В процессе построения этого автомата функция приспособленности была вычислена 2674290 раз, а время работы алгоритма составило 530 секунд на компьютере с процессором Intel Core 2 Duo T7300.
|
