Решение задачи повышения надежности резервирования с помощью эволюционного моделирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ние 100 поколений рекордное множество не изменилось, то дальнейшая работа алгоритма прекращается.
Глава 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 элементов, не было рассчитано, т.к. оно требовало слишком больших временных затрат. Тем не менее, общая динамика роста времени хорошо прослеживается. Далее для наглядности приведен график зависимости времени выполнения алгоритмов от размерности задачи, построенный по данной таблице.
Из графика и таблицы видно, что генетический алгоритм слабо зависит от размерности задачи.
Приведем ниже несколько примеров работы программы с рекомендуемыми параметрами.
Рис.6. Примеры работы программы с рекомендуемыми параметрами.
По рис.6 видно, что ГА хорошо приближает Парето-оптимальное множество данной задачи, кроме, может быть, тех точек, которые близки к экстремуму по одной из целевой функции. Такие точки на практике и не рассматриваются, т.к. они дают либо очень малую вероятность работы без отказа, либо очень большую стоимость, что неприемлемо.
Заключение
В ходе проделанной работы была изучена проблема повышения надежности резервирования компонентов стендовой информационно-управляющей системы для проведения огневых испытаний жидкостных ракетных двигателей и разработано приложение, позволяющее быстро получать множество альтернативных решений при выборе способа резервирования компонентов системы. При реализации программы были использованы методы эволюционного моделирования, которые являются достаточно универсальными, простыми, и в то же время довольно неприхотливыми к условиям задачи. Для эффективности тестирования в программе была также реализована возможность получения множества всех возможных решений с помощью метода перебора. В ходе тщательного тестирования были выявлены оптимальные параметры работы генетического алгоритма, а также оценена его производительность: скорость работы алгоритма очень слабо зависит от размерности задачи, что, бесспорно, является очень хорошим свойством. Также стоит отметить, что множество решений, получаемое с помощью ГА, хорошо покрывает множество в