Книги, научные публикации Pages: | 1 | 2 | 3 |

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) На правах рукописи УДК 50.10.41 САПУНОВ Григорий Владимирович СИСТЕМА АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ РЕЧЕВЫХ ...

-- [ Страница 2 ] --

9,00E-212 Приспособленность 8,00E-212 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 51 101 151 201 251 301 351 401 451 501 Поколение С мутацией Без мутации Рис.3.1. Сравнение методов генерирования начальной популяции Использование мутации во время генерирования начальной популяции особей оправдано в том случае, если разработчик намерен ограничиться небольшим числом поколений работы генетического алгоритма - в этом случае небольшой выигрыш в скорости имеет смысл. В целом, использование мутации при генерации начальной популяции - это полезный метод, и независимо от того, как много времени требует для работы оператор мутации (как правило это достаточно быстрый оператор), проводить её на этом этапе работы алгоритма имеет смысл, потому что в случае малого числа поколений это даст выигрыш в скорости, а в случае большого числа поколений дополнительные накладные расходы на проведение мутации исходной популяции будут незначительны в сравнении с работой всего алгоритма в целом. Кроме того, потенциально увеличение разнообразия популяции является плюсом, способным в отдельных случаях заметно ускорить работу алгоритма по нахождению более хороших решений. Следует заметить, что генетический алгоритм хорошо работает и в случае, когда начальная популяция сгенерирована целиком случайно, без опоры на результат работы какого-либо другого алгоритма. У данного метода тоже есть своё преимущество - существует возможность, что ввиду особенностей ландшафта решений при старте со случайной точки алгоритм придёт к более качественному решению, нежели начиная работать в окрестности одной фиксированной области. Исследования автора показали, что при таком старте алгоритм также сходится к достаточно хорошему решению, демонстрируя лишь некоторое запаздывание на начальных шагах работы в сравнении с двумя рассмотренными ранее методами генерации исходной популяции (рис. 3.2):

Приспособленность 9,00E-212 8,00E-212 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 41 81 121 161 201 241 281 321 361 Поколение Copy Mutation Random Рис.3.2 Случайный метод генерирования начальной популяции Под обозначением Copy на графике подразумевается метод с использованием результата работы предыдущего алгоритма (выходные результаты работы системы SdiApp), Mutation - результат работы предыдущего алгоритма (SdiApp) плюс мутация части особей и Random - случайное заполнение исходной популяции. Как видно из графика на рис.3.2, метод с заполнением исходной популяции случайными значениями также работает и приводит к тому же самому итоговому решению, к которому сходятся и первые два метода. Разница наблюдается лишь на начальных этапах работы алгоритма, где ему требуется дополнительное время для нахождения более хороших решений, из-за чего график приспособленности оказывается более пологим для этого случая.

Для пользователя разница будет заметна только в случае, когда выбрано малое число шагов работы алгоритма (рис. 3.3):

Приспособленность 9,00E-212 8,00E-212 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 11 21 31 41 51 61 71 81 91 Поколение Copy Mutation Random Рис.3.3. Разница на начальных этапах работы различных методов генерирования исходной популяции Подводя итог, можно сказать, что метод с заполнением исходной популяции решениями, сгенерированными каким-либо предыдущим алгоритмом (лCopy), удобен, когда требуется улучшить уже полученное решение. Хотя оно же порой может быть достигнуто и со случайной популяции, затраты на это могут быть весьма высоки, и разработчик алгоритма должен учесть это в целях повышения эффективности работы. Хорошим дополнением к предыдущему методу является мутация части исходных особей (лMutation), полученных из результатов работы другого алгоритма (например, алгоритма Баума-Велча). Такая мутация вносит некоторое разнообразие в популяции, что, как правило, положительно влияет на работу всего алгоритма в целом. И, наконец, метод со случайным заполнением исходной популяции (лRandom) показывает, что ГА может быть не привязан к начальным условиям и при этом всё равно способен найти хорошее решение. Метод очень хорош на этапе начального исследования или когда результаты работы других алгоритмов недоступны, а также в случае подозрения на то, что начальные решения группируются вокруг точки локального экстремума, и при необходимости более полно исследовать пространство решений, и поэтому будет использоваться, когда результаты работы предыдущего алгоритма недоступны, или при сомнениях в их оптимальности.

3.2.3 Размер популяции Для работы генетического алгоритма необходимо задать размер популяции или количество точек пространства поиска, которым будет оперировать алгоритм на каждом шаге процесса работы. При малом размере популяции в ней наблюдается низкое разнообразие, и она более подвержена застреванию в точках локальных экстремумов, поскольку всё небольшое количество особей быстро сходится к одной самой лучшей, наличествующей в популяции, после чего разнообразие генов пропадает, и кроссовер оказывается неспособен породить что-то новое. Если же в такой ситуации задана ещё и достаточно низкая вероятность мутации, то алгоритму может потребоваться очень большое время для выхода из сложившейся ситуации. Поэтому размер популяции не должен быть очень малым. С другой стороны, излишне большая популяция хотя и поддерживает высокий уровень разнообразия особей, требует на каждом шаге работы алгоритма большого времени на обработку. Поэтому целью определения размера популяции является соблюдение баланса между скоростью нахождения приемлемого решения, измеряемого числом необходимых для этого поколений эволюции, и скоростью работы самого алгоритма, выраженной в машинном времени. Это значение может быть определено экспериментально на основании серии тестов. Так, на речевой базе данных (РБД) кафедры ЭВА МИЭМ было оценено время сходимости алгоритма для отдельных слов в зависимости от размера популяции. Графики зависимости имеют следующий вид (рис. 3.4):

9,00E- 8,00E- 7,00E- 6,00E-212 Приспособленность 10 особей 5,00E-212 20 особей 50 особей 100 особей 4,00E-212 200 особей 500 особей 3,00E- 2,00E- 1,00E- 0,00E+00 1 48 95 142 189 236 283 330 377 424 471 518 565 612 659 706 753 800 847 894 941 988 Поколение Рис.3.4 Зависимость сходимости генетического алгоритма от размера популяции По горизонтальной оси графика отложено число поколений работы алгоритма, по вертикальной - значение фитнес-функции лучшего решения в популяции (равное вероятности генерации тестового слова моделью). Из эксперимента видно, что слишком малое выбранное значение размера популяции (10 особей) приводит к очень медленному движению алгоритма в сторону лучших решений, и кроме того на графике часто наблюдаются горизонтальные участки, которые свидетельствуют о застревании алгоритма в точках локальных экстремумов. При увеличении размера популяции алгоритм быстро набирает скорость и доходит до определённой точки, после которой дальнейшее увеличение популяции не оказывается особо эффективным, поскольку не даёт заметного улучшения работы. Так, популяция размером в 500 особей оказывается всего лишь незначительно эффективнее популяции размером 200 особей при том, что на её обработку требуется более чем в два раза больше времени. В итоге, по результатам этих экспериментов были сделаны выводы о том, что оптимальный размер популяции для данной задачи находится в районе 200 особей. Дальнейшее его увеличение не даёт заметного выигрыша.

3.2.4 Генетические операторы: оператор отбора Для осуществления скрещивания особей в основном цикле работы ГА требуется произвести отбор родителей для будущего поколения. На этом этапе работает оператор отбора, который руководствуется принципом выживает (или, точнее, даёт потомство) сильнейший. Поскольку генетические алгоритмы допускают высокую вариативность, здесь также возможны варианты. Стандартный путь - это использование пропорционального оператора отбора, когда вероятность отбора особи для последующего размножения Ps(i) прямо пропорциональна её приспособленности (значению целевой функции). Эта вероятность равна отношению приспособленности особи (fi) к суммарной приспособленности популяции: PS (i) = fi i = n. fi (4.1) Простейший оператор пропорционального отбора - рулетка (roulette-wheel selection), который отбирает особей с помощью n запусков. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью выбираются чаще, чем особи с низкой. Существуют и другие варианты реализации оператора отбора, например, турнирный отбор и элитные методы отбора [43], которые при необходимости могут быть легко встроены в генетический алгоритм без изменения остальных его частей. Оператор пропорционального отбора, использующийся в разработанной автором программе, обеспечивает экспоненциальное увеличение числа хороших схем в популяции и был рассмотрен в разделе 2.6, посвящённом теореме схем.

3.2.5 Генетические операторы: оператор скрещивания Оператор скрещивания призван обеспечить обмен генетической информацией между родителями, отобранными для размножения на предыдущем шаге алгоритма. Цель его - взять части генов от каждого из родителей (в идеале - лучшие части) и перенести их к потомку. Считается, что генетический алгоритм не вникает в сущность происходящего, то есть не знает, что именно скрывается за содержимым хромосом, а просто производит операции с ними. А потому он не может определить, какие части хромосом каждого из родителей лучше, чем у другого. Но он и не должен этим заниматься, потому что то, что кажется лучшим в краткосрочной перспективе, может вести в тупик в глобальном смысле, причём в тупик, не заметный явно, каким является, например, локальный экстремум, упорное восхождение на который может не позволить рассмотреть варианты, ведущие к другим более высоким пикам или же к глобальному экстремуму. Решение подобной задачи лежит на всём генетическом алгоритме в целом, и считается, что определение лучших особей должно произойти в результате действия эволюционного процесса целом. Впрочем, всё же нельзя исключать и возможности выполнения этой задачи (или хотя бы посильного участия в ней) оператором скрещивания, особенно при наличии некоей внешней для него информации. Такой подход более характерен для эволюционных стратегий. На данный момент наличие эвристик в задаче обучения СММ неизвестно, поэтому оператор скрещивания не будет пытаться интерпретировать хромосомы, а будет работать по принципу делай, что должно, и будь, что будет. Итак, оператор скрещивания производит обмен частей хромосом, не вникая в их содержимое. Как описывалось в главе 2, существуют различные варианты обмена генетической информацией: одноточечный кроссинговер, двухточечный, равномерный и другие. В нашей задаче допустимо применение любого из этих методов, при выполнении одного ограничения, обусловленного спецификой задачи, - строка матрицы должна рассматриваться как единое целое. То есть, точка разбиения не должна находиться внутри строки, а может лежать только на границе строк. Это условие возникает из рассмотренных ранее в главе 1 ограничений (1.2, 1.3) на строки матрицы вероятностей переходов, главное из которых то, что сумма элементов строки, то есть суммарная вероятность, должна быть равна единице. Иначе говоря, элементы внутри одной строки согласованы между собой и не связаны никакими другими жёсткими условиями с элементами остальных строк. Поэтому нет смысла формировать новые строки у потомков на основании различных по номеру строк родителей, хотя это и не запрещается при соблюдении условия (1.3). Ввиду сказанного возможно использование как одноточечного и двухточечного кроссинговера при расположении точки разбиения между строками матрицы (что не нарушает согласованности элементов одной строки), так и равномерного при условии оперирования строками как целыми и неделимыми элементами (то есть случайное число строк в потомке будет от одного родителя, а остальная часть - от другого, и данный метод в в итоге можно считать методом многоточечного кроссинговера). В разработанной автором программе реализованы три эти вышеперечисленных метода скрещивания, и было проведено их сравнение на РБД при следующих параметрах работы ГА:

Размер популяции: 100 Число поколений: 400 Вероятность мутации: 0,9 Вероятность мутации при создании исходной популяции: 0,9 Нормализация значений фитнес-функции: On Оператор (Random) Оператор мутации: однострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): 0 скрещивания: одноточечный (1-point), двухточечный (2-point), равномерный Результаты сравнения представлены на рис. 3.5.

9,00E-212 8,00E-212 Приспособленность 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 29 57 85 113 141 169 197 225 253 281 309 337 365 393 Поколение 1-point 2-point random Рис.3.5 Сравнение методов скрещивания Результаты работы методов оказываются достаточно близкими, и регулярных серьёзных расхождения в работе различных операторов скрещивания не наблюдается. В случае, если бы допускалось оперирование частями строк, можно было бы ожидать, что равномерный кроссинговер покажет худший результат в части случаев, когда строительные блоки хромосом будут достаточно малы, и значительная их часть будет разрушена во время этой операции. Но в силу введённого ограничения на работу с целыми строками этого не происходит, что способствует сохранению высокоприспособленных схем в популяции.

