Файл: Системы на базе генетических алгоритмов.docx

Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.

Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально.

Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально.

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

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

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

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

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

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

---

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

Системы на базе генетических алгоритмов

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

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



Рисунок 1. Система EDDIE

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

1. 
   Оптимизация функций.
   
2. 
   Оптимизация запросов в базах данных.
   
3. 
   Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний).
   
4. 
   Настройка и обучение искусственной нейронной сети.
   
5. 
   Задачи компоновки.
   
6. 
   Составление расписаний.
   
7. 
   Игровые стратегии.
   
8. 
   Теория приближений.
   
9. 
   Искусственная жизнь.
   

Заключение

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

В завершении хотелось бы отметить, что область применения генетических алгоритмов многогранна.

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

---

Список используемых источников

1. 
   Рутковская Д., Пилиньский М., Рутковский Л. – «Нейронные сети, генетические алгоритмы и нечеткие системы»
   
2. 
   Генетические алгоритмы [Электронный ресурс] Режим доступа - http://www.sernam.ru/book_gen.php
   
3. 
   Популярно о генетических алгоритмах [Электронный ресурс] Режим доступа:http://knowledge.allbest.ru/programming/3c0b65625b3bc78a5c43b89421316c27_0.html
   
4. 
   Особенности генетических алгоритмов [Электронный ресурс] Режим доступа - http://www.masters.donntu.edu.ua/2000/fkita/stupchak/oglavl.htm
   
5. 
   Генетические агоритмы [Электронный ресурс] Режим доступа -http://www.bestreferat.ru/referat-213707.html
   
6. 
   NeuroProject _ Обучение _ Статьи - Что такое генетические алгоритмы [Электронный ресурс] Режим доступа - http://works.tarefer.ru/69/100400/index.html
   
7. 
   Программирование искусственного интеллекта [Электронный ресурс] Режим доступа - http://www.itfru.ru/index.php/genetic-algorithms
   

---