Рабочая программа дисциплины «_Эволюционные алгоритмы »

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Омский государственный университет им. »

Институт математики и информационных технологий

Кафедра прикладной и вычислительной математики

«Утверждаю»

Проректор по учебной работе

_______________

«_____» ______________ 2011 г.

Рабочая программа дисциплины

«_Эволюционные алгоритмы »

цикл ФГОС ВПО ____ М2.Д________ часть ______вариативная___

(Б1, Б2, Б3) (обязательная, вариативная)

входит в число обязательных дисциплин

к следующим образовательным программам

по направлению подготовки магистра

Направление подготовки / специальность	Код направления подготовки / специальности
Прикладная математики и информатика	010400_02.68

г. Омск – 2011 г.

Программа дисциплины «Эволюционные алгоритмы»

Разработана:

_доцент, к. ф.-м. н., доцент_ _______________ ___

(должность, ученая степень и ученое звание) (подпись) ( инициалы, фамилия разработчика)

Программа рассмотрена на заседании кафедры (ученого совета факультета/ института)_____

_____________________________ (протокол № ______ от «_____» _____________ 20___ г.)

Программа разработана в соответствии с федеральным(и) государственным(и) образовательным(и) стандартом(амии) высшего профессионального образования РФ и согласована с факультетами/институтами, осуществляющими профессиональную подготовку по этим направлениям подготовки/специальностям:

Декан/директор Института математики и информационных технологий _________

(название факультета/института) (подпись, Ф. И.О. декана/директора)

1.  Цели освоения дисциплины

Целями освоения дисциплины ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ являются:

1)  изучение основных методов разработки эволюционных алгоритмов и метаэвристик при решении задач оптимизации;

2)  знакомство с теоретическими результатами, описывающими процесс работы генетических и некоторых других эволюционных алгоритмов;

3)  формирование представлений о возможностях использования эволюционных алгоритмов и метаэвристик для решения задач науки, техники, экономики и управления, в том числе, в проектно-конструкторской, управленческой и финансовой деятельности.

2.  Место дисциплины в структуре ООП вуза

Для изучения данной дисциплины необходимо усвоение студентам следующих дисциплин, разделов (или тем): математический анализ, аналитическая геометрия, дискретная математика и математическая логика, теория вероятностей, методы оптимизации, теория графов.

Семестр, в котором изучается дисциплина, может изменяться в зависимости от индивидуальной образовательной траектории магистранта.

3.  Компетенции обучающегося, формируемые в результате освоения дисциплины