3.2.6 Генетические операторы: оператор мутации Оператор мутации должен поддерживать разнообразие в популяции, не позволяя ей заморозиться на каком-либо одном, пусть и достаточно хорошем решении, и, в идеале, не остановиться на локальных максимумах, а выйти на глобальный. Иными словами, он обеспечивает приток новой крови. И снова генетические алгоритмы демонстрируют высокую вариативность. Существует много возможных реализаций оператора мутации, но, поскольку для кодирования хромосомы были выбраны вещественные числа, остановимся лишь на тех, которые имеют смысл при таком варианте кодирования. Находясь в поле вещественных (действительных) чисел, оператору мутации оправдано оперировать самими числами (а не их представлением, как было бы в случае кодирования битовой строкой). Использование мутации подразумевает введение некоторого элемента случайности, и аналогия с природными процессами может быть создана копированием законов распределения, наиболее распространённых в природе [26]. Для реализации было выбрано нормальное распределение (Гаусса), хотя возможно использование и других вероятностных распределений, например, степенного (Парето) и других. Итак, при данных условиях, реализация оператора мутации может производить следующие действия: 1. Заменять произвольно выбранный элемент строки на случайную величину с заданным законом распределения. 2. Изменять произвольно выбранный элемент строки на случайную величину с заданным законом распределения, то есть прибавлять (или отнимать) к выбранному элементу случайное значение. Разница с предыдущим вариантом - в том, что здесь сохраняется некоторая преемственность, выражающаяся в зависимости нового значения элемента строки от его предыдущего значения. Важная особенность оператора мутации в отличие от других генетических операторов состоит в том, что его работа изменяет внутреннее содержание строки, поэтому во время его работы должны проверяться и при необходимости восстанавливаться условия, накладываемые на строку, главное из которых - условие полной вероятности (ф-ла 1.3). Мутации подвергаются элементы матрицы, стоящие на её главной диагонали или правее, поскольку из-за особенностей речевого сигнала запрещено переходить в состояния, предшествующие данному, и элементы слева от главной диагонали - нулевые. В случае, если программа работает с СММ с поступательно-ограниченными переходами, число доступных для мутации элементов справа от диагонали также ограничено, обычно двумя-тремя элементами. Практические эксперименты с использованием программного комплекса Иволга, разработанного автором, показали, что более хорошие модели не всегда являются строгими СММ с поступательно-ограниченными переходами, а относятся к более широкому классу моделей Бэйкиса, рассмотренных в разделе 1.4. Ввиду этого, мутация оперирует всеми элементами справа от главной диагонали матрицы переходов. Для того чтобы соблюсти требуемые условия, оператор мутации должен после внесения изменения в случайно выбранный элемент матрицы скорректировать значения остальных элементов строки, чтобы условие полной вероятности соблюдалось. Реализуется это вычитанием из остальных допустимых элементов значения, на которое изменился мутировавший элемент матрицы. Этот метод можно интерпретировать как одновременную мутацию сразу двух элементов строки, при котором их суммарное значение не изменяется и не влияет на суммарное значение всей строки, сохраняя соблюдение требуемых условий. Возможны и более сложные схемы согласования строки матрицы после мутации, например, равномерное распределение изменений мутировавшего элемента по всем остальным допустимым элементам в сторону как увеличения их значения, так и уменьшения. Для одноточечного оператора мутации с прибавлением случайной величины автором получена экспериментальная зависимость работы алгоритма от вероятности мутации (рис. 3.6):

9,00E- 8,00E- 7,00E- 6,00E-212 Приспособленность 0.1 0.2 0.3 0.4 0.5 0. 5,00E- 4,00E- 0.7 0.8 0. 3,00E- 0. 2,00E- 1,00E- 0,00E+00 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 155 162 169 176 183 190 197 Поколение Рис.3.6 Зависимость работы генетического алгоритма от вероятности мутации Из графика видно, что алгоритм быстрее достигает лучших значений при высоких значениях вероятности мутации. Данная ситуация, вообще говоря, не характерна для большинства реализаций ГА, поскольку в них выбираются низкие значения вероятности на уровне 0.1-0.3. В данном же случае очень эффективной является и вероятность 0.95. Это может свидетельствовать о том, что одноточечная мутация для моделей в данной задаче недостаточно эффективна, и может быть объяснено большим размером хромосомы (типичная СММ с 10 состояниями содержит 100 элементов, соответственно и хромосома содержит в себе 100 чисел с плавающей точкой), и в результате низкая вероятность мутации не оказывает желаемого влияния на работу алгоритма. То есть одноточечные (правильнее говорить однострочные, поскольку при мутации всё же затрагиваются соседние с мутируемым элементы, чтобы было соблюдено условие полной вероятности для строки) мутации должны происходить чаще. Во многих задачах изменение одного гена не позволяет выйти решению из локального оптимума [51]. Если принять во внимание, что в случае сходимости популяции в локальном оптимуме, мутация остаётся единственным механизмом, способным вывести популяцию из него, то проблема становится весьма ощутимой. Альтернативой этому варианту является использование операторов мутации, затрагивающих несколько элементов или несколько строк сразу.

Модифицированный многострочный оператор мутации работает несколько иначе. В случае его использования вероятность мутации трактуется как вероятность мутации каждой из строк матрицы, а не единичной произвольно выбранной строки. В этом случае мутация может затронуть сразу несколько строк матрицы. На рис. 3.7 представлены результаты сравнения работы однострочного (Simple) и многострочного (Complex) операторов мутации с соответствующими им вероятностями мутации:

9,00E-212 8,00E-212 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 54 107 160 213 266 319 372 Поколение Complex 0.9 Complex 0.5 Complex 0.3 Complex 0.1 Complex 0.03 Simple 0.2 Simple 0.5 Simple 0. Приспособленность Рис.3.7 Сравнение однострочного и многострочного операторов мутации Из графика видно, что эффективность работы однострочного оператора мутации при высокой вероятности самой мутации сравнима с эффективностью работы многострочного оператора мутации при традиционно низких вероятностях мутации, что подтверждает выдвинутое ранее предположение. Кроме того, высокие значения вероятности в сочетании с многострочным оператором мутации, наоборот, сильно снижают эффективность работы алгоритма, что в соответствии с Теоремой схем выражается в разрушении строительных блоков хромосом и уничтожении хороших особей в популяции. В итоге, для работы автором выбран многострочный оператор мутации с низкими значениями вероятности мутации.

3.2.7 Генетические операторы: оператор редукции Оператор редукции поддерживает постоянный размер популяции, не давая ей неограниченно увеличиваться, в простейшем случае просто приводя её к фиксированному размеру в конце каждого шага основного цикла ГА. Фактически это сводится к тому, что время жизни каждой хромосомы (индивида в популяции) становится ограниченным (особенно в отсутствии элитизма, при использовании которого есть теоретическая возможность для особи быть вечной - эта возможность для неё реализуется в том случае, если особь с момента своего появления и на каждом последующем шаге алгоритма оказывается в числе лэлиты - лучших особей популяции, которые без изменений переходят в следующее поколение). На практике работа оператора редукции сводится к уничтожению в популяции худших её особей. Эта процедура проводится для расширенной популяции, то есть той популяции, что получается после добавления вновь получившихся после скрещивания и мутации особей к исходной. Возможно расширение генетического алгоритма введением времени жизни каждой особи и наложением определённых ограничений на работу оператора редукции по этому параметру. Например, может быть запрещено удаление из популяции совсем молодых особей, в особенности только что созданных на этом шаге. Вероятно, этот метод более эффективен в сочетании с плавающим размером популяции, когда допустимо временное превышение её размера. Адаптивный вариант ГА, способный изменять свои параметры во время работы алгоритма, будет рассмотрен далее в главе 4. В чём-то работа оператора редукции сродни работе оператора отбора, но есть и определённые отличия. Рассмотренный оператор редукции работает строго детерминированно: определяет худших особей по значению их целевой функции и удаляет их из результирующей популяции, переходящей на следующий шаг ГА.

Работа же оператора отбора вероятностна. С его точки зрения лучшие особи отличаются от худших тем, что у них больше шансов быть отобранными. Но шансы быть отобранными ненулевые и у худших особей. В этом принципиальная разница между операторами отбора и редукции. Если бы оператор редукции работал аналогичным оператору отбора образом, то он мог бы порой удалять и самых лучших особей популяции, пусть и редко. Подобная ошибка стоит значительно дороже ошибки оператора отбора, когда к размножению допускается далеко не лучшая особь, так как такая ошибка при редукции приводит к ухудшению популяции, а ошибка при отборе к этому не ведёт. Это ошибки разного рода. Более того, описанный вариант развития событий при отборе может и не считаться ошибкой, потому что способен создать новую очень хорошую особь на основе не лучших, но зато содержащих в своём генотипе очень хорошие участки, особей. В худшем случае он лишь замедляет достижение алгоритмом оптимального результата. В итоге, работа оператора редукции в разработанном автором программном комплексе Иволга заключается в уничтожении худших особей.

3.2.8 Критерий останова алгоритма Критерий останова ГА - это условие, при выполнении которого прекращается дальнейшее выполнение основного цикла ГА, выбирается лучшая особь (или лучшие особи) из результирующей популяции, и они и считаются результатами работы ГА. Их хромосомы декодируются, и эти полученные в результате работы алгоритма параметры могут использоваться в задаче, для которой они и предусматривались. Алгоритм может прекратить свою работу по достижению одного из следующих условий: 1. Отработано заданное пользователем количество поколений (или произведено заранее заданное число вычислений целевой функции). Заранее сказать, сколько поколений обычно достаточно для достижения сколько-нибудь приемлемого результата, нельзя. Это число зависит от самой задачи и от многих других факторов, например, от выбранных параметров самого ГА или от начальной популяции. Поэтому пользоваться данным критерием имеет смысл, когда уже есть представление о способностях алгоритма по решению данной конкретной задачи и о влиянии каждого из параметров алгоритма на его работу. Иначе говоря, этот критерий лучше использовать, уже обладая практическими данными о результатах его работы, когда алгоритм оттестирован, параметры изучены и есть статистика, позволяющая принимать решения. 2. Алгоритм отработал фиксированное условии работы время. Данный на метод эквивалентен предыдущему при программы системах одинаковой производительности и с одинаковой загрузкой, но при возможности работы на произвольном и заранее неизвестном парке систем различной производительности разумно использовать в качестве инварианта время работы алгоритма, а не число его поколений. Такой критерий останова оправдан, когда требуется предоставить пользователю сходные условия работы с программой на аппаратной базе с различающейся производительностью. Также метод может оказаться применимым при отсутствии пользователя, но при наличии необходимости поддерживать синхронизацию со сторонними процессами, например при распределённой работе или при работе с различных телекоммуникационных системах и сетях. Так, для сравнения, время работы алгоритма со следующими параметрами:

Размер популяции: 100 Число поколений: 400 Вероятность мутации: 0,2 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: многострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): на машине Pentium-III 500МГц составило 14 минут. 3. Достигнуто заданное пользователем значение целевой функции. Если разработчик заранее знает, какого результата (значения целевой функции) он хочет достичь, имеет смысл воспользоваться именно этим критерием. Это позволит сэкономить время работы по сравнению с предыдущим вариантом, если требуемое решение достигается достаточно быстро или же не требуется результат, превышающий определённое значение. Используя этот критерий, надо быть уверенным, что требуемый результат достижим, иначе алгоритм окажется в ситуации погони за недостижимым в принципе (или на практике при данных условиях) идеалом, поэтому всегда полезно иметь и другой дублирующий критерий, способный определить застопоривание работы алгоритма. Применительно к задаче оптимизации параметров СММ, где целевой функцией является вероятность генерации слова моделью, заранее сказать, какое численное значение вероятности должно быть достигнуто, проблематично, тем более, что от слова к слову оно может заметно различаться, поэтому использование этого критерия останова ГА не кажется осмысленным. Помимо прочего, значение целевой функции сильно зависит от настроек системы распознавания, в первую очередь от размера фреймов, на которые разбивается поступающий с микрофона речевой сигнал. При увеличении длины фрейма уменьшается длина последовательности наблюдений за счёт того, что сигнал той же длины покрывается меньшим числом фреймов. А уменьшение длины последовательности наблюдений приводит к уменьшению числа множителей при подсчёте вероятности генерации последовательности, что выражается в увеличении итогового значения целевой функции. Поэтому с данным критерием останова следует быть особенно внимательным. Вариантом этого критерия может быть задание численного значения вероятности, равного улучшенному на определённый процент исходному её значению для данного слова, скажем, 30%. Но при этом надо быть уверенным в том, что все слова и модели, для которых проводится оптимизация, записаны в близких условиях и имеют примерно одинаковое качество. Иначе может получиться, что для одной из моделей невозможно улучшение более чем на 10%, в то время как другие допускают улучшение на сотни процентов. В этом случае была бы полезной система оценки качества моделей, их потенциала оптимизации и адекватности. Кроме того, этот процент улучшения требует сбора большой статистики для определения того, какой запас есть у используемых моделей и какой разумный порог может быть установлен, поэтому есть смысл пользоваться этим критерием лишь при удовлетворении вышеперечисленным условиям. Эксперименты автора показали, что для моделей, начальная популяция для которых была сгенерирована случайным образом, увеличение вероятности генерации происходит на несколько десятичных порядков, в то время как уже обученные по алгоритму Баума-Велча модели, как правило, могут быть улучшены не более чем на десятки процентов. 4. Близким к предыдущему вариантом является останов алгоритма по достижении всеми особями популяции некоторого заданного порога. Ограничения у этого метода практически те же самые - в случае рассматриваемой задачи смысла в использовании этого критерия нет, поскольку результатом работы алгоритма является одна, лучшая, особь, а не вся результирующая популяция. 5. Достигнута определённая сходимость алгоритма, то есть особи по значению фитнес-функции стали близки между собой, и улучшение популяции идёт незначительными темпами или вообще не идёт, а результат колеблется в области одного значения. Этот критерий очень хорош на этапе исследования, поскольку позволяет остановиться тогда, когда ничего интересного в популяции уже не происходит, скрещивание даёт только близкие результаты, а мутации ни к чему лучшему уже не приводят. В этих случаях возможно использование встряски популяции - проведение широкомасштабной мутации большой её части. Это может быть реализовано применением оператора мутации с вероятностью большей, чем у основного оператора мутации в главном цикле, или, например, вбрасыванием в популяцию популяции. Использование данного критерия в серии запусков даёт разработчику возможность оценить потенциал улучшения модели генетическим алгоритмом и в дальнейшем установить фиксированные значения в один из предыдущих критериев, если в этом есть необходимость. В итоге, предлагается следующий подход к выбору критерия останова ГА: на этапе исследования моделей критерием является заданная сходимость алгоритма, когда же проведено достаточное количество испытаний, система может быть перенастроена на использование в качестве критерия фиксированного числа поколений генетического алгоритма. Так, для выбранного размера популяции (см. рис. 3.2) и других заданных параметров ГА типичный график сходимости решения, полученный автором на РБД, имеет вид (рис. 3.8): некоторого количества случайных или каким-то образом подготовленных особей, как это рассматривалось в разделе про создание исходной 9,00E-212 8,00E-212 Приспособленность 7,00E-212 6,00E-212 5,00E-212 4,00E-212 3,00E-212 2,00E-212 1,00E-212 0,00E+00 1 121 241 361 481 601 721 841 961 Поколение Рис.3.8. Значение целевой функции в зависимости от числа поколений Из графика видно, что за 250-300 поколений достигается значение целевой функции, дальнейшее улучшение которого идёт крайне незначительно и варьируется в лучшем случае в пределах единиц процентов от этого значения. Поэтому становится оправданным использование в качестве критерия останова фиксированного значения числа поколений работы генетического алгоритма в районе 250-300.

3.3 Выводы В главе предложена конкретная реализация генетического алгоритма для решения поставленной задачи оптимизации процесса обучения непрерывных СММ тренировочными последовательностями. Выбран метод кодирования информации в хромосомах вещественными числами как наиболее эффективный в поставленных условиях по сравнению с битовыми и символьными строками. Предложен вариант создания исходной популяции для работы генетического алгоритма, основанный на результатах работы алгоритма оценки стартовых параметров СММ, с дополнением популяции мутированными и случайными особями, поскольку это повышает эффективность работы алгоритма. Алгоритм также способен эффективно работать со случайно сгенерированной популяцией. Экспериментально определён размер популяции, наиболее разумный с точки зрения баланса между скоростью нахождения алгоритмом приемлемого решения и скоростью работы самого алгоритма. Оптимальный размер популяции составил 200 особей. Рассмотрены различные варианты реализации генетических операторов и выбраны параметры их работы, основываясь на тестах, проведённых с использованием речевой базы данных (РБД), а именно: 1. Выбран пропорциональный оператор отбора, эффективность которого доказана теоремой схем;

2. Рассмотрены и реализованы одноточечный, двухточечный и равномерный кроссинговеры с учётом ограничений на значения элементов матрицы вероятностей переходов. Эксперименты автора показали, что в данных условиях эффективность всех трёх операторов близка друг к другу и серьёзных различий в их работе не наблюдается;

3. Выбран вариант оператора мутации, оперирующий сразу несколькими строками матрицы вероятностей переходов СММ (т.н. многострочный оператор мутации), учитывающий ограничения на значения элементов матрицы и соблюдающий условие полной вероятности для строк матрицы;

4. Выбран оператор редукции и рассмотрены особенности его работы в сравнении с другими генетическими операторами, показана разница с цене ошибки работы для внешне похожих операторов редукции и отбора. Предложены усовершенствования алгоритма, связанные с введением времени жизни особи. Все выбранные операторы ГА были реализованы в разработанном автором программном комплексе Иволга, используемом на кафедре ЭВА МИЭМ для работ в области распознавания речи. Рассмотрены различные критерии останова работы генетического алгоритма, проанализированы их сильные и слабые стороны и определены условия, в которых использование каждого из критериев наиболее оправдано и эффективно. В качестве основного выбран критерий останова по достижению определённой сходимости алгоритма, когда значения хорошая фитнес-функции каждого последующего алгоритма, поколения незначительно отличаются друг от друга. Отмечена вариативность генетического допускающая различные варианты реализации его составных частей и выбор среди них наиболее эффективных в рамках данной задачи. Такая модульность является шагом на пути к созданию адаптивного генетического алгоритма.

Глава 4. Исследование эффективности оптимизации СММ с использованием генетических алгоритмов 4.1 Сравнение генетических алгоритмов с традиционными методами В данной главе производится исследование способности ГА решать поставленную задачу обучения СММ. Ориентиром при оценке является традиционный метод обучения СММ - метод Баума-Велча. Отобраны примеры, наглядно иллюстрирующие наиболее важные моменты в работе ГА. Тестирование проводилось на речевой базе данных (РБД) кафедры ЭВА МИЭМ, использовались словари: Русский фонетический алфавит (36 слов), Связь и коммуникации (46 слов), Графический (19 слов), Управление в коммуникации (15 слов), Числовой (21 слово), Новый (24 слова), Латинский фонетический алфавит (26 слов) и Stv (18 английских слов), а также отдельные слова из других словарей и слова, поступающие в систему распознавания непосредственно с микрофона, подключенного к компьютеру.

4.1.1 Метод Баума-Велча При сравнении использовалась реализация метода Баума-Велча из библиотеки Intel Recognition Primitives Library. Это хорошо оптимизированная по скорости работы библиотека, созданная специалистами компании Intel, которая предоставляет разработчику набор функций, часто используемых при разработке приложений распознавания речи или зрительных образов. В цифрах, однократный запуск генетического алгоритма с числом поколений равным 300, и количеством особей в популяции равным 200, (эти значения по результатам множества тестов признаны оптимальными для данной задачи) для слов одного словаря (Числовой), в сравнении с результатами обучения моделей для слов этого же словаря методом Баума-Велча, показывает результаты от -15% (на 15% худший результат) до +70% (на 70% лучший). Повторые запуски ГА способны найти ещё более хорошие решения (то есть, более качественно обученные модели слов). Так, уже троекратный запуск ГА для каждого слова из словаря и последующий выбор решения с наибольшим значением фитнес-функции для этого же словаря дал разброс значений от -7% до +72%.

Далее рассматриваются наиболее показательные примеры, наглядно демонстрирующие особенности функционирования ГА. Пример 1. Результат работы ГА лучше, чем результат метода Баума-Велча: В качестве тестовых слов для данного примера из РБД (словарь Гласные в предударном слоге (кроме 1-го слога) (у)) были выбраны варианты слова гуманист, произнесённые тремя разными дикторами. 1) Стартовые параметры СММ (матрица вероятностей переходов), полученные с помощью программы SdiApp:

0,97777778 0,01111111 0,01111111 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97727275 0,01136364 0,01136364 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97727275 0,01136364 0,01136364 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97727275 0,01136364 0,01136364 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97727275 0,01123596 0,01149132 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97727275 0,01162190 0,01110537 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97777778 0,01085859 0,01136364 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97674417 0,01189218 0,01136364 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97777778 0,02222222 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации этой моделью тестового слова составляет: F=1.726821E-532 2) Модель, обученная по алгоритму Баума-Велча:

0,95559531 0,04440471 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94398779 0,05601219 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95634621 0,04365379 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95669693 0,04330305 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94818640 0,05181359 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95486939 0,03008745 0,01504317 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95703518 0,04296482 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97034067 0,02965935 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97827351 0,02172647 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Для обученной модели вероятность генерации тестового слова составляет: F=1.481299E-529 Видно, что вероятность генерации слова стала значительно выше, а сама модель стала более строгой, допускающей практически во всех состояниях только переход в следующее состояние модели. 3) Модель, обученная с помощью генетического алгоритма:

Параметры ГА: Обрабатываемая HMM: humanist Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,5 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: однострочный Исходная популяция (Число мутированных особей): 0 Исходная популяция (Число случайных особей): В данном случае исходная популяция решений была сформирована случайным образом, не опираясь на результаты работы какого-либо алгоритма. Результирующая модель выглядит следующим образом:

0,94052202 0,05947788 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,97217846 0,02782157 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91180485 0,08819514 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,88275850 0,11724144 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93922961 0,06077039 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,90030348 0,09969651 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94970661 0,05029343 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96292341 0,03707662 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93350101 0,06649913 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, И вероятность генерации тестового слова составляет: F=1,928618E-529 Столь малые порядки величины вероятности генерации наблюдаемой последовательности возникают в силу того, что последовательность наблюдений имеет большую длину - нередки последовательности длиной 100-150 наблюдений, особенно в случае длинного слова, при малом размере фрейма и когда фреймы перекрываются друг с другом - все эти параметры задаются в настройках системы предобработки речевого сигнала. Как видно, в данном случае найденное решение на 20% лучше решения, к которому пришёл алгоритм Баума-Велча. Особенно интересно то, что генетический алгоритм стартовал с совершенно случайной точки и сумел обнаружить хорошее решение, в то время как для метода Баума-Велча является важным выбор стартовых параметров - та самая задача, для решения которой и предназначена программа SdiApp. При этом матрица решения стала очень строгой - каждое состояние допускает переход только в следующее состояние, а переходы ограничены ещё сильнее, чем в случае решения, найденного методом Баума-Велча. Более строгая матрица лучше описывает конкретный экземпляр слова, но хуже учитывает возможную вариативность в его произнесении. Такой результат хорош, когда нужно обеспечить работу системы распознавания с одним диктором, психо-физиологическое состояние которого в процессе работы с системой изменяется незначительно. Пример 2. Результат работы ГА заметно лучше, чем результат метода Баума-Велча: Ещё один запуск ГА для той же модели и тех же тестовых слов, что и в примере 1, но с изменёнными параметрами ГА: увеличено значение вероятности оператора мутации:

0,95874655 0,04031101 0,00000000 0,00090645 0,00000000 0,00003412 0,00000000 0,00000184 0,00000000 0,00000000 0,00000000 0,96958530 0,03026573 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00014896 0,00000000 0,00000000 0,00000000 0,95942461 0,04057539 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95637083 0,04362921 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93707424 0,06292575 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94376397 0,05623607 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96832579 0,03167425 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95078510 0,04921488 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96292055 0,03707949 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=2,491582E-529 В данном случае найдена матрица переходов СММ, дающая вероятность генерации тестового слова ещё более высокую (на 68% выше, чем у метода Баума-Велча), чем в предыдущих примерах. Надо заметить, что в данном случае матрица решения наоборот менее строга, чем в предыдущих случаях - некоторые состояния допускают переходыскачки в другие состояния, порой далеко отстоящие от исходного. Это может иметь место при работе со словами, записанными разными дикторами (что и наблюдается в данном примере), где часть звуков у одного из дикторов может оказаться пропущена или, как говорят, проглочена, или при наличии особенностей произнесения диктором отдельных фонем. Таким образом, данный вариант найденного решения хорош, когда система распознавания речи является многодикторной системой или когда можно ожидать изменения психо-физиологического состояния оператора в процессе работы с ней. Методу Баума-Велча трудно найти подобные решения, в то время как генетический алгоритм способен на это при определённых значениях параметров. В данном случае увеличение вероятности мутации привело к такому результату, что более хорошее решение было найдено. Пример 3. Результат одиночного запуска ГА хуже, чем результат работы метода Баума-Велча: В качестве тестовых слов для данного примера из РБД (словарь Связь и коммуникации) были выбраны варианты слова линформация, произнесённые двумя дикторами. 1) Стартовые параметры СММ, полученные с помощью программы SdiApp:

0,98484850 0,00751703 0,00763448 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98437500 0,00787306 0,00775194 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98461539 0,00769231 0,00769231 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98437500 0,00775194 0,00787306 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98437500 0,00781250 0,00781250 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98461539 0,00775194 0,00763268 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98461539 0,00763268 0,00775194 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98437500 0,00793457 0,00769043 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98461539 0,01538462 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=3.796501E-578 2) Модель, обученная по алгоритму Баума-Велча:

0,95465481 0,04534521 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0, 0,00000000 0,95313603 0,04686400 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95600164 0,04399837 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95087475 0,04912523 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95360994 0,04639006 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95309550 0,04690449 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95418280 0,04581719 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95325869 0,04674128 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95366406 0,04633596 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=7.385101E-574 3) Модель, обученная с помощью генетического алгоритма:

Параметры ГА: Обрабатываемая HMM: humanist Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,8 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: однострочный Исходная популяция (Число мутированных особей): 0 Исходная популяция (Число случайных особей): 0,97168839 0,02829902 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00001252 0,00000000 0,00000000 0,95831221 0,04168778 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94622624 0,05377370 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96296942 0,03703059 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93797940 0,06202062 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96205044 0,03794955 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94965202 0,05034798 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94338018 0,05661981 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95319307 0,04680698 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=6.003291E-574 Повторный запуск ГА с теми же параметрами:

0,95334357 0,04665637 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94416010 0,05583986 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94751960 0,05248038 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94471288 0,05528712 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94620299 0,05379696 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95557588 0,04442408 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95639884 0,04360124 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96260571 0,03739430 0, 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94602019 0,05397980 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=6.408732E-574 Как видно, в данном случае ГА нашёл решение, несколько худшее (на 15%), нежели метод Баума-Велча, хотя и сравнимое с ним. Это свидетельствует о вероятностном характере работы алгоритма, и порой надо совершить серию запусков, чтобы по результатам выбрать среди них лучшее решение. Данный метод с использованием ГА для оптимизации СММ может быть воплощён в жизнь при создании системы распознавания, способной во время простоя основной части системы перебирать с помощью генетического алгоритма варианты СММ в поисках более хороших моделей. Поскольку в этом случае время работы ГА не столь важно, может быть произведена серия запусков, и затем среди их результатов будет отобран лучший из них. По итогам исследования нужно сделать важное замечание - генетические алгоритмы и метод Баума-Велча не противостоят друг другу и не являются взаимоисключающими. Хотя они и предназначены для решения одной задачи, они могут действовать в её решении согласованно. Так, исходной точкой для работы ГА могут быть значения, полученные с помощью метода Баума-Велча, и тогда ГА будет работать в направлении улучшения имеющегося решения. Или же наоборот, методом Баума-Велча может быть улучшено решение, полученное генетическим алгоритмом, особенно, когда число шагов его работы было заметно ограничено. Два следующих примера наглядно подтверждают возможность согласованной работы ГА и метода Баума-Велча. Пример 4. Используется метод Баума-Велча для улучшения модели, обученной ГА: В качестве тестовых слов для данного примера из РБД (словарь Русский фонетический алфавит) были выбраны варианты слова Борис, произнесённые тремя разными дикторами. 1) Стартовые параметры СММ (матрица вероятностей переходов), полученные с помощью программы SdiApp:

0,98113209 0,00934237 0,00952555 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0, 0,00000000 0,98039216 0,00980392 0,00980392 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98076922 0,00970874 0,00952203 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98076922 0,00961538 0,00961538 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98039216 0,00961538 0,00999246 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98039216 0,00999246 0,00961538 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98113209 0,00934237 0,00952555 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98039216 0,00999616 0,00961169 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98076922 0,01923077 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации этой моделью тестового слова составляет: F= 6,882720E-578 2) Модель, обученная ГА Параметры ГА: Обрабатываемая HMM: boris(2453) Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,3 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: многострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): 0,91680098 0,08319901 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91277629 0,08722372 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91770154 0,08229847 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92673600 0,07326398 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,90279222 0,09720786 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91462642 0,08537359 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91149938 0,08850066 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91731179 0,08268818 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,91630411 0,08369587 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Для обученной модели вероятность генерации тестового слова составляет: F= 2.062270E-316 3) Далее эта же модель дообучается с помощью метода Баума-Велча: Результирующая матрица выглядит следующим образом:

0,95299762 0,04700240 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92367470 0,07632531 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94081390 0,05918608 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94465566 0,05534436 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94123155 0,05876847 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93930799 0,06069203 0,00000000 0,00000000 0, 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94516885 0,05483115 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94144899 0,05855099 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94276303 0,05723699 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, И вероятность генерации тестового слова составляет: F=2.146812E-316 Как видно из этого примера, метод Баума-Велча не сильно (примерно на 5%), но всё же смог улучшить найденное генетическим алгоритмом решение. Подобный подход часто используется при поиске оптимальных решений: на первом этапе ГА определяет наиболее кластеров. Пример 5. ГА используется для улучшения модели, обученной методом Баума-Велча: В качестве тестовых слов для данного примера из РБД (словарь Числовой) были выбраны варианты слова восемнадцать, произнесённые тремя разными дикторами. 1) Стартовые параметры СММ, полученные с помощью программы SdiApp:

0,98684210 0,00653538 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00671082 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00657895 0,00657895 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00666667 0,00666667 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00662252 0,00671082 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00671082 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00653538 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00680089 0,00653244 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,01315789 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, интересные области в пространстве решений, а на втором этапе специализированный алгоритм находит лучшее решение в каждом из получившихся Вероятность генерации тестового слова: F=5,269427E-572 2) Модель, обученная по алгоритму Баума-Велча:

0,95749456 0,04250544 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96217304 0,03782693 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96409637 0,03590362 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95970535 0,04029462 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95414972 0,04585027 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95203704 0,04796297 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96778935 0,03221066 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95979440 0,04020561 0, 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96275073 0,03724928 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=3.337348E-567 3) Модель, обученная с помощью генетического алгоритма:

Параметры ГА: Обрабатываемая HMM: 18 (1334) Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,3 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: многострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): 0,94153488 0,05846512 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96217304 0,03782693 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95286930 0,04713069 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95970535 0,04029462 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95766723 0,04233278 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94986355 0,05013643 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96671927 0,03328073 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94106972 0,05893026 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96365827 0,03634175 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=3.582001E-567 В данном примере ситуация обратная - ГА улучшает решение, найдённое методом Баума-Велча (улучшение составляет порядка 7%).

4.1.2 Случайный поиск Случайный поиск не используется при обучении СММ в системах распознавания речи в силу своей неэффективности, но в демонстрационных целях можно произвести исследование эффективности этого метода. В чистом виде последовательный случайный перебор заведомо бесполезен, что было показано в разделе 2.2.2, но можно сэмулировать один из вариантов случайного поиска с помощью ГА. Это реализуется посредством усиления случайной составляющей ГА (радикальное повышение вероятности мутации) и отключением детерминированности ГА (в первую очередь отключив отбор более приспособленных особей и их скрещивание). В результате получается алгоритм случайного поиска, работающий параллельно сразу с группой решений (как и ГА) и запоминающий лучшие обнаруженные решения благодаря сохранённому оператору редукции, но не использующий их как базу для создания новых решений. В качестве тестовых слов для данного примера были выбраны слудеющие слова: словарь Числовой, варианты слова четырнадцать, произнесённые тремя разными дикторами. 1) Стартовые параметры СММ, полученные с помощью программы SdiApp:

0,98684210 0,00653538 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00671082 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00657895 0,00657895 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00666667 0,00666667 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00662252 0,00671082 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00671082 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00653538 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00680089 0,00653244 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,01315789 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F= 2.240326E-663 2) Модель, найденная описанным методом случайного поиска:

Параметры случайного поиска: Обрабатываемая HMM: 14 Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,95 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: отсутствует Оператор мутации: многострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): 0,98684210 0,00653538 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00671082 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00657895 0,00657895 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00666667 0,00666667 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00662252 0,00671082 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,89519161 0,09818589 0,00662252 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,00653538 0,00662252 0, 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98666668 0,00680089 0,00653244 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,98684210 0,01315789 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F= 4,172212E-663 3) Модель, обученная с помощью генетического алгоритма:

Параметры ГА: Обрабатываемая HMM: 18 (1334) Размер популяции: 200 Число поколений: 300 Вероятность мутации: 0,3 Вероятность мутации при создании исходной популяции: 0,8 Нормализация значений фитнес-функции: On Оператор скрещивания: двухточечный Оператор мутации: многострочный Исходная популяция (Число мутированных особей): 100 Исходная популяция (Число случайных особей): 0,94126195 0,05873805 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95590889 0,04409109 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96143496 0,03856502 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95138687 0,04861314 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95757866 0,04242136 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94794405 0,05205593 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95955491 0,04044511 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,94529301 0,05470697 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,95734340 0,04265657 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Вероятность генерации тестового слова: F=1,939520E-567 Как показывает данный пример, случайный поиск способен найти более хорошее решение, но эффективность его работы крайне низка. При таком же количестве просмотренных точек пространства поиска ГА гораздо быстрее находит значительно более хорошие решения, чем случайный поиск. Данные методы поиска имеют общую структуру и отличаются лишь одной деталью - наличием механизма отбора хороших решений. То есть, экспериментально показано, что введение детерминированности в алгоритм случайного поиска значительно повышает эффективность его работы.

4.2 Показатели эффективности генетических алгоритмов Основными показателями эффективности ГА являются скорость алгоритма и устойчивость поиска. Эффективность генетического алгоритма при решении конкретной задачи зависит от многих факторов, и в частности от таких, как генетические операторы и выбор соответствующих значений параметров, а также от способа представления задачи на хромосоме. Оптимизация этих факторов приводит к повышению скорости и устойчивости поиска, что существенно для применения генетических алгоритмов. Скорость генетического алгоритма оценивается временем, необходимым для выполнения заданного пользователем числа итераций. Если критерием останова является качество популяции или ее сходимость, то скорость оценивается временем достижения генетическим алгоритмом одного из этих событий. Устойчивость поиска оценивается степенью устойчивости алгоритма к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению. Два этих фактора - скорость и устойчивость - и определяют эффективность генетического алгоритма для решения каждой конкретной задачи.

