Мультимодальные эволюционные алгоритмы
Разработка мультимодального генетического алгоритма для нахождения множества субоптимальных решений для заданной по варианту функции. Построение графика данной функции. Получение графического представления расположения особей на различных итерациях.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 07.09.2022 |
| Размер файла | 260,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ГУАП
КАФЕДРА № 43
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №1
МУЛЬТИМОДАЛЬНЫЕ ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ
по курсу: ЭВОЛЮЦИОННЫЕ МЕТОДЫ В ПРОГРАММНОЙ ИНЖЕНЕРИИ
Работу выполнил
Студент гр. № 4131М Д.В. Блинов
Преподаватель
доц.,д.т.н.., профессор. Ю.А. Скобцов
Санкт-Петербург 2022
Цель работы
Целью работы является изучение мультимодальных эволюционных алгоритмов мультимодальный генетический субоптимальный итерация
Задание на лабораторную работу
1. Разработать мультимодальный генетический алгоритм для нахождения множества субоптимальных решений (максимума) для заданной по варианту функции.
3. Вывести на экран график данной функции с указанием найденного экстремума для каждого поколения и особями популяции.
3. Получить графическое представление расположения особей на различных итерациях (в начале, середине и конце процесса поиска).
4. Сравнить найденные решения с действительными.
Индивидуальное задание по варианту.
Вариант 1
Тест функция:
Область определения [0,1]. Найти max.
Краткие теоретические сведения
Концепция мультимодальных задач имеет различные аспекты, но, как правило, считают, что: - существует несколько глобальных оптимальных решений, которые необходимо найти; - существуют глобальные и локальные оптимальные решения.
Если мы используем обычный ГА для поиска экстремумов функций, представленной на рис.1.1, то он может найти несколько глобальных решений через некоторое число итераций (поколений), но после этого потеряет большинство из них и все особи сконцентрируются в окрестности одного глобального решения вследствие генетического дрейфа. Поэтому нужны специальные методы, которые позволяют находить несколько глобальных оптимальных решений и некоторые интересные локальные решения.
Метод последовательных ниш
В этом методе после поиска глобального оптимального решения с использованием любого поискового алгоритма, в том числе и эволюционного, мы можем изменить ландшафт решения таким образом, чтобы притяжение в область уже найденного пика наказывается, чтобы обеспечить при следующем запуске поискового алгоритма нахождение другого пика. Продолжая описанный выше процесс, мы найдем несколько последовательных пиков. Ключом к последовательной нише является изменение ландшафта решения. Как правило, наказание за стремление в область уже найденного пика (ов) означает уменьшение значений целевой функции в этих пиках, что можно проиллюстрировать следующим образом:
Тогда измененный ландшафт решения может быть проиллюстрирован:
Это уравнение означает, что после нахождения пика, мы уменьшаем значение фитнесс-функции вокруг него и затем используем алгоритм поиска снова, чтобы найти другой экстремум
Программа и результаты выполнения индивидуального задания с комментариями и выводами
Реализуем метод последовательных ниш на языке python.
Определим класс Evo, в чьем конструкторе определим:
1. Length -- мощность популяции
2. Sigma -- радиус пика
3. Мax_generations -- максимальное число поколений
4. num_of_offsprings число выживших потомков после селекции
А также зададим тестовую функцию
class Evo: def __init__(self, length, sigma=0.1, max_generations=100, num_of_offsprings=5): self.length = length self.sigma = sigma self.genes = self.get_random_genes(self.length) self.score_arr = None self.max_generations = max_generations self.num_of_offsprings = num_of_offsprings self.current_fun = lambda x: m.sin(5 * m.pi * (x ** 0.75 - 0.05))**6
Реализуем основные методы генетических алгоритмов
В данной работе реализуем только метод мутации
def mutation(self, offsprings): a = -1 while (a < 0) or (a > 1): sample = offsprings[np.random.randint(self.num_of_offsprings)][0] a = sample + np.random.uniform(-0.1, 0.1) return a
Для присвоения рейтинга каждой особи реализуем функцию score, в которой используем изменения ландшафта решений.
def score(self, generation): for i, e in enumerate(generation): generation[i][1] = self.current_fun(e[0]) for i in range(len(generation)): nearby_list = [] for j in range(len(generation)): if (generation[j][0] > (generation[i][0] - self.sigma)) and (generation[j][0] < (generation[i][0] + self.sigma)): nearby_list.append(generation[j][0]) curr_fun = np.vectorize(self.current_fun) max_nearby = max(curr_fun(nearby_list)) generation[i][3] = max_nearby if max_nearby == generation[i][1]: generation[i][2] = 1 else: generation[i][2] = self.dist(generation[i][0], max_nearby) for i, e in enumerate(generation): generation[i][4] = e[1] - e[2] generation = generation[generation[:, 4].argsort()] return generation
На основе полученного рейтинга реализуем метод отбора
def select(self, generation): generation = generation[-self.num_of_offsprings:] return generation
Используя данные методы, реализуем метод создания следующего поколения
def next_generation(self, generation): generation_and_score = self.score(generation) offsprings = self.select(generation_and_score) generation = self.reproduction(offsprings) return generation
Полный метод эволюции реализуем с помощью метода evolution
def evolution(self): generation_pre = self.get_random_genes(self.length) generation = [] for i in generation_pre: generation.append([i, 0, 0, 0, 0]) generation = np.array(generation) generation_index = 1 for _ in range(self.max_generations): generation = self.next_generation(generation) return self.score(generation)
Данный метод возвращает результрующую популяцию отсортированные по их рейтингу. Вершину данной популяции возглавляют n особей занимающих пики
Графическое представление особей на различных итерациях
1 Итерация
20 итераций
Зеленые точки -- результирующие пики
Оранжевые плюсы -- остальные особи популяции
Выводы
В данной лабораторной работе были изучены мультимодальные эволюционные алгоритмы. А также реализован метод последовательных ниш.
Максимумы функции были найдены с высокой достоверности.
Размещено на Allbest.ru
...Подобные документы
Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
лабораторная работа [20,2 K], добавлен 03.12.2014Создание программы для поиска минимума функции двух вещественных переменных в заданной области с помощью генетического алгоритма. Генетические алгоритмы и операторы. Создание начальной популяции. Размножение. Мутация и селекция. Тестирование программы.
курсовая работа [131,6 K], добавлен 22.02.2015Построение схемы алгоритма и программы для создания графика временной функции, работающей в машинном и реальном времени. Выбор методов решения и их обоснование. Значение коэффициентов и временной функции. Реализация временных задержек в программе.
курсовая работа [6,2 M], добавлен 09.03.2012Операторы генетического алгоритма. Пример простейшей программы. Процесс генерации и накопления информации о выживании и продолжении рода в ряде поколений популяции. Программа, реализующая простой генетический алгоритм для нахождения минимума функции.
курсовая работа [39,3 K], добавлен 29.10.2012Разработка алгоритма и программы для вычисления функции, заданной интервально на различных промежутках. Алгоритм и программа формирования одномерного массива по условию, заданной интервально на различных промежутках. Решение нелинейного уравнения.
курсовая работа [38,3 K], добавлен 17.11.2010Исследование понятия алгоритма, особенностей линейных и разветвляющихся алгоритмов. Свойства алгоритма: понятность, точность, дискретность, массовость и результативность. Составление программы для вычисления значения функции и построение её графика.
контрольная работа [278,0 K], добавлен 25.03.2013Этапы работы генетического алгоритма, область его применения. Структура данных, генерация первоначальной популяции. Алгоритм кроссинговера - поиск локальных оптимумов. Селекция особей в популяции. Техническое описание программы и руководство пользователя.
реферат [1014,2 K], добавлен 14.01.2016Модификация алгоритма RPC таким образом, чтобы он не требовал входного параметра, но сохранил свою гибкость при решении задачи нахождения максимальной клики для разных графов. Метод ветвей и границ. Построение функции-классификатора. Листинг алгоритма.
курсовая работа [197,8 K], добавлен 06.10.2016Расчет и построение таблицы значений функции (протабулирование функции) при различных значениях аргумента. Нахождение наибольшего и наименьшего значений функции на отрезке и построение графика. Рабочий лист Excel в режимах отображения значений и формул.
контрольная работа [30,0 K], добавлен 27.05.2010Первые работы по симуляции эволюции. Основные понятия генетических алгоритмов. Постановка задачи и функция приспособленности. Инициализация, формирование исходной популяции. Выбор исходной популяции для генетического алгоритма, решение задач оптимизации.
курсовая работа [714,1 K], добавлен 31.03.2015Решение нелинейного уравнения вида f(x)=0 с помощью программы Excel. Построение графика данной функции и ее табулирование. Расчет матрицы по исходным данным. Проведение кусочно-линейной интерполяции таблично заданной функции с помощью программы Mathcad.
контрольная работа [1,8 M], добавлен 29.07.2013Анализ функции и разработка алгоритма по ее вычислению. Программирование отдельных блоков и структур алгоритма. Структура Паскаль-программы. Раздел описаний, подпрограммы, тело программы. Полная Паскаль-программа в соответствии с разработанным алгоритмом.
курсовая работа [241,8 K], добавлен 30.01.2016Программа вычисления системы, построение графика. Задача шага изменения аргумента. Набор диапазона значений и зависимость x от i. Наложение условия для решения заданной системы. Создание функции с помощью if. Общий вид графика решения заданной системы.
лабораторная работа [48,5 K], добавлен 25.12.2011Рассмотрение процесса разработки системы нахождения нулей функции. Изучение вычисления корня уравнения методом Ньютона или касательных. Основы проектирования графического интерфейса пользователя и описание алгоритма, тестирование готовой программы.
курсовая работа [1,2 M], добавлен 23.02.2014Анализ заданной сложной функции и разработка структурной схемы алгоритма по её вычислению. Программирование отдельных блоков и структур алгоритма решаемой задачи на языке Паскаль. Полная программа в соответствии с алгоритмом. Результаты расчётов на ПК.
курсовая работа [59,2 K], добавлен 09.04.2012Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Методика разработки, практической апробации программы в среде Turbo Pascal по построению графика прямой линии регрессии. Формирование блок-схемы данной программы, ее листинг. Построение графика с помощью математических формул и графического модуля Graph.
контрольная работа [46,2 K], добавлен 22.07.2011Определение минимума функции на заданном отрезке методами перебора, поразрядного поиска, дихотомии, золотого сечения и методом парабол. Нахождение и расчет нулей функции методом Ньютона. Построение графика данной функции, ее минимальное значение.
реферат [55,6 K], добавлен 09.04.2013Содержание фундаментальной теории гена. Описание простого генетического алгоритма поиска оптимальных решений. Сущность понятий "кроссинговер", "сайт", "иллегальная рекомбинация". Этапы реализации алгоритма Девиса по перераспределению участков хромосом.
контрольная работа [23,7 K], добавлен 17.09.2010История создания и развитие языка программирования Pascal, его версии. Особенности и порядок построения графика функции на языке Turbo Pascal с использованием декартовой системы координат. Блок схема алгоритма процедур, листинг и тестирование программы.
курсовая работа [102,7 K], добавлен 23.12.2011
