Генетические алгоритмы (стр. 3 из 3)
Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.
 |
Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально. 
Второй популярный способ основан на методе градиентного спуска. При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия.Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.
Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение.Однако, комбинируя переборный и градиентный методы, можно надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета.
Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск.
На рисунке показано, что такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач.Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время.
Литература и Ссылки:
Генетические алгоритмы по-русски http://www.chat.ru/~saisaНейроПроект. Аналитические технологии XXI векаhttp://www.neuroproject.ru
Научное издательство ТВПhttp://www.tvp.ru/mathem3.htm
Факультет вычислительной математики и кибернетики МГУ (ВМиК)
http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
Neural Bench Development http://www.neuralbench.ru/rus/theory/genetic.htm
Журнал "Автоматизация Проектирования" http://www.opensystems.ru/ap/1999/01/08.htm
(EHIPS) Генетические алгоритмы http://www.iki.rssi.ru/ehips/genetic.htm
SENN Генетические Алгоритмы http://fdmhi.mega.ru/ru/senn_ga.htm
Генетические алгоритмы и машинное обучение
http://www.math.tsu.ru/russian/center/ai_group/ai_collection/docs/faqs/ai/part5/faq3.html
Компьютерра | 11/1999 | Генетические алгоритмы: почему они работают?
http://www.vspu.ru/public_html/cterra/20.html
Лекции по нейронным сетям и генетическим алгоритмам
http://infoart.baku.az/inews/30000007.htm
@lgorithms: Catalogue of sources. http://algo.ekaboka.com/algo-rus/index.htm