Коды компетенций	Название компетенции	Краткое содержание/определение и структура компетенции. Характеристика (обязательного) порогового уровня сформированности компетенции у выпускника	Средства и технологии оценивания
1	2	3	4
ОК	ОБЩЕКУЛЬТУРНЫЕ КОМПЕТЕНЦИИ ВЫПУСКНИКА:
ОК–7	способность и готовность к активному общению в научной, производственной и социально-общественной сферах деятельности	Русский язык: Знает нормы русского литературного языка; особенности устной и письменной форм речи; законы и принципы правильного мышления; структуру аргументации и основные виды аргументов; систему логических приемов и уловок. Умеет продуцировать грамотные, логически стройные, обоснованные высказывания в устной и письменной формах; аргументированно отстаивать свою точку зрения, делать обоснованные выводы. Владеет нормами устной и письменной речи; навыками создания профессионально значимых текстов; культурой правильного мышления; культурой аргументации в диалоге; навыками ведения дискуссий; навыками формирования убеждений посредством аргументации. Пороговый уровень: Знает нормы литературного языка в его устной и письменной формах, основные законы и принципы правильного мышления, структуру аргументации. Умеет делать обоснованные выводы, создавать грамотные и логически выстроенные тексты в устной и письменной формах. Владеет культурой правильного мышления, культурой аргументации в диалоге. Иностранный язык: Знает языковые средства (лексические, грамматические, фонетические), на основе которых формируются и совершенствуются базовые умения говорения, аудирования, чтения и письма; закономерности построения различных типов текстов; подъязык специальности; особенности специальной лексики; стратегии и тактики построения устного дискурса и письменного текста. Умеет организовать общение в соответствии с социальными нормами и правилами характерными для официального общения; использовать формулы речевого общения для выражения различных коммуникативных намерений (согласие/несогласие, удивление, отказы и др.), а также для формулирования соответственной точки зрения; установить и поддержать контакты с зарубежными коллегами с целью обмена профессиональным опытом; получить информацию (на иностранном языке) в профессиональной сфере; выделять специальную информацию в научных текстах; работать с электронными специальными словарями, энциклопедиями и удаленными библиотечными каталогами университетов мира; составлять глоссарии по специальной лексике на иностранном языке; составлять реферат по материалам источников на иностранном языке; осуществлять перевод с учётом закономерностей построения разных типов текстов. Владеет способностью соотносить языковые средства с конкретными ситуациями, условиями и задачами межкультурного речевого общения; способностью взаимодействия в процессе профессиональной деятельности, которая предполагает потребление, передачу и производство профессионально-значимой информации; социальными нормами влияющими на речевое общение между представителями разных культур (правила хорошего тона, нормы общения между представителями разных поколений, полов, классов и социальных групп, языковое оформление определенных ритуалов, принятых в данном обществе); чтением специальной литературы как способом приобщения к последним мировым научным достижениям в своей профессиональной области, как выражением потребности в профессиональном росте (в научных или практических целях); оформлением профессионально-значимых текстов (устных и письменных) включая деловую переписку с соблюдением речевого этикета.	Выступление на семинаре Выступление на семинаре Выступление на семинаре, экзамен Выступление на семинаре, экзамен Выступление на семинаре
ПК	ПРОФЕССИОНАЛЬНЫЕ КОМПЕТЕНЦИИ ВЫПУСКНИКА
ПК–8	способность проводить семинарские и практические занятия с обучающимися, а также лекционные занятия спецкурсов по профилю специализации;	Знает основные законодательные документы, касающиеся системы народного образования, прав и обязанностей субъектов учебного процесса (преподавателей, руководителей, обучающихся и их родителей); сущность процессов обучения и воспитания, их психологические основы; общие вопросы организации педагогических исследований, методы исследований и их возможности, способы обобщения и оформления результатов исследовательского поиска; требования к минимуму содержания и уровню подготовки обучающихся по математике и информатике, устанавливаемые государственным образовательным стандартом; различных подходы к изучению основных тем курса, новых технологий обучения; методов формирования навыков самостоятельной работы и развития творческих способностей и логического мышления учащихся; Умеет ясно, логично излагать содержание нового материала, опираясь на знания и опыт обучающихся; применять дидактические и методические принципы при проектировании учебных занятий по математике и информатике; применять основные методы объективной диагностики знаний обучающихся по предмету и оценивать результаты обучения; применять сервисные программы, пакеты прикладных программ для подготовки учебно-методических материалов; анализировать и применять учебную и учебно-методическую литературу для построения собственного изложения программного материала; выбрать и реализовать образовательную программу, соответствующую уровню подготовленности обучающихся, их потребностям, а также - требованиям общества; создавать и поддерживать благоприятную учебную среду, способствующую достижению целей обучения; развивать интерес обучающихся и мотивацию обучения, формировать и поддерживать обратную связь; разрабатывать и проводить различные по форме обучения занятия, наиболее эффективные при изучении соответствующих тем и разделов программы, адаптировать их к разным уровням подготовки обучающихся; отбирать и использовать соответствующие учебные средства для построения технологии обучения; организовать учебную деятельность обучающихся, управлять ею; вносить коррективы в учебный процесс с учетом результатов педагогической диагностики;	Беседа Беседа
ПК–11	способность работать в международных проектах по тематике специализации	Знает структуру и содержание научно-исследовательской деятельности; современное состояние системы базовых знаний по направлению исследований; современное состояние смежных областей знаний; способы доступа к основным информационным ресурсам в глобальных компьютерных сетях по своей специальности. Умеет анализировать научную проблему (в соответствии с профилем подготовки); формулировать задачи исследования на основе цели; анализировать научные публикации, отражающие состояние данной научной области (в соответствии с профилем подготовки); разрабатывать и использовать программные продукты для выполнения научных исследований; доводить результаты научных исследований до нового либо усовершенствованного результата; работать в научном коллективе; эффективно использовать компьютер для представления в доступной и понятной форме результатов своей профессиональной деятельности; пользоваться электронными библиотеками и каталогами; пользоваться информационно-поисковыми системами; вести деловую переписку по электронной почте; общаться в социальных сетях. Владеет методами научного исследования (в соответствии с профилем подготовки); навыками использования компьютерных сетей для решения профессиональных задач; навыками работы в коллективе. Пороговый уровень: Знает структуру научного знания; структуру научного исследования как деятельности; имеет систему базовых знаний по специальности. Умеет формулировать задачи и применять методы научного исследования, отражающие состояние данной научной области (в соответствии с профилем подготовки). Умеет пользоваться информационно-поисковыми системами. Умеет пользоваться электронными библиотеками и каталогами.	Беседа Беседа Экзамен, тестирование
ПК–12	способность участвовать в деятельности профессиональных сетевых сообществ по конкретным направлениям	Знает структуру и содержание научно-исследовательской деятельности; современное состояние системы базовых знаний по направлению исследований; современное состояние смежных областей знаний; способы доступа к основным информационным ресурсам в глобальных компьютерных сетях по своей специальности. Умеет анализировать научную проблему (в соответствии с профилем подготовки); формулировать задачи исследования на основе цели; анализировать научные публикации, отражающие состояние данной научной области (в соответствии с профилем подготовки); разрабатывать и использовать программные продукты для выполнения научных исследований; доводить результаты научных исследований до нового либо усовершенствованного результата; работать в научном коллективе; эффективно использовать компьютер для представления в доступной и понятной форме результатов своей профессиональной деятельности; пользоваться электронными библиотеками и каталогами; пользоваться информационно-поисковыми системами; вести деловую переписку по электронной почте; общаться в социальных сетях. Владеет методами научного исследования (в соответствии с профилем подготовки); навыками использования компьютерных сетей для решения профессиональных задач; навыками работы в коллективе. Пороговый уровень: Знает структуру научного знания; структуру научного исследования как деятельности; имеет систему базовых знаний по специальности. Умеет формулировать задачи и применять методы научного исследования, отражающие состояние данной научной области (в соответствии с профилем подготовки). Умеет пользоваться информационно-поисковыми системами. Умеет пользоваться электронными библиотеками и каталогами.	Экзамен Беседа Экзамен

4.  Тематический план (с распределением общего бюджета времени)

Общая трудоемкость дисциплины ___3__ зачётнных единиц; ____108___ часов.

Раздел дисциплины, содержание	Объем часов (по видам работы)
Аудиторные занятия	Самостоятельная работа студентов
Всего	в том числе	Всего	в том числе
		Лекции	Практические занятия	Лабораторные занятия		Курсовая работа (проект)	Индивидуальные задания	Другие виды СРС, в т. ч. подготовка к экзамену, экзамену
	26		26		82		46	36
Введение. Терминология и общие принципы эволюционных алгоритмов, области их применения и биологические аналогии.			2
Глава 1. Генетические алгоритмы 1.Схема классического генетического алгоритма, исторический обзор. 2.Примеры приложений классического генетического алгоритма. Способы кодировки решений для различных задач непрерывной и дискретной оптимизации, различные функции приспособленности. 3. Теорема о схемах. Понятие схемы. Формулировка и доказательство теоремы о схемах и ее следствия. Практические рекомендации, основанные на теореме о схемах. Теорема о разнообразии популяции. 4. Модификации генетических алгоритмов. Нестандартные операторы селекции. Сравнение интенсивности различных способов селекции. 5. Схемы воспроизведения (стационарная, популяционная, элитная и другие). Операторы скрещивания и мутации. 6. Задача оптимальной рекомбинации и ее вычислительная сложность. 7. Генетический алгоритм как метод локального поиска.			2 2 2 2 2 2 2		7 7 7 7 7 6 6		4 4 4 4 4 3 3	3 3 3 3 3 3 3
Глава 2. Эволюционные алгоритмы 1. Введение Схема и общий вид операторов эволюционного алгоритма, примеры (генетический алгоритм, эволюционные стратегии). 2. Сходимость эволюционных алгоритмов. Классификация операторов эволюционного алгоритма, марковское свойство. 3. Теорема о сходимости эволюционных алгоритмов, ее применение. 4. Вероятностный поиск с запретами, теорема о его сходимости 5.Сравнение эволюционной стратегии (1+1)-EA с другими эволюционными алгоритмами.			2 2 2 2 2		7 7 7 7 7		4 4 4 4 4	3 3 3 3 3

