Реализация генетического алгоритма в пакете MATLAB 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Реализация генетического алгоритма в пакете MATLAB



Генетические алгоритмы позволяют решить задачи оптимизации с плохой обусловленностью, не поддающиеся решению с помощью классических методов оптимизации [34].

Генетические алгоритмы (ГА) – это метод решения оптимизационных задач, основанный на биологических принципах естественного отбора и эволюции.

Генетический алгоритм повторяет определенное количество раз процедуру модификации популяции (набора отдельных решений), добиваясь тем самым получения новых наборов решений (новых популяций). При этом на каждом шаге из популяции выбираются «родительские особи», то есть решения, совместная модификация которых (скрещивание) и приводит к формированию новой особи в следующем поколении [34,53].
Генетический алгоритм использует три вида правил, на основе которых формируется новое поколение: правила отбора, скрещивания и мутации.

Мутация позволяет путем внесения изменений в новое поколение избежать попадания в локальные минимумы оптимизируемой функции.

Специальные графические функции пакета обеспечивают визуализацию итерационного процесса, значений целевой функции, генеалогических параметров, размеров сетки и количества вычислений целевой функции. Пакет обеспечивает импорт текущей настройки задачи оптимизации для повторного использования [53].

Для решения задач многокритериальной оптимизации с помощью генетических алгоритмов мы воспользуемся одним из его многофункциональных пакетов – Multiobjective optimization using Genetic Algorithm или сокращенно называется gamultiobj [55,56].

Для запуска пакета следует выбрать Apps → Optimization. После этого запустится пакет генетических алгоритмов и на экране появится основное окно утилиты. Выбираем в командной строке Solver (решающее устройство) → gamultiobj, это и есть наш генетический алгоритм

рис.3.14. Вкладка Optimization Tool

В поле Fitness function (функция пригодности) указывается оптимизируемая функция в виде @fitnessfun, где fitnessfun.m – название M-файла, в котором предварительно следует описать оптимизируемую функцию. M-файл создается в среде MATLAB через меню File->New->Function.

Пример описания функции:

function f = chaos (x)

f(1)= -2*x(1)-2*x(2)-3*x(3)-3*x(4)-2*x(5);

f(2)= 5*x(1)+2*x(2)+3*x(3);

end

Вернемся к основному окну утилиты Optimization Tool. В поле Number of variables (число переменных) указывается длина входного вектора оптимизируемой функции. В рассмотренном выше примере функция my_fun имеет входной вектор длины 5.

В панели Constraints (ограничения) можно задать ограничения или ограничивающую нелинейную функцию. В поле Linear inequalities задается линейное ограничение неравенством вида: A*x ≤ b.

В поле Linear equalities данной панели задаются линейные ограничения равенством: A*x = b.

В обоих случаях A – некоторая матрица, b – вектор.

В поле Bounds (границы) в векторном виде задаются нижнее и верхнее ограничения переменных.

Если в конкретной задаче не требуется задание ограничений, все поля панели Constraints следует оставить незаполненными.

 

В Options, находится панель настройки графиков. Она позволяет выводить различные графики, отображающие информацию о работе генетического алгоритма. На основе этой информации можно менять настройки алгоритма с целью повышения эффективности его работы.

Подробнее эта панель будет описана ниже наравне с остальными панелями вкладки Options утилиты gamultiobj.

Панель Run Solver содержит управляющие элементы (кнопки Start, Pause и Stop для начала, временной и полной остановки работы генетического алгоритма). Также она содержит поля Current Iteration, в которое выводятся текущие результаты работы запущенного генетического алгоритма, и Final point, в котором выводится значение конечной точки работы алгоритма — наилучшей величины оптимизируемой функции (то есть, искомое значение).
В правой части основного окна утилиты Optimization Tool находится панель Options. Она позволяет устанавливать различные настройки для работы генетических алгоритмов. При щелчке мышью по кнопкам «+», которые находятся напротив названия каждого из настраиваемых параметров в панели Options, появляются выпадающие списки (вкладки), содержащие поля для ввода и изменения соответствующих параметров генетического алгоритма.

рис.3.15. Панель Options

Основными настраиваемыми параметрами в Optimization Tool являются:

1) популяция (вкладка Population);

2) оператор отбора (вкладка Selection);

3) оператор репродукции (вкладка Reproduction);

4) оператор мутации (вкладка Mutation);

5) оператор скрещивание (вкладка Crossover);

6) перенесение особей между популяциями (вкладка Migration);

7) многокритериальные специальные параметры (вкладка Multiobjective problem settings);

8) задание гибридной функции (вкладка Hybrid function);

9) задание критерия остановки алгоритма (вкладка Stopping criteria);

10) вывод различной дополнительной информации по ходу работы генетического алгоритма (вкладка Plot Functions);

11) вывод результатов работы алгоритма в виде новой функции (вкладка Output function);

12) задание набора информации для вывода в командное окно (вкладка Display to command window);

13) способ вычисления значений оптимизированной и ограничивающей функций (вкладка 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. «Multiobjective problem settings» определяет параметры, характерные для многокритериального генетического алгоритма. Можно задать следующие функции:

- 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» описывает, в каком порядке происходит вычисление значений оптимизируемой и ограничивающей функций (отдельно, параллельно в одном вызове или одновременно) [56].

Однако наличие многих критериев и ограничений затрудняют применение ГА в практических задачах, т.к. большинство подходов, предложенных в области эволюционной оптимизации, ориентированы только на одну проблему, т.е. либо на многокритериальность, либо на наличие ограничений. Подходы, сочетающие оба направления, встречаются редко и их эффективность не всегда удовлетворена.

При большом количестве альтернатив и критериев достаточно трудно сориентироваться и принять наилучшее решение. Именно компьютерные системы поддержки принятия решений делают структуру задачи наглядной и помогают выделить одно или несколько наиболее приемлемых ее решений.

 



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 846; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.235.145.95 (0.028 с.)