Содержание к диссертации
Введение
ГЛАВА 1. Интеллектуальные автоматизированные обучающие системы: этапы развития, классификация и проблемы создания 10
1.1. Основные теории, лежащие в основе построения автоматизированных систем обучения 11
1.2. Этапы развития АОС 13
1.3. Классификация АОС 15
1.4. Структура интеллектуальной обучающей системы и функциональное назначение ее элементов 21
1.5. Классификация интеллектуальных обучающих систем 29
1.6. Примеры ИОС 32
1.8. Программный контроль знаний 37
1.9. Проблемы, возникающие при проверке знаний 39
1.10. Задача автоматизированного проектирования контролирующих курсов 40
1.11. Цели и задачи диссертационной работы 43
Выводы 44
ГЛАВА 2. Моделирование и алгоритмы работы процесса управления контролем знаний 45
2.1. Структура системы проверки знаний 45
2.2. Основные понятия сетей Петри 50
2.3. Моделирование процесса контроля знаний 53
2.4. Цели контроля ...56
2.5. Модель обучаемого 57
2.6. Методы управления контролем 61
2.7. Алгоритм управления процессом контроля 64
2.7.1. Алгоритм «Краткий опрос» 66
2.7.2. Алгоритм «Полный опрос» 67
2.7.3. Адаптация процесса контроля к индивидуальным особенностям опрашиваемого 69
2.7.4. Алгоритм создания множества входных (выходных) элементов 71
2.7.5. Алгоритм проверки перехода на активность 72
Выводы 75
ГЛАВА 3. Программный контроль знаний 76
3.1. Статистические методы обработки ответов , 76
3.2. Использование методов искусственного интеллекта 80
3.3. Грубые функции принадлежности 87
3.4. Алгоритм принятия решения 91
3.5. Тонкая настройка нечеткой базы знаний 91
3.6. Генетические алгоритмы 92
3.7. Применение генетического алгоритма для настройки подсистемы выставления оценок 95
Выводы 97
ГЛАВА 4. Программная реализация системы контроля знаний 98
4.1. Требования к программе 98
4.2. Технические и программные средства для создания и функционирования интеллектуальной контролирующей системы 99
4.3. Структура данных 100
4.4. Программная реализация системы управления контролем знаний 103
4.4.1. Описание структуры 103
4.4.2. Используемые методы 107
4.4.3. Алгоритм программы 107
4.4.4. Используемые технические средства 108
4.4.5. Вызов и загрузка І08
4.4.6. Входные данные 108
4.4.7. Выходные данные 109
4.5. Архитектура подсистемы приобретения знаний 109
4.6. Программная реализация подсистемы создания контролирующих курсов 112
4.6.1. Описание структур . 112
4.6.2. Используемые методы „ 114
4.6.3. Алгоритм программы. 115
4.6.4. Функциональные ограничения 117
4.6.5. Используемые технические средства 117
4.6.6. Вызов и загрузка , 117
4.6.7. Входные данные 118
4.6.8. Выходные данные 118
4.7. Система автоматизированного контроля знаний 119
4.8. Исследование работы программы контроля 120
4.8.1. Настройка системы выставления оценок , 120
4.8.2. Характеристики процесса контроля 128
4.8.3. Статистика по вопросам 135
4.9. Применение автоматизированной системы контроля знаний к реализации учебной темы "Логические основы ЭВМ". Результаты внедрения в учебный процесс 138
Выводы 141
Заключение 142
Литература
- Структура интеллектуальной обучающей системы и функциональное назначение ее элементов
- Моделирование процесса контроля знаний
- Использование методов искусственного интеллекта
- Технические и программные средства для создания и функционирования интеллектуальной контролирующей системы
Введение к работе
Актуальность исследований. Обучение является древнейшим процессом человеческой деятельности. Необходимость значительного повышения эффективности обучения привела к тому, что ряд функций преподавателя передается компьютеру. Внедрение новых информационных технологий в обучение открывает широкие возможности к более качественной подготовке специалистов и индивидуализации обучения. Анализ работ в области создания автоматизированных обучающих систем (АОС) [3, 5, 7-11, 14, 15, 20, 46-48, 62, 66, 68, 72, 75, 77, 79, 80, 90-92, 107, 112-114, 125, 127-134] показал, что развитие систем идет по пути интеллектуализации управления процессом обучения, а механизм контроля плавно перетекает в механизмы анализа высказываний обучаемого. В настоящее время наиболее перспективным является развитие АОС, применяющих методы искусственного интеллекта для управления процессом обучения, - интеллектуальных обучающих систем (ИОС). ИОС способны «понимать» преподаваемый предмет и обучаемого, адаптироваться к его знаниям и особенностям, обеспечивать гибкий процесс обучения.
Анализ работ в области создания ИОС [3, 5, 7-11, 14, 15, 20, 46-48, 62, 66, 68, 72, 75, 77, 79, 80, 90-92, 107, 112-114, 125, 127-134] позволил выявить следующие недостатки:
использование только определенной предметной области;
стратегия управления не зависит от логической структуры курса;
все системы используются в основном только для обучения или диагностики знаний обучаемых;
контроль знаний используется чаще всего для выбора следующего управляющего воздействия или задачи;
при оценивании знаний не учитываются нечеткость, неопределенность данных о результате контроля.
5 Два последних недостатка особенно значимы, так как контроль знаний учащихся является одним из важных этапов обучения и средством обратной связи между преподавателем и обучаемым. Насыщенность занятий новым материалом не позволяет проводить опрос всех учащихся в течение одного занятия и оценивать уровень освоения ими материала. Решить эту проблему помогут интеллектуальные контролирующие системы. Использование интеллектуальных систем проверки знаний позволяет поддерживать нужный образовательный уровень обучаемых, увеличивает возможности преподавателя при проверке знаний. Программный контроль требует от студента кратких ответов, что позволяет сократить время, необходимое для оценки степени подготовки. В свою очередь, оперативная проверка знаний дает возможность немедленно скорректировать и восполнить знания, что ведет к увеличению объема и улучшению качества знаний. Применение интеллектуальных систем проверки знаний, предназначенных для проведения адаптивных опросов, сложность задания в которых изменяется в зависимости от ответов обучаемых, позволяет:
значительно сократить временные рамки, отводимые на обработку результатов проверки знаний;
автоматизировать процесс обработки ответов;
свести к минимуму субъективное мнение преподавателя на результаты контроля.
Цель диссертационной работы состоит в разработке методик, алгоритмов и инструментальных программных средств для проведения адаптивного контроля знаний в условиях неопределенности данных о состоянии знаний обучаемого с использованием логической структуры курса.
Для достижения цели необходимо решить следующие задачи:
- разработать модели представления знаний о процессе контроля;
- разработать алгоритмы управления контролем на основе моделей
представления знаний;
- разработать алгоритм оценивания знаний;
разработать структуру подсистемы приобретения знаний;
определить архитектуру контролирующей системы и функциональное назначение ее компонент;
реализовать компоненты интеллектуальной системы контроля знаний и подсистемы приобретения знаний.
Методы исследования. Разработка и исследования проводились на основе теории сетей Петри, теории нечетких множеств и нечеткой логики, теории принятия решения, теории экспертных систем, теории генетических алгоритмов, теории структур и баз данных, технологий модульного и объектно-ориентированного программирования,
Научная новизна заключается в следующем:
I) для решения задач оценивания качества знаний предложено вместо статистических методов обработки ответов применять методы искусственного интеллекта, которые позволяют при построении математической модели оценки качества знаний использовать логический опыт квалифицированных преподавателей, принимающих оценочные решения;
' 2) предложено в структуру интеллектуальной обучающей системы помимо экспертных систем (ЭС) по решению задач, диагностике ошибок и управлению обучением включать ЭС по выставлению оценок;
предложена структура построения экспертной системы, использующей для выставления оценки нечеткую базу знаний;
предложена методика настройки ЭС с помощью генетического алгоритма;
разработаны алгоритмы управления процессом контроля, позволяющие проводить контроль в различных предметных областях и адаптироваться к уровню знаний каждого обучаемого.
Практическая ценность работы. Осуществлена программная реализация интеллектуальной контролирующей системы с настраиваемой экспертной подсистемой выставления оценок, использующая указанные выще алгоритмы и методы. Для представления знаний в моделях предметной области,
7 обучаемого и управления процессом контроля использовалась модифицированная нечеткая сеть Петри. В Рязанском филиале Военного университета связи с помощью разработанной системы был создан контролирующий курс по дисциплине «Вычислительная техника». Проведенный с помощью данного курса контроль знаний показал, что предложенные алгоритмы и методы могут использоваться:
при проектировании ЭС, т.е. такого управления частными показателями, при которых интегральный показатель качества будет принимать желаемое значение;
для построения экспертных систем, которые способны оценить качество интеллектуальной деятельности;
для управления процессом адаптивного контроля знаний, при этом могут использоваться различные стратегии выбора контролирующего воздействия;
для поддержания различных форм контроля: текущего, промежуточного, итогового.
На защиту выносятся:
алгоритмы управления процессом контроля на основе используемых модели предметной области и модели обучаемого;
методика построения экспертной подсистемы, использующей для выставления оценки нечеткую логику;
методика и алгоритм настройки нечеткой подсистемы выставления оценки с помощью генетического алгоритма.
Достоверность полученных в диссертационной работе результатов подтверждается использованием положений и понятий теории экспертных систем, нечеткой логики, генетических алгоритмов; разработкой действующего программного обеспечения и внедрением полученных результатов.
Реализация и внедрение результатов. В рамках диссертационной работы разработана и внедрена интеллектуальная система контроля знаний, которая имеет свидетельство об официальной регистрации программы для
8 ЭВМ в РОСПАТЕНТ. Разработанные алгоритмы и инструментальные программные средства управления процессом контроля использованы в НИР «Исследование возможностей современных компьютерных технологий и инструментальных средств для проведения лабораторных работ по дисциплине «ВТ и ИГ», шифр «Средства», выполненной на кафедре «Автоматизированных систем управления войсками и связи» Рязанского филиала Военного университета связи, и внедрены в учебный процесс Рязанского филиала Военного университета связи (дисциплина «Вычислительная техника и информационные технологии») и Рязанского военного автомобильного института (дисциплина «Информатика»).
Апробация работы. Материалы докладывались и обсуждались на 4 конференциях:
межвузовской научно-методической конференции «Творческий подход к реализации государственного образовательного стандарта высшего профессионального образования. VIII Рязанские педагогические чтения», РГПУ, 2 февраля 2001 г., г. Рязань;
13-й межвузовской научно-практическая конференции, РВАИ, 24-25 февраля, 2002 г., г. Рязань;
14-й межвузовской научно-практическая конференции, РВАИ, 27-28 февраля, 2003 г., г. Рязань;
12-й международной научно-технической конференции, РГРТА, 13-14 января, 2004 г., г. Рязань.
По материалам диссертации опубликовано 18 работ, из них 5 в соавторстве. В их числе 1 статья в межвузовском сборнике, 2 статьи в вузовских сборниках, 12 тезисов докладов на конференциях, 3 свидетельства об официальной регистрации программ в РОСПАТЕНТ.
В первой главе проводится анализ состояния работ в области создания интеллектуальных обучающих систем, дается их классификация. Рассматриваются архитектура ИОС, функциональное назначение ее компонент. Проводится анализ существующих ИОС, определяются их недостатки и нере-
шенные проблемы. Проводится анализ проблем в области контроля знаний. Ставятся цели и задачи диссертационной работы. В качестве разрабатываемой выбирается система управляющего типа.
Во второй главе разрабатываются структура интеллектуальной контролирующей системы и функциональное назначение ее компонент. Рассматриваются модели обучаемого, предметной области и управления процессом контроля. Для представления знаний использовалась нечеткая сеть Петри. На основе разработанных моделей разработаны алгоритмы управления процессом контроля. Предложен алгоритм адаптации к уровню знаний обучаемых.
В третьей главе рассматриваются имеющиеся методы контроля знаний. Предложена методика построения нечеткой системы выставления оценки. Рассмотрена настройка данной системы с помощью генетического алгоритма. Рассмотрена задача автоматизированного проектирования контролирующих курсов. Определена структура и функции подсистемы приобретения знаний. Рассмотрена возможность увеличения числа вопросов за счет генерации условий.
В четвертой главе рассматриваются требования к программной реализации системы. Основные требования - выполнение всех функций управления контролем знаний; объективное выставление оценки; максимально удобный, «дружественный» интерфейс пользователей. Рассматриваются технические и программные средства для создания и функционирования интеллектуальной контролирующей системы и ее подсистем. Приведены результаты исследования работы интеллектуальной системы контроля знаний и результаты внедрения системы в учебный процесс.
Структура интеллектуальной обучающей системы и функциональное назначение ее элементов
Для поддержки «разумного» процесса обучения человек-педагог использует специальные знания трех основных типов: 1) знания о предмете обучения (чему учить); 2) знания о стратегии и методах обучения (как учить); 3) знания об обучаемом (как определить его успехи, заблулсдения). К этим специальным типам знаний можно добавить обычные «человеческие» умения общаться — сказать что-нибудь обучаемому, понять его ответ. В традиционных АОС фрагменты этих знаний, необходимые для реализации конкретной части курса обучения, были жестко встроены в текст его отдельных кадров. В ИОС необходимые знания явно выделены и представлены с помощью различных методов и технологий искусственного интеллекта. Используя эти знания ИОС способна выполнять различные функции педагога (помогать в процессе решения задач, определять причину ошибок обучаемого, выбирать оптимальное учебное воздействие) почти так же разумно, как это делает человек [7-10].
Идеальная ИОС должна уметь представлять и использовать все перечисленные типы знаний, что позволяет определить структуру идеальной ИОС в виде набора взаимодействующих модулей (рис. 1.2), в каждом из которых сосредоточены знания одного типа [9].
Модуль—эксперт проблемной области сосредотачивает фактографические, процедурные и другие знания об изучаемой проблемной (предметной) области (ПО), используемые в процессе обучения. Фактографические знания дают модулю возможность предъявлять обучаемому информацию по изучаемой ПО, отвечать на его вопросы. Структура представления фактографических знаний обычно отражает структуру изучаемой ПО, образуя информационную модель предметной области (МПО). Процедурные знания позволяют модулю-эксперту самому решать задачи, которые ИОС предлагает обучаемому, помогать обучаемому в процессе решения, проверять его реше ниє. Процедурные знания могут быть представлены в специальной продукционной форме в виде базы знаний.
Модуль анализа действий обучаемого представляет и поддерживает в актуальном состоянии необходимые системе знания о конкретном обучаемом.
Структура идеальной ИОС Для отражения этих знаний используется динамическая модель обучаемого (МО). В состав МО входят данные о состоянии знаний обучаемого, степени освоения им понятий, а также его личностные характеристики. Модель обучаемого постоянно обновляется в ходе обучения в соответствии с изменением отражаемых ею характеристик обучаемого. В идеальной ИОС модель обучаемого используется всеми модулями системы для адаптации их работы к конкретному обучаемому.
Модуль-педагог содержит в себе знания эксперта-педагога, касающиеся организации и поддержки целенаправленного процесса обучения. Совокупность таких знаний называют стратегией обучения. На основании этих знаний и модели обучаемого модуль-педагог явно или неявно осуществляет управление процессом обучения. Модуль-педагог определяет наиболее подходящую в данный момент подцель обучения и поддерживает ее реализацию, очередной изучаемый фрагмент курса, выбирает или генерирует очередную учебную задачу. При самостоятельной работе обучаемого модуль наблюдает за его действиями, решая, когда следует вмешаться и что при этом сказать.
Модуль интерфейса объединяет знания, необходимые для поддержки взаимодействия с обучаемым. Используя эти знания, он должен доносить до обучаемого в удобной и понятной форме то, что хотят сообщить другие модули, а также переводить запросы и ответы обучаемого в принятое другими модулями представление. Многие ИОС позволяют поддерживать диалог на ограниченном естественном языке. В этом случае модуль интерфейса должен включать в себя языковые знания, достаточные для понимания обучаемого и ответов ему в естественной форме.
Приведенная схема описывает идеальную ИОС. Являясь системой, использующей методы искусственного интеллекта, ИОС имеет архитектуру, общую для интеллектуальных программных систем [103] (рте. 1.3).
Система содержит 13 функциональных блоков, часть которых может быть объединена в функциональные группы. Одной такой группой является интеллектуальный интерфейс, обеспечивающий эффективную связь всей системы с пользователем и внешней средой.
Центральным блоком интеллектуальной системы является решатель -вычислительная система, состоящая из одного или нескольких процессоров, связанная с базами данных и знаний, а также с остальными блоками системы. Целенаправленная работа системы обеспечивается системой планирования, хранящей априорно введенные цели, а также запоминающей новые цели, полученные с помощью системы обучения. Последняя участвует также в формировании новых знаний, возникающих в ходе анализа взаимодействия интеллектуальной системы с внешней средой.
Моделирование процесса контроля знаний
Применим к разработке интеллектуальной контролирующей системы методику, изложенную в [66, 67]. Введем следующие понятия.
Под контролирующим воздействием (KB) будем понимать вопросы или задачи (множество V) для контроля и ответы и решения (множество О) для них, касающиеся каких-то определенных понятий предметной области (множества Xs). Т.е. каждое KB характеризуется следующим набором: Uran= m, п, V, О, Xs , где m - номер уровня опроса и п - номер вопроса в уровне образуют для каждого KB уникальное имя. Все контролирующие воздействия занесены в базу знаний и составляют множество KB: lMUmn}, где m=l, ..., М (число уровней); п=1, ... , N (число вопросов в каждом уровне).
Множество Xs состоит из подмножества понятий (Хвх), которые уже должны быть усвоены до ответа на вопрос (знания данных вопросов прокон тролированы), и подмножества понятий (Хк), которые контролируются данным KB (рис. 2.2 ): Xs—Хвх+Хк.
Эти подмножества задаются преподавателем при заполнении базы знаний. . Под Xi будем понимать множество всех понятий предметной области. Как Хг обозначим нечеткое подмножество необходимых для контроля понятий. N Х2 = R2 (A ) = Z х2к / х\к х2к є [ОД] k=l Элемент Х2к е[1 0] характеризует степень принадлежности понятия : к множеству необходимых знаний. Как Хз обозначим нечеткое подмножество проконтролированных понятий. N Хъ = (10=1 3Jt j Чк хЪк є [ОД] к=\
Элемент дгзА: е [ОДЗ соответствует степени познания обучаемым понятия . и называется коэффициентом уверенности в знаниях обучаемого. Его можно определить как x3k=Wi Mk/Nb, (2.1) где Мк - количество правильных ответов на вопросы, касающиеся к-го понятия; Nk — задано вопросов к k-му понятию; Wj - сложность заданного к k-му понятию і-го вопроса.
Коэффициент W; задается преподавателем при создании контролирующего курса, либо его можно определить как wrl-v/Vi, (2.2) где V; - количество обучаемых, правильно ответивших на i-ый вопрос; V; - число, показывающее сколько раз задавался i-ый вопрос.
При представлении предметной области с помощью сети Петри множество понятий отображается во множество позиций, а множество контролирующих воздействий - во множество переходов. Так как позиции сети связаны с нечеткими подмножествами Xj и Х2, а переходы - с нечеткими отношениями, то мы имеем нечеткую сеть Петри,
Начальная маркировка сети Цо показывает, что должен знать обучаемый до начала контроля.
Текущая маркировка сети i[ показывает степень знания обучаемым к-го понятия в данный момент времени (коэффициент уверенности).
Для определения маркировки позиций осуществляется переход от нечеткой сети Петри к обычной. Для этого для каждой позиции определяется порог Efc = yx2k; характеризующий какого уровня знания данного понятия должен достичь обучаемый. Если значение коэффициента уверенности х3к больше порога Еь то k-ю позицию сети Петри можно считать маркированной, а соответствующее понятие - усвоенным, т.е. [О, хзк Ек.
Переход сети Петри запускается (подается KB) в том случае, если все входные позиции помечены (понятия проконтролированы), а среди выходных есть хотя бы одно не помеченное (понятие не проконтролировано). После запуска перехода меняется маркировка сети: - маркировка входных позиций не меняется (понятия уже проконтро лированы); - выходные позиции маркируются; - меняются коэффициенты уверенности в знаниях обучаемого (по формуле 2.1).
Данная модель предметной области может быть использована: - для управления процессом контроля; - для идентификации знаний обучаемого в любой момент времени, т.е. в качестве модели обучаемого.
Использование методов искусственного интеллекта
Применение методов искусственного интеллекта, в частности нечеткой логики, для решения задач оценки качества знаний позволяет при построении математической модели оценки качества знаний использовать логический опыт квалифицированных преподавателей, принимающих оценочные решения. Автором диссертационной работы предлагается помимо экспертных систем по диагностике ошибок, решению задач и управлению учением (рис. 1.4) использовать экспертную систему выставления оценки. При формализации знаний экспертов удобно рассматривать входы и выходы экспертных правил как лингвистические переменные. Адекватность таких экспертных правил не изменяется при незначительных изменениях значений переменных. Совокупность экспертных правил составляет нечеткую базу знаний. Входы и выходы формализуются в виде нечетких множеств, заданных на соответствующем универсальном множестве с помощью функций принадлежности. Совокупность экспертных правил ЕСЛИ-ТО можно рассматривать как набор экспертных точек в пространстве «входы-выход». Применение аппарата нечеткого логического вывода помогает восстанавливать по этим точкам
многомерную поверхность, которая позволяет получать значения выхода при различных значениях входных переменных. Однако никто не может гарантировать совпадение результатов нечеткого вывода (теории) и экспериментальных данных. Поэтому необходима настройка системы путем обучения по экспертным данным. Суть настройки состоит в подборе таких весов правил ЕСЛИ-ТО и таких параметров функций принадлежности, которые минимизируют различие между желаемым (экспериментальным) и модельным (теоретическим) поведением системы. Настройка формулируется как задача нелинейной оптимизации, решаемая различными методами, в частности, с применением генетических алгоритмов. Построение экспертных систем, которые основаны на данной методике, дает возможность не только оценить качество интеллектуальной деятельности, но и создает условия для ее проектирования, т.е. такого управления частными показателями, при которых интегральный показатель качества будет принимать желаемое значение.
Процесс построения экспертной системы с нечеткой логикой (нечеткой экспертной системы) следующий [87, 119, 123, 124]:
1. Определение характеристик системы. Определяются входные и выходная переменные идентифицируемого объекта (с непрерывным или дискретным выходом). В качестве переменных могут использоваться и лингвистические переменные [23].
2. Формирование дерева логического вывода. Определяется структура зависимости выходной переменной от входных.
3. Определение функций принадлежности лингвистических термов. На этом шаге определяются модели функции принадлежности, используемые для формализации термов - оценок переменных.
4. Определение экспертных правил ЕСЛИ-ТО, описывающих поведение объекта. Экспертные правила ЕСЛИ-ТО вносятся в соответствующие матрицы (таблицы) знаний.
5. Настройка нечеткой экспертной системы путем решения задач оптимизации с использованием обучающей выборки.
В результате нечеткого логического вывода получаются функции принадлежности выходной переменной каждому из классов решений и интерпретированный результат.
В данной диссертационной работе считается, что оценка качества знаний (D) базируется на трех параметрах, заданных с помощью лингвистических переменных: КОЛИЧЕСТВО_ПРАВИЛЬНЬ1Х_ОТВЕТОВ_НА_ОЦЕН-КУ (Xl) , КОЛИЧЕСТВО_ОБРАІІДіНИЙ_К„ПОМОЩИ (х2) и ВРЕМЯ_ОТ-ВЕТА (х3). Лингвистические переменные оцениваются нечеткими термами: - КОЛИЧЕСТВОшПРАВИЛЬНЫХ_ОТВЕТОВ_НА_ОЦЕНКУ - хг - отлично (5), хорошо (4), удовлетворительно (3) и неудовлетворительно (2); - ВРЕМЯ_ОТВЕТА - х3 - малое (м), среднее (с), большое (б), очень большое (об); - КОЛИЧЕСТВО_ОБРАЩЕНИЙ_КшПОМОЩИ - х2 - отсутствует (о), мало (мл), много (мн); - ОЦЕНКА_КАЧЕСТВА_ЗНАНИЯ - D - отлично (о), хорошо (х), удовлетворительно (у), неудовлетворительно (ну).
Технические и программные средства для создания и функционирования интеллектуальной контролирующей системы
Оптимизация является важнейшим этапом решения задач идентификации. Основные трудности применения классических методов оптимизации нелинейных функций связаны с проблемами локального экстремума (рис.3.5) и «проклятия размерности» (рис.3.6.). Попытки преодоления, указанных проблем привели к созданию теории генетических алгоритмов, которые выращивают оптимальное решение путем скрещивания исходных вариантов с последующей селекцией по некоторому критерию. Излагаемые в этом разделе общие сведения о генетических алгоритмах, базируются на работах [13, 86, 87, 115,116, 118,126].
Генетический алгоритм (ГА) можно рассматривать как одну из разновидностей случайного поиска, которая основана на механизмах, напоминающих естественный отбор и размножение.
Существуют два главных преимущества генетических алгоритмов перед классическими оптимизационными методиками.
1. ГА не имеет значительных математических требований к видам целевых функций и ограничений. Исследователь не должен упрощать модель объекта, теряя ее адекватность, и искусственно добиваясь возможности при-мейения доступных математических методов. При этом могут использоваться самые разнообразные целевые функции и виды ограничений (линейные и нелинейные), определенные на дискретных, непрерывных и смешанных универсальных множествах.
2. При использовании классических пошаговых методик глобальный оптимум может быть найден только в том случае, когда проблема обладает свойством выпуклости. В тоже время эволюционные операции генетических алгоритмов позволяют эффективно отыскивать глобальный оптимум.
Генетический алгоритм представляет собой класс поисковых методов общего назначения, которые комбинируют элементы двух стратегий: эксплуатация наилучшего решения и исследование пространства решении. Использование этих методов позволяет удерживать приемлемый баланс между исследованием и эксплуатацией наилучшего решения. В начале работы генетического алгоритма популяция случайна и имеет разнообразные элементы. Поэтому оператор скрещивания осуществляет обширное исследование пространства решений. С ростом значения функции соответствия получаемых решений оператор скрещивания обеспечивает исследование окрестностей каждого из них. Другими словами, тип поисковой стратегии (эксплуатация наилучшего решения или исследование области решений) для оператора скрещивай определяется разнообразием популяции, а не самим этим оператором.
В отличие от существующих методик, ГА начинает работу с некоторого случайного набора исходных решений, который называется популяцией. Каждый элемент из популяции называется хромосомой и представляет некоторое решение проблемы в первом приближении. Хромосомы эволюционируют на протяжении множества итераций, носящих название поколении. В ходе каждой итерации хромосома оценивается с использованием некоторой меры соответствия, которую называют функцией соответствия. Для создания следующего поколения новые хромосомы, называемые отпрысками, формируются либо путем скрещивания двух хромосом - родителей из текущей популяции, либо путем случайного изменения (мутации) одной хромосомы. Новая популяция формируется путем: 1) выбора согласно функции соответствия некоторых родителей и отпрысков и 2) удаления оставшихся для того, чтобы сохранять постоянным размер популяции. Хромосомы- с большей функцией соответствия имеют больше шансов быть выбранньши (выжить). После нескольких итераций алгоритм сходится к лучшей хромосоме, которая является либо оптимальным, либо близким к оптимальному решением.
Генетический алгоритм осуществляет одновременный поиск по многим направлениям путем использования популяции возможных решений. Переход от одной популяции к другой позволяет избежать попадания в локальный оптимум. Популяция претерпевает нечто наподобие эволюции: в каждом поколения относительно хорошие решения репродуцируются, в то время как относительно плохие отмирают. ГА используют вероятностные правила для определения репродуцируемой или уничтожаемой хромосомы, чтобы направить поиск к областям вероятного улучшения целевой функции.
Общая структура генетического алгоритма имеет вид, где P(t) и c(t) являются родителями и отпрысками из текущей генерации t: Процедура: Генетический алгоритм Начать t:=0; Задать_начальное_значение P(t); Оценить P(t) с помощью функции соответствия; Пока (нет условия_завершения) Скрещивать P(t), чтобы получить C(t); Оценить C(t) с помощью функции соответствия; Выбрать P(t+1) из P(t) и C(t); t:=t+l; конец; конец.
Настройка подсистемы выставления оценок производится в том случае, если преподаватель не согласен с оценкой, выставленной системой (до настройки система для принятия решений (выставления оценки) использует грубые функции принадлежности, заданные экспертом).
Схема применения генетического алгоритма для настройки подсистемы выставления оценок (нечеткой базы знаний) следующая. 1. Провести контроль знаний в нескольких группах. Желательно, чтобы в этих группах были разные преподаватели - данное требование повышает в дальнейшем объективность настройки подсистемы. 2. Ввести выставленные преподавателем оценки в базу знаний. 3. Задать вероятности мутации, скрещивания и инверсии, число особей в популяции (N) и размерность (число бит на каждую настраиваемую величину). Также задается количество эпох - если в течении этого количества эпох приспособляемость популяции не менялась, то алгоритм заканчивает работу. 4. Запустить настройку подсистемы с помощью генетического алго ритма.
