Загрузка...
Учебная работа. Реферат: Генетические алгоритмы и их практическое применение
Введение………………………………………………………………………………………… 3
I. Теоритические нюансы решения задач при помощи генетических алгоритмов.
4
1. Традиционный ГА..
8
1.1 Постановка задачки и функция приспособленности.
8
1.2 Механизм работы ГА..
10
1.3 Метод работы..
10
1.4 Отбор.
11
1.5 Скрещивание.
12
1.6 Мутация.
13
1.7 Аспекты останова.
13
2.Достоинства и недочеты ГА..
14
2.1 Достоинства ГА..
14
2.2 Недочеты ГА..
14
3. Некотoрые модели генетических алгоритмов.
15
3.1 Canonical GA (I. Holland)
15
3.2 Genitor (D.Whitley)
15
3.3 Hybrid algorithm (L. “Dave” Davis)
16
3.4 Island Models GA..
16
3.5 CHC (Eshelman)
17
II. Пример практической реализации генетического метода.
19
1.1 Математическое обоснование принципа работы программки..
19
1.2 Механизм работы программки..
22
1.3 Листинг программки..
30
Заключение.
34
Перечень применяемой литературы..
35
Введение
В истинное время все наиболее животрепещущими стают задачки оптимизации, поиска, реализации распределенных и (либо) параллельных систем. Почти все из их просто реализуемы ординарными математическими способами, но некие задачки требуют к для себя особенного подхода. Эти задачки или не разрешимы ординарными способами, или их решение востребует значимого времени и размера ресурсов.
В процессе исследования разных подходов к решению таковых задач выдвигается догадка что, решение задач может быть при помощи генетических алгоритмов.[1]
Объектом
исследования данной учебно-исследовательской работы являются генетические методы.
Предметом
исследования – применение генетических алгоритмов для нахождения решения задачки.
Задачка
данной учебно-исследовательской работы состоит в исследовании теоретического нюанса использования генетических алгоритмов, а так же в практической реализации задачки с внедрением генетического метода.
I.
Теоретические нюансы решения задач при помощи генетических алгоритмов
Природа поражает собственной сложностью и богатством проявлений. Посреди примеров можно именовать сложные социальные системы, иммунные и нейронные системы, сложные связи меж видами. Они — всего только некие из чудес, ставшие явными при глубочайшем исследовании природы вокруг нас. Наука — это одна из систем, которая разъясняет окружающее и помогает приспособиться к новейшей инфы, получаемой из наружной среды. Почти все из того, что мы лицезреем и смотрим, можно разъяснить теорией эволюции через наследственность, изменение и отбор.[2]
На миропонимание людей очень повлияла теория эволюции Чарльза Дарвина, представленная в работе «Происхождение Видов», в 1859 году. Огромное количество областей научного познания почти всем должна революции, вызванной теорией эволюции и развития. Но Дарвин, подобно почти всем современникам, предполагающим, что в базе развития лежит естественный отбор, не мог не ошибаться. к примеру, он не сумел показать механизм наследования, при котором поддерживается изменчивость. Но Дарвин нашел основной механизм развития: отбор в соединении с изменчивостью. В почти всех вариантах, специальные индивидуальности развития через изменчивость и отбор все еще не неоспоримые, но, главные механизмы разъясняют неописуемо широкий диапазон явлений, наблюдаемые в природе.
Потому не умопомрачительно, что ученые, специализирующиеся компьютерными исследовательскими работами, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная ординарными механизмами изменчивости и отбора, могла бы работать по аналогии с законами эволюции в естественных системах, была весьма симпатичной. Эта надежда является предпосылкой возникновения ряда вычислительных систем, построенных на принципах естественного отбора.[3]
История эволюционных вычислений началась с разработки ряда различных независящих моделей. Главными из их были генетические методы и классификационные системы Голанда (Holland), разработанные сначала 60-х годов. Опосля выхода книжки, ставшей классикой — «адаптация в естественных и искусственных системах» («Adaptation in Natural and Artifical Systems», 1975), направление получило общее признание.[4]
Основная трудность при построении вычислительных систем, основанных на принципах естественного отбора и применении этих систем в прикладных задачках, заключается в том, что естественные системы достаточно беспорядочные, а все наши деяния, практически, носят четкую направленность. Мы используем комп как инструмент для решения определенных задач, что мы сами и формулируем, и акцентируем внимание на очень резвом выполнении при малых издержек. Естественные системы не имеют таковых целей либо ограничений, во всяком случае, нам они не известны. Выживание в природе не ориентировано к фиксированной цели, заместо этого эволюция делает шаг вперед в любом доступном направлении. Может быть это огромное обобщение, но усилия, направленные на моделирование эволюции по аналогии с естественными системами можно разбить на две огромных группы:
1. системы, смоделированные на био принципах. Они удачно употребляются для задач многофункциональной оптимизации и могут просто быть описаны небиологическим языком;
2. системы, которые на биологическом уровне наиболее правдоподобны, но на практике неэффективными. Они больше похожи на био системы, имеют сложное и увлекательное естественно, на практике недозволено делить эти вещи так строго. Эти группы — просто два полюса, меж которыми лежат различные вычислительные системы. Поближе к первому полюсу — эволюционные методы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические методы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Поближе ко второму полюсу — системы, которые могут быть классифицированы как Искусственная жизнь (Artificial Life).[5]
Генетические методы являются частью группы способов, именуемой эволюционными вычислениями, которые объединяют разные варианты использования эволюционных принципов для заслуги поставленной цели.
Также в ней выделяют последующие направления:
· Эволюционные стратегии
o способ оптимизации, основанный на идеях адаптации и эволюции. Степень мутации в данном случае изменяется с течением времени – это приводит к, так именуемой, самоадаптации.
· Генетическое программирование
o Применение эволюционного подхода к популяции программ.
· Эволюционное программирование
o Было в первый раз предложено Л.Дж. Фогелем в 1960 году для моделирования эволюции как процесса обучения с целью сотворения искусственного ума. Он употреблял конечные автоматы, предсказывающие знаки в цифровых последовательностях, которые, эволюционируя, становились наиболее адаптированными к решению поставленной задачки.[6]
Генетические методы используются для решения последующих задач:
· оптимизация функций
· Оптимизация запросов в базах данных
· Различные задачки на графах (задачка коммивояжера, раскраска, нахождение паросочетаний)
· Настройка и обучение искусственной нейронной сети
· задачки компоновки
· Составление расписаний
· Игровые стратегии
· Аппроксимация функций
· Искусственная жизнь
· Биоинформатика [7]
1. Традиционный ГА
1.1 Постановка задачки и функция приспособленности
Пусть перед нами стоит задачка оптимизации, к примеру:
· Задачка лучшего приближения
o Если разглядывать систему
линейных уравнений с
неведомыми
=
в случае, когда она переопределена (
>
), то время от времени оказывается естественной задачка о нахождении вектора
, который «удовлетворяет данной для нас системе лучшим образом», т. е. из всех «не решений» является наилучшим.
· задачка о рационе.
o Пусть имеется
разных пищевых товаров, содержащих
разных питательных веществ. Обозначим через aij
содержание (долю)
-го питательного вещества в
-ом продукте, через bj
— суточную Потребность организма в
-ом питательном веществе, через ci
— стоимость единицы
-го продукта. Требуется составить дневной рацион питания малой цены, удовлетворяющий Потребность во всех питательных субстанциях
· Транспортная задачка.
o Эта задачка — традиционная задачка линейного программирования. К ней сводятся почти все оптимизационные задачки. Формулируется она так. На
складах находится груз, который необходимо развезти
пользователям. Пусть ai
(
= 1, …,
) — количество груза на
-ом складе, а bj
(
= 1, …,
) — Потребность в грузе
-го пользователя, cij
— стоимость перевозки единицы груза с
-го склада
-му пользователю. Требуется минимизировать стоимость перевозок.
· задачки о распределении ресурсов.
o Общий смысл таковых задач — распределить ограниченный ресурс меж пользователями хорошим образом. Разглядим простой пример —
Пусть
электростанций питают одну нагрузку мощности
. Обозначим через xj
активную мощность, генерируемую
-ой электростанцией. Техническими критериями определяются вероятный минимум mj
и максимум Mj
вырабатываемой
-ой электростанцией мощности. Допустим Издержки на генерацию мощности
на
-ой электростанции равны ej
(
). Требуется сгенерировать требуемую мощность
при малых издержек.[8]
Переформулируем задачку оптимизации как задачку нахождения максимума некой функции f(x1
, x2
, …, xn
), именуемой
(fitness function). Она обязана принимать неотрицательные значения на ограниченной области определения (для того, чтоб мы могли для каждой особи считать её приспособленность, которая не быть может отрицательной), при всем этом совсем не требуются непрерывность и дифференцируемость.
Любой параметр функции приспособленности кодируется строчкой битов.
Особью будет называться строчка, являющаяся конкатенацией строк упорядоченного набора характеристик (рис1):
1010 10110 101 … 10101
| x1 | x2 | x3 | … | xn |
Рис 1. Ионкатенационная строчка упорядоченного набора характеристик
Универсальность ГА состоит в том, что от определенной задачки зависят лишь такие характеристики, как функция приспособленности и кодирование решений. Другие шаги для всех задач выполняются идиентично.[9]
Генетические методы оперируют совокупой особей (популяцией), которые представляют собой строчки, кодирующие одно из решений задачки. Сиим ГА различается от большинства остальных алгоритмов оптимизации, которые оперируют только с одним решением, улучшая его.[10]
При помощи функции приспособленности посреди всех особей популяции выделяют:
· более адаптированные (наиболее пригодные решения), которые получают возможность скрещиваться и давать потомство
· наихудшие (нехорошие решения), которые удаляются из популяции и не дают потомства
Таковым образом, приспособленность новейшего поколения в среднем выше предшествующего.[11]
В традиционном ГА:
· исходная популяция формируется случайным образом
· размер популяции (количество особей N) фиксируется и не меняется в течение работы всего метода
· любая особь генерируется как случайная L-битная строчка, где L — длина шифровки особи
· длина шифровки для всех особей схожа[12]
1.3 метод работы
На рисунке 2 изображена схема работы хоть какого генетического метода:
Рис 2. Схема работы хоть какого генетического метода.
Шаг метода состоит из 3-х стадий:
1. генерация промежной популяции (
) методом отбора (
) текущего поколения
2. скрещивание (
) особей промежной популяции методом
(
), что приводит к формированию новейшего поколения
3. мутация новейшего поколения [13]
1.4 Отбор
Промежная популяция — это набор особей, получивших Право плодиться. Более адаптированные особи могут быть записаны туда несколько раз, менее адаптированные с большенный вероятностью туда совершенно не попадут.[14]
В традиционном ГА возможность каждой особи попасть в промежную популяцию пропорциональна ее приспособленности, т.е. работает
(
).
Существует несколько методов реализации данного отбора:
—
. Пусть особи размещаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности.
раз запуская рулетку, избираем требуемое количество особей для записи в промежную популяцию.
—
. Для каждой особи рассчитывается отношение ее приспособленности к средней приспособленности популяции. Целая часть этого дела показывает, сколько раз необходимо записать особь в промежную популяцию, а дробная указывает её возможность попасть туда ещё раз. Воплотить таковой метод отбора комфортно последующим образом: расположим особи на рулетке так же, как было описано. сейчас пусть у рулетки не одна стрелка, а
, при этом они отсекают схожие сектора. Тогда один пуск рулетки изберет сходу все
особей, которые необходимо записать в промежную популяцию.[15]
Таковой метод иллюстрируется рисунком 3:
Рис 3. Метод
в реализации отбора
1.5 Скрещивание
Особи промежной популяции случайным образом разбиваются на пары, позже с некой вероятностью скрещиваются, в итоге что получаются два потомка, которые записываются в новое поколение, либо не скрещиваются, тогда в новое поколение записывается сама пара.
В традиционном ГА применяется одноточечный оператор кроссовера (1-
): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями [16]
(рис.4).
Рис 4. Одноточечный оператор кроссовера
1.6 Мутация
К приобретенному в итоге отбора и скрещивания новенькому поколению применяется оператор мутации, нужный для «выбивания» популяции из локального экстремума и содействующий защите от досрочной сходимости.
Любой бит каждой особи популяции с некой вероятностью инвертируется. Эта возможность обычно весьма мала, наименее 1% (рис 5).
1011001100
101101 -> 1011001101
101101Рис 5. Мутация
Можно выбирать некое количество точек в хромосоме для инверсии, при этом их число также быть может случайным. Также можно инвертировать сходу некую группу попорядку идущих точек.[17]
1.7 Аспекты останова
Таковой процесс эволюции, совершенно говоря, может длиться до бесконечности, пока не будет выполнен аспект остановки метода. Таковым аспектом быть может:
1. нахождение глобального, или субоптимального решения;
2. исчерпание числа поколений, отпущенных на эволюцию;
3. исчерпание времени, отпущенного на эволюцию. Генетические методы служат, основным образом, для поиска решений в весьма огромных, сложных местах поиска.[18]
2
. Достоинства и недочеты ГА
2.1
Достоинства
Опыты, описанные в литературе, демонстрируют, что генетические методы весьма эффективны в поиске глобальных минимумов адаптивных рельефов, потому что в их исследуются огромные области допустимых значений характеристик нейронных сетей. (Градиентные методы дают возможность отыскивать лишь локальные минимумы.) Иная причина того, что генетические методы не застревают в локальных минимумах — случайные мутации, которые подобны температурным флуктуациям способа имитации отжига.
В литературе есть указания на довольно высшую скорость обучения при использовании генетических алгоритмов. Хотя скорость сходимости градиентных алгоритмов в среднем выше, чем генетических алгоритмов.
Генетические методы дают возможность оперировать дискретными значениями характеристик нейронных сетей. Это упрощает разработку цифровых аппаратных реализаций нейронных сетей. При обучении на компе нейронных сетей, не нацеленных на аппаратную реализацию, возможность использования дискретных значений характеристик в неких вариантах может приводить к сокращению общего времени обучения.[19]
2.2
Недочеты
Генетические методы обучения сложны для осознания и программной реализации. Есть такие случаи, где не только лишь не лучше, да и проблематично употреблять ГА: в случае когда нужно отыскать четкий глобальный оптимум; время выполнения функции оценки велико; нужно отыскать все решения задачки, а не одно из их; конфигурация является не обычный (кодирование решения); поверхность ответа имеет слабоизменяющийся рельеф.[20]
3. Некие модели генетических алгоритмов
3.1
Canonical
GA
(
J
.
Holland
)
Данная модель метода является традиционной. Она была предложена Джоном Холландом в его известной работе «адаптация в природных и исусственных средах» (1975). Нередко можно повстречать описание
(Simple GA, D. Goldberg), он различается от канонического тем, что употребляет или рулеточный, или турнирный отбор. Модель канонического ГА имеет последующие свойства:
— Фиксированный размер популяции.
— Фиксированная разрядность генов.
— Пропорциональный отбор.
— Особи для скрещивания выбираются случайным образом.
— Одноточечный кроссовер и одноточечная мутация.
— Последующее поколение формируется из потомков текущего поколения без «элитизма». Потомки занимают места собственных родителей. [21]
3
.
2
Genitor (D. Whitley)
В данной модели употребляется специфичная стратегия отбора. Сначала, как и полагается, популяция инициализируется, и её особи оцениваются. Потом выбираются случайным образом две особи, скрещиваются, при этом выходит лишь один потомок, который оценивается и занимает пространство менее адаптированной особи. Опосля этого опять случайным образом выбираются 2 особи, и их потомок занимает пространство особи с самой низкой приспособленностью. Таковым образом, на любом шаге в популяции обновляется лишь одна особь. Подводя итоги можно выделить последующие соответствующие индивидуальности:
— Фиксированный размер популяции.
— Фиксированная разрядность генов.
— Особи для скрещивания выбираются случайным образом.
— Ограничений на тип кроссовера и мутации нет.
— В итоге скрещивания особей выходит один потомок, который занимает пространство менее адаптированной особи.[22]
3.3 Hybrid algorithm (L. «Dave» Davis)
Внедрение гибридного метода дозволяет соединить достоинства ГА с преимуществами традиционных способов. Дело в том, что ГА являются робастными методами, т.е. они разрешают отыскивать не плохое решение, но нахождение рационального решения часто оказывается намного наиболее трудной задачей в силу стохастичности принципов работы метода. Потому появилась мысль употреблять ГА на исходном шаге для действенного сужения места поиска вокруг глобального экстремума, а потом, взяв наилучшую особь, применить один из «традиционных» способов оптимизации. свойства метода:
— Фиксированный размер популяции.
— Фиксированная разрядность генов.
— Любые композиции стратегий отбора и формирования последующего поколения
— Ограничений на тип кроссовера и мутации нет.
— ГА применяется на исходном шаге, а потом в работу врубается традиционный способ оптимизации.[23]
3.4
Island Model GA
Представим для себя последующую ситуацию. В неком океане есть группа близлежащих островов, на которых живут популяции особей 1-го вида. Эти популяции развиваются независимо, и лишь время от времени происходит обмен представителями меж популяциями. Островная модель ГА употребляет описанный принцип для поиска решения. Вариант, непременно, увлекательный и является одной из разновидностей параллельных ГА. Данная модель генетического метода владеет последующими качествами:
— наличие нескольких популяций, обычно, схожего фиксированного размера.
— Фиксированная разрядность генов.
— Любые композиции стратегий отбора и формирования последующего поколения в каждой популяции. Можно создать так, что в различных популяциях будут употребляться различные композиции стратегий, хотя даже один вариант дает различные решения на разных «островах».
— Ограничений на тип кроссовера и мутации нет.
— Случайный обмен особями меж «островами». Если миграция будет очень активной, то индивидуальности островной модели будут сглажены, и она будет не весьма очень различаться от моделей ГА без параллелизма.[24]
3
.
5 CHC (Eshelman)
CHC расшифровываетсякак Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный метод достаточно стремительно сходится из-за того, что в нем нет мутаций, употребляются популяции маленького размера, и отбор особей в последующее поколение ведется и меж родительскими особями, и меж их потомками. В силу этого опосля нахождения некого решения метод перезапускается, при этом наилучшая особь копируется в новейшую популяцию, а оставшиеся особи подвергаются мощной мутации (мутирует приблизительно третья часть битов в хромосоме) имеющихся и поиск повторяется. Еще одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, при этом скрещиваются лишь те пары, в каких хромосомы особей значительно различны (хэммингово расстояние больше некого порогового плюс вероятны ограничения на малое расстояние меж последними различающимися битами). При скрещивании употребляется так именуемый HUX-оператор (Half Uniform Crossover) — это разновидность однородного кроссовера, но в нем к любому потомку попадает ровно половина битов хромосомы от всякого родителя. Таковым образом, модель владеет последующими качествами:
— Фиксированный размер популяции.
— Фиксированная разрядность генов.
— Перезапуск метода опосля нахождения решения.
— Маленькая популяция.
— Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных различий.
— Отбор в последующее поколение проводится меж родительскими особями и потомками.
— Употребляется половинный однородный кроссовер (HUX).
— Макромутация при перезапуске.[25]
II. Практическая часть реализации генетических алгоритмов
В данной учебно-исследовательской работе приведен пример программки использующей генетический метод. программка сотворена средством среды программирования С++. метод компонента представляет собой применение способов, узнаваемых в теории эволюции, для эвристического поиска решений переборных задач.
1. Математическое обоснование принципа работы программки
Проверим эффективность работы генетических алгоритмов на примере нахождения значений коэффициентов неведомых в Диофа́нтовом уравнении.
Диофа́нтово уравнение либо уравнение в целых числах — это уравнение с целыми коэффициентами и неведомыми, которые могут принимать лишь целые значения. Названы в честь древнегреческого математика Диофанта.[26]
Разглядим диофантово уравнение: a+2b+3c+4d=30, где a, b, c и d — некие положительные целые. Применение ГА за весьма куцее время находит разыскиваемое решение (a, b, c, d).
Архитектура ГА-систем дозволяет отыскать решение резвее за счет наиболее ‘осмысленного’ перебора. Мы не перебираем все попорядку, но приближаемся от случаем избранных решений к наилучшим.
Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Совершенно говоря, мы можем употреблять наименьшее ограничение для b,c,d, но для упрощения пусть будет 30.
Хромосома
(a,b,c,d)
1
(1,28,15,3)
2
(14,9,2,4)
3
(13,5,7,3)
4
(23,8,16,19)
5
(9,13,5,2)
Таблица 1
: 1-е поколение хромосом и их содержимое
Чтоб вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от приобретенного значения до 30 и будет необходимым значением.
Хромосома
Коэффициент выживаемости
1
|114-30|=84
2
|54-30|=24
3
|56-30|=26
4
|163-30|=133
5
|58-30|=28
Таблица 2
: Коэффициенты выживаемости первого поколения хромосом (набора решений)
Потому что наименьшие значения поближе к 30, то они наиболее желательны. В нашем случае огромные численные значения коэффициентов выживаемости подступают, как досадно бы это не звучало, меньше. Чтоб сделать систему, где хромосомы с наиболее пригодными значениями имеют огромные шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) быть может выбрана любая. Одно решение состоит в том, чтоб взять сумму оборотных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел — ГСЧ)
Хромосома
Подходящесть
1
(1/84)/0.135266 = 8.80%
2
(1/24)/0.135266 = 30.8%
3
(1/26)/0.135266 = 28.4%
4
(1/133)/0.135266 = 5.56%
5
(1/28)/0.135266 = 26.4%
Таблица 3
: Возможность оказаться родителем
Для выбора 5-и пар родителей (любая из которых будет иметь 1 потомка, всего — 5 новейших решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 — хромосома 2, на 2640 сторонах — хромосома 3, на 556 — хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтоб избрать первую пару кидаем кость дважды и избираем выпавшие хромосомы. Таковым же образом выбирая других, получаем:
Хромосома отца
Хромосома мамы
3
1
5
2
3
5
2
5
5
3
Таблица 4
: Симуляция выбора родителей
Любой потомок содержит информацию о генах и отца и от мамы. Совершенно говоря, это можно обеспечить разными методами, но в нашем случае можно употреблять т.н. «кроссовер» (cross-over). Пусть мама содержит последующий набор решений: a1,b1,c1,d1, а отец — a2,b2,c2,d2, тогда может быть 6 разных кроссоверов (| = разделительная линия):
Хромосома-отец
Хромосома-мать
Хромосома-потомок
a1
| b1
,c1
,d1
a2
| b2
,c2
,d2
a1
,b2
,c2
,d2
or a2
,b1
,c1
,d1
a1
,b1
| c1
,d1
a2
,b2
| c2
,d2
a1
,b1
,c2
,d2
or a2
,b2
,c1
,d1
a1
,b1
,c1
| d1
a2
,b2
,c2
| d2
a1
,b1
,c1
,d2
or a2
,b2
,c2
,d1
Таблица 5
: Кроссоверы меж родителями
Есть довольно много путей передачи инфы потомку, и кроссовер — лишь один из их. Размещение разделителя быть может полностью произвольным, как и то, отец либо мама будут слева от черты.
А сейчас попробуем сделать это с нашими потомками
Хромосома-отец
Хромосома-мать
Хромосома-потомок
(13 | 5,7,3)
(1 | 28,15,3)
(13,28,15,3)
(9,13 | 5,2)
(14,9 | 2,4)
(9,13,2,4)
(13,5,7 | 3)
(9,13,5 | 2)
(13,5,7,2)
(14 | 9,2,4)
(9 | 13,5,2)
(14,13,5,2)
(13,5 | 7, 3)
(9,13 | 5, 2)
(13,5,5,2)
Таблица 6
: Симуляция кросс-оверов хромосом родителей
сейчас мы можем вычислить коэффициенты выживаемости (fitness) потомков.
Хромосома-потомок
Коэффициент выживаемости
(13,28,15,3)
|126-30|=96
(9,13,2,4)
|57-30|=27
(13,5,7,2)
|57-30|=22
(14,13,5,2)
|63-30|=33
(13,5,5,2)
|46-30|=16
Таблица 7
: Коэффициенты выживаемости потомков (fitness)
Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент приравнивался 59.4. Последующее поколение может мутировать. к примеру, мы можем поменять одно из значений какой-либо хромосомы на случайное целое от 1 до 30.
Продолжая таковым образом, одна хромосома в конце концов достигнет коэффициента выживаемости 0, другими словами станет решением.
системы с большей популяцией (к примеру, 50 заместо 5-и сходятся к хотимому уровню (0) наиболее стремительно и размеренно.[27]
1.
1
Механизм работы программки
Oбранимся к теоретическим пояснениям в практической реализации данной задачки в среде программирования С++ :
Сперва поглядим на заголовок класса:
#include <stdlib.h>
#include <time.h>
#define MAXPOP 25
struct gene {
int alleles[4];
int fitness;
float likelihood;
// Test for equality.
operator==(gene gn) {
for (int i=0;i<4;i++) {
if (gn.alleles[i] != alleles[i]) return false;
}
return true;
}
};
class CDiophantine {
public:
CDiophantine(int, int, int, int, int);
int Solve();
// Returns a given gene.
gene GetGene(int i) { return population[i];}
protected:
int ca,cb,cc,cd;
int result;
gene population[MAXPOP];
int Fitness(gene &);
void GenerateLikelihoods();
float MultInv();inverse.
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
};
Есть две структуры: gene и класс CDiophantine. gene употребляется для слежения за разными наборами решений. Создаваямая популяция — популяция ген. Эта генетическая структура выслеживает свои коэффициенты выживаемости и возможность оказаться родителем. Также есть маленькая функция проверки на равенство.
сейчас по функциям:
Fitness function
Вычисляет коэффициент выживаемости (приспособленности — fitness) всякого гена. В нашем случае это — модуль разности меж хотимым результатом и приобретенным значением. Этот класс употребляет две функции: 1-ая вычисляет все коэффициенты, а 2-ая – гораздо меньше — вычисляет коэффициент для какого-то 1-го гена.
int CDiophantine::Fitness(gene &gn) {
int total = ca * gn.alleles[0] + cb * gn.alleles[1]
+ cc * gn.alleles[2] + cd * gn.alleles[3];
return gn.fitness = абс(total — result);
}
int CDiophantine::CreateFitnesses() {
float avgfit = 0;
int fitness = 0;
for(int i=0;i<MAXPOP;i++) {
fitness = Fitness(population[i]);
avgfit += fitness;
if (fitness == 0) {
return i;
}
}
return 0;
}
Заметим, что если fitness = 0, то найдено решение — возврат. Опосля вычисления приспособленности (fitness) нам необходимо вычислить возможность выбора этого гена в качестве родительского.
Likelihood functions
Как и было объяснено, возможность рассчитывается как сумма обращенных коэффициентов, деленная на величину, оборотную к коэффициенту данному значению. Вероятности кумулятивны (складываются), что делает весьма легким вычисления с родителями. к примеру:
Хромосома
Возможность
1
(1/84)/0.135266 = 8.80%
2
(1/24)/0.135266 = 30.8%
3
(1/26)/0.135266 = 28.4%
4
(1/133)/0.135266 = 5.56%
5
(1/28)/0.135266 = 26.4%
В программке, при схожих исходных значениях, вероятности сложатся: представьте их в виде кусков пирога. 1-ый ген — от 0 до 8.80%, последующий идет до 39.6% (потому что он начинает 8.8). Таблица вероятностей будет смотреться примерно так:
Хромосома
Возможность (smi = 0.135266)
1
(1/84)/smi = 8.80%
2
(1/24)/smi = 39.6% (30.6+8.8)
3
(1/26)/smi = 68% (28.4+39.6)
4
(1/133)/smi = 73.56% (5.56+68)
5
(1/28)/smi = 99.96% (26.4+73.56)
Крайнее одна вычисляет smi, а иная генерирует вероятности оказаться родителем.
float CDiophantine::MultInv() {
float sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].fitness);
}
return sum;
}
void CDiophantine::GenerateLikelihoods() {
float multinv = MultInv();
float last = 0;
for(int i=0;i<MAXPOP;i++) {
population[i].likelihood = last
= last + ((1/((float)population[i].fitness) / multinv) * 100);
}
}
Итак, у нас есть и коэффициенты выживаемости (fitness) и нужные вероятности (likelihood). Можно перебегать к размножению (breeding).
Breeding Functions
Функции размножения состоят из 3-х: получить индекс гена, отвечающего случайному числу от 1 до 100, конкретно вычислить кроссовер 2-ух генов и главной функции генерации новейшего поколения. Разглядим все эти функции сразу и то, как они друг друга вызывают. Вот основная функция размножения:
void CDiophantine::CreateNewPopulation() {
gene temppop[MAXPOP];
for(int i=0;i<MAXPOP;i++) {
int parent1 = 0, parent2 = 0, iterations = 0;
while(parent1 == parent2 || population[parent1]
== population[parent2]) {
parent1 = GetIndex((float)(rand() % 101));
parent2 = GetIndex((float)(rand() % 101));
if (++iterations > (MAXPOP * MAXPOP)) break;
}
temppop[i] = Breed(parent1, parent2); // Create a child.
}
for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
Итак, сперва мы создаем случайную популяцию генов. Потом делаем цикл по всем генам. Выбирая гены, мы не желаем, чтоб они оказались схожи (ни к чему скрещиваться с самим собой, и совершенно — нам не необходимы схожие гены (operator = в gene). При выбирании родителя, генерируем случайное число, а потом вызываем GetIndex. GetIndex употребляет идею кумулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число:
int CDiophantine::GetIndex(float val) {
float last = 0;
for(int i=0;i<MAXPOP;i++) {
if (last <= val && val <= population[i].likelihood) return i;
else last = population[i].likelihood;
}
return 4;
}
Ворачиваясь к функции CreateNewPopulation(): если число итераций превосходит MAXPOP2, она изберет всех родителей. Опосля того, как предки выбраны, они скрещиваются: их индексы передаются ввысь на функцию размножения (Breed). Breed function возвращает ген, который помещается во временную популяцию. Вот код:
gene CDiophantine::Breed(int p1, int p2) {
int crossover = rand() % 3+1;
int first = rand() % 100;
gene child = population[p1];
int initial = 0, final = 3;
if (first < 50) initial = crossover;
else final = crossover+1;
for(int i=initial;i<final;i++) {
child.alleles[i] = population[p2].alleles[i];
if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);
}
return child;
}
В конце концов мы определим точку кроссовера. Заметим, что мы не желаем, чтоб кроссовер состоял из копирования лишь 1-го родителя. Сгенерируем случайное число, которое обусловит наш кроссовер. Остальное понятно и разумеется. Добавлена малая мутация, влияющая на скрещивание. 5% — возможность возникновения новейшего числа.
сейчас уже можно посмотреть на функцию Solve(),которая вернет аллель, содержащую решение. Она всего только итеративно вызывает вышеперечисленные функции. Заметим, что мы находится проверка: удалось ли функции получить итог, используя исходную популяцию. Это маловероятно, но лучше проверить.
int CDiophantine::Solve() {
int fitness = -1;
// Generate initial population.
srand((unsigned)time(NULL));
for(int i=0;i<MAXPOP;i++) {
for (int j=0;j<4;j++) {
population[i].alleles[j] = rand() % (result + 1);
}
}
if (fitness = CreateFitnesses()) {
return fitness;
}
int iterations = 0;
while (fitness != 0 || iterations < 50) {
GenerateLikelihoods();
CreateNewPopulation();
if (fitness = CreateFitnesses()) {
return fitness;
}
iterations++;
}
return -1;
}
Описаниезавершено.
2.
Листинг
программки
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
#define MAXPOP 25
struct gene {
int alleles[4];
int fitness;
float likelihood;
// Test for equality.
operator==(gene gn) {
for (int i=0;i<4;i++) {
if (gn.alleles[i] != alleles[i] }
return false;
}
return true;
}
};
class CDiophantine {
public:
CDiophantine(int, int, int, int, int); // Constructor with coefficients for a,b,c,d.
int Solve(); // Solve the equation.
// Returns a given gene.
gene GetGene(int i) { return population[i];}
protected:
int ca,cb,cc,cd; // The coefficients.
int result;
gene population[MAXPOP]; // Population.
int Fitness(gene &); // Fitness function.
void GenerateLikelihoods(); // Generate likelihoods.
float MultInv(); // Creates the multiplicative inverse.
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
};
CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {}
int CDiophantine::Solve() {
int fitness = -1;
// Generate initial population.
srand((unsigned)time(NULL));
for(int i=0;i<MAXPOP;i++) { // Fill the population with numbers between
for (int j=0;j<4;j++) { // 0 and the result.
population[i].alleles[j] = rand() % (result + 1);
}
}
if (fitness = CreateFitnesses()) {
return fitness;
}
int iterations = 0; // Keep record of the iterations.
while (fitness != 0 || iterations < 50) {// Repeat until solution found, or over 50 iterations.
GenerateLikelihoods(); // Create the likelihoods.
CreateNewPopulation();
if (fitness = CreateFitnesses()) {
return fitness;
}
iterations++;
}
return -1;
}
int CDiophantine::Fitness(gene &gn) {
int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3];
return gn.fitness = абс(total — result);
}
int CDiophantine::CreateFitnesses() {
float avgfit = 0;
int fitness = 0;
for(int i=0;i<MAXPOP;i++) {
fitness = Fitness(population[i]);
avgfit += fitness;
if (fitness == 0) {
return i;
}
}
return 0;
}
float CDiophantine::MultInv() {
float sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].fitness);
}
return sum;
}
void CDiophantine::GenerateLikelihoods() {
float multinv = MultInv();
float last = 0;
for(int i=0;i<MAXPOP;i++) {
population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100);
}
}
int CDiophantine::GetIndex(float val) {
float last = 0;
for(int i=0;i<MAXPOP;i++) {
if (last <= val && val <= population[i].likelihood) return i;
else last = population[i].likelihood;
}
return 4;
}
gene CDiophantine::Breed(int p1, int p2) {
int crossover = rand() % 3+1; // Create the crossover
int first = rand() % 100; // Which parent comes first?
gene child = population[p1]; // Child is all first parent initially.
int initial = 0, final = 3; // The crossover boundaries.
if (first < 50) initial = crossover; // If first parent first. start from crossover.
else final = crossover+1; // Else end at crossover.
for(int i=initial;i<final;i++) { // Crossover!
child.alleles[i] = population[p2].alleles[i];
if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);
}
return child; // Return the kid…
}
void CDiophantine::CreateNewPopulation() {
gene temppop[MAXPOP];
for(int i=0;i<MAXPOP;i++) {
int parent1 = 0, parent2 = 0, iterations = 0;
while(parent1 == parent2 || population[parent1] == population[parent2]) {
parent1 = GetIndex((float)(rand() % 101));
parent2 = GetIndex((float)(rand() % 101));
if (++iterations > 25) break;
}
temppop[i] = Breed(parent1, parent2); // Create a child.
}
for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
void main() {
CDiophantine dp(1,2,3,4,30);
int ans;
ans = dp.Solve();
if (ans == -1) {
cout << «No solution found.» << endl;
} else {
gene gn = dp.GetGene(ans);
cout << «The solution set to a+2b+3c+4d=30 is:n»;
cout << «a = » << gn.alleles[0] << «.» << endl;
cout << «b = » << gn.alleles[1] << «.» << endl;
cout << «c = » << gn.alleles[2] << «.» << endl;
cout << «d = » << gn.alleles[3] << «.» << endl;
}
}
Заключение
Мы с вами сделали большенный путь, открывая себе генетические методы, их, чудилось бы, элементарную и сразу с сиим гениальную идею, взятую из природы. По окончанию работы можно создать выводы о том, что: во-1-х, генетические методы являются всепригодным способом оптимизации многопараметрических функций, что дозволяет решать широкий диапазон задач; во-2-х, они имеют огромное количество модификаций и очень зависят от характеристик. Часто маленькое изменение 1-го из их может привести к нежданному улучшению результата. Но следует держать в голове, что применение ГА полезно только в тех вариантах, когда для данной задачки нет пригодного специального метода решения.
Невзирая на маленькое количество задач в данной научно-исследовательской работе, которое мы с вами разглядели: решение Диофантова уравнения и задачку коммивояжера, мы стопроцентно подтверждаем догадку. задачки оптимизации удачно решаются с помощью генетических алгоритмов.
Перечень применяемой литературы
1. HTTP://www.basegroup.ru/download/genebase.htm
2. http://www.basegroup.ru/genetic/math.htm
3. HTTP://saisa.chat.ru/ga.html
4. http://algolist.Manual.ru/ai/ga/ga1.php
5. http://www.ai.tsi.lv/ru/ga/ga_intro.html
6. http://port33.ru/users/acp/articles/Genetic_algorithms/index.html
7. http://paklin.newmail.ru/mater/gene_net.html
8. http://www.iki.rssi.ru/ehips/genetic.htm
9. http://fdmhi.mega.ru/ru/senn_ga.htm
10. HTTP://www.vspu.ru/public_html/cterra/20.html
11. HTTP://www.chat.ru/~saisa
12. http://www.xakep.ru/post/18589/default.asp
13. HTTP://g-u-t.chat.ru/ga/oper.htm
14. http://iissvit.narod.ru/rass/vip4.htm
15. HTTP://www.nestor.minsk.by/kg/index.html
16. http://algo.ekaboka.com/algo-rus/index.htm
17. HTTP://www.neuroproject.ru
18. http://math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html
19. http://www.interface.ru/home.asp?artId=8109
20. http://algolist.ru/ai/ga/dioph.php
21. HTTP://ru.wikipedia.org/wiki/Диофантово_уравнение
[1]
http://paklin.newmail.ru/mater/gene_net.html
[2]
http://www.ai.tsi.lv/ru/ga/ga_intro.html
[3]
http://iissvit.narod.ru/rass/vip4.htm
[4]
HTTP://algo.ekaboka.com/algo-rus/index.htm
[5]
http://www.neuroproject.ru
[6]
HTTP://www.interface.ru/home.asp?artId=8109
[7]
http://math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html
[8]
http://www.basegroup.ru/genetic/math.htm
[9]
http://www.basegroup.ru/download/genebase.htm
[10]
HTTP://www.nestor.minsk.by/kg/index.html
[11]
http://www.iki.rssi.ru/ehips/genetic.htm
[12]
HTTP://fdmhi.mega.ru/ru/senn_ga.htm
[13]
http://chat.ru/ga.html
[14]
http://www.chat.ru/~saia
[15]
http://www.xakep.ru/post/18589/default.asp
[16]
HTTP://port33.ru/users/acp/articles/Genetic_algorithms/index.html
[17]
http://paklin.newmail.ru/mater/gene_net.html
[18]
http://www.vspu.ru/public_html/cterra/20.html
[19]
http://algolist.manual.ru/ai/ga/ga1.php
[20]
http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
[21]
http://algo.ekaboka.com/algo-rus/index.htm
[22]
HTTP://algolist.ru/ai/ga/dioph.php
[23]
http://g-u-t.chat.ru/ga/oper.htm
[24]
HTTP://g-u-t.chat.ru/ga/oper.htm
[25]
http://chat.ru/ga.html
[26]
HTTP://ru.wikipedia.org/wiki/Диофантово_уравнение
[27]
http://algolist.ru/ai/ga/dioph.php
]]>