4.2.1 Скорость работы генетического алгоритма По результатам экспериментов автора можно сделать вывод, что наибольшее влияние на скорость работы генетического алгоритма при решении поставленной задачи оказывают размер популяции и критерий останова. Кроме того, на скорость работы влияет и размер хромосомы, но этот параметр зависит не от разработчика, а от самой СММ, с которой проводится работа в данный момент времени - работа с СММ, соответствующим более длинным словам идёт несколько дольше. Варьирование других параметров работы ГА, как то вероятность применения оператора алгоритма. Как было показано в Главе 3, правильный выбор размера популяции позволяет соблюсти баланс между скоростью нахождения алгоритмом хорошего решения и скоростью работы самой программы, реализующей алгоритм. Экспериментально было определено, что наиболее удачное соотношение между этими требованиями имеет место при размере популяции порядка 100-200 особей. При таких размерах популяции, с одной скрещивания, вероятность применения оператора мутации, варианты операторов отбора и редукции, не оказывают сильного влияния на скорость работы стороны, достаточно быстро достигается хорошее решение, а, с другой, не происходит сильного замедления работы программы, как при популяциях размером 500 особей и выше. Кроме того, такие популяции не требуют большого объёма памяти для работы алгоритма, и в этом смысле не имеет большого веса минус кодирования хромосомы вещественными числами, заключающийся в требовании большего объёма памяти, чем при использовании других методов, например, битовой строки, рассмотренных в Главе 3. Что касается критерия останова, то, как было показано ранее, как правило, популяция достаточно быстро сходится к устойчивому хорошему решению за фиксированное число шагов, которое может быть экспериментально определено на этапе исследования, как это было описано в разделе 3.2.8, где оптимальным оказалось число 250-300 поколений. В этом случае хорошие результаты работы обеспечиваются при использовании в качестве критерия останова фиксированного числа поколений. Дополнительный плюс этого метода заключается в возможности довольно точной оценки требуемого для работы алгоритма времени, что может найти своё применение в системах, особо требовательных к точности и предсказуемости временных границ работы программы: в системах реального времени, в телекоммуникационных системах, там, где могут быть заранее заданы временные промежутки для работы системы оптимизации СММ. В случае если у разработчика имеются сомнения относительно одинакового поведения всех моделей в процессе оптимизации посредством ГА, как это может быть, например, в случае, когда слова записаны в различных условиях, разными дикторами или по каналам различного качества, что может выразиться в том, что часть моделей уже изначально достаточно хороша и не способна сильно улучшиться за разумное время, а другая часть, наоборот, допускает заметную оптимизацию, то тогда будет наиболее эффективен критерий останова, самостоятельно определяющий сходимость решения. Для оценки потенциала моделей в плане их возможной оптимизации была бы полезна система, способная оценивать качество модели в этом контексте. Ещё одним важным фактором, влияющим на скорость работы генетического алгоритма, является фитнес-функция. Фитнес-функция численно равна вероятности генерации заданного слова моделью и расчитывается для всех особей на каждом шаге работы алгоритма. Это то место в программе, где задача обучения СММ (Задача №3 среди основных задач, встающих перед разработчиком при работе с СММ, из классификации в Главе 1) вплотную соприкасается с Задачей №1 - задачей эффективного вычисления вероятности генерации заданной последовательности, и от успешного решения задачи № зависит эффективное решение задачи №3. Ввиду того, что вычисление фитнес-функции требуется регулярно, так как это наиболее часто используемая деталь алгоритма, она должна требовать минимум ресурсов, и потому важно, чтобы сама процедура её вычисления была достаточно эффективна. Поэтому оптимизация самой фитнес-функции также является методом повышения скорости работы генетического алгоритма. Эффективное вычисление вероятности генерации последовательности наблюдений - Задача №1 - подробно рассмотрена в Главе 1. Автором была выбрана высокоэффективная реализация данной функции из библиотеки Intel Recognition Primitives Library.

4.2.2 Средства повышения скорости работы генетических алгоритмов Основным способом повышения скорости работы генетических алгоритмов является распараллеливание [95]. Причем этот процесс можно рассматривать с двух позиций. Распараллеливание может осуществляться на уровне организации работы генетического алгоритма и на уровне его непосредственной реализации на вычислительной машине. На уровне непосредственной реализации ГА используется следующая особенность генетических алгоритмов. В процессе работы многократно приходится вычислять значения целевой функции для каждой особи, осуществлять преобразования оператора скрещивания и мутации для нескольких пар родителей и т. д. Все эти процессы могут быть реализованы одновременно на нескольких параллельных системах или процессорах, что пропорционально повысит скорость работы алгоритма. Алгоритм требует достаточно большого количества вычислений, но в то же время не требуется его работа в реальном времени, поскольку процесс оптимизации моделей слов в системе может быть запущен во времена её простоя или проводиться отдельным процессом в фоновом режиме параллельно основной работе системы распознавания. Кроме того, работа генетического алгоритма может быть распараллелена, в том числе между различными машинами в сети, что является весьма интересным дальнейшим шагом в развитии системы в перспективе. На уровне организации работы ГА применяется структурирование популяции решений на основе одного из двух подходов: 1) Популяция разделяется на несколько различных подпопуляций (демосов), которые впоследствии развиваются параллельно и независимо. То есть скрещивание происходит только между членами одного демоса. На каком-то этапе работы происходит обмен частью особей между подпопуляциями на основе случайной выборки. И так может продолжаться до завершения работы алгоритма. Данный подход получил название концепции островов (island model) [43, 94]. 2) Для каждой особи устанавливается ее пространственное положение в популяции. Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области (cellular genetic algorithms) [94]. Оба подхода, очевидно, также могут эффективно реализовываться на параллельных вычислительных машинах, что даёт хорошие перспективы использованию ГА в контексте современных тенденций развития аппаратных средств систем распознавания. Кроме того, практика показала, что структурирование популяции приводит к повышению эффективности генетического алгоритма даже при использовании традиционных вычислительных средств [19]. Еще одним средством повышения скорости работы является кластеризация [62]. Суть ее состоит, как правило в двухэтапной работе генетического алгоритма. На первом этапе генетический алгоритм работает традиционным образом с целью получения популяции более хороших решений. После завершения работы алгоритма из итоговой популяции выбираются группы наиболее близких решений. Эти группы в качестве единого целого образуют исходную популяцию для работы генетического алгоритма на втором этапе. Размер такой популяции будет, естественно, значительно меньше, и, соответственно, алгоритм будет далее осуществлять поиск значительно быстрее. Сужения пространства поиска в данном случае не происходит, поскольку применяется исключение из рассмотрения только ряда очень похожих особей, существенно не влияющих на получение новых видов решений.

4.2.3 Устойчивость работы генетического алгоритма Устойчивость или способность генетического алгоритма эффективно формировать лучшие решения зависит в основном от принципов работы генетических операторов (операторов отбора, скрещивания, мутации и редукции). Вычислительная эффективность этого процесса была рассмотрена при обсуждении теоремы схем в разделе 2.6. Рассмотрим механизм этого воздействия подробнее. Как правило, диапазон влияния можно оценить, рассматривая вырожденные случаи генетических операторов.

Вырожденными формами операторов скрещивания являются, с одной стороны, точное копирование потомками своих родителей, а с другой, порождение потомков, в наибольшей степени отличающихся от них. Преимуществом первого варианта является скорейшее нахождение лучшего решения, а недостатком, в свою очередь, тот факт, что алгоритм не сможет найти решения лучше, чем уже содержится в исходной популяции, поскольку в данном случае алгоритм не порождает принципиально новых особей, а лишь копирует уже имеющиеся. Чтобы всетаки использовать достоинства этой предельной формы операторов скрещивания в реальных генетических алгоритмах, применяют элитизм, речь о котором шла в главе 2. Во втором случае алгоритм рассматривает наибольшее число различных особей, расширяя область поиска, что, естественно, приводит к получению более качественного результата. Недостатком в данном случае является значительное замедление поиска. Одной из причин этого, в частности, является то, что потомки, значительно отличаясь от родителей, не наследуют их полезных свойств. В качестве реальных операторов скрещивания используются промежуточные варианты. В частности, родительское воспроизводство с мутацией и родительское воспроизводство с рекомбинацией и мутацией. Родительское воспроизводство означает копирование строк родительских особей в строки потомков. В первом случае после этого потомки подвергаются воздействию мутации. Во втором случае после копирования особипотомки обмениваются подстроками (то есть происходит кроссовер или рекомбинация). После рекомбинации потомки также подвергаются воздействию мутации. Последний подход получил наибольшее распространение в области генетических алгоритмов. Наиболее распространенными при этом являются одноточечный, двухточечный и равномерный операторы скрещивания. Основным параметром оператора мутации является вероятность его воздействия. Обычно она выбирается достаточно малой, чтобы, с одной стороны, обеспечивать расширение области поиска, а с другой, не привести к чересчур серьезным изменениям потомков, нарушающим наследование полезных параметров родителей. Сама же суть воздействия мутации обычно определяется фенотипом и на эффективность алгоритма особого воздействия не оказывает. Эксперименты на разработанном автором программно-аппаратном комплексе Иволга показали, что для решения задачи оптимизации СММ одиночные мутации с низкой вероятностью малоэффективны. Это обусловлено большим размером хромосомы, кодирующей матрицу вероятностей переходов скрытой марковской модели, и тем, что такие мутации затрагивают лишь малую часть модели. Иначе говоря, работа случайной составляющей в генетическом алгоритме недостаточна и является ограничивающим фактором для всего алгоритма в целом. Устранение этого узкого места способно привести к общему повышению эффективности алгоритма. Выполненное автором сравнение результатов для одноточечного оператора мутации и для многострочного в третьей главе (рис. 3.7) показало, что многоточечный оператор при малой вероятности мутации (порядка 0.05-0.1) эквивалентен одноточечному оператору при высокой вероятности его применения (0.9-0.95). При увеличении вероятности его применения ГА становится неустойчивым, поскольку значительная часть хороших решений разрушаются этим оператором в соответствии с теоремой схем.

4.2.4 Средства повышения устойчивости работы генетических алгоритмов Существует также дополнительная стратегия расширения поискового пространства, называемая стратегией разнообразия [19]. Если генетический алгоритм использует данную стратегию, то каждый порожденный потомок подвергается незначительному случайному изменению. Отличие разнообразия и мутации в том, что оператор мутации вносит в хромосому достаточно значительные изменения, а оператор разнообразия - наоборот, малозаметные. Ведь если часто вносить в хромосомы потомков незначительные изменения, то они могут быть полезны с точки зрения как расширения пространства поиска, так и наследования полезных свойств. В этом заключается основная причина стопроцентной вероятности применения оператора разнообразия. Отметим, что стратегия разнообразия применяется далеко не во всех генетических алгоритмах, поскольку является лишь средством повышения их эффективности. Одним из параметров, также влияющих на устойчивость и скорость поиска, является размер популяции, с которой работает алгоритм. Классические генетические алгоритмы предполагают, что размер популяции должен быть фиксированным. В этом случае оптимальным считается размер 2log2(n), где n - количество всех возможных решений задачи [19]. Однако в некоторых случаях бывает полезно варьировать размер популяции в определенных пределах. [60] В данном случае после очередного порождения потомков усечения популяции не происходит. Таким образом, на протяжении нескольких итераций размер популяции может расти, пока не достигнет определенного порога. После чего популяция усекается до своего исходного размера. Такой подход способствует расширению области поиска, но вместе с тем не ведет к значительному снижению скорости, поскольку усечение популяции, хотя и реже, но все же происходит. Аналогично, изменение размера популяции может происходить в адаптивных генетических алгоритмах, рассматриваемых далее.

