Современные алгоритмы обработки данных
Алгоритм решения задач оптимизации, основанный на идеях наследственности в биологических популяциях, был впервые предложен Джоном Холландом (1975). Он получил название репродуктивного плана Холланда, и широко использовался как базовый алгоритм в эволюционных вычислениях. Дальнейшее развитие эти идеи, как собственно и свое название - генетические алгоритмы, получили в работах Гольдберга и Де Йонга.
В настоящее время эффективные алгоритмы разрабатываются в рамках научного направления, которое можно назвать (природные вычисления), объединяющего такие разделы, как генетические алгоритмы, эволюционное программирование, нейросетевые вычисления, клеточные автоматы и ДНК вычисления, муравьиные алгоритмы. Исследователи обращаются к природным механизмам, которые миллионы лет обеспечивают адаптацию биоценозов к окружающей среде. Одним из таких механизмов, имеющих фундаментальный характер, является механизм наследственности. Его использование для решения задач оптимизации привело к появлению генетических алгоритмов.
Генетические алгоритмы
Алгоритм решения задач оптимизации, основанный на идеях наследственности в биологических популяциях, был впервые предложен Джоном Холландом (1975). Он получил название репродуктивного плана Холланда, и широко использовался как базовый алгоритм в эволюционных вычислениях.
Цель генетического алгоритма при решении задачи оптимизации состоит в том, чтобы найти лучшее возможное, но не гарантированно оптимальное решение. Для реализации генетического алгоритма необходимо выбрать подходящую структуру данных для представления решений. В постановке задачи поиска оптимума, экземпляр этой структуры должен содержать информацию о некоторой точке в пространстве решений.
Структура данных генетического алгоритма состоит из набора хромосом. Хромосома, как правило, представляет собой битовую строку, так что термин строка часто заменяет понятие «хромосома». Хромосомы генетических алгоритмов не ограничены только бинарным представлением. Известны другие реализации, построенные на векторах вещественных чисел.
Для иллюстрации идеи мы ограничимся только структурами, которые являются битовыми строками. Каждая хромосома (строка) представляет собой последовательное объединение ряда подкомпонентов, которые называются генами. Гены расположены в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями - это биологическая терминология. В представлении хромосомы бинарной строкой, ген является битом этой строки, локус - есть позиция бита в строке, а аллель - это значение гена, равное 0 или 1.
Генотип. Биологический термин «генотип» относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме.
Фенотип. Термин «фенотип» относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров задачи.
Мутация. В генетике под мутацией понимается преобразование хромосомы, случайно изменяющее один или несколько генов. Наиболее распространенный вид мутаций - случайное изменение только одного из генов хромосомы.
Кроссинговер. Термин кроссинговер обозначает порождение из двух хромосом двух новых путем обмена генами.
Чтобы решить задачу оптимизации нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. При максимизации целевая функция часто сама выступает в качестве функции приспособленности, для задач минимизации целевая функция инвертируется и смещается в область положительных значений.
Рассмотрим фазы работы простого генетического алгоритма. В начале случайным образом генерируется начальная популяция (набор хромосом). Работа алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не будет смоделировано заданное число поколений или выполнен некоторый критерий останова. В каждом поколении реализуется пропорциональный отбор приспособленности, одноточечная рекомбинация и вероятностная мутация. Пропорциональный отбор реализуется путем назначения каждой особи (хромосоме) i вероятности Р(і), равной отношению ее приспособленности к суммарной приспособленности популяции (по целевой функции):
1. Создать начальную популяцию 2. Цикл по поколениям пока не выполнено условие останова // цикл жизни одного поколения 3. Оценить приспособленность каждой особи 4. Выполнить отбор по приспособленности 5. Случайным образом разбить популяцию на две группы пар 6 . Выполнить фазу вероятностной рекомбинации для пар популяции и заменить родителей 7. Выполнить фазу вероятностной мутации 8 . Оценить приспособленность новой популяции и вычислить условие останова 9. Объявить потомков новым поколением 10. Конец цикла по поколениям
Модификации генетического алгоритма
Применение генетических алгоритмов
Генетический алгоритм может стать эффективной процедурой поиска оптимального решения, если: • пространство поиска достаточно велико, и предполагается, что целевая функция не является гладкой и унимодальной в области поиска, т.е. не содержит один гладкий экстремум • задача не требует нахождения глобального оптимума, необходимо достаточно быстро найти приемлемое «хорошее» решение, что довольно часто встречается в реальных задачах.
Сегодня генетические алгоритмы успешно применяются для решения классических AP-полных задач, задач оптимизации в пространствах с большим количеством измерений, ряда экономических задач оптимального характера, например, задач распределения инвестиций.
Муравьиные алгоритмы
Муравьиные алгоритмы представляют собой новый перспективный метод решения задач оптимизации, в основе которого лежит моделирование поведения колонии муравьев. Колония представляет собой систему с очень простыми правилами автономного поведения особей. Однако, несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным. Исследования в этой области начались в середине 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия.
Биологические принципы поведения муравьиной
Коллектив муравьев называется колонией. Число муравьев в колонии может достигать нескольких миллионов. Одним из подтверждений оптимальности поведения колоний является тот факт, что сеть гнезд суперколоний близка к минимальному остовному дереву графа их муравейников. Колония не имеет централизованного управления, и ее особенностями является обмен локальной информацией только между отдельными особями и наличие непрямого обмена, который и используется в муравьиных алгоритмах.
Непрямой обмен - стигмержи (stigmergy), представляет собой разнесенное во времени взаимодействие, при котором одна особь изменяет некоторую область окружающей среды, а другие используют эту информацию позже, в момент, когда они в нее попадают. Концентрация феромона на тропе определяет предпочтительность движения по ней.
Идея муравьиного алгоритма
Идея муравьиного алгоритма — моделирование поведения муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своем движении муравей метит свой путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьев находить новый путь, если старый оказывается недоступным. Дойдя до преграды, муравьи с равной вероятностью будут обходить ее справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащен феромоном. Поскольку движение муравьев определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном. Очевидная положительная обратная связь быстро приведет к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьев. Моделирование испарения феромона — отрицательной обратной связи, гарантирует нам, что найденное локально оптимальное решение не будет единственным - муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, ребра которого представляют собой возможные пути перемещения муравьев, в течение определенного времени, то наиболее обогащенный феромоном путь по ребрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма.