Проектирование пользовательского интерфейса
Требования задания
Цель работы – изучение современной технологии разработки диалоговых комплексов оптимизации, ориентированной на применение языков программирования C++, либо C#; модификация программы, разработанной в лабораторной работе 3.
Модифицированная программа должна обеспечивать:
· оптимизацию целевых функций с любым числом переменных;
· задание критерия останова (максимальное количество итераций и вырождение популяции с заданной точностью e) в диалоговом режиме;
· построение сводного графика зависимостей средней приспособленности по популяции и приспособленности лучшей особи от количества пройденных итераций.
Программа должна быть дружественной пользователю:
· содержать необходимые заставки и сообщения, характеризующие программу, используемый метод, характер выводимой информации, допущенную ошибку при вводе данных и т. д.;
· содержать блокировку ошибочных действий при вводе данных и обеспечивать простоту исправления ошибки;
· обеспечивать в демонстрационном режиме возможность выбора одной из нескольких (трех-пяти) тестовых функций и запуск на поиск решения.
При составлении программы предусмотреть:
· структурирование программы в соответствии с объектно-ориентированным подходом к разработке программного обеспечения;
· использование класса битовой цепочки для представления в программе операций для работы с хромосомами;
· возможность сравнения по качеству найденного решения двух способов кодирования хромосом – целочисленногои вещественного;
· выбор по требованию пользователя способа кодирования хромосом, возможность смены типа скрещивания. Также предусмотреть возможность опционального отключения дополнительных операторов (популяционного всплеска и уплотнения сетки);
· возможность задания величины разрыва поколений (процента элитных особей);
· сохранение журналов с подробным описанием хода решения и значениями ведущих переменных в текстовый файл.
Контрольные вопросы
1.Каким образом было реализовано целочисленное кодирование в классе битовой цепочки? Привести диаграмму класса в UML-нотации[1].
2.Привести общую диаграмму классов, предназначенных для функционирования генетического алгоритма, включая activity-диаграмму[2].
3.Какие, по Вашему мнению, преимущества дает объектно-ориентированный подход при разработке генетического алгоритма?
4.Каким образом организовано хранение цепочек хромосом? Является ли выбранный вариант достаточно быстрым и эффективным? Обоснуйте свой выбор, опираясь на тесты памяти во время работы генетического алгоритма.
Содержание отчета
1.Цель работы и требования задания.
2.Спецификация программы, раскрывающая смысл входных и выходных данных, основных переменных, функций и классов. Диаграммы каждого класса должны быть приведены согласно UML-нотации. Одна use-case диаграмма для описания самого алгоритма.
3.Текст программы с детальными комментариями ведущих операторов программы.
4.Описание интерфейса пользователя программы.
5.Результаты сравнения двух способов кодирования – целочисленногои вещественного.
6.Сводные графики зависимостей средней приспособленности по популяции и приспособленности лучшей особи от количества пройденных итераций.
7.Результаты сравнения работы программы с результатами работы MathCAD или надстройки «Поиск решения» в MSExcel (на выбор).
8.Ответы на контрольные вопросы.
9.Выводы по работе.
3.5. Исследование схемы «генетический алгоритм– классический метод оптимизации».
Требования задания
Цель работы – модификация программы, исполненной в лабораторной работе 4 для изучения схемы «генетический алгоритм – классический метод оптимизации». При выполнении данной лабораторной работы предлагается выбрать целочисленное кодирование хромосом.
М1 – популяция 100 особей, турнирный отбор (размер 2), 1-точечное скрещивание (pc = 0,7), мутация (pm = 0,1), инверсия (pI = 0,05), условие остановки - 100 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Давидона–Флетчера–Пауэлла[3] (100 итераций);
М2 – популяция 50 особей, турнирный отбор (размер 3), 2-точечное скрещивание (pc = 0,8), мутация (pm = 0,03), инверсия (pI = 0,03), условие остановки - 50 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Бройдена–Флетчера–Гольдфарба–Шенно (150 итераций);
М3 – популяция 30 особей, турнирный отбор (размер 4), однородное скрещивание (pc = 0,9), мутация (pm = 0,05), условие остановки - разница приспособленности лидера и «наихудшей» особи меньше 0,01. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Мак-Кормика (150 итераций);
М4 – популяция 70 особей, турнирный отбор (размер 5), 1-точечное скрещивание (pc = 0,75), инверсия (pI = 0,07), условие остановки - 50 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Флетчера–Ривса (100 итераций);
М5 – популяция 100 особей, турнирный отбор (размер 2), 2-точечное скрещивание (pc = 0,8), инверсия (pI = 0,1), условие остановки - 100 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Нелдера–Мида;
М6 – популяция 60 особей, турнирный отбор (размер 3), однородное скрещивание (pc = 0,85), мутация (pm = 0,2), инверсия (pI = 0,03), условие остановки - 70 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Пауэлла;
М7 – популяция 70 особей, турнирный отбор (размер 4), 1-точечное скрещивание (pc = 0,9), мутация (pm = 0,1), условие остановки - 70 итераций. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Розенброка (200 итераций);
М8 – популяция 30 особей, турнирный отбор (размер 5), 2-точечное скрещивание (pc = 0,7), мутация (pm = 0,15), условие остановки – разница приспособленности лидера и «наихудшей» особи меньше 0,01. После останова генетического алгоритма лучшую особь используем в качестве стартовой точки для метода Зангвилла (200 итераций).
Для всех вариантов: Длина гена m = 12.
Варианты задания
| Вариант | ||||||||
| Метод | М1 | М2 | М3 | М4 | М5 | М6 | М7 | М8 |
| Тестовая функция | (9) (10) | (11) (7) | (13) (6) | (15) (5) | (17) (4) | (19) (3) | (20) (2) | (8) (1) |
Контрольные вопросы
1.В чем, по Вашему мнению, преимущество данной гибридной схемы перед классическим генетическим алгоритмом? Перед классическим методом?
2.В чем будет отличие процедуры передачи лучшей особи в качестве стартовой точки для классического метода оптимизации при вещественном кодировании хромосом от целочисленного варианта?
3.Необходимо ли накладывать на классический метод оптимизации те же ограничения, что накладываются на генетический алгоритм при задании поисковых интервалов для каждого параметра? Что может произойти, если их не накладывать?
4.Какие еще варианты совместного применения классических методов оптимизации и генетического алгоритма Вы можете придумать? Обоснуйте их эффективность.
5.Допустим, что есть некая схема «классический метод оптимизации – генетический алгоритм». Каким образом классический метод может «помочь» генетическому алгоритму перед поиском? Изложите ваши идеи.
Содержание отчета
1.Цель работы и требования задания.
2.Краткое описание алгоритма на основании материала лекционного курса и описание схемы пошагового выполнения вычислительного алгоритма.
3.Укрупненнаяблок-схема программы с пояснением всех ее частей.
4.Спецификация программы, раскрывающая смысл входных и выходных данных, основных переменных и функций.
5.Текст программы с детальными комментариями ведущих операторов программы.
6.Результаты тестирования программы на наборе целевых функций с указанием числа итераций и количества вычислений целевой функции. Журнал вычислений, иллюстрирующий поисковый процесс и изменение ключевых переменных.
7.Качественный анализ результатов работы алгоритма (пример см. в разд. 6.1), статистическая оценка (среднее по 50 прогонам и ее стандартная ошибка).
8.При неудовлетворительных результатах поиска, исходя из анализа результатов алгоритма, необходимо улучшить результат за счет подгонки данных в задании начальных параметров. Весь процесс отладки алгоритма с соответствующими графиками, комментариями и выводами также должен быть документирован в отчете.
9.Графики функции, построенные в среде MathCAD или MatLab (если целевая функция зависит не более чем от двух переменных, то построить трехмерный график и контурные графики по всем парам переменных функции, иначе – только контурные графики).
10. Выводы по работе.
11. Ответы на контрольные вопросы.