Программное средство для исследования свойств двух алгоритмов глобальной оптимизации

ВВЕДЕНИЕ 10
1. Общие положения 13
1.1 Постановка задачи глобальной оптимизации 13
1.2 Методы решения задач глобальной оптимизации 13
1.3 Классификация методов глобальной оптимизации 15
2. Генетический алгоритм 18
2.1 Перечень настраиваемых параметров 20
2.1.1 Отбор (селекция) 20
2.1.2 Выбор родителей 23
2.1.3 Размножение (скрещивание) 23
2.1.4 Стратегия формирования нового поколения 25
3 Алгоритм, основанный на селективном усреднении искомых переменных 26
3.1 Перечень настраиваемых параметров алгоритма 28
3.1.1 Ядерные функции 28
4 Описание программной реализации 30
4.1 Обзор существующих аналогов 30
4.2 Требования к программному средству 31
4.3 Выбор аппаратных и программных средств 32
4.4 Обоснование выбора языковой среды 32
4.5 Функциональные возможности программного средства 32
4.5.1 Решение поставленной задачи глобальной оптимизации 33
4.6 Структура программного средства 33
5. Численные исследования 37
5.1 Тестовая функция №1 37
5.2 Тестовая функция №2 41
ЗАКЛЮЧЕНИЕ 47
СПИСОК ИСПОЛЬЗОВАННЫЙ ИСТОЧНИКОВ 48

Купить

Задача поиска оптимального значения целевой функции является одной из актуальных в области науки и техники. Большинство практических задач, возникающих в различных сферах человеческой деятельности, могут быть сведены к задачам оптимизации. Это различные задачи расчета параметров конструкций, траектории движения объекта, распределения ресурсов. Применение стратегии поиска оптимума для построения и решения задач синтеза сложных систем приводит к повышению качества управления, планирования и проектирования.
При быстро возрастающей сложности оптимизируемых объектов совершенно естественным является и усложнение их математических моделей, что, как следствие, значительно затрудняет поиск оптимальной комбинации параметров. Очень часто не представляется возможным найти такую комбинацию аналитически и возникает необходимость построения численных методов для ее поиска.
Проблема численного решения задач оптимизации, в свою очередь, сопряжена со значительными трудностями. Во многом они связаны с их размерностью, видом оптимизирующей целевой функции и наличием помех. Такие задачи характеризуются целевой функцией со следующими свойствами. Во-первых, она может быть многоэкстремальной, недифференцируемой и, более того, заданной в форме черного ящика (т. е. в виде некоторой вычислительной процедуры или прибора, на вход которого подается аргумент, а на выходе наблюдается соответствующее значение функции). Во-вторых, каждое вычисление функции в некоторой точке допустимой области может требовать значительных вычислительных ресурсов.
Увеличение числа прикладных проблем, описываемых математическими моделями подобного типа, и бурное развитие вычислительной техники вызвали значительный интерес к указанным задачам и инициировали развитие глобальной оптимизации как области математического программирования, занимающейся разработкой теории и методов решения многоэкстремальных оптимизационных задач.
Численные методы глобальной оптимизации существенно отличаются от стандартных локальных методов поиска, которые часто неспособны найти глобальное (т. е. абсолютно лучшее) решение рассматриваемых задач в силу многоэкстремальности целевой функции. Локальные методы, как правило, оказываются не в состоянии покинуть зоны притяжения локальных оптимумов и, соответственно, упускают глобальный оптимум. Использование же найденных локальных решений может оказаться недостаточным, поскольку глобальное решение может дать существенный выигрыш по сравнению с локальными.
Как уже было сказано, особенностями решаемых задач оптимизации являются нелинейность, недифференцируемость, многоэкстремальность (мультимодальность), овражность, отсутствие аналитического выражения (плохая формализованность) и высокая вычислительная сложность оптимизируемых функций, высокая размерность пространства поиска, сложная топология области допустимых значений. На сегодняшний день для их решения получено чрезвычайно большое число алгоритмов глобальной оптимизации. В свою очередь среди них нет универсального метода для решения задач. В частности, решение двух различных задач глобальной оптимизации выбранным алгоритмом в первом случае (для первой задачи) даст оптимальное решение, во втором (для второй задачи) - оптимальное решение не будет достигнуто. В связи с этим актуальной становится разработка эффективных и достаточно универсальных алгоритмов глобальной оптимизации.
В свою очередь не перестает быть актуальной задача исследования уже существующих и зарекомендовавших себя алгоритмов глобальной оптимизации.
Для каждой задачи применение алгоритмов глобальной оптимизации требует настройки соответствующих параметров и нет универсального средства для решения поставленной задачи, учитывая, что задача глобальной оптимизации актуальна на сегодняшний день можно сделать вывод, что необходимо программное средство наглядно указывающая достоинства и недостатки одного из выбранных алгоритмов.
Данные алгоритмы имеют ряд преимуществ и недостатков друг относительно друга и реализуемое программное средство призвано на практике их показать.
Цель работы. Проектирование и реализация универсального программного средства для исследования свойств алгоритмов глобальной оптимизации. Исследование свойств двух выбранных алгоритмов: генетического алгоритма и алгоритма, основанного на селективном усреднении переменных на тестовых задачах.
Постановка задачи. Разработать универсальное программное средство для решения задач оптимизации и исследования свойств алгоритмов.
Объём и структура работы. Выпускная квалификационная работа состоит из введения, 5 глав и заключения. Общий объем выпускной квалификационной работы 46 страниц, включая библиографический список из 6 источников. Иллюстративный материал представлен на 20 рисунке.
Купить