Решение задачи повышения надежности резервирования
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
рока со второй по величине суммой расстояний получит оценку k+(m-2)/m. Строка с минимальной суммой расстояний до остальных особей данного ранга будет иметь оценку k.
Такой подход к оцениванию экземпляров популяции настраивает алгоритм не только на поиск недоминируемых решений (любая недоминируемая строка будет иметь оценку выше любой доминируемой), но и на поддержание разнообразия популяции (удаленные точки получают более высокие оценки), что обеспечивает лучшую аппроксимацию парето-оптимального множества.
4-й этап. Отбор(селекция).
В качестве процедуры селекции будем использовать стандартные механизмы пропорционального или турнирного отбора, и чем выше у индивида оценка приспособленности, тем вероятнее она попадет в родители следующего поколения.
5-й этап. Скрещивание и мутация.
Для создания новых особей-потомков может использоваться любая стандартная мутация и любой из классических операторов скрещивания (одноточечный, двухточечный, равномерный кроссовер), дополненные процедурой исправления недопустимых решений. Недопустимыми решения могут оказаться только за счет невыполнения ограничения . Это можно подкорректировать, исправив несколько координат в соответствующей строке (например, случайным образом значение 3 исправить на 2 или 1, либо значение 1 исправить на 2). Такие исправления позволят уменьшить левую часть этого ограничения. Они проводятся до тех пор, пока это ограничение не будет выполнено.
6-й этап. Критерий прекращения работы.
В качестве рекорда хранится множество недоминируемых за все время заботы алгоритма вариантов. Как критерий остановки вычислений используется следующая проверка: если за последние 100 поколений рекордное множество не изменилось, то дальнейшая работа алгоритма прекращается.
6. Разработка приложения
6.1 Требования к приложению
Данное приложение должно позволять получать приблизительное решение задачи выбора вариантов резервирования компонентов стендовой информационно-управляющей системы с помощью генетических алгоритмов с незначительными временными затратами
Данное приложение должно так же позволять получить точное решение (множество всех оптимальных по Парето точек) данной задачи.
Данное приложение должно иметь простой в использовании русскоязычный графический интерфейс, понятный пользователю, ознакомленному с сутью проблемы резервирования компонентов стендовой информационно-управляющей системы и математической моделью, описанной во главе 3.
Данное приложение должно адекватно реагировать на некорректные данные и выводить соответствующие сообщения.
Данное приложение должно быть совместимо с операционными системами Windows XP\Vista\7.
6.2 Особенности реализации
Для реализации данного приложения была выбрана программная среда Embarcadero RAD Studio 2010. Язык программирования - Delphi. Выбор основан на том, что данная среда имеет все необходимые визуальные компоненты, а язык обеспечивает простую работу с динамическими массивами.
Программа состоит из двух модулей. Unit1 содержит обработчики кнопок. Unit2 отвечает за реализацию генетического алгоритма.
При написании программы применялись как процедурный подход (реализация генетических алгоритмов), так и подход ООП (визуальные компоненты).
В генетических алгоритмах использовались: случайное формирование начальной популяции, турнирная селекция, одноточечный кроссовер, одноточечная мутация.
6.3 Графический интерфейс
На рис. 4 представлен графический интерфейс приложения.
Рис. 4. Графический интерфейс
6.4 Тестирование приложения, определение оптимальных параметров
Путем многократного запуска программы и сравнения результатов было установлено, что рекомендуемые параметры программы:
Количество особей: 50 (увеличение не дает улучшения результата, однако оказывает значительное влияние на скорость выполнения алгоритма).
Вероятность мутации: <0,1 (увеличение данного значения ухудшает качество получаемого множества ответов, а также замедляет алгоритм). На рис. 5 видно, как решения, получаемые при больших значениях вероятности мутации, заметно отличаются от истинного оптимального множества решений.
Рис. 5. Плохая аппроксимация оптимального множества решений при большом значении вероятности мутации
Вероятность скрещивания: <0,7 (изменения в сторону увеличения и изменения не дают сильного эффекта, однако использование критических значений, близких к 0 или 1 нежелательно).
Количество оптимальных решений: определяется пользователем. Чем больше данный параметр, тем разнообразнее множество ответов.
Далее приведена сравнительная таблица времени работы генетического алгоритма и перебора:
Таблица 1 - Время работы в зависимости от размерности задачи
Кол-во элементовВремя перебораВремя работы генетического алгоритма10000:00:10:2881900:00:02:4961800:00:01:9561700:00:01:7661600:00:01:7561500:00:01:6831400:00:01:4321300:00:01:2331200:01:04:40900:00:01:2041100:00:46:57300:00:01:0541000:00:06:22600:00:00:543900:00:00:94300:00:00:466800:00:00:25500:00:00:474700:00:00:3300:00:00:471600:00:00:0500:00:00:492
Время перебора, начиная с 13 элементов, не было рассчитано, т.к. оно требовало слишком больших временных затрат. Тем не менее, общая динамика роста времени хорошо прослеживается. Далее для наглядности приведен график зависимости времени выполнения алгоритмов от размерности задачи, построенный по данной таблице.<