Форма промежуточного контроля __экзамен__

5.  Содержание дисциплины

Тема 1.

Введение. Терминология и общие принципы эволюционных алгоритмов, области их применения и биологические аналогии.

Тема 2.

Схема классического генетического алгоритма, исторический обзор.

Тема 3.

Примеры приложений классического генетического алгоритма.

Способы кодировки решений для различных задач непрерывной и дискретной оптимизации,

различные функции приспособленности.

Тема 4.

Теорема о схемах. Понятие схемы. Формулировка и доказательство теоремы о схемах и ее следствия. Практические рекомендации, основанные на теореме о схемах. Теорема о разнообразии популяции.

Тема 5.

Модификации генетических алгоритмов.

Нестандартные операторы селекции. Сравнение интенсивности различных способов селекции.

Тема 6.

Схемы воспроизведения (стационарная, популяционная, элитная и другие). Операторы скрещивания и мутации.

Тема 7.

Задача оптимальной рекомбинации и ее вычислительная сложность.

Тема 8.

Генетический алгоритм как метод локального поиска.

Тема 9.

Схема и общий вид операторов эволюционного алгоритма, примеры (генетический алгоритм, эволюционные стратегии).

Тема 10.

Сходимость эволюционных алгоритмов.

Классификация операторов эволюционного алгоритма, марковское свойство.

Тема 11.

Теорема о сходимости эволюционных алгоритмов, ее применение.

Тема 12.

Алгоритмы генетического программирования.

Схемы алгоритмов генетического программирования и их применение.

Тема 13.

Сравнение эволюционной стратегии (1+1)-EA с другими эволюционными алгоритмами.

6.  Оценочные средства для текущего контроля успеваемости, промежуточной аттестации и учебно-методическое обеспечение самостоятельной работы студентов.

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

Критерии выставления оценки на экзамене:

1)  для получения оценки «удовлетворительно» студент должен верно ответить на вопросы по определениям, схемам алгоритмов и формулировкам теорем, без использования литературы или конспектов лекций;

2)  для получения оценки «хорошо», кроме перечисленного в п. 1, студент должен, в основном полно, изложить ответ на два теоретических вопроса билета и справиться с упражнением;

3)  для получения оценки «отлично», кроме перечисленного в п. 1, студент должен полно изложить ответ на два теоретических вопроса билета и справиться с упражнением, небольшие неточности допускаются в одном из вопросов.

