Генетический алгоритм применен для распознавания прописных букв русского алфавита.
Программа, реализующая алгоритм, является частью приложения, решающего задачи прогнозирования стоимости ценных бумаг. Приложение реализовано на языке FoxPro и основано на базе данных, описывающей предметную область.
Входные данные рассматриваемой задачи поделены на две части. Первая часть содержит эталонные представления букв, а вторая – те же буквы, но с искажениями. Вторая часть используется для тестирования и оценки эффективности программы.
Каждая буква задается в матрице 7*8, как последовательность нулей и единиц. В наборе входных данных матрица представляется в виде последовательности ее строк. В качестве разделителя между строками использован символ *. Так, прописная буква А задается следующей строкой:
0011000*0011000*0100100*0100100*1111110*1000010*1000010*1000010
Табличное (матричное) представление этой буквы приведено на рис. 1. В пустых ячейках таблицы находятся нули.
Рис. 1. Эталонное и искаженное представление буквы А
Такие буквы, как Ж, М или Ф, занимают все столбцы таблицы. На рис. 2 приведена буква Ж, представляемая в эталонном наборе исходных данных следующей строкой:
1101011*0101010*0101010*0011100*0011100*0101010*0101010*1101011
Рис. 2. Эталонное и искаженное представление буквы Ж
Задача состоит в том, чтобы, зная эталонные представления букв, распознать их искаженные представления.
Для ее решения использован генетический алгоритм.
Обе части входных данных (эталонные и тестовые) хранятся в таблице Lttrs.dbf с двумя следующими символьными полями:
Nm (2 символа);
Lttr (63 символа).
В первом поле указывается буква, а во втором – ее представление.
Сначала следуют эталонные буквы, а затем тестовые. Записи в каждой части отсортированы по алфавиту. Буквы в тестовой части таблицы в поле Nm снабжены окончанием в виде цифры 2. Фрагмент таблицы Lttrs (конец эталонной и начало тестовой частей) приведен на рис. 3.
Рис. 3. Таблица входных данных
И эталонная, и тестовые части таблицы имеют по 29 строк (отсутствуют буквы Ё, Й и Щ).
На вход программы распознавания подается номер nT строки тестовой части таблицы. Результатом работы программы является номер nM строки из эталонной части таблицы. Результат положителен, если nT – nM = 29. Так, если на вход подан номер nT = 31 строки, содержащей искаженное представление буквы Б, то правильным решением будет номер nM = 2 строки, содержащей эталонное представление буквы Б.
Используются идеи генетического алгоритма, содержащего операции скрещивания и мутации.
Популяция, описывающая букву, состоит из восьми двоичных чисел. Каждое число отвечает строке в табличном представлении буквы.
Так, популяция, описывающая искаженную букву Ж (nT = 36), состоит из следующих чисел:
1101011
0101010
0101010
0011100
0010100
0101010
0101010
0100011
Жирным шрифтом выделены числа, не совпадающие с соответствующими числами в эталонном представлении буквы.
Эту популяцию назовем исходной. Она описывается 8-ю хромосомами. Каждая хромосома имеет по 7 генов.
При распознавании берется эталонное представление некоторой буквы, скажем буквы А, и затем исходная популяция посредством операций скрещивания и мутаций преобразовывается в эталонную. При этом запоминается число операций, потраченных на описанное преобразование. В случае эталонной буквы А исходная популяция должна быть преобразована к следующему виду:
0011000
0011000
0100100
1000010
1111110
1000010
1000010
1000010
Далее берется иная эталонная буква, и вновь исходная популяция преобразовывается в эталонную. Число операций также запоминается.
Этот процесс повторяется с каждой эталонной буквой. Решением является эталонная буква, для получения которой потребовалось наименьшее число операций скрещивания и мутаций.
Интуитивно понятно, что число операций для преобразования искаженной буквы Ж в эталонную букву А должно быть существенно больше, чем число операций для преобразования искаженной буквы Ж в эталонную букву Ж.
Проблемы могут возникнуть с похожими буквами. К таким можно отнести буквы Э и З или буквы Ъ и Ь: даже незначительные искажения этих букв могут стать причиной неверного распознавания.
Популяцию, получаемую на каждом этапе преобразований, будем называть текущей.
Популяцию, отвечающую эталонной букве, будем называть эталонной.
Все популяции описываются 8-ю хромосомами. Положение каждой хромосомы задается номером – числом из диапазона от 1 до 8.
Каждая хромосома имеет по 7 генов. Положение каждого гена задается номером – числом диапазона от 0 до 6.
В операции скрещивания участвуют хромосомы с одинаковыми номерами из текущей и эталонной популяций. При этом в хромосому из текущей популяции переносятся несколько генов из хромосомы эталонной популяции. Номера заменяемых и переносимых генов совпадают. Хромосома эталонной популяции не меняется.
Операцию скрещивания иллюстрирует рис. 4.
Рис. 4. Перенос генов эталонной хромосомы в текущую
Число переносимых генов на каждом шаге одинаково, однако их номера выбираются случайным образом.
Операция мутации заключается в инвертировании значений нескольких случайно выбранных генов текущей хромосомы.
Близость текущей хромосомы к эталонной оценивается по числу, равному разности между десятичными представлениями текущей и эталонной хромосомами.
Пусть перед выполнением операции это число равно nB, а после выполнения эта разность равна nA.
Операция принимается, если nA <= nB.
В противном случае гены текущей хромосомы не меняются.
Кроме того, операции скрещивания и мутации не выполняются вовсе, если nB = 0. То есть если текущая и эталонная хромосомы совпадают.
Полностью алгоритм распознавания выглядит следующим образом:
Код состоит из головной программы и следующих процедур и функций.
* Получает номер rN строки таблицы Lttrs и формирует массив rrPpltn
* с числовым представлением буквы в строке rN таблицы Lttrs
* Возвращает символьное представление буквы в строке rN таблицы Lttrs
PROCEDURE rdPpltn(rN, rrPpltn, lttrWd, prn)
LOCAL k, k2, mLlttr, wrd
GO rN IN lttrs
mLlttr = lttrs.Lttr
FOR k = 1 TO 8
wrd = GETWORDNUM(mLlttr, k, "*")
lttrVl = 0
FOR k2 = 1 TO lttrWd
lttrVl = lttrVl + IIF(SUBSTR(wrd, k2, 1) = '1', 2^(lttrWd - k2), 0)
NEXT
rrPpltn[k] = lttrVl
NEXT
* Будут напечатаны промежуточные данные, если prn = .Т.
IF prn
lttrVl = ''
FOR k = 1 TO 8
lttrVl = lttrVl + ' ' + TRANSFORM(rrPpltn[k])
NEXT
? lttrVl
ENDIF
RETURN lttrs.Nm
ENDPROC
* Сравнивает две популяции и записывает расхождения в массив rrDst
FUNCTION cmprsn(rrPpltn, rrRslt, rrDst, prn)
LOCAL k, dstS, d
dstS = 0
FOR k = 1 TO 8
d = ABS(rrRslt[k] - rrPpltn[k])
rrDst[k] = d
dstS = dstS + d
NEXT
* Будут напечатаны промежуточные данные, если prn = .Т.
IF prn
rslt = ''
FOR k = 1 TO 8
rslt = rslt + ' ' + TRANSFORM(rrDst[k])
NEXT
? rslt
ENDIF
RETURN INT(dstS)
ENDFUNC
* vl2 - новое значение исследуемой хромосомы
* Результат принимается, если новое значение не хуже текущего
* Результат будет принят всегда, если lws = .T.
PROCEDURE ctn(lws, d, k, k2, vl, vl2, rrRslt, rrPpltnCrrnt, rrDst, dstS, prn)
d2 = ABS(rrRslt[k] - vl2)
* Будут напечатаны промежуточные данные, если prn = .Т.
IF prn
? k2, vl, vl2, d, d2, rrRslt[k]
ENDIF
IF d2 <= d OR lws
rrPpltnCrrnt[k] = vl2
rrDst[k] = d2
dstS = dstS - (d - d2)
ENDIF
ENDPROC
* Формирует следующую популяцию, выполняя операции скрещивания и мутации
PROCEDURE nxtPpltn(lws, nCV, nMt, rrRslt, rrDst, rrPpltnCrrnt, dstS, lttrWd, dCV, dMttn, prn)
LOCAL k, k2, k3, vl, vl2, d, d2
* Скрещивание будет выполняться, если dCV = .Т.
IF dCV
* Скрещивание
FOR k = 1 TO 8
d = rrDst[k]
IF d > 0
k2 = INT(ROUND((lttrWd - nCV - 1) * RAND( ), 0))
vl = rrRslt[k]
vl2 = rrPpltnCrrnt[k]
FOR k3 = k2 TO k2 + nCV - 1
vl2 = IIF(BITTEST(vl, k3), BITSET(vl2, k3), BITCLEAR(vl2, k3))
NEXT
ctn(lws, d, k, k2, vl, vl2, @rrRslt, @rrPpltnCrrnt, @rrDst, @dstS, prn)
ENDIF
NEXT
ENDIF
* Мутации будут выполняться, если dMttn = .Т.
IF dMttn
* Мутации
FOR k = 1 TO 8
d = rrDst[k]
IF d > 0
vl = rrPpltnCrrnt[k]
FOR k3 = 1 TO nMt
k2 = INT(ROUND((lttrWd - 1) * RAND( ), 0))
vl2 = IIF(BITTEST(vl, k2), BITCLEAR(vl, k2), BITSET(vl, k2))
NEXT
ctn(lws, d, k, k2, vl, vl2, @rrRslt, @rrPpltnCrrnt, @rrDst, @dstS, prn)
ENDIF
NEXT
ENDIF
ENDPROC
* Выводит в окно wnd изображение буквы, описанной в строке rN таблицы Lttrs
* Пример печати приведен на рис. 5
PROCEDURE shLttr(rN)
GO rN IN lttrs
mLlttr = lttrs.lttr
DEFINE WINDOW wnd AT 10,10 SIZE 10,8 FLOAT CLOSE TITLE "Letter";
IN DESKTOP SYSTEM
ACTIVATE WINDOW wnd
FOR k = 1 TO 8
wrd = GETWORDNUM(mLlttr, k, "*") + CHR(13) + CHR(10)
wrd = STRTRAN(wrd, "0", " ")
wrd = STRTRAN(wrd, "1", "*")
TEXT TO tLttr TEXTMERGE ADDITIVE NOSHOW
<<wrd>>
ENDTEXT
NEXT
? tLttr
ENDPROC
Рис. 5. Изображение буквы Э, полученное процедурой shLttr
* Выводит в файл d:1.txt результат работы программы
* Параметр lttrsLL – это число букв в эталонной части таблицы
* Массив rrFnd содержит lttrsLL элементов, каждый из которых равен
* либо символу '–', если число преобразований превысило пороговое значение nKMnS,
* либо числу итераций nkMn, потраченных на поиск решения,
* либо пробелу, если эталонная буква получена в результате преобразований, но число
* итераций больше nkMn
* Пример результата для всего тестового набора данных приведен на рис. 6
PROCEDURE prntRslt(lttrsLL, rrFnd, nRsltM, kRnd)
SET SAFETY OFF
SET ALTERNATE TO d:1.txt
SET ALTERNATE ON
SET CONSOLE OFF
fstLn = SPACE(16)
fstLn = ' R D L '
FOR k = 1 TO lttrsLL
GO k IN lttrs
fstLn = fstLn + lttrs.Nm + ' '
NEXT
? fstLn
FOR k = 1 TO lttrsLL
? rrFnd[k]
NEXT
? "Success = " + TRANSFORM(ROUND(100.0 * nRsltM / lttrsLL, 2));
+ "%; seed = " + TRANSFORM(kRnd)
SET ALTERNATE TO
MODIFY FILE d:1.txt
ENDPROC
Рис. 6. Пример результатов распознавания
В первом столбце находится плюс, если результат верен, и минус – в противном случае.
Во втором столбце выведено расстояние между искаженной и соответствующей ей эталонной буквами. Расстояние вычисляется функцией Cmprsn.
В третьем столбце указаны принятая в качестве решения эталонная буква и буква, поданная на вход для распознавания.
В нижней части рисунка напечатаны процент угаданных букв и использованная начальная затравка датчика случайных чисел.
Код основной программы:
IF NOT USED('lttrs')
USE lttrs IN 1
ENDIF
* Число генов в хромосоме
lttrWd = 7
* Число букв
lttrsLL = 29
nRslt = lttrsLL
DIMENSION rrPpltn(8), rrRslt(8), rrPpltnCrrnt(8), rrDst(8)
DIMENSION rrNk(lttrsLL), rrFnd(lttrsLL), rrKDst(lttrsLL), rrFndM(lttrsLL)
* Предельное число итераций для выбранной эталонной популяции
nKMnS = 50
* Размер части хромосомы, заменяемой при скрещивании (число заменяемых генов)
nCV = 2
* Число мутаций в одной операции
nMt = 1
dCV = .T.
dMttn = .T.
lws = .F.
kRnd = 20
* Берем поочередно все тестовые буквы
FOR rNpt = lttrsLL + 1 TO lttrsLL + lttrsLL
nKMn = nKMnS
kMn = 0
* Получаем числовые описания тестовой и ей соответствующей эталонной букв
* Массивы передаются по ссылке
* rrPpltn – массив хромосом исходной популяции
nptLttr = rdPpltn(rNpt, @rrPpltn, lttrWd, .F.)
* rrRslt – массив хромосом эталонной популяции, являющейся решением задачи
* для текущей буквы тестового табота
rdPpltn(rNpt - lttrsLL, @rrRslt, lttrWd, .F.)
* Вычисляем расстояние между тестовой и ей соответствующей эталонной популяциями
dstS0 = cmprsn(@rrPpltn, @rrRslt, @rrDst, .F.)
* Берем поочередно все эталонные буквы
FOR k = 1 TO lttrsLL
RAND(kRnd)
* Получаем числовое описание взятой эталонной буквы (эталонная популяция)
rdPpltn(k, @rrRslt, lttrWd, .F.)
* Формируем массив хромосом текущей популяции
FOR k2 = 1 TO 8
rrPpltnCrrnt[k2] = rrPpltn[k2]
NEXT
* Расстояние между текущей и взятой эталонной популяциями
dstS = cmprsn(@rrPpltnCrrnt, @rrRslt, @rrDst, rNpt = lttrsLL + 1 AND k = 0)
nK = 0
* Выполняем в соответствии с алгоритмом преобразования текущей популя-ции,
* приводя ее в выбранной эталонной популяции (букве)
DO WHILE .T.
nK = nK + 1
IF nK > nKMn OR dstS = 0
rrNk[k] = nK
IF nK < nKMn
nkMn = nK
kMn = k
ENDIF
EXIT
ELSE
nxtPpltn(lws, nCV, nMt, @rrRslt, @rrDst, @rrPpltnCrrnt,;
@dstS, lttrWd, dCV, dMttn, rNpt = lttrsLL + 1 AND k = 0)
ENDIF
ENDDO
NEXT
* Подготовка данных для вывода результата
IF kMn = 0
rrFnd(rNpt - lttrsLL) = nptLttr + " not FOUND(" + TRANSFORM(dstS) + ")"
nRslt = nRslt - 1
ELSE
GO kMn IN lttrs
tmp = RTRIM(lttrs.Nm) + " / " + nptLttr
FOR k = 1 TO lttrsLL
nK = rrNk[k]
IF nK < nKMnS + 1
nK = IIF(nK > nkMn, ' ', TRANSFORM(nK, '99'))
ELSE
nK = ' -'
ENDIF
rrNk[k] = nK
NEXT
IF kMn = rNpt - lttrsLL
prfx = " + "
ELSE
prfx = " - "
nRslt = nRslt - 1
ENDIF
rslt = prfx + TRANSFORM(dstS0, '99') + " (" + tmp + ")"
FOR k = 1 TO lttrsLL
rslt = rslt + ' ' + rrNk[k]
NEXT
rrFnd(rNpt - lttrsLL) = rslt
ENDIF
NEXT
* Печать результата
prntRslt(lttrsLL, @rrFnd, nRslt, kRnd)
Далее следуют использованные эталонные и тестовые данные.
A 0011000*0011000*0100100*1000010*1111110*1000010*1000010*1000010
Б 1111100*1000000*1000000*1111100*1000010*1000010*1000010*1111100
B 1111100*1000010*1000010*1111100*1000010*1000010*1000010*1111100
Г 1111100*1000010*1000000*1000000*1000000*1000000*1000000*1000000
Д 0011000*0100100*0100100*0100100*0100100*0100100*1111110*1000010
E 1111110*1000000*1000000*1111100*1000000*1000000*1000000*1111110
Ж 1101011*0101010*0101010*0011100*0011100*0101010*0101010*1101011
З 0111100*1000010*0000010*0011100*0000010*0000010*1000010*0111100
И 1000010*1000010*1000110*1001010*1010010*1100010*1000010*1000010
K 1000010*1000100*1001000*1010000*1110000*1001000*1000100*1000010
Л 0000110*0001010*0010010*0010010*0010010*0010010*0100010*1000010
M 1000001*1100011*1010101*1001001*1000001*1000001*1000001*1000001
H 1000010*1000010*1000010*1111110*1000010*1000010*1000010*1000010
O 0111100*1000010*1000010*1000010*1000010*1000010*1000010*0111100
П 1111110*1000010*1000010*1000010*1000010*1000010*1000010*1000010
P 1111100*1000010*1000010*1111100*1000000*1000000*1000000*1000000
C 0111100*1000010*1000000*1000000*1000000*1000000*1000010*0111100
T 1111100*0010000*0010000*0010000*0010000*0010000*0010000*0010000
У 1000010*1000010*1000010*0111110*0000010*0000010*1000010*0111100
Ф 0001000*0111110*1001001*1001001*0111110*0001000*0001000*0001000
X 1000001*0100010*0010100*0001000*0001000*0010100*0100010*1000001
Ч 1000010*1000010*1000010*0111110*0000010*0000010*0000010*0000010
Ш 1001001*1001001*1001001*1001001*1001001*1001001*1001001*1111111
Ъ 1100000*0100000*0100000*0111100*0100001*0100001*0100001*0111110
Ы 1000001*1000001*1000001*1111001*1000101*1000101*1000101*1111001
Ь 0100000*0100000*0100000*0111100*0100001*0100001*0100001*0111110
Э 0111100*1000010*0000010*0011110*0000010*0000010*1000010*0111100
Ю 1001110*1010001*1010001*1110001*1010001*1010001*1010001*1001110
Я 0111110*1000010*1000010*0111110*0001010*0010010*0100010*1000010
A2 0011000*0010000*0100100*1000010*1111110*1000010*1000010*1000001
Б2 1111110*1000000*1000000*1111100*1000010*1000010*1000010*1111100
B2 1111100*1000010*1000010*1111100*1000010*1000010*1000010*0111100
Г2 1111100*1000010*1000000*1000000*0000000*1000000*1000000*1000000
Д2 0011000*0100100*0100100*0100100*0100100*0100100*1110110*1000010
E2 1111110*1000000*1000000*1101100*1000000*1000000*1000000*1111110
Ж2 1101011*0101010*0101010*0011100*0010100*0101010*0101010*0100011
З2 0111100*1000010*0000010*0011100*0000010*0000010*1000010*0110100
И2 1000010*1000010*1000110*1000010*1010010*1100010*1000010*1000010
K2 1000001*1000100*1001000*1010000*1110000*1001000*1000100*1000010
Л2 0000110*0001010*0010010*0010010*0010010*0010010*0100010*1000000
M2 1000001*1100011*1010101*1001001*1000001*1000001*1000001*1000000
H2 1000010*1000010*1000010*1101110*1000010*1000010*1000010*1000010
O2 0110100*1000010*1000010*1000010*1000010*1000010*1000010*0111100
П2 1111110*1000010*1000010*1000010*1000010*1000010*1000010*1000000
P2 1101100*1000010*1000010*1111100*1000000*1000000*1000000*1000000
C2 0110100*1000010*1000000*1000000*1000000*1000000*1000010*0111100
T2 1111111*0010000*0010000*0010000*0010000*0010000*0010000*0010000
У2 1000010*1000010*1000010*0111010*0000010*0000010*1000010*0111100
Ф2 0001000*0111110*1001001*1001001*0110110*0001000*0001000*0001000
X2 1000001*0100010*0010100*0001000*0001000*0010100*0100010*1001001
Ч2 1000010*1000010*1000010*0111110*0000010*0000010*0000010*0000000
Ш2 1001001*1001001*1001001*1001001*1001001*1001001*1001001*1110111
Ъ2 1100000*0000000*0100000*0111100*0100001*0100001*0100001*0111110
Ы2 1000001*1000001*1000001*1111001*1000101*1000101*1000100*1111001
Ь2 0100000*0100000*0100000*0111100*0100001*0100001*0100001*0110110
Э2 0111110*1000010*0000010*0011110*0000010*0000010*1000010*0111100
Ю2 1001110*1010001*1010001*1110001*1010001*1010001*1010001*1001011
Я2 0111110*1000010*1000010*0111110*0001010*0010010*0100010*1000000
Приведенная программа содержит немногим более 100 строк. Это говорит о простоте технической стороны рассматриваемой задачи.
Сложнее добиться устойчивого распознавания. Так, в рассматриваемом примере результат сильно зависит от начальной затравки датчика случайных чисел. Кроме того, на результат влияют и число мутаций в одной операции, и размер части хромосомы, заменяемой при скрещивании, и, разумеется, величина искажений.
Заметим, что в данной задаче применение идей генетического алгоритма – это не самое удачное решение. Однако оно вполне отвечает целям учебного процесса.