Реферат по теме выпускной работы
Содержание
ВВЕДЕНИЕ
1 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
1.1 Представление обьектов.
1.2 Основные генетические операторы.
1.3 Схема функционирования.
1.4 Механизм отбора
2
ГЕНЕТИЧЕСКИЕ
АЛГОРИТМЫ В MATLAB
3. ЭКСПЕРИМЕНТ
3.1 Описание задания
3.2 Целевая функция
3.2 Результаты
ПЕРЕЧЕНЬ ИСТОЧНИКОВ
Введение
Генетические алгоритмы возникли в результате наблюдения и попыток копирования естественных процессов, происходящих в мире живых организмов, в частности, эволюции и связанной с ней селекции (естественного отбора) популяций живых существ. При подобном сопоставлении нейронных сетей и генетических алгоритмов следует обращать внимание на принципиально различную длительность протекания упоминаемых естественных процессов. т.е. на чрезвычайно быструю обработку информации в нервной системе и очень медленный процесс естественной эволюции. Однако при компьютерном моделировании эти различия оказываются несущественными,
Генетические алгоритмы применяются при
разработке программного обеспечения, в системах искусственного
интеллекта, оптимизации, искусственных нейронных сетях и в
других отраслях знаний. Следует отметить, что с их помощью решаются
задачи, для которых ранее использовались только нейронные сети. В этом
случае генетические алгоритмы выступают просто в роли
независимого от нейронных сетей альтернативного метода,
предназначенного для решения той же самой задачи. Примером может
служить задача коммивояжера . изначально решавшаяся при помощи
сети Хопфилда. Генетические алгоритмы часто используются
совместно с нейронными сетями. Они могут поддерживать нейронные сети
или наоборот, либо оба метода взаимодействуют в рамках гибридной
системы, предназначенной для решения конкретной задачи.
Генетические алгоритмы также применяются совместно с нечеткими системами
1.ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
1.1 Представление объектов. Кодирование признаков
Из биологии мы знаем, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе . Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.
Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака.
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины.
1.2 Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:
1 из популяции выбираются две особи, которые будут родителями;
2 определяется (обычно случайным образом) точка разрыва;
3 потомок определяется как конкатенация части первого и второго родителя.
Рассмотрим функционирование этого оператора
|
Хромосома_1: |
0000000000 |
|
Хромосома_2: |
1111111111 |
Допустим, разрыв происходит после 3-го бита хромосомы, тогда получаем.
Хромосома_1: 0000000000>>0001111111 Результирующая хромосома 1
Хромосома_1:11111111111>>1110000000Результриующая хромосома 2
Итак, рассмотрим все же операторы по порядку:
1) кроссинговер - создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется. Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом:
000 1111111 >> 1111111 000
2) инверсия - перестановка в структуре некоторой ее части наоборот
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).
3) мутация - замена в структуре одного из значений случайно выбранной компоненты
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).
В принципе для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.
1.3 Схема функционирования
Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.
Инициировать начальный момент времени t=0 . Случайным образом сформировать начальную популяцию, состоящую из k особей.
Вычислить приспособленность каждой особи и популяции в целом (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
1. Выбрать особь из популяции.
2. С определенной вероятностью (вероятностью кроссовера ) выбрать вторую особь из популяции и произвести оператор кроссовера.
3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации.
4. С определенной вероятностью (вероятностью инверсии ) выполнить оператор инверсии.
5. Поместить полученную хромосому в новую популяцию
6. Выполнить операции, начиная с пункта 2, k раз.
7. Увеличить номер текущей эпохи t=t+1.
Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2 .
Распишем более подробно следующие этапы:
1. Выбор родительской пары .
Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора (о чем будет сказано ниже), который бы "тормозил" слишком быструю сходимость алгоритма.
Другие два способа формирования родительской пары, на которые хотелось бы обратить внимание, это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров. В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга оказалось более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма. Наиболее полезно применение обоих представленных методов для многоэкстремальных задач . Однако два этих способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.
1.3 Механизм отбора
Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Наиболее эффективные два механизма отбора элитный и отбор с вытеснением.
Идея элитного отбора, в общем, не нова, этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективной. Второй метод, на котором хотелось бы остановиться, это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения.
2.ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В MATLAB
Для решения задач многокритериальной оптимизации с помощью генетических алгоритмов мы воспользуемся одним из его многофункциональных пакетов – Multiobjectiveoptimizationusing Genetic Algorithm или сокращенно gamultiobj.
Для запуска пакета следует выбрать Apps→Optimization. После этого запустится пакет генетических алгоритмов и на экране появится основное окно утилиты. Выбираем в командной строке Solver(решающее устройство)→gamultiobj, это и есть наш генетический алгоритм
В поле Number of variables (число переменных)указывается длина входного вектора оптимизируемой функции.
В панели Constraints (ограничения) можно задать ограничения или ограничивающую нелинейную функцию. В поле Linear inequalities задается линейное ограничение неравенством вида: A*x ≤ b.
В поле Linear equalities данной панели задаются линейные ограничения равенством: A*x = b. В обоих случаях A – некоторая матрица, b – вектор.
В поле Bounds (границы) в векторном виде задаются нижнее и верхнее ограничения переменных. Если в конкретной задаче не требуется задание ограничений, все поля панели Constraints следует оставить незаполненными.
В Options, находится панель настройки графиков. Она позволяет выводить различные графики, отображающие информацию о работе генетического алгоритма. На основе этой информации можно менять настройки алгоритма с целью повышения эффективности его работы. Подробнее эта панель будет описана ниже наравне с остальными панелями вкладки Options утилиты gamultiobj.
Панель Run Solver содержит управляющие элементы (кнопки Start, Pause и Stop для начала, временной и полной остановки работы генетического алгоритма). Также она содержит поля CurrentIteration, в которое выводятся текущие результаты работы запущенного генетического алгоритма, и Final point, в котором выводится значение конечной точки работы алгоритма — наилучшей величины оптимизируемой функции (то есть, искомое значение).В правой части основного окна утилиты OptimizationTool находится панель Options. Она позволяет устанавливать различные настройки для работы генетических алгоритмов. При щелчке мышью по кнопкам «+», которые находятся напротив названия каждого из настраиваемых параметров в панели Options, появляются выпадающие списки (вкладки), содержащие поля для ввода и изменения соответствующих параметров генетического алгоритма.
Основными настраиваемыми параметрами в Optimization Tool являются:
· популяция (вкладка Population);
· оператор отбора (вкладка Selection);
· оператор репродукции (вкладка Reproduction);
· оператор мутации (вкладка Mutation);
· оператор скрещивание (вкладка Crossover);
· перенесение особей между популяциями (вкладка Migration);
· многокритериальные специальные параметры (вкладка Multiobjective problem settings);
· задание гибридной функции (вкладка Hybrid function);
· задание критерия остановки алгоритма (вкладка Stopping criteria);
· вывод различной дополнительной информации по ходу работы генетического алгоритма (вкладка Plot Functions);
· вывод результатов работы алгоритма в виде новой функции (вкладка Output function);
· задание набора информации для вывода в командное окно (вкладка Display to command window);
· способ вычисления значений оптимизированной и ограничивающей функций (вкладка User function evaluation).
Рассмотрим подробнее все вышеперечисленные вкладки панели Options и элементы, которые они содержат:
1. Во вкладке настройки популяций пользователь имеет возможность выбрать тип математических объектов, к которому будут относиться особи всех популяций (двойной вектор, битовая строка или пользовательский тип). При этом стоит учитывать, что использование битовой строки и пользовательских типов накладывают ограничения на перечень допустимых операторов создания, мутации и скрещивания особей. Так, например, при выборе в качестве формы представления особей битовой строки для оператора скрещивания нельзя использовать гибридную функцию или нелинейную ограничивающую функцию.
Также вкладка популяции позволяет настраивать размер популяции (из скольких особей будет состоять каждое поколение) и каким образом будет создаваться начальное поколение (Uniform – если отсутствуют накладываемые ограничения, в противном случае – Feasible population). Кроме того, в рассматриваемой вкладке имеется возможность задать вручную начальное поколение (используя пункт Initial population) или его часть, начальный рейтинг особей (пункт Initial scores), а также ввести ограничительный числовой диапазон, которому должны принадлежать особи начальной популяции (Initial range).
2. Вкладка «Selection» позволяет выбрать оператор отбора родительских особей на основе данных из функции масштабирования. В качестве доступных для выбора вариантов оператора отбора предлагаются следующие:
Tournament – случайно выбирается указанное число особей, среди них на конкурсной основе выбираются лучшие;
Custom– позволяет писать свою собственную функцию выбора.
3. Вкладка «Reproduction» уточняет каким образом происходит создание новых особей. Пункт Crossover fraction указывает долю особей, которые создаются путем скрещивания. Остальная доля создается путем мутации.
4. Во вкладке оператора мутации выбирается тип оператора мутации. Доступны следующие варианты:
Gaussian – добавляет небольшое случайное число (согласно распределению Гаусса) ко всем компонентам каждого вектора-особи;
Uniform – выбираются случайным образом компоненты векторов и вместо них записываются случайные числа из допустимого диапазона;
Adaptive feasible – генерирует набор направлений в зависимости от последних наиболее удачных и неудачных поколений и с учетом налагаемых ограничений продвигается вдоль всех направлений на разную длину;
Custom – позволяет задать собственную функцию.
5. Вкладка «Crossover» позволяет выбрать тип оператора скрещивания (одноточечное, двухточечное, эвристическое, арифметическое или рассеянное (Scattered), при котором генерируется случайный двоичный вектор соответствия родителей). Также имеется возможность задания произвольной (custom) функции скрещивания.
6. Во вкладке «Migration» можно настраивать правила, согласно которым особи будут перемещаться между подпопуляциями в пределах одной популяции. Подпопуляции создаются, если в качестве размера популяции указан вектор, а не натуральное значение. В данной вкладке можно указать направление миграции (forward – в следующую подпопуляцию, both – в предыдущую и следующую), долю мигрирующих особей и частоту миграции (сколько поколений проходит между миграциями). Если создание подпопуляций не требуется, эту вкладку всегда стоит оставлять без изменений.
7. «Multiobjectiveproblemsettings» определяет параметры, характерные для многокритериального генетического алгоритма. Можно задать следующие функции:
Distance measure function
Pareto front population fraction
8. Вкладка «Hybrid function» позволяет задать ещё одну функцию минимизации, которая будет использоваться после окончания работы алгоритма. В качестве возможных гибридных функций доступны следующие встроенные в саму среду MATLAB функции: none (не использовать гибридную функцию) и – fgoalattain.
9. Во вкладке критерия остановки («Stopping criteria») указываются ситуации, при которых алгоритм совершает остановку. При этом, настраиваемыми являются следующие параметры:
Generations – максимальное число поколений, после превышения которого произойдет остановка;
Time limit – лимит времени на работу алгоритма;
Fitness limit – если оптимизируемое значение меньше или равно данного лимита, то алгоритм остановится;
Stall generations – количество мало отличающихся поколений, по прошествии которых алгоритм остановится;
Function tolerance – минимальные значения изменений оптимизируемой и ограничивающей функций соответственно, при которых алгоритм продолжит работу.
10. Особый интерес представляет вкладка «Plot Functions», которая позволяет выбирать различную информацию, которая выводится по ходу работы алгоритма и показывает как корректность его работы, так и конкретные достигаемые алгоритмом результаты. Наиболее важными и используемыми для отображения параметрами являются:
Plot interval – число поколений, по прошествии которого происходит очередное обновление графиков;
Distance – вывод интервала между значениями особей в поколении;
Genealogy – вывод генеалогического дерева особей;
Score diversity – вывести гистаграмму рейтинга в каждом поколении;
Selection – вывод гистограммы родителей;
Stopping – вывод информации о состоянии всех параметров, влияющих на критерии остановки;
Custom function– отображение на графике некоторой указанной пользователем функции.
11. Вкладка вывода результатов в виде новой функции («Output function») позволяет включить вывод истории работы алгоритма в отдельном окне с заданным интервалом поколений, а также позволяет задать и вывести произвольную выходную функцию, задаваемую в поле Custom function.
12. Вкладка «Display to command window» позволяет настраивать информацию, которая отображается в основном командном окне MATLAB при работе алгоритма. Возможны следующие значения:
Off – нет вывода в командное окно;
Iterative – вывод информации о каждой итерации работающего алгоритма;
Diagnose – вывод информации о каждой итерации и дополнительных сведениях о возможных ошибках и измененных ключевых параметрах алгоритма;
Final – выводится только причина остановки и конечное значение.
13. Наконец, вкладка «User function evaluation» описывает, в каком порядке происходит вычисление значений оптимизируемой и ограничивающей функций (отдельно, параллельно в одном вызове или одновременно)
Однако наличие многих критериев и ограничений затрудняют применение ГА в практических задачах, т.к. большинство подходов, предложенных в области эволюционной оптимизации, ориентированы только на одну проблему, т.е. либо на многокритериальность, либо на наличие ограничений. Подходы, сочетающие оба направления, встречаются редко и их эффективность не всегда удовлетворена. Компьютерные системы поддержки принятия решений делают структуру задачи наглядной и помогают выделить одно или несколько наиболее приемлемых ее решений.
3. ЭКСПЕРИМЕНТ
Целью эксперимента является проверка работоспособности генетических алгоритмов в среде Matlab ,а так же применение их при решении задач оптимизации.
Условие задачи: нахождение коэффициентов передаточной функции методом наименьших квадратов с помощью генетических алгоритмов.
Рис.3.1 – Модель исходной системы
Для блока Discrete Transfer Fcn задаемся выбранными случайным образом коэффициентами : b1=2, b0=3.5, a2=3.388, a1=1.5, a0=0.1.
Блок Unit delay выполняет задержку входного сигнала на один шаг модельного времени.
Исходная популяция. k представлена в виде матрицы k=[k1,k2,k3,k4] ,где k1,k2,k3,k4-особи, генотип которых является матрицей размерностью [51,1].
3.2 Целевая функция
Целевая функция – это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума
В данной задачи целевой функцией является метод наименьших квадратов.
Суть метода заключается в нахождении коэффициентов линейной зависимости, при которых функция двух переменных а и b
принимает наименьшее значение. То есть, при данных а и b сумма квадратов отклонений экспериментальных данных от найденной прямой будет наименьшей. В этом вся суть метода наименьших квадратов.
Таким образом, решение примера сводится к нахождению экстремума функции двух переменных.
Для его реализации в Матлабе была создана функция отдельным m-файлом:
function [ y ] = mnk( a,k )
global a k ;
y=sum((([k(1),k(2),k(3),k(4)]*k')'-a).^2);
end
3.3 Результаты
Для получения результатов, воспользуемся пакетом gamultiobj , описанным выше.
Рис.3.2 – Ввод данных
@mnk – название оптимизированной функции.
Число переменных данной функции 4 .
В поле Linear inequalities задаемся линейным ограничением неравенством вида: k*x ≤ a. Ограничение нужно для того, чтобы операции проводились в пределах заданной популяции.
Основные настраиваемые параметры в Optimization Tool были оставлены по умолчанию.
Рис.3.3 – Результат работы gamultiobj
Решение найдено за 51 итерацию.
Коэффициенты передаточной функции:
0.59 ; 1.033 ; -0.443 ; -0.03
Выполним
проверку, сравнив вручную выведенными коэффициенты
с коэффициентами найденными ГА.
|
ГА
|
Выведенные вручную |
|
|
0.59 |
0.59 |
|
|
1.033 |
1.033 |
|
|
-0.0443 |
0.0443 |
|
|
-0.03 |
0.03 |
Таблица 3.1 – Сравнение результатов
Как
видно из таблицы 3.1 , коэффициенты совпали, из этого
следует что найденное решение является правильным.