Сравнение эффективности применения классических и интеллектуальных методов решения задач оптимизации - Курсовая работа

Для проведения минимизации была выбрана функция Сферы. Ее трехмерный вид для n = 2 показан ниже: Рис.1.1 Трехмерный вид функции Сфера для n=2Здесь через М обозначена точка n-мерного пространства с координатами x?, x, . . Изменяя эту переменную, будем двигаться от начальной точки x?=x?? в сторону убывания функции, пока не дойдем до ее минимума при x?=x??, после которого она начинает возрастать. ,xn=xn0 и рассмотрим функцию f как функцию одной переменной x: f(x??, x, x? . . Изменяя x , будем опять двигаться от начального значения x2=x20 в сторону убывания функции, пока не дойдем до минимума при x2=x21 .Точку с координатами {x??, x?, x? . . , которой соответствует монотонная последовательность значений функции f(M0) ?f (M?)?f(M)???Обрывая ее на некотором шаге k можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области.int menu_select(void); void result (void); {choice = menu_select(); } int menu_select(void) } void result(void)Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов: 1) инициализация, или выбор исходной популяции хромосом; Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Если исходная форма функции приспособленности не удовлетворяет этим условиям, то выполняется соответствующее преобразование (например, задачу минимизации функции можно легко свести к задаче максимизации). Селекция хромосом заключается в выборе (по расчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы.int menu_select(void); void result (void); {choice = menu_select(); } int menu_select(void) } void result(void)Рассмотрим задачу глобальной безусловной минимизации целевой функций Ф(Х) в n-мерном арифметическом пространстве Rn: min Ф{Х) = Ф(Х) В момент времени t = 0, 1, 2 ... координаты частицы Pi определяются вектором Хі,t = (xi,t,1, xi,t,2, xi,t,n), а ее скорость - вектором Vi,t= (vi,t,1, vi,t,2, vi,t,n). Здесь U[a,b] представляет собой n-мерный вектор псевдослучайных чисел, равномерно распределенных в интервале [a, b]; - символ покомпонентного умножения векторов; - вектор координат частицы Pi с наилучшим значением целевой функции Ф(Х); за все время поиска; Xg,t - вектор координат соседней с данной частицы с наилучшим за время поиска значением целевой функции Ф(Х); ?,?,? - свободные параметры алгоритма. Пересчет координат частиц по формулам (7), (8) может происходить по синхронной схеме (обновление координат частиц выполняется только после определения текущих скоростей всех N частиц) или по асинхронной схеме (расчет новых координат части проводится до завершения указанных вычислений). В процессе итераций вектор образует так называемый собственный путь (private guide) частицы Pi, а вектор Xg,t - локальный путь (local guide) этой частицы.int menu_select(void); void result (void); {choice = menu_select(); } int menu_select(void) } void result(void)Исходя из представленного выше графика можно сделать следующие выводы: Наиболее быстрым алгоритмом для решения поставленной задачи является метод покоординатного спуска,однако решение, найденное данным методом будет приблизительным - проблема «ямы» экстремума;Исходя из представленного выше графика можно сделать следующие выводы: Объем выборки для покоординатного спуска почти не влияет на количество итераций;В процессе выполнения курсовой работы были написаны программы, реализующие поиск минимума функции для трех методов: покоординатного спуска, генетического алгоритма и метода PSO.

Содержание

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

2. Используемые методы оптимизации

2.1 Метод покоординатного спуска

2.1.1 Краткие теоретические сведения

2.1.2 Разработка программного обеспечения

2.2 Генетический алгоритм

2.2.1 Краткие теоретические сведения

2.2.2 Разработка программного обеспечения

2.3 Метод PSO

2.3.1 Краткие теоретические сведения

2.3.2 Разработка программного обеспечения

3. Сравнительный анализ работы алгоритмов

3.1 График зависимости времени выполнения программы от объема выборки

3.2 График зависимости количества итераций от объема выборки

Выводы

Список литературы

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