Современные алгоритмы обработки данных(Часть 2)
Генетические алгоритмы
Алгоритм решения задач оптимизации, основанный на идеях наследственности в биологических популяциях, был впервые предложен Джоном Холландом (1975). Он получил название репродуктивного плана Холланда, и широко использовался как базовый алгоритм в эволюционных вычислениях.
Цель генетического алгоритма при решении задачи оптимизации состоит в том, чтобы найти лучшее возможное, но не гарантированно оптимальное решение. Для реализации генетического алгоритма необходимо выбрать подходящую структуру данных для представления решений. В постановке задачи поиска оптимума, экземпляр этой структуры должен содержать информацию о некоторой точке в пространстве решений.
Структура данных генетического алгоритма состоит из набора хромосом. Хромосома, как правило, представляет собой битовую строку, так что термин строка часто заменяет понятие «хромосома». Хромосомы генетических алгоритмов не ограничены только бинарным представлением. Известны другие реализации, построенные на векторах вещественных чисел.
Для иллюстрации идеи мы ограничимся только структурами, которые являются битовыми строками. Каждая хромосома (строка) представляет собой последовательное объединение ряда подкомпонентов, которые называются генами. Гены расположены в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями - это биологическая терминология. В представлении хромосомы бинарной строкой, ген является битом этой строки, локус - есть позиция бита в строке, а аллель - это значение гена, равное 0 или 1.
Генотип. Биологический термин «генотип» относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме.
Фенотип. Термин «фенотип» относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров задачи.
Мутация. В генетике под мутацией понимается преобразование хромосомы, случайно изменяющее один или несколько генов. Наиболее распространенный вид мутаций - случайное изменение только одного из генов хромосомы.
Кроссинговер. Термин кроссинговер обозначает порождение из двух хромосом двух новых путем обмена генами.
Чтобы решить задачу оптимизации нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. При максимизации целевая функция часто сама выступает в качестве функции приспособленности, для задач минимизации целевая функция инвертируется и смещается в область положительных значений.
Рассмотрим фазы работы простого генетического алгоритма. В начале случайным образом генерируется начальная популяция (набор хромосом). Работа алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не будет смоделировано заданное число поколений или выполнен некоторый критерий останова. В каждом поколении реализуется пропорциональный отбор приспособленности, одноточечная рекомбинация и вероятностная мутация. Пропорциональный отбор реализуется путем назначения каждой особи (хромосоме) i вероятности Р(і), равной отношению ее приспособленности к суммарной приспособленности популяции (по целевой функции):
1. Создать начальную популяцию 2. Цикл по поколениям пока не выполнено условие останова // цикл жизни одного поколения 3. Оценить приспособленность каждой особи 4. Выполнить отбор по приспособленности 5. Случайным образом разбить популяцию на две группы пар 6 . Выполнить фазу вероятностной рекомбинации для пар популяции и заменить родителей 7. Выполнить фазу вероятностной мутации 8 . Оценить приспособленность новой популяции и вычислить условие останова 9. Объявить потомков новым поколением 10. Конец цикла по поколениям
Модификации генетического алгоритма
Применение генетических алгоритмов
Генетический алгоритм может стать эффективной процедурой поиска оптимального решения, если: • пространство поиска достаточно велико, и предполагается, что целевая функция не является гладкой и унимодальной в области поиска, т.е. не содержит один гладкий экстремум • задача не требует нахождения глобального оптимума, необходимо достаточно быстро найти приемлемое «хорошее» решение, что довольно часто встречается в реальных задачах.
Сегодня генетические алгоритмы успешно применяются для решения классических AP-полных задач, задач оптимизации в пространствах с большим количеством измерений, ряда экономических задач оптимального характера, например, задач распределения инвестиций.
Муравьиные алгоритмы
Муравьиные алгоритмы представляют собой новый перспективный метод решения задач оптимизации, в основе которого лежит моделирование поведения колонии муравьев. Колония представляет собой систему с очень простыми правилами автономного поведения особей. Однако, несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным. Исследования в этой области начались в середине 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия.
Биологические принципы поведения муравьиной
Коллектив муравьев называется колонией. Число муравьев в колонии может достигать нескольких миллионов. Одним из подтверждений оптимальности поведения колоний является тот факт, что сеть гнезд суперколоний близка к минимальному остовному дереву графа их муравейников. Колония не имеет централизованного управления, и ее особенностями является обмен локальной информацией только между отдельными особями и наличие непрямого обмена, который и используется в муравьиных алгоритмах.
Непрямой обмен - стигмержи (stigmergy), представляет собой разнесенное во времени взаимодействие, при котором одна особь изменяет некоторую область окружающей среды, а другие используют эту информацию позже, в момент, когда они в нее попадают. Концентрация феромона на тропе определяет предпочтительность движения по ней.
Идея муравьиного алгоритма
Идея муравьиного алгоритма — моделирование поведения муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своем движении муравей метит свой путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьев находить новый путь, если старый оказывается недоступным. Дойдя до преграды, муравьи с равной вероятностью будут обходить ее справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащен феромоном. Поскольку движение муравьев определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном. Очевидная положительная обратная связь быстро приведет к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьев. Моделирование испарения феромона — отрицательной обратной связи, гарантирует нам, что найденное локально оптимальное решение не будет единственным - муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, ребра которого представляют собой возможные пути перемещения муравьев, в течение определенного времени, то наиболее обогащенный феромоном путь по ребрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма.
Параллельные алгоритмы
Введение в параллелизм
Категории компьютерных систем
Компьютерные системы можно разделить на четыре основных категории. Для этого нужно несколько сменить наше представление о том, как работает программа. С точки зрения центрального процессора программа представляет собой поток инструкций, которые следует расшифровать и выполнить. Данные тоже можно считать поступающими в виде потока. Четыре категории, о которых мы говорим, определяются тем, поступают ли программы и данные одним потоком или несколькими.
Один поток инструкций / Один поток данных
Модель Один поток инструкций / Один поток данных (SISD) представляет собой классическую модель с одним процессором. К ней относятся как компьютеры предыдущих поколений, так и многие современные компьютеры. Процессор такого компьютера способен выполнять в любой момент времени лишь одну инструкцию и работать лишь с одним набором данных. В таких последовательных системах никакого параллелизма нет в отличие от прочих категорий.
Один поток инструкций / Несколько потоков данных
В компьютерах с одним потоком инструкций и несколькими по- токами данных (SIMD) имеется несколько процессоров, выполняющих одну и ту же операцию, но над различными данными. SIMD- машины иногда называются также векторными процессорами, поскольку они хорошо приспособлены для операций над векторами, в которых каждому процессору передается одна координата вектора и после выполнения операции весь вектор оказывается обработанным. Например, сложение векторов покоординатная операция. Первая координата суммы векторов -- сумма первых координат суммируемых векторов, вторая — сумма вторых координат, и т.д. В нашей SIMD- машине каждый процессор получит инструкцию сложить пару координат входных векторов. После выполнения этой единственной инструкции результат будет подсчитан полностью. Заметим, что на векторе из N элементов SISD-машине потребуется выполнить N итераций цикла, а SIMD-машине с не менее, чем N процессорами, хватит одной операции.
Несколько потоков инструкций / Один поток данных
Возможность одновременно выполнять различные операции над одними и теми же данными может поначалу показаться странной: не так уж часто встречаются программы, в которых нужно какое-то значение возвести в квадрат, умножить на 2, вычесть из него 10 и т.д. Однако, если посмотреть на эту ситуацию с другой точки зрения, то мы увидим, что на машинах такого типа можно усовершенствовать проверку числа на простоту . Если число процессоров равно N, то мы можем проверить простоту любого числа между 1 и Л^ на MISD-машине за одну операцию: если число X составное, то у него должен быть делитель, не превосходящий \fX. Для проверки простоты числа X < 7V поручим первому процессору делить на 2, второму — делить на 3, третьему - на 4, и так до процессора с номером К — 1, который будет делить на К, где К = [Л/А]. Если на одном из этих процессоров деление нацело проходит успешно, то число X составное. Поэтому мы достигаем результата за одну операцию. Как нетрудно видеть, на последовательной машине выполнение этого алгоритма потребовало бы по меньшей мере [л/-?] проходов, на каждом из которых производится одно деление.
Несколько потоков инструкций / Несколько потоков данных
Это наиболее гибкая из категорий. В случае MIMD-систем мы имеем дело с несколькими процессорами, каждый из которых способен выполнять свою инструкцию. Кроме того имеется несколько потоков данных, и каждый процессор может работать со своим набором данных. На практике это означает, что MIMD-система может выполнять на каждом процессоре свою программу или отдельные части одной и той же программы, или векторные операции так же, как и SIMD- конфигурация. Большинство современных подходов к параллелизму - включая кластеры компьютеров и мультипроцессорные системы — лежат в категории MIMD.
Параллельные архитектуры
В архитектуре параллельных компьютерных систем основную роль играют два аспекта: как связаны между собой процессоры и их память и как процессоры взаимодействуют. Об этих аспектах мы и будем говорить при обсуждении параллельных алгоритмов, поскольку те или иные решения могут иметь разную эффективность для различных задач.
Слабо и сильно связанные машины
В машинах со слабой связью у каждого процессора есть своя собственная память, а связь между процессорами осуществляется по «сетевым» кабелям. Это архитектура компьютерных кластеров: каждый компьютер кластера представляет собой отдельную компьютерную систему и может работать самостоятельно. Параллелизм осуществляется за счет распределения заданий по компьютерам кластера центральным управляющим компьютером. В машинах с тесными связями все процессоры пользуются общей центральной памятью. Взаимодействие процессоров осуществляется за счет того, что один из них записывает информацию в общую память, а остальные считывают ее оттуда.
Принципы анализа параллельных алгоритмов
При работе с параллельными алгоритмами нас будут интересовать два новых понятия: коэффициент ускорения и стоимость.
Коэффициент ускорения параллельного алгоритма показывает, насколько он работает быстрее оптимального последовательного алгоритма. Так, мы видели, что оптимальный алгоритм сортировки требует O(Nlog N) операций. У параллельного алгоритма сортировки со сложностью O(N) коэффициент ускорения составил бы О (log N). Второе интересующее нас понятие — стоимость параллельного ал- горитма, которую мы определяем как произведение сложности алгоритма на число используемых процессоров. Если в нашей ситуации алгоритм параллельной сортировки за O(N) операций требует столько же процессоров, каково число входных записей, то его стоимость равна O(N ). Это означает, что алгоритм параллельной сортировки обходится дороже, поскольку стоимость алгоритма последовательной сортировки на одном процессоре совпадает с его сложностью и равна поэтому O(Nlog N). Близким понятием является расщепляемость задачи. Если единственная возможность для нашего алгоритма параллельной сортировки состоит в том, что число процессоров должно равняться числу входных записей, то такой алгоритм становится бесполезным как только число входных записей оказывается достаточно большим. Никаких похожих ограничений в алгоритме последовательной сортировки нет. По большей части нас будут интересовать такие алгоритмы параллельной сортировки, в которых число процессоров значительно меньше потенциального объема входных данных и это число не требует увеличения при росте длины входа.
Модель PRAM
Одна из проблем параллельных систем состоит в чтении данных из памяти и записи в память. Что произойдет, например, если два процессора попытаются записать данные в одно и то же место общей памяти? В рассмотренных нами в главах 2-6 алгоритмах предполагалось, что машина, на которой они реализуются, обладает прямым доступом к любой наперед заданной ячейке памяти (RAM). Алгоритмы этой главы будут основаны на параллельном варианте такой машины, называемом PRAM. Процессоры нашей PRAM-машины тесно связаны между собой и пользуются общим блоком памяти. В каждом процессоре есть несколько регистров, в которых может храниться небольшой объем данных, однако основная часть данных содержится в общей памяти. Помимо требования тесной связи между процессорами мы также будем предполагать, что все они осуществляют один и тот же цикл обработки, состоящий в чтении данных из памяти, выполнении операции над ними и записи результата в память. Это означает, что все процессоры одновременно читают память, одновременно обрабатывают про- читанные данные и одновременно производят запись. Спор за ячейки памяти может возникнуть как при чтении, так и при записи. Требование трехшагового цикла означает, что мы можем не беспокоиться, что произойдет, если процессор Y меняет содержимое ячейки памяти в то время, как процессор X обрабатывает только что прочитанные оттуда данные. Не может также возникнуть и ситуация, в которой один процессор читает содержимое ячейки памяти в тот момент, когда другой пытается что-либо записать в нее.