Генетический алгоритм
Дипломная работа - Биология
Другие дипломы по предмету Биология
>
for j=1:N
Выбор родительской пары хромосом;
Кроссинговер;
Мутации;
Оценка функции полезности F потомков;
Селекция;
end
Замена текущего поколения новым;
end
Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссинговера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение.
Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме.
.1 Выбор родителей
Этот оператор имитирует естественный отбор, если отбор в родительскую пару хромосом с лучшими значениями функции полезности более вероятен. Например, пусть требуется минимизировать. Тогда вероятность выбора родителя с хромосомой можно рассчитать по формуле
(1)
где - наихудшее значение целевой функции среди экземпляров (членов) текущего поколения, - значение целевой функции -го экземпляра.
Правило (1) называют правилом колеса рулетки . Если в колесе рулетки выделить секторы, пропорциональные значениям , то вероятности попадания в них суть , определяемые в соответствии с (1).
Пример 1
Пусть , значения и приведены в табл. 1.[1]
Таблица 1
1250,527003610,14340,4
.2 Кроссинговер (скрещивание)
Кроссинговер, иногда называемый кроссовером, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссинговере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в таблице 2, где разрыв подразумевается между пятым и шестым локусами.[1]
Таблица 2
ХромосомаГен 1Ген 2Ген 3Ген 4Ген 5Ген 6Ген 7Ген 8Родителя AfacdgkveРодителя BabcdefghПотомка CfacdgfghПотомка Dabcdekve
2.3 Мутации
Оператор мутации выполняется с некоторой вероятностью , т.е. с вероятностью происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска.
. Селекция .
После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары.
Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным . Количество повторений внешнего цикла чаще всего определяется автоматически по появлению признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени.
2.4 Селекция
На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется в живых на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности. Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.[2]
эволюционный генетический алгоритм синтез
3. Реализация простого генетического алгоритма в MATLAB
Согласно моему заданию я должен был написать процедуру-функцию, реализующую генетический алгоритм и с помощью составленной программы провести поиск минимума функции
На рис.2 изображен результат выполнения функции для 5 генов. Символом * обозначен финальный результат.
Рис. 2. Результат выполнения программы для 5 генов
4. Список литературы
1. - База и Генератор Образовательных Ресурсов - Все учебные курсы - Эволюционные методы для решения задач проектирования и логистики.