4.3 Направления развития генетических алгоритмов 4.3.1 Использование комбинированной фитнес-функции Как было отмечено ранее, в произнесении команд у человека может наблюдаться вариативность, вызванная изменением его психо-физиологического состояния. В целях учёта такой ситуации проводить оптимизацию надо на наборе вариантов произнесения слова, а не на одном его экземпляре. Также может потребоваться работа системы с группой дикторов. Чтобы учесть такие варианты и повысить адаптивность САРР, автор предлагает использовать комбинированную фитнес-функцию. В зависимости от варианта работы системы распознавания речи, должна ли она работать с одним диктором в каждый момент времени или со многими, на вход системы подаются несколько образцов одного и того же слова, произнесённые диктором в разные моменты времени или в разном эмоциональном состоянии, или же произнесённые различными дикторами. Комбинированная фитнес-функция должна учитывать этот полный набор слов и проводить оценивание особей по каждому экземпляру слова, подводя обобщённый итоговый результат. Такая фитнес-функция получает вероятности генерации для каждого из образцов слова, входящего в набор, и составляет их взвешенную сумму, отражающую итоговый результат. Здесь появляется возможность варьировать вклад каждого варианта произнесения слова в итоговую фитнес-функцию, например, с учётом статистики по частоте эмоциональных состояний диктора или по частоте работы различных дикторов с системой распознавания. При реализации подобной комбинированной фитнес-функции система распознавания команд может быть обучена на использование выбранных словарей и дикторов практически без вмешательства человека, если у неё есть интерфейс с речевой базой данных, содержащей всю необходимую информацию.

4.3.2 Адаптивный ГА В области исследований, направленных на повышение эффективности генетических алгоритмов, большое значение приобрели идеи создания адаптивных генетических алгоритмов, которые могут изменять свои параметры в процессе работы [61]. Они стали продолжением развития идеи поколенческих алгоритмов, которые в процессе работы изменяют размер популяции. Адаптивные алгоритмы способны изменять не только этот параметр, но и суть генетических операторов, вероятность мутации и даже генотип алгоритма. Как правило, данные изменения происходят путем выбора параметров из нескольких вариантов, определенных перед началом работы алгоритма. Дополнительным плюсом подобных алгоритмов является то, что они не требуют задания большого множества параметров перед своей работой. Класс подобных генетических алгоритмов называется pGA (parameterless GA) - генетические алгоритмы без параметров [57]. Задача поддержания динамического равновесия параметров ГА, когда все их значения флуктуируют в районе оптимальных и в то же время способны подстраиваться под изменяющуюся ситуацию, даёт возможность избавить разработчика от выбора многих параметров, предоставив ему лишь контролирующую функцию, и переложив задачу нахождения оптимальных параметров функционирования на сам алгоритм. Полезна данная возможность в условиях, когда ситуация изменяется с течением времени, динамически перестраивается структура систем, с которыми работает ГА, а постоянный контроль человека невозможен, да и не нужен, и его вмешательство носит лишь ситуационный характер, например, периодический аудит работы или эпизодическая перенастройка системы. Данная ситуация регулярно наблюдается в телекоммуникационных сетях, способных динамически менять свою структуру, и неудивительно, что генетические алгоритмы находят своё применение при решении задач марштуризации в подобных условиях. Применительно к задачам распознавания речи и к работе с СММ в частности, подобный подход может быть актуален при динамическом изменении словарей, с которыми работает система распознавания речи, смене дикторов или психо-физиологических состояний работающего в данный момент с системой диктора, изменении условий снятия сигнала для системы предобработки в составе целостной системы распознавания, что может иметь место, скажем, при смене качества соединения при пакетной передаче голоса в системах IP-телефонии и так далее. Система распознавания должна уметь подстроиться под изменившиеся условия без участия человека. Существует два основных подхода к определению параметров ГА [57]: регулировка параметров (parameter tuning) и управление параметрами (parameter control). Регулировка параметров заключается в запуске множества тестов с целью определить, при каких значениях параметров ГА ведёт себя наилучшим образом. Так, экспериментально выясняются значения вероятностей мутации и кроссовера, размер популяции и другие параметры. Данный подход и был применён автором в диссертационной работе, глава 3 посвящена выбору значений параметров ГА, работающего с вещественными числами. Для бинарного кодирования хромосомы при использовании специальных тестовых функций известны свои наборы хороших значений параметров [59]. Такой подход требует много времени на исследования и не гарантирует, что те же параметры будут хорошо работать на несколько отличающейся задаче. Управление параметрами подразумевает старт алгоритма с некими начальными значениями параметров, возможно, определёнными с помощью первого метода. Далее во время работы алгоритма эти параметры подвергаются модификациям различными путями. В зависимости от способа модификации параметров ГА такие системы классифицируют на несколько категорий [61]: 1. Детерминистические (deterministic) ГА. 2. Адаптивные (adaptive) ГА. 3. Сапоприспосабливающиеся (self-adaptive) ГА. В детерминистическом ГА параметры изменяются во время работы алгоритма по некоторому заранее заданному закону, который чаще всего зависит от времени (от числа поколений или от количества вычислений целевой функции). Так, например, Фогарти [63] изменял вероятность мутации по следующему закону: Pm = 1 0.11375 +, 240 2t (4.1) где t - номер поколения. Практически все подобные формулы включают в себя условие 1/t, где t - номер поколения. В этом случае начальная вероятность мутации достаточно высока и уменьшается по мере работы алгоритма. Это согласуется с идеей о том, что в самом начале ГА быстро определяет наиболее интересные для себя области (с помощью мутации), а затем неторопливо их исследует (с помощью кроссовера). Такие формулы не только устраняют необходимость задавать этот параметр, но, по оценкам исследователей, значительно повышают эффективность ГА [46]. В адаптивных ГА информация о работе алгоритма посредством обратной связи влияет на значения его параметров. Однако, в отличие от самоприспосабливающихся алгоритмов, значения этих параметров едины для всех особей популяции. Такой способ управления алгоритмом впервые был использован Реченбергом [84]. Он постулировал, что одна из пяти мутаций должна вести к появлению лучшего индивидума. Далее, он связал вероятность мутации с частотой хороших мутаций. Так, если частота хороших мутаций выше 1/5, то вероятность мутации уменьшается, и наоборот. В самоприспосабливающихся ГА также благодаря обратной связи используется информация о работе алгоритма, но каждая особь популяции имеет собственные значения параметров. Впервые такой подход был использован Шефелем [87] в эволюционных стратегиях, где он пытался управлять шагом мутаций. Бэк [47] распространил его идеи на генетические алгоритмы. Он добавил к хромосоме дополнительные биты, в которых кодировались вероятности мутации и кроссовера. Идея адаптивных генетических алгоритмов получила свое воплощение во множестве разных концепций, одной из наиболее интересных среди которых является nGA [19]. nGA представляет многоуровневые генетические алгоритмы. Нижний уровень такого алгоритма непосредственно выполняет задачу улучшения популяции решений. Верхние уровни представляют собой генетические алгоритмы, решающие оптимизационную задачу по улучшению параметров алгоритма нижнего уровня. При этом в качестве целевой функции используется обычно скорость работы алгоритма нижнего уровня и скорость улучшения им популяции от поколения к поколению. Подобная организация алгоритма, отталкиваясь от базовых параметров, определённых в работе автора, должна быть способна подстраиваться под изменяющиеся условия функционирования системы распознавания речи, тем самым повышая надёжность её работы. Кроме того использование подобного метода даёт возможность освободить оператора от кропотливой настройки системы, найдя лучшие значения параметров самостоятельно.

4.4 Выводы В главе описано сравнение результатов работы генетического алгоритма с традиционно используемым для обучения СММ методом Баума-Велча. Приведены наиболее характерные примеры и показана высокая эффективность работы ГА при решении поставленной задачи и наличие определённых преимуществ перед методом Баума-Велча, как то независимость от начальных условий и способность выходить из локальных экстремумов. В сравнении со случайным поиском ГА обеспечивает гораздо более быстрое нахождение хорошего решения. Результаты, полученные с помощью ГА сопоставимы с результатами работы метода Баума-Велча, а в некоторых случаях превосходят его, что говорит о способности алгоритма выходить из локальных экстремумов. На основании этих данных предлагается следующая схема организации процесса обучения в системе распознавания речевых команд на основе СММ: система содержит модуль, реализующий обучение традиционным методом Баума-Велча и параллельно несёт в себе модуль ГА. Первоначальное обучение марковской модели слова производится с помощью метода Баума-Велча, а в дальнейшем (например, во время простоя системы, когда вычислительные ресурсы компьютера свободны) производятся запуски системы ГА как со случайной стартовой популяцией, так и с популяцией, построенной на основе уже обученных моделей. При нахождении генетическим алгоритмом модели слова лучшей, чем имеющаяся в словаре системы, производится её замена на новую. Данный подход позволяет произвести быстрое начальное обучение системы и затем последовательно работать над улучшением моделей слов в словаре. Независимость подтверждается работы генетического алгоритма от начальных условий при использовании в качестве начальной популяции случайно сгенерированных решений. В этом случае разница с вариантом, когда используются созданные другим алгоритмом начальные решения, заметна лишь на ранних шагах работы алгоритма и заключается в некотором отставании ГА, т.е. возникновении ситуации, когда для достижения аналогичного результата ему требуется некоторое дополнительное время. Эта особенность может проявиться только в случае, когда в качестве критерия останова выбрано слишком малое число поколений работы ГА. Рассмотрены показатели эффективности работы генетических алгоритмов, изучено влияние параметров генетического алгоритма на эффективность его работы. Выявлено, что скорость работы генетического алгоритма напрямую зависит от правильного выбора размера популяции и критерия останова, а также от качественной реализации фитнесфункции. Автором определены наиболее эффективные значения параметров ГА и использована высокоэффективная реализация фитнес-функции. Отмечена хорошая масштабируемость генетического алгоритма, позволяющая повысить его скорость путём распараллеливания как на уровне организации работы генетического алгоритма и на уровне его непосредственной реализации на вычислительной машине. Кроме того, способность параллельного выполнения ГА на нескольких машинах даёт возможность создания системы распределённых вычислений, целью которой является оптимизация СММ. При наличии парка компьютеров время их простоя может быть минимизировано за счёт выполнения таких распределённых вычислений в моменты, свободные от решения иных задач. Предложены пути дальнейшего усовершенстования алгоритма, описанного в предыдущей главе - введение генетического алгоритма второго уровня в целях адаптивного подбора параметров функционирования основного ГА без вмешательства человека и использование комбинированной фитнес-функции, способной положительно повлиять на качество обучения (и последующего распознавания) в случае работы системы распознавания команд с несколькими дикторами или с одним диктором, но при возможности смены его психо-физиологического состояния.

Выводы и заключение 1. Для современных систем управления, использующих системы автоматического распознавания речевых команд на основе скрытых марковских моделей (СММ), при фиксированной аппаратной базе таких систем и существующих тенденциях её развития в ближайшем будущем проведёно исследование задачи обучения СММ тренировочными последовательностями. Исследование показало, что существует перспективное направление повышения эффективности обучения СММ посредством использования аппарата генетических алгоритмов (ГА), которые преодолевают ограничения и недостатки методов, традиционно используемых для оптимизации 2. Для решения СММ, задачи а также обладают очень хорошими перспективами наиболее использования с учётом тенденций развития аппаратных средств. оптимизации числами, тестовой обучения СММ разработан приспособленный для этой цели ГА, выбран и реализован механизм кодирования хромосом вероятность вещественным генерации создана фитнес-функция, последовательности вычисляющая наиболее моделью эффективным способом. Разработанные генетические операторы ориентированы на работу с СММ и учитывают характерные для них ограничения. На основании теоремы схем показано, что выбранный оператор отбора ведёт к эффективному нахождению более хороших решений задачи. Определены условия эффективного применения различных вариантов реализации критерия останова ГА. Экспериментально определены наиболее эффективные значения параметров алгоритма (размер популяции, вероятность мутации) для использования в задаче обучения СММ. 3. В результате исследования эффективности оптимизации обучения СММ с помощью генетического алгоритма и сравнения его с традиционными методами обучения установлено, что предложенный автором генетический алгоритм показывает результаты, сравнимые с методом Баума-Велча, а в некоторых случаях и превосходит их, находя решения за пределами локальных экстремумов, которые не может обнаружить метод Баума-Велча. Генетический алгоритм преодолевает и такое важное ограничение традиционных методов, как сильную зависимость от стартовых значений. Предложенный подход показал свою эффективность и перспективность использования в задачах распознавания речевых команд. 4. Экспериментально определены параметры, оказывающие влияние на эффективность решения алгоритмом поставленной задачи. Предложены методы, направленные на дальнейшее повышение эффективности и качества работы ГА в контексте рассматриваемой задачи: возможность оптимизации выбора параметров с использованием 2-уровневого ГА и использование комбинированной фитнесфункции. Это открывает путь к созданию самообучающихся систем распознавания и позволяет повысить качество распознавания команд при работе с разными дикторами, дикторами в условиях стресса, с дикторами, речь которых имеет особенности в виде проглатывания части звуков, а также в телекоммуникационных системах при работе по каналам связи низкого качества, где часть голосовой информации может быть потеряна, в том числе и в сетях сотовой связи или IP-телефонии. 5. В рамках работы создан программно-аппаратный комплекс Иволга для исследования генетических алгоритмов. Программная его часть является дополнением системы SdiApp, решающей задачу оценки стартовых параметров СММ и функционирующей на кафедре ЭВА МИЭМ с 1998 г., и написана в среде Borland C++ Builder 6. Необходимая для работы аппаратная часть - ПК с процессором класса Pentium-3 500МГц и 256Мб оперативной памяти, а также звуковая карта, поддерживающая при записи звука частоты дискретизации до 44КГц. 6. Автором предлагается следующая схема организации процесса обучения в системе распознавания речевых команд на основе СММ: система содержит модуль, реализующий обучение традиционным методом Баума-Велча и параллельно несёт в себе модуль ГА. Первоначальное обучение марковской модели слова производится с помощью метода Баума-Велча, а в дальнейшем (например, во время простоя системы, когда вычислительные ресурсы компьютера свободны) производятся запуски системы ГА как со случайной стартовой популяцией, так и с популяцией, построенной на основе уже обученных моделей. При нахождении генетическим алгоритмом модели слова лучшей, чем имеющаяся в словаре системы, производится её замена на новую. Данный подход позволяет произвести быстрое начальное обучение системы и затем работать над улучшением моделей слов в словаре (в том числе и имея возможность распределить вычисления между различными компьютерами в сети). Предложенное в данной работе решение задачи оптимизации обучения СММ способно улучшить процесс обучения СММ тренировочными последовательностями и повысить надёжность работы систем распознавания речевых команд, использующих в своей работе марковские модели.

Литература 1. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы: Учебник. - М.: Финансы и статистика, 2004. - 424 с.: ил. 2. Анохин П.К. Философский смысл проблемы естественного и искусственного интеллекта, Вопросы философии (1973, № 6, с.83-97). 3. Баричев С. Нас мало, но мы - супер!, Компьютерра, #47 (571), 2004, стр.19. 4. Белянин В.П. Психолингвистика: учебник. - М.:Флинта: Московский психологосоциальный институт, 2003. - 232 с. 5. Буря А.Г. Фонетическая база данных для речевых исследований, Диплом, Москва, МИЭМ, 2000 6. Витяев Е.Е. Вероятностное прогнозирование и предсказание как принцип работы мозга // Измерение и Модели Когнитивных Процессов, Труды ИМ СО РАН (Выч. системы, 162), Новосибирск, 1998, Стр. 14-40. 7. Галунов В.И. Актуальные проблемы речевой акустики, Акустика речи. Медицинская и биологическая акустика. Сборник трудов XIII сессии Российского акустического общества. Т.3. - М.: ГЕОС, 2003. - 274 с. Стр.16-19. 8. Галунов В.И. Современные речевые технологии (обзорная статья), 1999, 9. Галунов В.И., Кутуков Г.П., Матюнин С.Н. Состояние исследований в области речевых технологий и задачи, выдвигаемые государственными заказчиками, Секция по автоматическому распознаванию и синтезу речи РАН, 1999. 10. Галяшина Е.И. Основы судебного речеведения, изд-во СТЭНСИ, 2003. 11. Годфруа Ж. Что такое психология: В 2-х т. Изд 2-е, стереотипное. Т.1: Пер. с франц. - М.: Мир, 1999. - 496 с., ил. 12. Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы Финансы и статистика, Москва, 1998. 13. Дьяконов В. MATLAB. Обработка сигналов и изображений. Специальный справочник. - СПб.: Питер, 2002. - 608 с.:ил. 14. Златоустова Л.В., Потапова Р.К., Потопов В.В., Трунин-Донской В.Н. Общая и прикладная фонетика. - М.: МГУ, 1997. 15. Иконин С.Ю., Сарана Д.В. Система автоматического распознавания речи SPIRIT ASP Engine, Цифровая обработка сигналов, #3, 2003. 16. Капра Ф. Паутина жизни. Новое научное понимание живых систем, К.: София;

2002.

17. Клемент Р. Генетические алгоритмы: почему они работают? Когда их применять?, Компьютерра, №289, 1999, стр. 20-23. 18. Кольман Я., Рём К.-Г. Наглядная биохимия: Пер. с нем. - М.: Мир, 2000. - 469 с. 19. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. - М.: Нолидж, 2000. - 352 с., ил. 20. Коротков А.В. Послесловие к матрице: виртуальные миры или искусственная жизнь. - М.: МПБ Деловая культура;

Альпина Бизнес Букс, 2005. - 308 с. 21. Косарев Ю.А. Естественная форма диалога с ЭВМ. Ч Л.:Машиностроение, 1989. 22. Кочетков А. Умные телефоны заговорили, Компьютерра #16 (588), 2005, стр.50-51. 23. Люгер Дж. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание.: пер.с англ. - М.:Издательский дом Вильямс, 2003, - 864 с. 24. Озеров С. Архитектура CPU, Компьютерра #37 (609), 2005, стр.24-39. 25. Озеров С. Ячейка. Она же клетка, она жеЕ Cell, Компьютерра #38 (610), 2005, стр.38-41. 26. Петерс Э. Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка: Пер. с англ. - М.: Мир, 2000, - 333 с. 27. Пиотровский Р.Г. и др. Математическая лингвистика. Учеб. пособие для пед. ин-тов. М., Высшая школа, 1977. 28. Попов Э.В. Общение с ЭВМ на естественном языке. Изд. 2-е, стереотипное. - М.: Едиториал УРСС, 2004. - 360 с. (Науки об искусственном.) 29. Потёмкин В.Г. MATLAB 6: среда проектирования инженерных приложений. - М.: Диалог-МИФИ, 2003. - 448 с. 30. Саймон Г. Науки об искусственном. Пер с англ. Изд. 2-е. - М.: Едиториал УРСС, 2004. 144 с. (Науки об искусственном.) 31. Самойленко А.П., Дюк В.А. Data Mining. Учебный курс, изд-во Питер, 2001 32. Сапунов Г.В., Труфанов Ф.А. Генетические алгоритмы как метод оптимизации скрытых марковских моделей в задачах распознавания речи, проф. Азарова В.Н. - М.:МИЭМ, 2004. 33. Серов А.А. Оценка стартовых параметров СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала, диссертация, УДК 534.78, Москва, МИЭМ, 2001. 34. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. - М.:Издательский дом Вильямс, 2003. - 1104 с.: ил. Информационные технологии в системах вычислительной техники. Выпуск 3. Под общей редакцией 35. Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры цифровой обработки сигналов. - СПб.: БХВ-Петербург, 2002. - 464 с.: ил. 36. Солсо Р. Когнитивная психология. - СПб.:Питер, 2002. - 592 с. 37. Сусов И.П. Введение в теоретическое языкознание. Основы общей фонетики и фонологии. ( 38. Таран О., Мирошниченко С., Гуриев В. Ничего никому не скажу?, Компьютерра, #36 (608), 2005, стр.25-33. 39. Тейлор Д., Грин Н., Стаут У. Биология: в 3-х т. Т.1: Пер. с англ./Под ред. Р.Сопера - 3-е изд., - М.: Мир, 2001. - 454 с. 40. Тьюринг А. Может ли машина мыслить? (С приложением статьи Дж. фон Неймана Общая и логическая теория автоматов. Пер. и примечания Ю.В. Данилова). М.: ГИФМЛ, 1960. 41. Уитби Б. Искусственный интеллект: реальна ли Матрица. М.: Фаир-пресс, 2004, 210 с. 42. Хофштадтер Д., Деннетт Д. Глаз разума. - Самара: Издательский дом Бахрах-М, 2003. - 432 с. 43. Цой Ю. Модели ГА, 44. Ярушкина Н.Г. Основы теории нечётких и гибридных систем: Учеб. пособие. - М.: Финансы и статистика, 2004, - 320 с. 45. Artificial Intelligence FAQ What are Gray codes, and why are they used?, 46. Bck Th., Evolutionary Algorithms in theory and practice, Oxford University Press, 1996. 47. Bck Th., Self-Adaptation in Genetic Algorithms, University of Dortmund, Department of Computer Science, Dortmund, Germany, 1992. 48. Baum L.E., Petrie T., Statistical inference for probabilistic functions of finite state Markov chains, Ann. Math. Stat., vol.37, pp.1554-1563, 1966. 49. Baum L.E. An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes, Inequalities, vol.3, pp. 1-8, 1972. 50. Blickle T., Thiele L., A Comparison of Selection Schemes used in Genetic Algorithms, Computer Engineering and Communication Networks Lab, Swiss Federal Institute of Technology, Zurich, Switzerland, 1995. 51. Burger Y. Мягкие вычисления, 52. Carnegie Mellon Engineering Researchers To Create Speech Recognition in Silicon, 13 September 2004, 53. Capra F. The Hidden Connections, Harper Collins Publishers, 2002, ISBN 0-00-257047-5. 54. Chau C.W., Kwong S., Diu C.K., Fahrner W.R. Optimization of HMM by a Genetic Algorithm, Proceedings of the 1997 International Conference on Acoustics, Speech and Signal Processing, 1997, pp. 1727-1730. 55. Clement R.P., Wren A. Genetic Algorithms and Bus-Driver Scheduling, Presented at the 6th International Conference for Computer-Aided Transport Scheduling, Lisbon, Portugal, 1993. 56. CompTek, В России появился первый коммерческий продукт распознавания русской речи для телефонных приложений, 57. Daridi F., Kharma N., Salik J.F.N. Parameterless Genetic Algorithms: Review and Innovation, IEEE Canadian Review, Summer 2004, No. 47. 58. Deb K., Agrawal S. Understanding Interactions Among Genetic Algorithm Parameters, Kanpur Genetic Algorithms Laboratory, Kanpur, India, 1998. 59. De Jong, K.A. An analysis of the behavior of a>

