ТИДЗ_Курсовая. Системы на базе генетических алгоритмов
 Скачать 50.18 Kb.
|
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА» (СПбГУТ) ИНСТИТУТ ㅤ НЕПРЕРЫВНОГО ОБРАЗОВАНИЯ КУРСОВАЯ РАБОТА Дисциплина: «Теория информации, данные и знания» КУРСОВАЯ РАБОТА Эссе на тему: Системы на базе генетических алгоритмов Фамилия: Мельник Имя: Владимир Отчество: Николаевич Группа: №: ИБ-04з Санкт-Петербург 2023 ОглавлениеВведение 3 Естественный отбор в природе 4 Что такое генетический алгоритм 6 Подробное описание генетического алгоритма 9 Особенности генетических алгоритмов 11 Системы на базе генетических алгоритмов 13 Заключение 14 Список используемых источников 15 ВведениеГенетические алгоритмы - это аналитические технологии, созданные и выверенные самой природой за миллионы лет ее существования. Они позволяют решать задачи прогнозирования, классификации, поиска оптимальных вариантов, и совершенно незаменимы в тех случаях, когда в обычных условиях решение задачи основано на интуиции или опыте, а не на строгом (в математическом смысле) ее описании. Цель данной работы - это обзор выше упомянутой темы, для того чтоб в дальнейшем разработать систему генерирующей решение с помощью генетических алгоритмов. Ниже будет подробно освещена эта тема и затронуты наиболее важные аспекты этой задачи. Вначале заглянем в источник этих алгоритмов. Были определены следующие задачи: 1. Рассмотреть естественный отбор в природе. 2. Рассмотреть понятие генетического алгоритма. 3. Изучить подробное описание генетического алгоритма. 4. Изучить особенности генетических алгоритмов. 5. Рассмотреть системы на базе генетических алгоритмов. Естественный отбор в природеЭволюционная теория утверждает, что каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. В процессе эволюции многие виды насекомых и рыб приобрели защитную окраску, еж стал неуязвимым благодаря иглам, человек стал обладателем сложнейшей нервной системы. Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Рассмотрим, какими же средствами природа решает эту задачу оптимизации. Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает. Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (Дезоксирибо-Нуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой. Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т.д.) кодируется определенной частью хромосомы, которая называется геном этого свойства. Например, ген цвета глаз содержит информацию, кодирующую определенный цвет глаз. Различные значения гена называются его аллелями. При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками. При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Что такое генетический алгоритмПусть дана некоторая сложная функция (целевая функция), зависящая от нескольких переменных, и требуется найти такие значения переменных, при которых значение функции максимально. Задачи такого рода называются задачами оптимизации и встречаются на практике очень часто. Один из наиболее наглядных примеров - задача распределения инвестиций. В этой задаче переменными являются объемы инвестиций в каждый проект, а функцией, которую нужно максимизировать - суммарный доход инвестора. Также даны значения минимального и максимального объема вложения в каждый из проектов, которые задают область изменения каждой из переменных. Попытаемся решить эту задачу, применяя известные нам природные способы оптимизации. Будем рассматривать каждый вариант инвестирования (набор значений переменных) как индивидуума, а доходность этого варианта - как приспособленность этого индивидуума. Тогда в процессе эволюции (если мы сумеем его организовать) приспособленность индивидуумов будет возрастать, а значит, будут появляться все более и более доходные варианты инвестирования. Остановив эволюцию в некоторый момент и выбрав самого лучшего индивидуума, мы получим достаточно хорошее решение задачи. Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. Вот как моделируется генетическое наследование:
Чтобы смоделировать эволюционный процесс, сгенерируем вначале случайную популяцию - несколько индивидуумов со случайным набором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений. Жизненный цикл популяции - это несколько случайных скрещиваний (посредством кроссовера) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов. Отбор в генетическом алгоритме - это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее. Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:
Таким образом, модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Часто используется так называемая стратегия элитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов. Возвращаясь к задаче оптимального распределения инвестиций, поясним особенности реализации генетического алгоритма в этом случае. Индивидуум = вариант решения задачи = набор из 10 хромосом Хj Хромосома Хj= объем вложения в проект j = 16-разрядная запись этого числа Так как объемы вложений ограничены, не все значения хромосом являются допустимыми. Это учитывается при генерации популяций. Так как суммарный объем инвестиций фиксирован, то реально варьируются только 9 хромосом, а значение 10-ой определяется по ним однозначно. Подробное описание генетического алгоритма1. Создание структуры решения искомой задачи в виде массива a [i], i = 1,. n, где n - максимальное число компонент структуры. Пример: поиск функции y=f (x) наилучшего в классе полиномов приближения экспериментальных точек {xi, yi}, j=1,.,m. Структура определяется битовым массивом, где каждому элементу массива сопоставлен простейший многочлен типа xi, i=1,. n, где n - максимальная степень полинома. 2. Создание показателя эффективности структуры, заполненной конкретными значениями. Пример: Показателем эффективности для нашего примера будет невязка определенная методом наименьших квадратов Ja=I1+I2+. +Im, где Ij= (yj-fa (xj)) 2, где fa (x) есть сумма всех элементов вида aixi, где ai = 0 или 1 3. Задание некоторого массива различных структур Sk, k=1,.,N, размерностью N, большей, чем число компонент n в структуре Данный массив можно сгенерировать случайно, задав нули и единицы в каждой структуре. 4. Расчет показателей эффективности Jk для каждой структуры Sk. По формуле заданной в пункте 2. 5. Естественный отбор структур по некоторому правилу выбора наилучших структур среди заданного массива структур. Пример: можно по правилу вида J0=M (Jk) - среднее значение Jk, если Jk 6. Замена выбывших структур на новые, рожденные от наиболее приспособленных структур с помощью генетических операторов а) мутация - замена в структуре одного из значений случайно выбранной компоненты Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0). б) инверсия - перестановка в структуре некоторой ее части наоборот Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0). в) кроссинговер - создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй. Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E). 7. Переход к этапу 4. Особенности генетических алгоритмовГенетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известны два основных пути решения таких задач - переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать. Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера. Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов). Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода. Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально. Второй популярный способ основан на методе градиентного спуска. При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является. Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение. Однако, комбинируя переборный и градиентный методы, можно надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета. Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск. Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время. Системы на базе генетических алгоритмовГенетический алгоритм имеет широкое применение в совокупности с другими эвристиками. В упомянутой ранее системе генетический алгоритм работает на базе мультиагентной концепции. В работе торговая система работает в 2 этапа: в начале, с помощью алгоритма создаётся оптимальное дерево решений, затем с использованием генетического алгоритма оптимизируются параметры этой стратегии. Пример применения генетического программирования для генерации торговых стратегий продемонстрирован в системе EDDIE. Используя предложенные пользователем показатели, система тренирует наиболее приспособленное дерево решений. Общая схема работа продемонстрирована на рисунке 1.  Рисунок 1. Система EDDIE Генетические алгоритмы применяются для решения следующих задач: Оптимизация функций. Оптимизация запросов в базах данных. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний). Настройка и обучение искусственной нейронной сети. Задачи компоновки. Составление расписаний. Игровые стратегии. Теория приближений. Искусственная жизнь. ЗаключениеВ ходе работы были рассмотрены исторические сведения, основные понятия генетических алгоритмов, общий вид генетического алгоритма, генетические операторы. Также мы рассмотрели применение генетического алгоритма, на примере задачи нахождения максимума функции. В завершении хотелось бы отметить, что область применения генетических алгоритмов многогранна. Генетические алгоритмы в различных формах применяются ко многим научным и техническим проблемам. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (такие как экономика и политические системы) и когнитивные системы. Список используемых источниковРутковская Д., Пилиньский М., Рутковский Л. – «Нейронные сети, генетические алгоритмы и нечеткие системы» Генетические алгоритмы [Электронный ресурс] Режим доступа - http://www.sernam.ru/book_gen.php Популярно о генетических алгоритмах [Электронный ресурс] Режим доступа:http://knowledge.allbest.ru/programming/3c0b65625b3bc78a5c43b89421316c27_0.html Особенности генетических алгоритмов [Электронный ресурс] Режим доступа - http://www.masters.donntu.edu.ua/2000/fkita/stupchak/oglavl.htm Генетические агоритмы [Электронный ресурс] Режим доступа -http://www.bestreferat.ru/referat-213707.html NeuroProject _ Обучение _ Статьи - Что такое генетические алгоритмы [Электронный ресурс] Режим доступа - http://works.tarefer.ru/69/100400/index.html Программирование искусственного интеллекта [Электронный ресурс] Режим доступа - http://www.itfru.ru/index.php/genetic-algorithms |