Файл: Интеллектуальные информационные системы и технологии.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 352
Скачиваний: 11
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
рекомбинация). Одним из типов рекомбинации является кроссинговер, который соответствует реком-бинации, предусматривающей обмен определенными участками между хромосомами. Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков
в одном решении.
При разработке генетических алгоритмов преследуются две цели:
абстрактное и формальное объяснение процессов адаптации в ес-тественных системах;
проектирование искусственных программных систем, воспроизво-дящих механизм функционирования естественных систем.
Основные отличия генетических алгоритмов оптимизации:
используются не параметры, а закодированные множества па-раметров;
поиск осуществляется не из единственной точки, а из популяции точек;
в процессе поиска используются значения целевой функции, а не ее приращения;
применяются вероятностные, а не детерминированные правила по-иска и генерации решений;
выполняется одновременный анализ различных областей простран-ства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счет объединения квази-оптимальных решений из разных популяций [6, 18].
Пример 11.1. Реализация генетического алгоритма для решения задачи оптимизации
Пусть заданы произвольная не дифференцируемая функция f(x, y)
и области существования ее аргументов х = [–10, 25], y = [–5, 5]. Необходимо определить max f(x, y) c использованием генетического алгоритма [6].
На первом этапе создается фонд хромосом С0, С1, С2, …, состоящих из двух генов (х, у), с использованием генератора случайных чисел в со-ответствии с областями существования генов (аргументов) и вычисляются значения функции (табл. 11.1).
Таблица 11.1
На втором этапе необходимо выбрать пары родителей для рекомбинации на основе значений
f(x, y) (здоровье хромосомы). Здоровье хромосомы С1 самое плохое (функция имеет минимальное значение), поэтому из дальнейшего рассмотрения она исключается. На основе первой пары родителей (С2, С3) формируются новые хромосомы С4 (ХС2, УС3), С5 (ХС3, УС2), а на основе второй пары (С0, С3) формируются хромосомы С6 (ХС3, УС0), С7 (ХС0, УС3), после чего рассчитываются значения здоровья новых хромосом (табл. 11.2).
Таблица 11.2
Лучшее решение в новой популяции (0,8) выше, чем в предыдущей (0,44).
На третьем этапе снова выбираются самые здоровые хромосомы (С4, С5, С7), из которых формируются пары новых родителей, и реализуется процедура рекомбинации и т.д.
Пример 11.2. Решение задачи поиска тематической информации в Интернете с использованием генетического алгоритма
С помощью различных поисковых систем пользователь Интернета осуществляет целенаправленный единичный поиск требуемой информации (описание объекта, явления с заданными свойствами), что, как правило,
не вызывает особых проблем, или тематический поиск, ориентированный на целую категорию скоординированной информации в некотором те-матическом сегменте [14].
При выполнении тематического поиска неизбежно возникает ряд вопросов. Как совместно оценить релевантность документов, найденных разными запросами? Является ли ранжирование результатов корректным с позиций ожиданий пользователей? Все ли результаты, доступные для непосредственной оценки, соответствуют ожиданиям пользователей? Как отфильтровать документы, не относящиеся к искомой тематике? На эти вопросы невозможно однозначно ответить в рамках тривиальных решений.
Для получения эффективного множества поисковых запросов может быть использован подход на основе генетических алгоритмов. Определим основные этапы генетического алгоритма для формирования эффективного множества запросов в случае тематического поиска информации.
1. Подготовка ключевых слов, множество которых формирует поисковый образ документов заданной тематики и задается как параметр алгоритма.
2. Выбор поисковой системы. При этом может быть использована любая поисковая система, имеющая API для доступа к результатам поиска (Bing, Google и др.).
3. Формирование исходной популяции запросов. Каждый поисковый запрос есть совокупность ключевых слов.
4. Выполнение запросов популяции. Результатом является мно-жество дескрипторов найденных документов (заголовок, описание, адрес текста). Множества результатов различных запросов могут пере-секаться.
5. Вычисление целевой функции. Исходная позиция для определения целевой функции предусматривает, что множество эффективных результатов поиска должно формироваться документами, которые удовлетворяют следующим условиям:
находятся в первых позициях ранжированного списка результатов поиска, построенного поисковой системой;
присутствуют в списках результатов, полученных при выполнении как можно большего числа различных запросов;
семантически близки к поисковому образу множества документов заданной тематики.
6. Селекция лучших запросов.
7. Выбор родительских пар запросов. Используется генотипный аутбридинг. При этом первый запрос выбирается случайно, а второй должен быть максимально «далек» от первого.
8. Скрещивание запросов, что реализуется дискретной реком-бинацией или одноточечным кроссинговером – обменом ключевыми словами или их группами между запросами.
9. Мутация запросов путем замены случайно выбранного слова на его синоним.
10. Формирование объединенной популяции. Используется элитарный отбор. Создается промежуточная популяция из родителей и их потомков. В результате выбирается N запросов с лучшими значениями целевой функции.
11. Остановка алгоритма при условии стабильности популяции.
В настоящее время все большее распространение получают нетрадиционные методы моделирования сложных систем на основе экспериментальных данных
, в частности метод группового учета аргументов (МГУА) [8], предполагающий в процессе идентификации моделей многократную обработку различных частей одних и тех же (входных данных. Теория самоорганизации моделей, положенная в основу МГУА, отвергает путь расширения и усложнения модели, увеличения объема входных данных, постулируя при этом существование опти-мального, ограниченного размера области моделирования и единственной модели оптимальной сложности. Их можно найти при помощи самоорганизации, т.е. перебора многих моделей-претендентов (кон-курирующих моделей) по целесообразно выбранным критериям.
В отличие от традиционных методов структурно-параметрической идентификации, использующих критерий среднеквадратической ошибки, который является внутренним (рассчитанным по всем точкам исходной выборки), индуктивный метод самоорганизации основан на внешних критериях, для определения которых применяются входные данные, не использованные в процессе построения модели. Любой внутренний критерий сравнения конкурирующих моделей приводит к ложному правилу: чем сложнее структура модели, тем она точнее.
Согласно МГУА исходные данные делятся на обучающую, проверочную и экзаменационную последовательности. В качестве внешних используются критерии регулярности, минимума смещения и баланса переменных. Алгоритмы МГУА подразделяются на однорядные и многорядные. В однорядных (комбинаторных) алгоритмах реализуется процедура полного перебора всех возможных вариантов модели, которые можно получить из заданного полного описания. Комбинаторные алго-ритмы МГУА применяются для решения определенных и переопре-деленных задач структурно-параметрической идентификации, в которых число параметров модели меньше объема выборки. Для решения недо-определенных задач используются многорядные алгоритмы МГУА. При этом итерационные генераторы реализуют специальную процедуру перцептронного типа для усложнения структуры моделей с помощью учета небольших групп переменных.
Как правило, в комбинаторных алгоритмах МГУА постулируется полиномиальная модель. В блоке перебора моделей выполняются следующие основные операции:
идентификация двоичного вектора, единичные элементы которого указывают структуру частной модели;
формирование соответствующей системы нормальных уравнений и ее решение;
вычисление значений внешних критериев; текущий отбор заданного числа лучших моделей.
Задача структурно-параметрической идентификации модели опти-мальной сложности решается в два этапа: из полного набора моделей различной сложности отбирается по одному из внешних критериев N лучших структур, параметры которых затем пересчитываются по всей выборке. На основе сравнительного анализа полученных моделей конечный пользователь осуществляет выбор лучшей.
11.4. Интегрированные экспертные системы
Современные тенденции интеграции исследований в различных областях привели к необходимости совмещения семантически разнородных объектов, моделей, методологий и технологий, что породило принципиально новые классы задач и новые архитектуры ИИС. Интегрированная ЭС (ИЭС) включает собственно ЭС и некоторый программный компонент (ПК), обеспечивающий решение формализованный составляющей задачи и включающий пакеты прикладных программ (ППП), системы автоматизированного проектирования (САПР), автоматизированные системы научных исследований (АСНИ), обучающие системы и др. Основу технологии, ориентированной на построение ИЭС, составляют концептуальные модели, базирующиеся на эвристических знаниях. Анализ существующих архитектур ИЭС осуществляется на основе системного анализа с использованием многоуровневой модели интеграции.
Процессы интеграции в ИЭС с позиций многоуровневой модели могут быть рассмотрены с точки зрения следующих аспектов:
- поверхностная и глубинная интеграции различных компонентов, реализующих как решение неформализованных задач, так и формализованных. При этом поверхностная интеграция достигается с помощью любого способа обмена информацией между компонентами ИЭС, а глубинная интеграция связана с модификацией любого из компонентов системы путем включения в него функций других компонентов;
- средний уровень интеграции – это интеграция (функциональная, структурная, концептуальная), связанная с используемыми концепциями ИЭС и их компонентов;
- нижний уровень интеграции – это информационная, программная и техническая интеграция, основанная на применяемых технологиях, инструментальных средствах и платформах.
Наибольший интерес представляет средний уровень, на котором осуществляется распределение функций между ЭС и ПК. При этом структурная интеграция компонентов может быть реализована в следующих вариантах:
- полное включение ПК в ЭС;
- параллельное использование ЭС и ПК для решения одной и той же задачи;
- частичное включение ЭС и ПК друг в друга;
- организация интеллектуального интерфейса между ЭС и ПК.
С позиции верхнего уровня можно выделить подклассы с поверхностной и глубинной интеграцией компонентов. Самым высоким уровнем интеграции ИЭС является полная интеграция, заключающаяся в соединении лучших качеств компонентов ЭС и ПК и создании совершенно новых систем. Следует отметить, что ИЭС шире, чем понятие гибридной интеллектуальной системы и совпадает только в случае полной интеграции компонентов в системе.
в одном решении.
При разработке генетических алгоритмов преследуются две цели:
абстрактное и формальное объяснение процессов адаптации в ес-тественных системах;
проектирование искусственных программных систем, воспроизво-дящих механизм функционирования естественных систем.
Основные отличия генетических алгоритмов оптимизации:
используются не параметры, а закодированные множества па-раметров;
поиск осуществляется не из единственной точки, а из популяции точек;
в процессе поиска используются значения целевой функции, а не ее приращения;
применяются вероятностные, а не детерминированные правила по-иска и генерации решений;
выполняется одновременный анализ различных областей простран-ства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счет объединения квази-оптимальных решений из разных популяций [6, 18].
Пример 11.1. Реализация генетического алгоритма для решения задачи оптимизации
Пусть заданы произвольная не дифференцируемая функция f(x, y)
и области существования ее аргументов х = [–10, 25], y = [–5, 5]. Необходимо определить max f(x, y) c использованием генетического алгоритма [6].
На первом этапе создается фонд хромосом С0, С1, С2, …, состоящих из двух генов (х, у), с использованием генератора случайных чисел в со-ответствии с областями существования генов (аргументов) и вычисляются значения функции (табл. 11.1).
Таблица 11.1
| Хромосома | x | y | f(x, y) |
| C0 | –1 | 2 | 0,167 |
| С1 | –2 | 3 | 0,007 |
| С2 | 1,5 | 0 | 0,31 |
| С3 | 0,5 | –1 | 0,44 |
На втором этапе необходимо выбрать пары родителей для рекомбинации на основе значений
f(x, y) (здоровье хромосомы). Здоровье хромосомы С1 самое плохое (функция имеет минимальное значение), поэтому из дальнейшего рассмотрения она исключается. На основе первой пары родителей (С2, С3) формируются новые хромосомы С4 (ХС2, УС3), С5 (ХС3, УС2), а на основе второй пары (С0, С3) формируются хромосомы С6 (ХС3, УС0), С7 (ХС0, УС3), после чего рассчитываются значения здоровья новых хромосом (табл. 11.2).
Таблица 11.2
| Хромосома | x | y | f(x, y) |
| С4 | 1,5 | -1 | 0,24 |
| С5 | 0,5 | 0 | 0,8 |
| С6 | 0,5 | 2 | 0,19 |
| С7 | –1 | –1 | 0,33 |
Лучшее решение в новой популяции (0,8) выше, чем в предыдущей (0,44).
На третьем этапе снова выбираются самые здоровые хромосомы (С4, С5, С7), из которых формируются пары новых родителей, и реализуется процедура рекомбинации и т.д.
Пример 11.2. Решение задачи поиска тематической информации в Интернете с использованием генетического алгоритма
С помощью различных поисковых систем пользователь Интернета осуществляет целенаправленный единичный поиск требуемой информации (описание объекта, явления с заданными свойствами), что, как правило,
не вызывает особых проблем, или тематический поиск, ориентированный на целую категорию скоординированной информации в некотором те-матическом сегменте [14].
При выполнении тематического поиска неизбежно возникает ряд вопросов. Как совместно оценить релевантность документов, найденных разными запросами? Является ли ранжирование результатов корректным с позиций ожиданий пользователей? Все ли результаты, доступные для непосредственной оценки, соответствуют ожиданиям пользователей? Как отфильтровать документы, не относящиеся к искомой тематике? На эти вопросы невозможно однозначно ответить в рамках тривиальных решений.
Для получения эффективного множества поисковых запросов может быть использован подход на основе генетических алгоритмов. Определим основные этапы генетического алгоритма для формирования эффективного множества запросов в случае тематического поиска информации.
1. Подготовка ключевых слов, множество которых формирует поисковый образ документов заданной тематики и задается как параметр алгоритма.
2. Выбор поисковой системы. При этом может быть использована любая поисковая система, имеющая API для доступа к результатам поиска (Bing, Google и др.).
3. Формирование исходной популяции запросов. Каждый поисковый запрос есть совокупность ключевых слов.
4. Выполнение запросов популяции. Результатом является мно-жество дескрипторов найденных документов (заголовок, описание, адрес текста). Множества результатов различных запросов могут пере-секаться.
5. Вычисление целевой функции. Исходная позиция для определения целевой функции предусматривает, что множество эффективных результатов поиска должно формироваться документами, которые удовлетворяют следующим условиям:
находятся в первых позициях ранжированного списка результатов поиска, построенного поисковой системой;
присутствуют в списках результатов, полученных при выполнении как можно большего числа различных запросов;
семантически близки к поисковому образу множества документов заданной тематики.
6. Селекция лучших запросов.
7. Выбор родительских пар запросов. Используется генотипный аутбридинг. При этом первый запрос выбирается случайно, а второй должен быть максимально «далек» от первого.
8. Скрещивание запросов, что реализуется дискретной реком-бинацией или одноточечным кроссинговером – обменом ключевыми словами или их группами между запросами.
9. Мутация запросов путем замены случайно выбранного слова на его синоним.
10. Формирование объединенной популяции. Используется элитарный отбор. Создается промежуточная популяция из родителей и их потомков. В результате выбирается N запросов с лучшими значениями целевой функции.
11. Остановка алгоритма при условии стабильности популяции.
В настоящее время все большее распространение получают нетрадиционные методы моделирования сложных систем на основе экспериментальных данных
, в частности метод группового учета аргументов (МГУА) [8], предполагающий в процессе идентификации моделей многократную обработку различных частей одних и тех же (входных данных. Теория самоорганизации моделей, положенная в основу МГУА, отвергает путь расширения и усложнения модели, увеличения объема входных данных, постулируя при этом существование опти-мального, ограниченного размера области моделирования и единственной модели оптимальной сложности. Их можно найти при помощи самоорганизации, т.е. перебора многих моделей-претендентов (кон-курирующих моделей) по целесообразно выбранным критериям.
В отличие от традиционных методов структурно-параметрической идентификации, использующих критерий среднеквадратической ошибки, который является внутренним (рассчитанным по всем точкам исходной выборки), индуктивный метод самоорганизации основан на внешних критериях, для определения которых применяются входные данные, не использованные в процессе построения модели. Любой внутренний критерий сравнения конкурирующих моделей приводит к ложному правилу: чем сложнее структура модели, тем она точнее.
Согласно МГУА исходные данные делятся на обучающую, проверочную и экзаменационную последовательности. В качестве внешних используются критерии регулярности, минимума смещения и баланса переменных. Алгоритмы МГУА подразделяются на однорядные и многорядные. В однорядных (комбинаторных) алгоритмах реализуется процедура полного перебора всех возможных вариантов модели, которые можно получить из заданного полного описания. Комбинаторные алго-ритмы МГУА применяются для решения определенных и переопре-деленных задач структурно-параметрической идентификации, в которых число параметров модели меньше объема выборки. Для решения недо-определенных задач используются многорядные алгоритмы МГУА. При этом итерационные генераторы реализуют специальную процедуру перцептронного типа для усложнения структуры моделей с помощью учета небольших групп переменных.
Как правило, в комбинаторных алгоритмах МГУА постулируется полиномиальная модель. В блоке перебора моделей выполняются следующие основные операции:
идентификация двоичного вектора, единичные элементы которого указывают структуру частной модели;
формирование соответствующей системы нормальных уравнений и ее решение;
вычисление значений внешних критериев; текущий отбор заданного числа лучших моделей.
Задача структурно-параметрической идентификации модели опти-мальной сложности решается в два этапа: из полного набора моделей различной сложности отбирается по одному из внешних критериев N лучших структур, параметры которых затем пересчитываются по всей выборке. На основе сравнительного анализа полученных моделей конечный пользователь осуществляет выбор лучшей.
11.4. Интегрированные экспертные системы
Современные тенденции интеграции исследований в различных областях привели к необходимости совмещения семантически разнородных объектов, моделей, методологий и технологий, что породило принципиально новые классы задач и новые архитектуры ИИС. Интегрированная ЭС (ИЭС) включает собственно ЭС и некоторый программный компонент (ПК), обеспечивающий решение формализованный составляющей задачи и включающий пакеты прикладных программ (ППП), системы автоматизированного проектирования (САПР), автоматизированные системы научных исследований (АСНИ), обучающие системы и др. Основу технологии, ориентированной на построение ИЭС, составляют концептуальные модели, базирующиеся на эвристических знаниях. Анализ существующих архитектур ИЭС осуществляется на основе системного анализа с использованием многоуровневой модели интеграции.
Процессы интеграции в ИЭС с позиций многоуровневой модели могут быть рассмотрены с точки зрения следующих аспектов:
- поверхностная и глубинная интеграции различных компонентов, реализующих как решение неформализованных задач, так и формализованных. При этом поверхностная интеграция достигается с помощью любого способа обмена информацией между компонентами ИЭС, а глубинная интеграция связана с модификацией любого из компонентов системы путем включения в него функций других компонентов;
- средний уровень интеграции – это интеграция (функциональная, структурная, концептуальная), связанная с используемыми концепциями ИЭС и их компонентов;
- нижний уровень интеграции – это информационная, программная и техническая интеграция, основанная на применяемых технологиях, инструментальных средствах и платформах.
Наибольший интерес представляет средний уровень, на котором осуществляется распределение функций между ЭС и ПК. При этом структурная интеграция компонентов может быть реализована в следующих вариантах:
- полное включение ПК в ЭС;
- параллельное использование ЭС и ПК для решения одной и той же задачи;
- частичное включение ЭС и ПК друг в друга;
- организация интеллектуального интерфейса между ЭС и ПК.
С позиции верхнего уровня можно выделить подклассы с поверхностной и глубинной интеграцией компонентов. Самым высоким уровнем интеграции ИЭС является полная интеграция, заключающаяся в соединении лучших качеств компонентов ЭС и ПК и создании совершенно новых систем. Следует отметить, что ИЭС шире, чем понятие гибридной интеллектуальной системы и совпадает только в случае полной интеграции компонентов в системе.