68. Goldberg D.E., Deb K., Clark J.H. Genetic algorithms, noise, and the sizing of populations, Complex systems, 6(4), 1992, August, pp.333-362. 69. Gorges-Schleuter M. Explicit Parallelism of Genetic Algorithms through Population Structures. Paralles Problem Solving from Nature, Springer Verlag, 1991, pp.150-159. 70. Grefenstette J.J. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. Systems, Man, and Cybernetics, 16(1), 1986, pp.122-128. 71. Hand D., Mannila H., Smyth P. Principles of Data Mining, Massachusetts Institute of Technology, 2001, ISBN 0-262-08290-X. 72. Holland J.H. Adaptation in Natural and Artificial Systems: 2nd edition, MIT Press, 1992. 73. Holland J.H. Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions, MIT Press, Evolutionary Computation #8(4), 2000, pp.373-391. 74. Jelinek F. Statistical Methods for Speech Recognition, Massachusetts Institute of Technology, 1998, ISBN 0262100665. 75. Kaiser J. Training of HMM with Genetic Algorithms, University of Maribor, Faculty of Electrical Engineering and Computer Science, Slovenia. 76. Kaiser J., Kai Z. Uenje prikritih modelov Markova z genetskimi algoritmi, Fakulteta za elektrotehniko, raunalnitvo in informatiko, Univerza v Mariboru, Slovenija. 77. Koutras A., Dermatas E., Kokkinakis G. Recognizing simultaneous speech: a genetic algorithm approach, WCL, Electrical and Computer Engineering Dept., University of Patras, Greece. 78. Luke S. When Short Runs Beat Long Runs, George Mason University. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann, 2001, pp. 74-80. 79. Marczyk A. Genetic Algorithms and Evolutionary Computation, 2004, 80. Mathias K., Whitley D. Transforming the Search Space with Gray Coding, Department of Computer Science, Colorado State University, 1994. 81. Penrose R. Shadows of the Mind, Vintage Science, 1995, ISBN 0-09-958211-2. 82. Popovici E., De Jong K. Understanding EA Dynamics via Population Fitness Distributions, Department of Computer Science, George Mason University, Fairfax, USA, 2003. 83. Rabiner L.R., A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IЕЕЕ, vol, 77. no.2, February 1989, рр. 257-284. 84. Rechenberg I. Evolutions strategie: Optimierung technischer systeme nach prinzipien der biologischen evolution, Frommann, 1973.

85. Sakrament ASR Engine, 86. Sastry K., OТReilly U.M., Goldberg D.E. Population Sizing for Genetic Programming Based Upon Decision Making, IlliGAL Report No. 2004028, April, 2004. 87. Schwefel H-P. Numerische optimierung von computer-modellen mittels der evolutionsstrategie, Volume 26 of Interdisciplinary systems research. Birkhauser, Basel, 1997. 88. Smith W.S. The Scientist and EngineerТs Guide to Digital Signal Processing, Second Edition, California Technical Publishing, San Diego, California, 1999, ISBN 0-9660176-6-8 89. SPIRIT Corp., 90. StatSoft's Electronic Statistics Textbook, 1999 91. Tegmark M. Parallel Universes, Scientific American, May, 2003. 92. Vector Quantization, 93. Viterbi A.J., Error bounds for convolutional codes and an asymptotically optimal decoding algorithm. IEEE Trans. Informat. Theory, vol. IT-13, pp. 260-269, Apr. 1967. 94. Whitley D. A Genetic Algorithm Tutorial, Computer Science Department, Colorado State University, USA, 1993. 95. Wikipedia. Genetic algorithm, 96. Wikipedia. Artificial life, Предметный указатель EM (expectation-modification) метод.................................................................................................................. 29 Forward-Backward процедура............................................................................................................................. 26 nGA................................................................................................................................................................... 103 pGA, parameterless GA...................................................................................................................................... 101 Баума-Велча процедура, Baum-Welch............................................................................................................... 29 векторое квантование......................................................................................................................................... 21 Витерби алгоритм............................................................................................................................................... 28 ГА адаптивный, adaptive.................................................................................................................................... 102 детерминистический, deterministic.............................................................................................................. 102 сапоприспосабливающийся, self-adaptive................................................................................................... 102 генетические алгоритмы (ГА), Genetic Algorithms (GA)................................................................................... 38 генетические операторы..................................................................................................................................... 42 генотип................................................................................................................................................................ 40 длина схемы....................................................................................................................................................... 47 индивидуум.................................................................................................................................... См. хромосома искусственная жизнь, Artificial Life................................................................................................................... 38 качество особи.................................................................................................................................................... 41 комбинаторный взрыв........................................................................................................................................ 35 кроссинговер, crossover.............................................................................................. См. оператор скрещивания матрица вероятностей начальных состояний.............................................................................................................. 19 вероятностей переходов................................................................................................................................ 18 мера давления отбора (selection pressure).......................................................................................................... 50 методы оптимизации направленные................................................................................................................................................. 34 ненаправленные............................................................................................................................................. 34 перечислительные.......................................................................................................................................... 35 модель бионическая................................................................................................................................................... 38 марковская..................................................................................................................................................... 16 скрытая марковская, СММ............................................................................................................................ 17 мутация, mutation............................................................................................................................................... 45 неявный параллелизм......................................................................................................................................... 47 нулевой переход................................................................................................................................................. 25 оператор мутации............................................................................................................................................... 41 оператор отбора................................................................................................................................................... 41 оператор редукции............................................................................................................................................... 41 оператор скрещивания......................................................................................................................................... 41 особь............................................................................................................................................... См. хромосома переменная "обратная"...................................................................................................................................................... 27 "прямая"......................................................................................................................................................... 26 поколение............................................................................................................................................................ 41 популяция............................................................................................................................................................ 41 порядок схемы.................................................................................................................................................... 47 потомок............................................................................................................................................................... 41 правило Холланда.............................................................................................................................................. 48 проблема баланса исследования и использования......................................................................................... 51 проблема поля для гольфа.............................................................................................................................. 52 размер популяции................................................................................................................................................ 41 размножение....................................................................................................................................................... 41 регулировка параметров, parameter tuning....................................................................................................... 101 рекомбинация............................................................................................................................. См. кроссинговер родитель............................................................................................................................................................. 41 СММ "слева-направо", left-right model.................................................................................................................... 22 авторегрессионная......................................................................................................................................... Бэйкиса, Bakis model......................................................................................................... См. "слева-направо" полносвязная.................................................................................................................................................. 22 с длительностью состояний........................................................................................................................... 24 с непрерывными плотностями вероятностей................................................................................................ 24 с параллельными путями............................................................................................................................... 23 с поступательно-ограниченными переходами.............................................................................................. 22 эргодическая..........................................................................................................................См. полносвязная строительный блок............................................................................................................................................. 47 схема хромосомы............................................................................................................................................... 46 теорема схем....................................................................................................................................................... 47 управление параметрами, parameter control..................................................................................................... 101 фенотип............................................................................................................................................................... 40 фитнес-функция, fitness function.......................................................................См. функция приспособленности функция приспособленности............................................................................................................................. 43 хромосома........................................................................................................................................................... 40 эволюционное программирование, Evolutionary Programming......................................................................... 38 эволюционные вычисления................................................................................................................................ 37 эволюционные стратегии, Evolution Strategies.................................................................................................. 39 элитизм............................................................................................................................................................... Приложение 1. Описание программного комплекса для изучения генетических алгоритмов.

Разработанный автором программный комплекс Иволга (Eevolga, Electronic Evolition: Genetic Algorithms) предназначен для исследования генетических алгоритмов в задачах распознавания речи на основе скрытых марковских моделей с кепстральной предобработкой речевого сигнала, что приводит к использованию непрерывных СММ. Программный комплекс создан автором на базе программы SdiApp, которая была разработана Серовым А.А. на кафедре ЭВА МИЭМ для оценки стартовых параметров СММ в задачах распознавания команд при кепстральной обработке речевого сигнала. Блок работы с генетическими алгоритмами реализован в виде отдельного модуля программы с собственным диалоговым окном настройки параметров, интегрированным в общую систему. Исходные данные программа принимает как из речевой базы данных (РБД), разработанной и используемой на кафедре ЭВА МИЭМ, так и непосредственно с микрофона или из заранее приготовленных wav-файлов.

Структура и функционирование программы Программа Eevolga написана на языке С++ как многопоточное приложение с применением среды разработки приложений Borland C++ Builder 6.0. Реализация программы в виде нескольких взаимодействующих потоков позволила наиболее эффективно использовать ресурсы системы и дала принципиальную возможность осуществить работу со звуковой подсистемой компьютера в режиме реального времени. Передача данных между потоками осуществляется посредством очередей и синхронизированного доступа к ним. Данные в очередях представляются в виде структур, содержащих всю необходимую и сопутствующую информацию для правильной работы последующих модулей-потоков. На рис. 5.1 представлена структура программы:

Рис. 5. 1 Структура программного комплекса Здесь видны потоки команд и данных между модулями-потоками и их направление. По этой схеме можно судить о маршрутах прохождения информации через модули. Так, например, чтобы данные попали из файла в буфер речевых единиц, они должны проследовать через модуль АЦП, в котором они преобразуются в последовательность фреймов в соответствии с настройками модуля. И наоборот, чтобы данные попали из буфера речевых единиц в модуль генетических алгоритмов, они должны проследовать через модуль DSP. Каждому потоку приложения соответствует одно или несколько диалоговых окон, через которые осуществляется управление алгоритмами, которые реализует поток, и также через эти окна производится отображение результатов работы.

Назначение модулей программы На рис.5.2 представлено основное окно программы. Отдельным кнопкам в её окне соответствуют диалоговые окна для настройки и управления обозначенными модулями программы.

Рис. 5.2 Основное окно программы VCL Этот модуль является основным потоком приложения, правда, при этом он не участвует ни в каких вычислениях. Он занимается взаимодействием с операционной системой и графической подсистемой компьютера в частности, т.е. все диалоги и окна приложения находятся в его ведении. За все, что видно на экране, ответственен VCL.

АЦП В обязанности этого модуля входит: з з з з разрядность управление драйвером звуковой карты. реакция на прерывания со стороны звуковой карты. формирование заданного потока фреймов из данных поступающих от звуковой карты. отображение параметров текущего сигнала. сигнала с микрофона. Здесь же задаются параметры В диалоге управления этим потоком можно задать частоту дискретизации и оцифровки формируемого потока фреймов. Также в диалоговом окне этого модуля отображается текущее значение параметров входного сигнала, что позволяет настраивать систему на оптимальную работу с данной звуковой подсистемой компьютера.

Таксоном Модуль таксономии речи занимается вычленением изолированных слов из непрерывного потока данных, поступающего от АЦП, и помещает эти слова в буфер речевых единиц. Также через диалог этого модуля осуществляется управление этим буфером. По сути, это центр управления основными функциями системы. Отсюда речевые единицы отправляются на предобработку.

DSP Это главный вычислительный центр. Этот модуль производит все трудоемкие вычисления, те, которые в аппаратных системах обычно выполняет цифровой сигнальный процессор. Этот модуль обслуживается несколькими диалоговыми окнами. Данные в модуль DSP поступают из модуля Таксоном в виде целых речевых единиц. Далее модуль производит кепстральное преобразование. В этом модуле реализована таксономия слов на фонемы, сохранние полученных фонем в виде wav и cps-файлов. Отсюда же слова передаются в простейший редактор, встроенный в программу.

ГА Модуль, реализующий генетические алгоритмы: основной цикл работы генетического алгоритма, работу с популяциями, генетические операторы. В процессе работы модуль может взаимодействовать со словарём системы и с буфером речевых единиц.

Настройка системы генетических алгоритмов Диалог настройки параметров генетического алгоритма доступен при нажатии на кнопку Eevolga в главном окне программы. При этом вызывается окно с базовыми параметрами ГА (рис. 5.3), где пользователь может задать размер популяции, а также параметры генерации исходной популяции: число случайных и мутировавших особей и вероятность мутации, применяющуюся при создании мутировавших особей начальной популяции.

Рис. 5.3 Базовые параметры ГА Следующая закладка этого окна (рис. 5.4) позволяет настроить параметры оператора отбора. Среди этих параметров располагается выбор метода отбора а также переключатель, указывающий производить ли нормализацию значений фитнес-функции при пропорциональном отборе.

Рис. 5.4 Параметры отбора Следующая закладка (рис. 5.5) управляет параметрами оператора скрещивания, здесь пользователь может выбрать метод кроссовера - одноточечный, двухточечный или равномерный:

Рис. 5.5 Параметры оператора скрещивания Закладка с параметрами оператора мутации (рис. 5.6). Здесь задаётся вероятность применения оператора мутации, метод мутации - однострочная или многострочная, а также переключатель, допускающий странные мутации, то есть мутации, ведущие к появлению ненулевых элементов в матрице слева от главной диагонали:

Рис. 5.6 Параметры оператора мутации Закладка с параметрами критерия останова (рис. 5.7). Здесь задаётся число поколений работы генетического алгоритма:

Pages: | 1 | 2 | 3 |

Книги, научные публикации

Blog