Генетические алгоритмы и их практическое применение

Содержание:

Введение………………………………………………………………………………………… 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. системы, которые биологически более правдоподоб

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать