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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Введение

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

Эволюционные вычисления составляют один из разделов искусственного интеллекта. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, например, это может быть и нейронная сеть и набор логических правил. К основным эволюционным методам относятся методы отжига, генетические, поведения "толпы" (PSO), колонии муравьев (ACO), генетического программирования.

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

В методе отжига (Simulated Annealing) имитируется процесс минимизации потенциальной энергии тела во время отжига деталей. В текущей точке поиска происходит изменение некоторых управляемых параметров. Новая точка принимается всегда при улучшении целевой функции и лишь с некоторой вероятностью при ее ухудшении.

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

Свойства объектов представлены значениями параметров, объединяемых в запись, называемую в эволюционном методе хромосомой. В генетическом алгоритме оперируют подмножеством хромосом, называемом популяцией. Имитация генетических принципов -- вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции -- ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению.

Среди эволюционных методов находят применение также методы, которые в отличие от генетического алгоритма оперируют не множеством хромосом, а единственной хромосомой. Так, метод дискретного локального поиска (его англоязычное название Hillclimbing) основан на случайном изменении отдельных параметров (т.е. значений полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют мутациями. После очередной мутации оценивают значение функции полезности (Fitness Function) и результат мутации сохраняется в хромосоме только, если улучшилась.

При "моделировании отжига" результат мутации сохраняется с некоторой вероятностью, зависящей от полученного значения .

В методе PSO (Particles Swarm Optimization) имитируется поведение множества агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента.

Метод колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих длину своих маршрутов на пути от муравьиной кучи до источника пищи.[]

• 2. Простой генетический алгоритм
• Для применения генетического алгоритма необходимо:
• 1. выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его полезность, т.е. выделить множество управляемых параметров среди могут быть величины различных типов (real, integer, Boolean, enumeration). Наличие нечисловых величин (enumeration) обусловливает возможность решения задач не только параметрической, но и структурной оптимизации;
• 2. сформулировать количественную оценку полезности вариантов объекта -- функцию полезности . Если в исходном виде задача многокритериальна, то такая формулировка означает выбор скалярного (обобщенного) критерия;
• 3. разработать математическую модель объекта, представляющую собой алгоритм вычисления для заданного вектора ;
• 4. представить вектор в форме хромосомы -- записи следующего вида (см. рис. 1).
• Рис. 1. Хромосома
• В генетическом алгоритме используется такая терминология:
• · ген -- управляемый параметр ;
• · аллель -- значение гена;
• · локус (позиция) -- позиция, занимаемая геном в хромосоме;
• · генотип -- экземпляр хромосомы, генотип представляет совокупность внутренних параметров проектируемого с помощью генетического алгоритма объекта;
• · генофонд -- множество всех возможных генотипов;
• · функция полезности (приспособленности) -- целевая функция;
• · фенотип -- совокупность значений критериев, получаемых после декодирования хромосомы, под фенотипом часто понимают совокупность выходных параметров синтезируемого с помощью генетического алгоритма объекта.
• Вычислительный процесс начинается с генерации исходного поколения множества, включающего хромосом, -- размер популяции. Генерация выполняется случайным выбором аллелей каждого гена.
• Далее организуется циклический процесс смены поколений:
• for k=1:G
• for j=1:N
• Выбор родительской пары хромосом;
• Кроссинговер;
• Мутации;
• Оценка функции полезности F потомков;
• Селекция;
• end
• Замена текущего поколения новым;
• end
• Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссинговера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение.
• Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.
• 2.1 Выбор родителей
• Этот оператор имитирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями функции полезности более вероятен. Например, пусть требуется минимизировать. Тогда вероятность выбора родителя с хромосомой можно рассчитать по формуле
• (1)
• где -- наихудшее значение целевой функции среди экземпляров (членов) текущего поколения, -- значение целевой функции -го экземпляра.
• Правило (1) называют правилом колеса рулетки. Если в колесе рулетки выделить секторы, пропорциональные значениям , то вероятности попадания в них суть , определяемые в соответствии с (1).
• Пример 1
• Пусть , значения и приведены в табл. 1.[1]
• Таблица 1

1	2	5	0,5
2	7	0	0
3	6	1	0,1
4	3	4	0,4

• 2.2 Кроссинговер (скрещивание)
• Кроссинговер, иногда называемый кроссовером, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссинговере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в таблице 2, где разрыв подразумевается между пятым и шестым локусами.[1]
• Таблица 2

Хромосома	Ген 1	Ген 2	Ген 3	Ген 4	Ген 5	Ген 6	Ген 7	Ген 8
Родителя A	f	a	c	d	g	k	v	e
Родителя B	a	b	c	d	e	f	g	h
Потомка C	f	a	c	d	g	f	g	h
Потомка D	a	b	c	d	e	k	v	e

• 2.3 Мутации
• Оператор мутации выполняется с некоторой вероятностью , т.е. с вероятностью происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска.
• 4. Селекция.
• После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары.
• Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным . Количество повторений внешнего цикла чаще всего определяется автоматически по появлению признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени.
• 2.4 Селекция
• На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности. Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.[2]
• эволюционный генетический алгоритм синтез
• 3. Реализация простого генетического алгоритма в MATLAB
• Согласно моему заданию я должен был написать процедуру-функцию, реализующую генетический алгоритм и с помощью составленной программы провести поиск минимума функции
• На рис.2 изображен результат выполнения функции для 5 генов. Символом “*” обозначен финальный результат.
• Рис. 2. Результат выполнения программы для 5 генов
• 4. Список литературы
• 1. http://bigor.bmstu.ru/ - База и Генератор Образовательных Ресурсов - Все учебные курсы - Эволюционные методы для решения задач проектирования и логистики.
• Размещено на Allbest.ru