Содержание: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

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

    Объектом изучения данной учебно-исследовательской работы являются генетические алгоритмы.

    Предметом изучения – применение генетических алгоритмов для нахождения решения задачи.

    Задача данной учебно-исследовательской работы состоит в изучении теоретического аспекта использования генетических алгоритмов, а так же в практической реализации задачи с использованием генетического алгоритма. 
 
 
 
 
 
 
 
 

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

     Природа поражает своей сложностью и богатством проявлений. Среди примеров можно  назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.²

     На  мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в природе.

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

     История эволюционных вычислений началась с  разработки ряда разных независимых  моделей. Основными из них были генетические алгоритмы и классификационные  системы Голанда (Holland), разработанные в начале 60-х годов. После выхода книги, ставшей классикой - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975), направление получило общее признание.⁴ 

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

1. системы, смоделированные на биологических принципах. Они успешно используются для задач функциональной оптимизации и могут легко быть описаны небиологическим языком;
2. системы, которые биологически более правдоподобны, но на практике неэффективными. Они больше похожи на биологические системы, имеют сложное и интересное поведение, и, наверняка, в ближайшем будущем получат практическое применение.

     Конечно, на практике нельзя разделять эти  вещи так строго. Эти категории - просто два полюса, между которыми лежат разные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).⁵

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

   Также в ней выделяют следующие направления:

• Эволюционные стратегии
• Метод оптимизации, основанный на идеях адаптации и эволюции. Степень мутации в данном случае меняется со временем – это приводит к, так называемой, самоадаптации.
• Генетическое программирование
• Применение эволюционного подхода к популяции программ.
• Эволюционное программирование
• Было впервые предложено Л.Дж. Фогелем в 1960 году для моделирования эволюции как процесса обучения с целью создания искусственного интеллекта. Он использовал конечные автоматы, предсказывающие символы в цифровых последовательностях, которые, эволюционируя, становились более приспособленными к решению поставленной задачи.⁶

Генетические алгоритмы применяются для решения следующих задач:

• Оптимизация функций
• Оптимизация запросов в базах данных
• Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
• Настройка и обучение искусственной нейронной сети
• Задачи компоновки
• Составление расписаний
• Игровые стратегии
• Аппроксимация функций
• Искусственная жизнь
• Биоинформатика ⁷

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

1.1 Постановка задачи и функция приспособленности

Пусть перед нами стоит задача оптимизации, например:

• Задача наилучшего приближения
• Если рассматривать систему n линейных уравнений с m неизвестными

Ax = b

в случае, когда она переопределена (n > m), то иногда оказывается естественной задача о нахождении вектора x, который "удовлетворяет этой системе наилучшим образом", т. е. из всех "не решений" является лучшим.

• Задача о рационе.
• Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через a_ij содержание (долю) j-го питательного вещества в i-ом продукте, через b_j — суточную потребность организма в j-ом питательном веществе, через c_i — стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах
• Транспортная задача.
• Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть a_i (i = 1, ..., n) — количество груза на i-ом складе, а b_j (j = 1, ..., m) — потребность в грузе j-го потребителя, c_ij — стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок.
• Задачи о распределении ресурсов.
• Общий смысл таких задач — распределить ограниченный ресурс между потребителями оптимальным образом. Рассмотрим простейший пример — задачу о режиме работы энергосистемы. Пусть m электростанций питают одну нагрузку мощности p. Обозначим через x_j активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум m_j и максимум M_j вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны e_j(x). Требуется сгенерировать требуемую мощность p при минимальных затратах.⁸

     Переформулируем задачу оптимизации как задачу нахождения максимума некоторой функции f(x₁, x₂, …, x_n), называемой функцией приспособленности (fitness function).  Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом совершенно не требуются непрерывность и дифференцируемость.

Каждый  параметр  функции приспособленности кодируется строкой битов.

     Особью  будет называться строка, являющаяся конкатенацией строк упорядоченного набора параметров (рис1):  

1010   10110   101    …    10101

|  x1  |    x2    |   x3   |  … |    xn   |

Рис 1. Ионкатенационная строка упорядоченного набора параметров 

     Универсальность ГА заключается в том, что от конкретной задачи зависят только такие параметры, как функция приспособленности  и кодирование решений. Остальные  шаги для всех задач производятся одинаково.⁹

1.2 Принцип работы ГА

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

     С помощью функции приспособленности  среди всех особей популяции выделяют:

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

     Таким образом, приспособленность нового поколения в среднем выше предыдущего.¹¹

В классическом ГА:

• начальная популяция формируется случайным образом
• размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма
• каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи
• длина кодировки для всех особей одинакова¹²

1.3 Алгоритм работы

На рисунке 2 изображена схема работы любого генетического алгоритма:

Рис 2. Схема работы любого генетического алгоритма. 

Шаг алгоритма  состоит из трех стадий:

1. генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения
2. скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения
3. мутация нового поколения ¹³