I. Теоретические аспекты решения задач с помощью генетических алгоритмов

Введение

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

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

Классический ГА