На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Декабря 2024

Исследование эффективности бионических алгоритмов комбинаторной оптимизации

Effectiveness investigation of biology-inspired algorithms for combinatorial optimization
Статья опубликована в выпуске журнала № 3 за 2013 год. [ на стр. 126-130 ]
Аннотация:Для решения задачи коммивояжера предлагаются самонастраивающиеся бионические алгоритмы. Самонастройка алгоритмов обеспечивается за счет стохастического выбора настроек и/или параметров в ходе решения задачи в соответствии с распределениями вероятностей применения этих операторов. Распределения вероятностей модифицируются на каждом шаге алгоритма в соответствии с успешностью применения операторов (параметров), определяемой значением пригодности индивидов (решений), построенных с их помощью. Эффективность предложенных алгоритмов сравнивается с известными бионическими алгоритмами – обычным генетическим алгоритмом, муравьиным алгоритмом и алгоритмом умных капель, а также с локальным поиском (эвристикой Лина–Кернигана). На тестовых задачах большой размерности демонстрируется полезность предложенного подхода.
Abstract:Self-adaptive biology-inspired algorithms for the travelling salesman problem are introduced. Self-adaptation is organized through the settings and/or parameters stochasticchoice based on probability distributions of these operators ac-tivation (parameters use) during an algorithm execution. Probability distributions are modified on each algorithm’s step ac-cordingly to the operators (parameters) use success that is defined through the fitness value of solutions built with these oper-ators (parameters). Effectiveness of proposed algorithms is compared with known bio-inspired algorithms, namely with con-ventional genetic algorithm, ant colony optimization algorithm and intelligent water drops algorithm as well as with local search (Lean–Kernighan heuristic). The usefulness of the proposed approach is demonstrated on problems with high dimen-sion.
Авторы: Семенкина О.Е. (oleese@mail.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева (младший научный сотрудник), г. Красноярск, Россия, Семенкина О.Э. (semenkina.olga@mail.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева (профессор), г. Красноярск, Россия, доктор технических наук
Ключевые слова: адаптивность., эвристика лина–кернигана, алгоритм умных капель, муравьиный алгоритм, генетический алгоритм, комбинаторная оптимизация
Keywords: self-adaptive, lin–kernighan heuristic, intelligent water drops algorithm, ant colony optimization, generic algorithm, combinatorial optimization
Количество просмотров: 13888
Версия для печати
Выпуск в формате PDF (13.63Мб)
Скачать обложку в формате PDF (1.39Мб)

Размер шрифта:       Шрифт:

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

Пусть имеется заданное множество из n городов. Требуется найти замкнутый обход минимальной длины при условии, что каждый город должен быть посещен только один раз.

Задача коммивояжера имеет множество практических применений, таких как задачи маршрутизации, составления расписания с ограничениями, задачи игрового типа для поиска оптимальной стратегии и т.д.

Широкое применение при решении таких задач получили недетерминированные многоагентные алгоритмы, в том числе бионические. В данной статье рассматриваются генетический алгоритм (ГА) [1], муравьиный алгоритм (Ant Colony Opti­mization, ACO) [2], алгоритм умных капель (Intelli­gent Water Drops, IWDs) [3], эвристика Лина–Кер­нигана [4] и авторские адаптивные ГА и АСО.

Описание алгоритмов

Алгоритм ACO основан на имитации поведения колонии муравьев в природе [2]. Являясь практически слепыми, муравьи все же отыскивают кратчайший путь от гнезда до источника пищи и обратно. Для обмена информацией они используют фермент (называемый феромоном), который оставляют на пройденном пути. Вероятность того, что муравей выберет определенный путь, пропорциональна количеству феромона на нем. Следовательно, чем больше муравьев прошло данным путем, тем более притягательным он становится для следующих.

Каждый муравей, совершая обход, пополняет свой табу-лист, то есть список посещенных городов, а после завершения обхода оставляет некоторое количество феромона, то есть след, на каждом пройденном им ребре. Вероятность выбора города является функцией расстояния до города и количества феромона, оставленного всеми муравьями на соединяющем ребре. Интенсивность следа обновляется по завершении всеми муравьями своих обходов. Поиск повторяется до исчерпания выделенного вычислительного ресурса. Алгоритм АСО управляется четырьмя параметрами (относительные важности следа и расстояния до следующего города, интенсивность испарения следа и др.). Так как каждый параметр может принимать большое количество значений, число различных наборов этих параметров очень велико, но в своих экспериментах авторы не ставили целью тонкую подстройку алгоритма под конкретную задачу и поэтому оставили только 16 вариантов.

Алгоритм IWDs основан на имитации поведения потоков (множеств капель) в реке [3]. Для каждого множества капель река является окружающей средой, которая влияет на него, но в то же время и это множество влияет на реку. То есть как капли влияют на маршрут реки, так и путь реки влияет на маршрут каждой отдельной капли. Большое влияние на движение реки оказывают тип грунта и его сопротивление потоку, так как от него зависит скорость капель. Таким образом, река представляет собой результат противоборства множества капель воды и сопротивления окружающей среды. Можно также заметить, что все реки в природе имеют множество изгибов и поворотов, так как под действием силы тяжести, выбирая путь наименьшего сопротивления, вода движется по направлению к самой низкой точке.

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

На основании рассмотренных выше свойств Шах-Хоссейни в 2007 году предложил алгоритм умных капель [3]. Каждая умная капля воды (IWD) имеет два важных свойства: количество грунта (soil), который она несет, и скорость (velocity), с которой она двигается. Эти свойства могут изменять то, как движется капля в окружающей среде.

С математической точки зрения окружающая среда представляет собой решаемую задачу, а река, состоящая из капель, ищет оптимальный путь. Эффективность алгоритма зависит от многих параметров, часть которых (коэффициенты обновления скоростей капель и грунта и др.) в авторских экспериментах были фиксированы в соответствии с рекомендациями [3], но другие требовали настройки под конкретную задачу (начальное количество капель, начальная скорость каждой капли, параметр обновления грунта, значимость лучшего решения при обновлении матрицы грунта – всего 24 различных варианта).

Одним из классических методов решения за- дачи коммивояжера, как и задач оптимизации, является локальный спуск, в частности алгоритм 3-за­мена, или эвристика Лина–Кернигана [4]. При построении алгоритмов локального поиска основным является определение окрестности. Для за- дачи коммивояжера обычно используются окрестности типа k-замены: два обхода лежат в такой окрестности, если они могут быть получены друг из друга удалением и заменой k ребер. Алгоритм локального поиска перебирает элементы окрестности текущего решения до обнаружения улучшения. Если улучшение находится, то соответствующее решение становится центром окрестности и алгоритм продолжает поиск, в противном случае текущее решение и есть локальный оптимум. В своих работах Лин показал, что 3-оптимальные решения намного лучше 2-оптимальных, а 4-опти­мальные лучше 3-оптимальных, но не настолько, чтобы были оправданы дополнительные вычислительные затраты [4]. Именно поэтому в данной работе рассматривается алгоритм 3-замены, являющийся частным случаем k-замены.

ГА основывается на заимствовании из природы идеи естественной эволюции [1]. В связи с этим решение задачи является хромосомой индивида в популяции (множество решений). В своей работе ГА использует несколько операторов, итерационно следующих друг за другом: селекция, рекомбинация (порождение потомков), мутация, селекция выживших, формирование следующего поколения. В связи с тем, что представление решения в виде хромосомы при решении задачи коммивояжера отличается от стандартной бинарной строки (представляет собой перестановку n чисел), стандартные генетические операторы видоизменены. Однако сохраняется большое количество настраиваемых параметров, таких как вероятность мутации, тип селекции – турнирная (с выбором размера турнира), пропорциональная и ранговая (с линейным или экспоненциальным ранжированием), тип скрещивания и т.д. Авторы экспериментально проверяли взаимодействие типов селекции и уровней мутации, приняв остальные параметры неизменными. Это привело к необходимости проверки 24 вариантов настройки алгоритма.

Выбор эффективных вариантов настроек ГА или АСО сам по себе является трудной задачей даже для специалиста в области эволюционных вычислений. Поэтому целесообразной кажется идея самонастраивающегося ГА и самонастраивающегося АСО с автоматической настройкой параметров алгоритма по ходу его работы.

Суть предлагаемого подхода для ГА в следующем. Для каждого оператора выбор его варианта осуществляется отдельно. Пусть z – число вариантов данного оператора. Например, если варианты оператора селекции турнирная с размерами турнира 2, 4 и 8 и пропорциональная, то z=4.

В начале работы алгоритма вероятности выбора всех вариантов оператора одинаковы: p=1/z. На каждом поколении производится оценка эффективности каждого варианта оператора следующим образом:  i=1, 2, …, z, где ni – количество индивидов, полученных с применением i-го варианта оператора; fij – пригодность j-го индивида, полученного i-м вариантом оператора; averagefitnessi – средняя пригодность потомков, порожденных i-м вариантом оператора.

Вероятность варианта оператора с наибольшим значением averagefitness (то есть наиболее эффективного) увеличивается на ((z–1)∙K)/(z∙N), тогда как вероятности всех остальных операторов уменьшаются на K/(z∙N), где N – число прошедших поколений работы алгоритма; K – константа, обычно равная 2. Кроме того, устанавливается порог снижения вероятности, так как ни в одном из вариантов оператора эта вероятность не может быть равна нулю. При достижении минимально возможного значения вероятности такой вариант оператора перестает отдавать свою долю в пользу лучшего. Сумма вероятностей для всех вариантов одного оператора всегда равна единице. Таким образом, распределение вероятностей выбора варианта оператора постепенно смещается в сторону более эффективных за счет менее эффективных вариантов.

Описанным способом выбирается вариант каждого оператора для каждого будущего потомка перед началом процесса его порождения. В таком случае у самонастраивающегося алгоритма не остается вариантов выбора настроек – он единственный. Разумеется, необходимо заранее выбрать размер популяции и число поколений алгоритма (предоставляемый ресурс), но это верно и для всех других алгоритмов и не рассматривается как их настройка.

Такой же подход к созданию адаптивных алгоритмов был применен и для ACO. В этом случае рассматриваются не операторы с различными вариантами настроек, а параметры (относительная важность следа и относительная важность расстояния до соседнего города) с различными значениями. Аналогично операторам ГА для каждого значения каждого из параметров вероятность его использования изменяется по приведенным выше формулам.

В данной работе адаптивный ACO располагал шестнадцатью вариантами настроек (по четыре для каждого из параметров), а именно 1, 2, 5, 10. Адаптивный ГА имел 8 вариантов селекции: турнирная с размером турнира 2, 4 и 8, ранговая с линейным ранжированием, ранговая с экспоненциальным ранжированием с параметром λ, равным 0,95, 0,8 и 0,5, и пропорциональная, а также 5 вариантов мутации: очень низкая, низкая, средняя, высокая и очень высокая.

Анализ работы бионических алгоритмов комбинаторной оптимизации

Описанные выше алгоритмы были реализованы на языке программирования С++ в виде программной системы решения комбинаторных задач оптимизации на перестановках. Эффективность работы этих алгоритмов сравнивалась на двух широко известных тестовых задачах – Eil51 и Oliver30 [5], число городов в которых равно соответственно 51 и 30.

На задаче Oliver30 алгоритм 3-замены для сходимости в среднем требовал 52 800 вычислений целевой функции, поэтому всем остальным алгоритмам давалось такое же количество ресурсов (30 индивидов, 1 760 итераций). Усреднение проводилось по 100 прогонам, оптимальное решение этой задачи имеет длину 423,741.

На задаче Eil51 алгоритм 3-замены в среднем требовал 342 210 вычислений целевой функции, поэтому количество ресурсов, выделяемое остальным алгоритмам, – 51 индивид, 6 710 поколений. Усреднение на данной задаче проводилось по 50 прогонам, а оптимальное решение имеет длину 426.

Результаты работы при лучших настройках, а именно длина лучшего маршрута из всех прогонов, средняя длина маршрута по всем прогонам, а также среднеквадратичное отклонение (СКО) для обеих задач приведены в таблице 1.

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

Таблица 1

Эффективность работы алгоритмов на задачах Oliver30 и Eil51

Алгоритм

Длина лучшего обхода

Средняя длина обхода

СКО

Oliver30

3-замена

423,741

428,610

7,4740

ACO

423,741

423,782

0,1675

 

IWDs

423,741

425,500

3,7022

 

GA

423,741

432,356

13,2365

 

Adaptive GA

423,741

434,239

13,6875

 

Adaptive ACO

423,741

426,428

3,7653

 

Eil51

 

3-замена

428,872

438,598

5,0160

 

ACO

429,484

432,732

3,11622

 

IWDs

428,872

437,279

5,57137

 

GA

431,953

447,943

7,5848

 

Adaptive GA

429,118

449,938

9,94143

 

Adaptive ACO

429,484

433,936

2,88955

 

Поскольку эффективность бионических алгоритмов на конкретной задаче существенно различается в зависимости от настроек, более реалистичным будет предположение, что при однократном решении задачи, что и ожидается на практике, эффективность применяемых алгоритмов будет более близка к средней на этой задаче, а не к наилучшей. Такое сравнение на задаче Oliver30 приведено в таблице 2, где три строки для каждого алгоритма (GA, ACO, IWDs) содержат значения целевой функции, найденные при наилучших и наихудших настройках, а также усредненные по всем настройкам, а столбцы содержат усреднение по прогонам и СКО.

Таблица 2

Сравнение эффективности алгоритмов при различных настройках

Задача

Oliver30

Настройки/прогоны

Лучший

Средний

СКО

GA

Лучшие

423,741

431,647

11,3784

Средние

424,139

442,982

12,8611

Худшие

425,267

469,459

27,0638

ACO

Лучшие

423,741

424,040

0,4299

Средние

428,684

443,771

11,7151

Худшие

461,453

504,088

28,0251

IWDs

Лучшие

423,741

426,413

3,1992

Средние

423,965

434,7496

10,1741

Худшие

424,692

449,307

19,0374

3-opt

423,741

434,610

11,9310

Adaptive GA

423,741

434,485

12,7539

Adaptive ACO

423,741

426,428

3,7653

Анализ полученных результатов показывает, что оба адаптивных алгоритма превосходят остальные алгоритмы с неоптимальными настройками, а адаптивный АСО превосходит и ГА с оптимальными настройками. Это позволяет сделать вывод о полезности выполненной модификации бионических алгоритмов, предусматривающей их автоматическую настройку.

Подытоживая, отметим, что в данной работе предложен и апробирован подход к построению адаптивных бионических алгоритмов комбинаторной оптимизации, основанный на автоматической подстройке вероятностей выбора типов операторов или дискретных значений параметров. Показано, что полученные таким образом алгоритмы близки по эффективности к своим оптимально настроенным аналогам, хотя и не требуют усилий по настройке. Данный подход не может напрямую распространяться на алгоритм IDWs, обладающий большим количеством вещественных параметров, требующих тонкой подстройки. Для его применения в данном случае требуются отдельные исследования.

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

Литература

1.     Гуменникова А.В., Емельянова М.Н., Семенкин Е.С., Сопов Е.А. Об эволюционных алгоритмах решения сложных задач оптимизации // Вестн. СибГАУ. 2003. № 4. С. 14–23.

2.     Dorigo М., Gambardella L.M., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol. 1, Is. 1, 1997, pp. 53–66.

3.     Shah-Hosseini H., Optimization with the Nature-Inspired Intelligent Water Drops Algorithm, Evolutionary Computation, Vienna, InTech, 2009, pp. 299–319.

4.     Lin Sh., Kernighan B.W., An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, 1973, no. 21 (2), pp. 498–516.

5.     Oliver I.M., Smith D.J., Holland J.R.C., A study of permutation crossover operators on the travelling salesman problem, Proc. 2nd Intern. Conf. on Genetic Algorithms and their application, 1987, pp. 224–230.

References

1.     Gumennikova A.V., Emelyanova M.N., Semenkin E.S., Sopov E.A., Vestnik SibGAU [Bulletin of the SibSAU], 2003, no. 4, pp. 14–23.

2.     Dorigo М., Gambardella L.M., IEEE Transactions on Evolutionary Computation, Vol. 1, iss. 1, 1997, pp. 53–66.

3.     Shah-Hosseini H., Evolutionary Computation, Vienna, InTech, 2009, pp. 299–319.

4.     Lin Sh., Kernighan B.W., Operations Research, 1973, no. 21 (2), pp. 498–516.

5.     Oliver I.M., Smith D.J., Holland J.R.C., Proc. of the 2nd Int. Conf. on Genetic Algorithms and their application, 1987, pp. 224–230.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=3572&lang=&lang=&like=1
Версия для печати
Выпуск в формате PDF (13.63Мб)
Скачать обложку в формате PDF (1.39Мб)
Статья опубликована в выпуске журнала № 3 за 2013 год. [ на стр. 126-130 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: