Современные алгоритмы обработки данных
Современные алгоритмы обработки данных
В настоящее время эффективные алгоритмы разрабатываются в рамках научного направления которое можно назвать “Природное вычисление” объединяющее такие разделы как генетические алгоритмы, эволюционное программирование, клеточные автоматы и днк вычисления, муравьиные алгоритмы. Миллионы лет обеспечивают адаптацию биоценозов к окружающей среде. Одним из таких механизмов имеющей фундаментальный характер является механизм наследственности. Его использования для решения задач оптимизации привело к появлению генетических алгоритмов.
Алгоритмы решения задач оптимизации основанный на идеях наследственности биологических популяций был впервые предложен Джоном Холландом в 1975 году. Этот алгоритм получил название репродуктивного плана Холланда и широко использовался как базовый алгоритм эволюционных вычислений
Цель генетического алгоритма состоит в том, чтобы найти лучшие возможные, но не гарантированное оптимальные решения. В постановке задачи поиска оптимального решения. Экземпляр этой структуры должен содержать информацию о некоторой точки в пространстве решений.
Структура данных генетического алгоритма состоит из набора хромосом. Хромосома как правило представляет собой битовую строку так что термин строка может заменить понятие хромосомы в генетическом алгоритме. Хромосомы в генетическом алгоритме(строки) не ограничены только в бинарном представлении. Известны другие реализации, построенные на векторах вещественных чисел.
Для иллюстрации идеи мы ограничимся только структурами, которые являются битовыми строками. Каждая хромосома, то есть строка представляет собой последовательные объединения ряда подкомпонентов, которые называются генами. Гены расположены в различных позициях или локусах хромосомы и принимают значение называемыми аллель. Представление хромосомы бинарной строкой, ген является битом этой строки. Локус — это позиция бита в строке. Аллель – значение гена, равное 0 или 1.
Чтобы решить задачу оптимизации нужно задать некоторую меру качества для каждой структуры в программе ….
Для этой цели используется функция …. При максимизации целевая функция в основном сама выступает в качестве функции приспособленности. Для задач минимизации целевая функция инвертируются и смещается в область положительных значений.
2) Цикл по поколениям, пока не выполнено условия останова (цикл жизни одного поколения)
3) Оценить приспособленность каждой особи.
4) Выполнить отбор по приспособленности
5) Случайным образом разбить популяцию на две группы пар
6) Выполнить фазу вероятности рекомбинации для пар популяции и заменить родителей.
7) Выполнить фазу вероятности мутации
8) Оценить приспособленность новой популяции и вычислить условия останова.
9) Объявить потомков новым поколением.
10) Конец цикла по поколениям.
Некоторые модификации генетического алгоритма. (Турнирный алгоритм, двухточечная рекомбинация, равномерная рекомбинация)
Применение генетических алгоритмов:
Генетический алгоритм может стать эффективным методом поиска оптимального решения в ситуациях, когда пространство поиска огромно, а целевая функция не является простой для нахождения. Если задача не требует глобального оптимального решения, необходимо быстро найти приемлемые решения. На сегодняшний день успешно применяется в экономике.