Основной формой контроля до экзамена является тестирование (6-я и 11-я недели семестров). Под тестированием понимается следующее: студентам выдаются списки понятий и теорем (несколько вариантов), понятиям следует дать точные определения, теоремам – точные формулировки. Каждый из вариантов содержит одинаковое число вопросов (всего от 10 до 15 вопросов). Ответы студенты дают письменные (либо на специальных бланках, либо на чистых подписываемых ими листах). Время на ответ дается из расчета 2 минуты на вопрос, т. е. от 20 до 30 минут. Включать в тест более 15 вопросов не целесообразно.

Список вопросов для промежуточного и итогового контроля содержится в приложении.

Задания для самостоятельной работы студентов:

изучение учебных пособий; изучение тем и проблем, не выносимых на лекции и семинарские занятия; выполнение исследовательских и творческих заданий; конспектирование статьи

7.  Учебно-методическое обеспечение

Основная литература:

1.  Еремеев алгоритмы и оптимизация // Учебное пособие. – Омск: ОмГУ, 2007. – 46 с. (13 экз)

2.  , Филимонов игр и исследование операций // Учебное пособие. Омск: ОмГУ. 2010. - 122 с. (52 экз)

3.  Ширяев : Учеб. для вузов: в 2 кн.- М. МЦНМО, 2004. - 927 с. (50 экз)

Дополнительная литература:

1.  Батищев алгоритмы решения экстремальных задач // Учебное пособие. - Воронеж: Воронеж. гос. техн. ун-т, 1995. - 69 с.

, , Деменьтьев задачи стандартизации. – Новосибирск: Наука, 1978. - 385 с. , О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. N 3. С. 3-10. http://iitam. . ru/~eremeev/papers. mat/b_e1.ps

4.  Боровков вероятностей. - М.: Наука, 1986. - 431 с.

5.  Вычислительные машины и труднорешаемые задачи. 1982. - 416 с.

6.  Карманов программирование. - М.: Наука, 1986. - 285 с.

7.  Кемени Дж., Снелл Дж. Конечные цепи Маркова. –М.: Наука, 1970. - 272 с.

8.  Колоколов дискретной оптимизации // Учебное пособие. – Омск: ОмГУ, 1984. – 75 с.

«Вероятностные методы локального поиска для задач дискретной оптимизации» // Дискретная математика и ее приложения. – М.: Изд-во центра прикладных исследований при механико-математическм факультете МГУ, 2001. – С 84-117. http://iitam. . ru/~eremeev/papers. sk/kochet. ps

10.  Растригин методы поиска. - М.: Наука, 1968. 376 с.

11.  Нейронные сети, генетические алгоритмы и нечеткие системы. - М.: Горячая линия -- Телеком, 2006. - 452 с.

12.  Искусственный интеллект и эволюционное моделирование. – М.: Мир, 1969. - 230 с.

8. Методические рекомендации (материалы) для преподавателя

·  следует учитывать специфику аудитории (студенты разных курсов имеют различную подготовку);

·  при изложении материала целесообразно его структурировать, выделять наиболее важные моменты;

·  для более эффективного изучения материала на занятиях следует более широко использовать активные методы изучения: проблемное изложение, метод аналогии, анализа и синтеза, обобщения.

Полезно использовать мультимедийный проектор для презентаций такого материала, как определения, схемы алгоритмов и формулировки теорем, однако, доказательства теорем и других утверждений лучше усваиваются при изложении их на доске.

Учебно-методические пособия, разработанные преподавателями университета и направленные на более эффективное освоение данной учебной дисциплины:

Еремеев алгоритмы и оптимизация // Учебное пособие. – Омск: ОмГУ, 2007. – 46 с.

Методические указания для студентов.

·  для более полного понимания изучаемого материала следует задавать вопросы непосредственно на занятиях, чтобы не оставлять «белых пятен» в изучении;

·  полезно (по возможности) посещать все лекции;

·  при подготовке к экзамену следует изложить письменно наиболее существенные понятия, утверждения, формулы по каждому разделу программы;

·  при ответе на теоретические вопросы на экзамене следует постараться раскрыть суть вопроса, полезно сопровождать свой ответ различными примерами.

