Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 11
Текст из файла (страница 11)
Сравнение эффективности алгоритмовРассмотрим классический последовательныйалгоритмимитацииотжига,последовательный алгоритм, использующий разбиение на области, и параллельныйалгоритм.Для исследования использовались графы модели прикладной программы соследующими характеристиками: количество рабочих интервалов от 100 до 250, числопроцессов от 40 до 90.По степени связности были выделены три класса графов:малое количество связей - K / N 1.2 ;среднее количество связей – 1.2 K / N 1.6 ;большое количество связей – K / N 1.6 .Здесь K – число дуг в графе, N - число вершин.Было проведено сравнительное исследование времени, затрачиваемого на поискрешения одного и того же качества классическим последовательным алгоритмом,последовательным алгоритмом, реализующим разбиение на области и параллельнымалгоритмом.
Были получены следующие результаты.На одном узле, без обмена данными с другими узлами возможно отсечение до 25%областей (рис. 3.7.), ещё до 20% от оставшихся областей исключается после обменаданных между узлами (рис. 3.8.). На рис. 3.9. показано количество отсеченных областей, взависимости от количества итераций алгоритмов в этих областях.5230%25%20%15%10%5%0%Высокая Средняя Низкаясвязность связность связностьРис.
3.7. Отсечение областей на одномузле без обмена с другими узлами.25%20%15%10%5%0%Высокая СредняяНизкаясвязность связность связностьРис. 3.8. Отсечение областей в результатеобмена с другими узлами.76543210%01I2I3I4I5I6I7I8I9I 10I 11I 12I 13I 14I 15I 16I 17IРис 3.9. Зависимость количества отсеченных областей от количества итераций алгоритмовзапущенных в этих областях. I = 1000.53Последовательный алгоритм, использующий разбиение на области по сравнению склассическим делает в 2-3 раза меньше итераций для графов с высокой связностью. Дляграфов со средней и низкой связностью этот показатель существенно ниже.В среднем параллельный алгоритм, запущенный на четырех процессорах, получалрешение в 2.21 раза быстрее, чем последовательный, применяющий разбиение на области;на восьми процессорах параллельный алгоритм осуществлял поиск решения в 3.34 разабыстрее, чем последовательный.
Предел увеличения быстродействия параллельногоалгоритма связан с тем, что около 20% операций (разбиение на области) выполняются наодном узле последовательно. Однако следует заметить, что операция разбиения наобласти также может быть распараллелена, что позволит достичь лучшего отношениявремен работы последовательного и параллельного алгоритмов. В среднем увеличениескорости выполнения параллельного алгоритма по сравнению с последовательным независит от параметров входного графа.Время работы алгоритмов, использующих разбиение на области, увеличивается суменьшением связности графа (рис. 3.10.).
Это обусловлено тем, что с уменьшениемсвязности графа, уменьшается процент областей, отсекаемых алгоритмом в ходе работы.На графах с высокой связностью критический путь близок к времени выполнениярасписания, получаемого алгоритмом, и большинство областей с высокими критическимипутями исключается из рассмотрения.На рис. 3.10. приведены обобщённые результаты исследования. За 100% взятонаибольшее зафиксированное время работы алгоритмов.54Низкая связностьСредняясвязностьВысокаяВысокаясвязностьсвязность00классическийклассический202040406060сс разбиениемразбиением нана областиобласти8080%%100100параллельныйпараллельный 44паралельныйпаралельныйРис. 3.10. Сравнение времени работы алгоритмов.Также было проведено сравнительное исследование качества решений приодинаковомвремениработыалгоритмов.Полученыследующиерезультаты.Параллельный алгоритм, работающий на четырех процессорах, в среднем получаетрасписания с временем выполнения на 1.8% меньшим, чем последовательный, и на 2.7%меньшим, чем классический.
Наибольшее уменьшение времени выполнения построенногорасписания наблюдается на графах с низкой связностью и составляет в среднем 3.8% посравнению с последовательным и 5.1% по сравнению с классическим. Это обусловленотем, что на графах с низкой степенью связности время выполнения оптимальногорасписания существенно больше критического пути в графе и за малое времяклассический и последовательный алгоритмы не успевают довести расписание до«хорошего» локального минимума.
На рис. 3.11.приведены обобщённые результатыисследования.55Низкая связностьСредняясвязностьВысокаясвязность%01c разбиением на области23456параллельный 4Рис. 3.11. Улучшение качества решений при использовании разбиения на области ипараллельного алгоритма по сравнению с решениями, полученными классическималгоритмом.564. Генетические и эволюционные алгоритмы4.1.Простой генетический алгоритм (алгоритм Холланда)Генетические и эволюционные алгоритмы основаны на использовании механизмовестественной эволюции. Эволюция, по Дарвину [Charles Darwin. The Origin of Species.
John Murray,London, 1859.],осуществляется в результате взаимодействия трех основных факторов:изменчивости, наследственности, естественного отбора. Изменчивость служит основойобразования новых признаков и особенностей в строении и функциях организма.Наследственность закрепляет эти признаки. Естественный отбор устраняет организмы,плохо приспособленные к условиям существования.Генетические и эволюционные вычисления получили общее признание послевыхода книги Холланда “Адаптация в естественных и искусственных системах” [HollandJ.N.
Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.].Предложенная в данной работе концепция построения генетических алгоритмов оказаласьчрезвычайно эффективной для решения многих задач, не поддающихся решениютрадиционнымиметодами.Концепциюпостроенияалгоритмов,предлагаемуюХолландом, схематично можно представить следующим образом:1. Сгенерировать случайным образом популяцию размера P.2. Выполнить операцию скрещивания.3. Выполнить операцию мутации.4.
Вычислить функцию выживаемости для каждой строки популяции.5. Выполнить операцию селекции.6. Если критерий останова не достигнут, перейти к шагу 2, иначе завершить работу.Популяция - это множество битовых строк. Каждая строка представляет взакодированном виде одно из возможных решений задачи. По строке может бытьвычислена функция выживаемости, которая характеризует качество решения.
В качественачальной популяции может быть использован произвольный набор строк. Основныеоперации алгоритма: селекция, скрещивание и мутация выполняются над элементамипопуляции. Результатом их выполнения является очередная популяция. Данный процесспродолжается итерационно до тех пор, пока не будет, достигнут критерий останова.57Кодированиерешений.Способкодированиярешенийдолженобладатьследующими свойствами:1. Однозначность, т.е. каждая закодированная строка должна соответствоватьединственному решению исходной задачи. Выполнение данного критериянеобходимо для статистической прогнозируемости поведения алгоритма иулучшения нахождения алгоритмом областей оптимальных решений.2. Возможность кодирования любого допустимого решения.3.
Получение в результате генетических операций корректных вариантов решений.4. Возможность перехода от любого корректного решения к любому другомукорректному решению.Универсальные подходы к кодированию решений очень часто или невозможны илине эффективны для решения сложных задач условной оптимизации. Однако, для задачнепрерывного и целочисленного математического программирования, наиболее частооптимизируемые параметры задаются, или двоичным кодом числа, или кодами Грея.Битовая строка получается склейкой битовых полей параметров.Операция селекции обеспечивает формирование на очередной итерации алгоритмаиз строк, полученных на шагах 2 и 3, новой популяции. Операция должна удовлетворятьследующим требованиям:1. Выделять каждой строке количество потомков в соответствии со значением еёфункции выживаемости, т.е.
если f(x1)>f(x2), то вероятность того, что Ch(x1)Ch(x2)должна быть достаточно велика. Здесь f– целевая функция, x1 и x2 – строкипопуляции, Ch(x) – количество потомков, присваиваемых строке x;2. Обеспечивать сохранение в популяции лучших решений, т.е. решения, имеющиемаксимальное значение целевой функции, должны сохраняться в популяции, впротивном случае алгоритм может утрачивать найденные хорошие значения;3. Не допускать обеднения и вырождения популяции, т.е. недопустимы популяции, вкоторых одно решение с высокой целевой функцией заполняет всю популяции, таккак в этом случае алгоритм утрачивает способность поиска по всему пространствурешений и скатывается к локальному оптимуму.Приведемдваклассическихвариантавыполненияоперации:схемапропорциональной селекции и схема рулетки.Схема пропорциональной селекции выглядит следующим образом:1.
Вычислить среднее значение функции выживаемости F для популяции.58F2. Для i-ой строки популяции выделить i потомков, где Fi – значение функции F выживаемости i-ой строки.3. Из полученных строк сформировать новую популяцию.Схема рулетки работает следующим образом:1. Вычислить среднее значение функции выживаемости для популяции.2. Для i-ой строки популяции выделить сектор рулетки с центральным углом 2FiF,где Fi – значение функции выживаемости i-ой строки.3. Сделать P запусков рулетки, где P – размер популяции. Каждый раз выделяемстроке в чей сектор мы попали 1-го потомка.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
