Читать курсовая по математике: "Непрерывные генетические алгоритмы" Страница 2

(Назад) (Cкачать работу)

Второй путь - провести полный перебор вариантов инвестирования. Если каждая из 10 функций задана в 100 точках, то придется проверить около 1020 вариантов, что потребует не менее нескольких месяцев работы современного компьютера.

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

Наиболее популярными и проверенными из этих технологий являются нейронные сети и генетические алгоритмы. Первые коммерческие реализации на их основе появились в 80-х годах и получили широкое распространение в развитых странах.

Теория алгоритмов. Задача коммивояжера.

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.

Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности P, NP и другим.

Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных.

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

В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.).

К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга).

К классу NP - задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, т.е. машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу.

Другое определение класса NP: классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых сильно зависит от размера входных данных, но если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу. Проблема в том, что найти таких свидетелей бывает сложно, поэтому многие алгоритмы из класса NP считаются долгими. Классическим примером NP-задачи является задача коммивояжёра.

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

Похожие работы