Тема, раздел	Всего часов	Задания для самостоятельной работы1	Список литературы для подготовки	Форма контроля2
Генетические алгоритмы	26	Изучение учебного пособия Еремеев алгоритмы и оптимизация. Учебное пособие. Омск, ОмГУ, 2008. -48с. Выполнение творческих заданий по самостоятельному доказательству утверждений и теорем, сформулированных на занятиях без доказательства (утверждение о геометрическом смысле кроссинговера, утверждение о свойствах кодировки Грея, оценки дисперсии для операторов селекции и др.). Выполнение творческих заданий по самостоятельной разработке вычислительных схем эволюционных алгоритмов, предложенных в качестве упражнений на занятиях.	Еремеев алгоритмы и оптимизация. Учебное пособие. Омск, ОмГУ, 2008. -48с. Нейронные сети, генетические алгоритмы и нечеткие системы. - М.: Горячая линия -- Телеком, 2006. - 452 с.	индивидуальные беседы и консультации с преподавателем, проверка письменных отчётов
Эволюционные алгоритмы	20	Конспектирование статьи , О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. N 3. С. 3-10. Выполнение творческих заданий по самостоятельному доказательству следствий из теоремы о сходимости эволюционных алгоритмов.	, О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. N 3. С. 3-10.	проверка конспектов статей, индивидуальные беседы и консультации с преподавателем

Приложения к программе

Материалы по формам контроля:

ВОПРОСЫ к экзамену

Классический генетический алгоритм (схема алгоритма, определения операторов) Стандартная двоичная кодировка и кодировка Грэя, их свойства Утверждение о геометрическом смысле кроссинговера Определение схемы, теорема о схемах Теорема о разнообразии популяции Селекция Бэкера, утверждение о сравнении селекции Бэкера и стандартной селекции «методом рулетки», турнирная селекция Популяция с элитой, стационарная схема воспроизведения Генетический алгоритм с турнирной селекцией как метод локального поиска Задача оптимальной рекомбинации, сложность оптимальной рекомбинации для задачи о независимом множестве Утверждение о сводимости задач оптимальной рекомбинации, сложность задачи оптимальной рекомбинации для задачи об упаковке множества Общий вид операторов ЭА и общая схема ЭА Эволюционные стратегии, оператор мутации с нормально распределенным шагом Классификация операторов эволюционных алгоритмов (невырожденная селекция, связывающий оператор воспроизведения, невырожденные и консервативные операторы выживания) Теорема о сходимости эволюционных алгоритмов, ее следствие для положительного оператора воспроизведения Алгоритм поиска с запретами Вероятностный поиск с запретами и теорема о его сходимости

17.  Гибридные эволюционные алгоритмы. Локальная оптимизация решений.

18.  Алгоритмы корректировки решений

19.  Декодирующие эвристики

20.  Теорема о сравнении эволюционной стратегии (1+1)-EA с другими эволюционными алгоритмами

Образец экзаменационного билета:

ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

С/К Эволюционные алгоритмы

Экзаменационный билет 1.

1. Классический генетический алгоритм (схема алгоритма, определения операторов)

2. Алгоритм поиска с запретами, вероятностный поиск с запретами и теорема о его сходимости

ВОПРОСЫ для промежуточного контроля

Тест 1

Стандартная двоичная кодировка Кодировка Грэя Теорема о свойстве смежности Оператор одноточечного кроссинговера Оператор мутации Схема Теорема о схемах Теорема о разнообразии популяции Селекция Бэкера Турнирная селекция Срезающая селекция Популяция с элитой Стационарная схема воспроизведения

Тест 2

Эволюционная стратегия Оператор мутации с нормально распределенным шагом Невырожденная селекция Связывающее воспроизведение Невырожденный оператор выживания Консервативный оператор выживания Теорема о сходимости эволюционных алгоритмов