[Перевод] Алгоритм генетической колонии пчел для задачи коммивояжера04.11.2024 18:31

I. Введение

Выбор наилучшего элемента из нескольких существующих альтернатив называется задачей оптимизации. Во большинстве таких задачах исчерпывающий поиск нецелесообразен. Это имеет важные приложения в нескольких областях, включая искусственный интеллект, машинное обучение, математику и программную инженерию. Большинство таких задач считаются NP-трудными, то есть их нельзя решить оптимально за полиномиальное время вычислений. Некоторые общие задачи, связанные с оптимизацией, включают задачу коммивояжера, задачу о минимальном остовном дереве и другие. 

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

Существуют различные метаэвристики и алгоритмы приближенного решения, которые быстро дают хорошие решения.[5] [6] [7]  Современные методы могут находить решения для чрезвычайно больших задач (миллионы городов) за разумное время. Несколько алгоритмов, использующих метаэвристические подходы, такие как генетический алгоритм (ГА),[5] оптимизация колонии муравьев (ОКМ), [11] оптимизация роя частиц (ОРЧ)[7] или оптимизация пчелиной колонии (ОПК),[6] [8]  были применены для решения ЗК. Существуют также несколько гибридных методов, которые решают ЗК.

Сарают и Сирифон[9] предложили ОКМ -ГА и ОКМ- ОРЧ как гибридные методы. Эти методы работают на основе настройки параметра Qo. Если Qo высок, локальный поиск будет ориентирован на эксплуатацию, а когда Qo низок — на исследование. Вонг и др. применили[8] ОПК для решения ЗК. Эти алгоритмы в среднем дают решения с меньшей точностью. Для улучшения этих результатов мы сосредоточимся на алгоритме ИПК,[11]  эффективном алгоритме, который уже применяется в нескольких задачах оптимизации. [11]

В этой статье мы расширяем ИПК и ГА на область комбинаторных задач. Предложенный метод совмещает ИПК и ГА с тремя основными операторами пчелиной колонии для нахождения оптимальности. Для проверки эффективности предложенного метода в нашем эксперименте используется ЗК.

Генетический алгоритм применяется во время обновления решения, и перед каждым успешным обновлением используются пчелы-работницы, а после обновления применяются наблюдательные и разведывательные пчелы. Это, в свою очередь, приводит к модификации позиции (решения) в их памяти для нахождения новой цепочки путей и тестирует количество нектара (значение приспособленности) нового решения. Экспериментальные результаты показывают, что предложенный метод (РГАПК) дает лучшие и более эффективные результаты по сравнению с классическим генетическим алгоритмом. 

Структура статьи следующая: в разделе II дается краткое введение в генетический алгоритм. В разделе III объясняется оптимизация с помощью искусственной пчелиной колонии, в разделе IV вводится задача коммивояжера (ЗК). В разделе V описывается алгоритм генетической колонии реальных пчел; предложенная методология (РГАПК) объясняется в разделе VI. В разделе VII изложены экспериментальная установка и результаты, в разделе VIII приводится заключение.

II. Генетический алгоритм

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

Генетический алгоритм использует принцип «выживания наиболее приспособленных» в процессе поиска для выбора и генерации индивидуумов (дизайнерских решений), которые адаптированы к своей среде (дизайнерским целям/ограничениям). Поэтому на протяжении нескольких поколений (итераций) желательные черты (дизайнерские характеристики) будут эволюционировать и сохраняться в геномной композиции популяции (набор дизайнерских решений, генерируемых на каждой итерации) в отличие от черт с более слабыми нежелательными характеристиками. Генетический алгоритм хорошо подходит для решения сложных задач оптимизации дизайна и широко применяется для этого, поскольку он может обрабатывать как дискретные, так и непрерывные переменные, а также нелинейные целевые функции и функции ограничений без необходимости в градиентной информации.

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

Если у особи относительно высокая величина приспособленности, у нее больше шансов оставить потомство в следующем поколении по правилу выбора на основе приспособленности. Этот оператор является искусственной версией естественного отбора. На этапе скрещивания два индивидуума из текущей популяции выбираются случайным образом, и они обмениваются своими битами с точки пересечения, определенной другим случайным числом. Во время процесса мутации каждый бит имеет равную вероятность быть замененным на свой комплементарный номер. Это имитация естественного скрещивания и также очень редка в процессе работы ГА. Генетический алгоритм с действительными кодами (ГАСДК) использует строки действительных чисел для параметров, которые необходимо исследовать; общее количество параметров равно k. Sr = {1.52, 0.856, 15.23, …………, 6.93} 

Где Sr представляет собой конкатенированные строки ГАСДК соответственно. Поскольку представление хромосом в ГАСДК отличается от представления в бинарном генетическом алгоритме, оператор скрещивания должен быть модифицирован. До сих пор было предложено множество видов операторов скрещивания, включая простое скрещивание, арифметическое скрещивание [13], BLX-CY скрещивание [12] и модифицированное простое скрещивание [14]. В данной работе мы использовали линейное скрещивание.

III. Иcкусственная пчелиная колония

Алгоритм искусственной пчелиной колонии (ИПК) — это алгоритм оптимизации, основанный на интеллектуальном поведении пчел при сборе нектара. Эта модель была предложена Дервисом Карабога в 2005 году и основана на изучении поведения настоящих пчел при поиске количества нектара и обмене информацией о источниках пищи с другими пчелами в улье. Эти специализированные пчелы стремятся максимизировать количество нектара, хранящегося в улье, выполняя эффективное распределение труда и самоорганизацию. Три агента в искусственной пчелиной колонии:

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

• Наблюдатель-пчела: Наблюдатели — это пчелы, которые ждут на танцевальной площадке, чтобы решить, какой источник пищи лучше. Это решение принимается на основе информации, предоставленной рабочими пчелами. Наблюдатели выполняют глобальный поиск для нахождения глобального оптимума. Пчёлы-разведчики проводят случайный поиск пищи.

• Пчёл-разведчик: пчёлы-разведчики выполняют случайный поиск пищи. Разведчики исследуют новые области, которые не были охвачены рабочими пчелами; эти пчелы действуют совершенно случайным образом в процессе поиска. Пчёлы-разведчики избегают процесса поиска, чтобы не застрять в локальных минимумах.

В алгоритме ИПК каждая позиция источника пищи представляет собой кандидатное решение задачи оптимизации. В задаче оптимизации каждое решение связано с его значением пригодности, на основе которого определяется, какое решение лучше. Таким образом, количество нектара источника пищи соответствует значению пригодности связанного решения в алгоритме ИПК. Количество занятых пчел или наблюдателей равно количеству решений в популяции. Алгоритм ИПК генерирует случайное решение или начальную популяцию размером NF, где NF обозначает размер популяции или общее количество источников пищи. Каждое решение представляет собой позицию источника пищи и обозначается как Xij, где i представляет конкретное решение (i=1,2, …, NF), а каждое решение является D-мерным вектором, так что j представляет конкретное измерение конкретного решения (j=1,2, …, D).

После инициализации случайного решения занятые пчелы начинают поиск. Занятые пчелы ищут источник пищи рядом с предыдущим источником пищи; если сгенерированное новое решение лучше предыдущего, то новое решение заменяет старое. Сравнение источников пищи или решений производится на основе значения пригодности или количества нектара источника пищи. После того как все занятые пчелы завершат процесс поиска, они делятся информацией о нектарах источников пищи (решениях) и их позиционной информацией с наблюдателями. Теперь наблюдатель выбирает источник пищи в зависимости от вероятностного значения Pi, связанного с источником пищи. Вероятностное значение для каждого источника пищи рассчитывается по следующему уравнению (1):

 (1) где  fᵢ — это значение пригодности решения  i  или количество нектара источника пищи, оцененное занятыми пчелами, а NF — это количество источников пищи. Таким образом, после оценки источников пищи занятыми пчелами определяется вероятность для каждого источника пищи, которая используется наблюдателями.

Для генерации кандидатного решения из предыдущего решения искусственная пчела использует следующее уравнение (2):

(2)

Где  j — индекс для измерения (j=1,2, …., D),   k — индекс, который представляет конкретного индивидуума или решение из популяции (k=1,2,3……, NF), а i  также является индексом, представляющим конкретное решение (i=1,2, ……, NF). Разница между i  и k  заключается в том, что k  определяется случайным образом, и значение  k  должно отличаться от i. это случайное число в диапазоне [-1,1]. Оно контролирует генерацию соседних позиций пищи вокруг. Когда разница между параметрами и уменьшается, то и возмущение на позиции также уменьшается. Таким образом, по мере того как поиск приближается к оптимальному решению в пространстве поиска, длина шага сокращается. После генерации кандидатного решения вычисляется его значение пригодности, а затем оно сравнивается с пригодностью .

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

IV. Задача путешествующего торговца

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

Рисунок 1: графическое представление ЗК

На рисунке 1 каждый узел графа представляет собой город, а каждое взвешенное ребро графа представляет путь от одного города к другому. Вес ребра — это стоимость путешествия для достижения города. Функция пригодности для задачи коммивояжера будет определяться следующим образом:

гдеэто стоимость пути от города i к городу j, а k — это количество городов или размерность.

V. Алгоритм генетической колонии пчёл

Генетический алгоритм (ГА) и оптимизация на основе искусственной колонии пчел (ИПК) являются эвристическими методами поиска, основанными на популяции, которые используются для решения задач оптимизации. ГА является эффективной техникой оптимизации как для непрерывных, так и для дискретных задач оптимизации. Проблема с генетическими алгоритмами заключается в том, что гены нескольких сравнительно высокоэффективных (но не оптимальных) особей могут быстро начать доминировать в популяции, что приводит к ее сходимости к локальному максимуму. Как только популяция сойдется, способность ГА продолжать поиск лучших решений фактически исчезает: кроссовер (также называемый рекомбинацией, это генетический оператор, используемый для объединения генетической информации двух родителей с целью создания нового потомства) почти идентичных хромосом дает мало нового. Остается только мутация, которая исследует совершенно новые области, но это просто медленный случайный поиск. Для лучшего исследования локального пространства поиска в процессе поиска и для избежания проблемы сходимости к локальному максимуму добавляются работники и наблюдательные пчелы ИПК. Оба оператора являются основными операторами алгоритма ИПК.

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

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

VI. Методология

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

A. Представление 

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

В задаче коммивояжера (ЗК) у нас есть набор городов, пути между ними и стоимость, связанная с каждым путем, которые служат входными данными. Это позволяет определить, какой путь следует использовать для перемещения между городами и в каком порядке. РГАПК основан на концепции популяции, и каждый индивидуум в популяции представляет собой решение. В случае ЗК решение — это последовательность путей, проходящих через каждый город с минимальной стоимостью. Поэтому сначала необходимо сформулировать каждого индивидуума в РГАПК.

Наши предложенные алгоритмы РГАПК генерируют вектор действительных значений для индивидуума, но задача ЗК является задачей дискретной оптимизации, поэтому нам нужно сопоставить сгенерированный вектор действительных значений с дискретными значениями, используемыми для задачи ЗК. Мы использовали правило ЗКП (значение кратчайшей позиции) для сопоставления сгенерированного вектора действительных значений с вектором дискретных значений. Для каждого сгенерированного индивидуума Tid в РГАПК мы создали другой вектор дискретных значений Sij, называемый последовательным вектором, используя правило ЗКП.

Выходом для задачи ЗК является оптимальный набор последовательности городов, через которые должен проехать продавец. Последовательный вектор Sij, сгенерированный для индивидуума, используется как последовательность для перемещения продавца по городам. Мы представляем размерность индивидуума как количество городов. Значение размерности каждого индивидуума содержит действительные значения из пространства поиска. Каждый индивидуум представлен как Tid = {ti1, ti2, ti3, ……, tid}, а для каждого индивидуума существует последовательный вектор Sid = {Si1, Si2, Si3, …Sid}, где i — конкретный индивидуум, а d представляет индекс размерности и рассчитывается с использованием РГАПК с правилом ЗКП. Последовательный вектор каждого индивидуума преобразуется на основе вектора действительных значений индивидуума Tid = {t1, t2, t3, ……, td}. Индивидуум получает свои значения случайным образом изначально, а связанный последовательный вектор преобразуется с использованием правила ЗКП для данного индивидуума.

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

Индивидуум Tid имеет непрерывные значения. С помощью правила ЗКП это непрерывное позиционное значение может быть преобразовано в дискретное значение, образуя Sid = [si1, si2, ……, sid]. Sid — это последовательность пути i-го индивидуума в порядке обработки относительно d-мерности. Эти вновь сгенерированные индивиды затем обновляются работниками и наблюдателями пчелиного колонии, после чего снова выполняется преобразование обновленных частиц в вектор последовательности. После каждого изменения индивидуума рассчитывается вектор последовательности, связанный с этим индивидуумом.

Например, если у нас есть 6 городов, как показано на рисунке 1, то размерность будет равна 6. На основе правил ЗКП непрерывная позиция или индивидуум преобразуются в последовательность Sid, которая представляет собой последовательность городов, подразумеваемую индивидуумом Tid. Индивидуум Tid рассчитывается с использованием РГАПК={4.83,-0.55,1.90,3.46,1.05,2.87,-0.28,0.19,4.0,2.28}. Затем с использованием правила ЗКП преобразование Tid в Sid дает нам значение Sid = {9,0, 4, 7,3,6,1,2,8,5}. Эти значения сортируются, и их индексы сохраняются в векторе, который будет использоваться для доступа к стоимости, связанной с путем, хранящейся в двумерных массивах заранее.

B. Функция приспособленности 

После представления каждого индивидуума сначала необходимо рассчитать значение его приспособленности. На основе значения приспособленности мы определяем оптимальное решение. В случае задачи коммивояжера (ЗК) оптимальным решением является минимизация значения уравнения (2). Уравнение (2) представляет собой сумму затрат на путешествие от одного города к другому в пути, охватывающем все города. Для расчета значения приспособленности сначала необходимо вычислить матрицу затрат. Матрица затрат содержит стоимость перемещения от одного города к другому. Наша главная цель — минимизировать значение приспособленности; индивидуум с минимальным значением приспособленности считается оптимальным решением.

C. Алгоритм Реальной Пчелиной Генетической Колонии 

Генетической Колонии. Мы задаем начальную популяцию, выбирая случайные стартовые значения из пространства поиска, после чего рассчитывается последовательный вектор, связанный с каждым индивидуумом; последовательный вектор является членом множества x! последовательностей, где x — общее количество городов. После получения начальной популяции и ассоциации начального последовательного вектора мы вычисляем значение приспособленности каждого индивидуума согласно уравнению (2). На следующем этапе эти индивиды посещаются рабочими пчелами пчелиной колонии. Эти операторы используются для локального поиска, чтобы избежать проблемы локального максимума.

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

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

Алгоритм 1: ЗК с использованием РГАПК

[Фаза инициализации]

for p=0 to размер популяции do

for d=0 to размер do

                        Случайно инициализирует частицу

                        Используя правило ЗКП, генерируется вектор последовательности.

            end for d

            Вычислить приспособленность этой частицы

 end for s

Повторение

[Фаза действия рабочего]

for i=0 to макс. количество занятых пчел do

            for d= 0 to размер do

                        создать нового кандидата для решения

                        создать последовательность кандидатов на основе

                        варианта решения

            end for d

  Вычислить приспособленность особи

  если пригодность нового решения-кандидата лучше, чем

  существующее решение, заменяет старое решение и его

  вектор последовательности.

end for i

Рассчитать вероятность для каждой особи.

[Фаза обновления]

            [Фаза оператора кроссовера]

Если критерии кроссовера удовлетворены, то 

выбрать двух случайных индивидов из текущей популяции для операции кроссовера. 

Применить операцию кроссовера, чтобы сгенерировать новых индивидов — потомков, полученных от родителей в результате кроссовера. 

Генерируется новый набор векторов последовательностей для новых потомков. 

Вычислить стоимость для этих потомков. 

Вычислить приспособленность обновленного индивидуума. 

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

[Фаза действия наблюдателя]

for i=0 to max no of onlooker bee do

            выбрать источник пищи на основе вероятности

            for d= 0 to dimension do

                        создать нового кандидата для решения

                        создать последовательность кандидатов на основе

                        варианта решения

end for d

вычислить приспособленность индивидуума

если приспособленность нового кандидата на решение лучше, чем

существующее решение, заменить старое решение и его

вектор последовательности.

end for i

[Фаза действия разведчика]

Если какой-либо источник пищи исчерпан,

то заменить его случайной позицией, сгенерированной разведчиком,

запомнить лучшее решение и последовательность, найденные до сих пор,

until (критерии остановки не будут выполнены)

VII. Экспериментальная установка и результаты

A. Экспериментальная установка 

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

Первый контрольный параметр — максимальное число циклов: максимальное число циклов (MCN) равно максимальному числу поколений. Мы взяли результаты для значений MCN 1500, 2000 и 2500. Следующий параметр в нашем эксперименте — максимальное число популяции, и мы установили его значение равным 30 и 60. Другой контрольный параметр — количество запусков, и мы установили его значение в нашем эксперименте равным 30. Следует отметить, что каждый запуск содержит максимальное число циклов, которое составляет 1500, 2000 или 2500 в нашем эксперименте. Четвертый контрольный параметр — размерность, и он зависит от числа городов. В этом эксперименте мы используем функцию линейного оператора кроссовера в алгоритме РГАПК. Контрольный параметр для оператора кроссовера — вероятность. Поэтому нам также нужно определить значение этого параметра. Его значение может варьироваться от 0.1 до 0.9.

B. Экспериментальные результаты 

В этом разделе мы анализируем результаты, полученные нашим алгоритмом. Для проверки эффективности результатов нашего алгоритма результаты РГАПК сравниваются с результатами реального кодированного генетического алгоритма. В задаче коммивояжера (ЗК) у нас уже есть информация о количестве городов, пути и стоимости, связанной с маршрутом, который будет пройден продавцом для выполнения задачи. Нам нужно только найти последовательность маршрута, которая даст нам оптимальные результаты. Мы провели эксперимент, изменяя количество городов, а также меняя стоимость, связанную с маршрутом, а затем сравнили наши результаты с результатами генетического алгоритма (ГА). В частности, мы рассмотрели два случая, в которых было выбрано разное количество городов и стоимость.

Эксперимент 1: Здесь мы предполагаем, что есть 30 городов. Ниже приведено время выполнения (в единицах), затраченное РГАПК и ГА. 

таблица 1: расстояние, рассчитанное ГА и РГАПК для 30 городов

Последовательность, сгенерированная ГА: 0, 25, 28, 23, 14, 18, 19, 22, 16, 9, 5, 6, 24, 15, 4, 11, 13, 21, 12, 27, 1, 20, 2, 7, 3, 17, 29 и 10, 26, 8. 

Последовательность, сгенерированная РГАПК: 4, 27, 9, 26, 2, 13, 16, 15, 6, 10, 24, 5, 17, 3, 7, 11, 14, 23, 8, 29, 21, 20, 19, 22, 0, 18, 12, 25, 28.

Эксперимент 2: Здесь мы предполагаем, что есть 60 городов. Ниже приведено время выполнения (в единицах), затраченное РГАПК и ГА.

таблица 2: расстояние, рассчитанное ГА и РГАПК для 60 городов

Последовательность, сгенерированная ГА: 0, 35, 34, 17, 9, 51, 59, 58, 19, 55, 13, 14, 33, 20, 39, 8, 56, 57, 45, 44, 2, 58, 12, 53, 25, 48, 38, 43, 21, 5, 4, 46, 6, 10, 36, 41, 10, 15, 18, 49, 32, 24, 50, 22, 52, 54, 11, 29, 47, 23, 56, 40, 27, 30, 42, 31, 7, 37, 1, 3. 

Последовательность, сгенерированная РГАПК: 50, 40, 57, 21, 49, 7, 51, 11, 31, 13, 8, 16, 6, 18, 37, 46, 39, 44, 52, 22, 27, 20, 45, 33, 55, 41, 3, 17, 14, 23, 15, 32, 19, 25, 48, 10, 0, 24, 35, 28, 38, 12, 54, 47, 1, 26, 59, 42, 50, 9, 58, 43, 56, 53, 2, 36, 4, 34, 29 и 30. 

Сгенерированные алгоритмами последовательности показывают маршрут для путешествия продавца. Последовательность показывает номера городов, через которые продавец проходит один за другим. Например, в последовательности:0, 22, 5, 17, 20, 27, 12, 18, 14, 28, 25, 11, 16, 15, 29, 21,19,2,4,1,3,7,8,23,13,24,10,26,9,6. 

Продавец начинает с города номер 0 и затем переходит в город номер 22 и затем в город номер 5 и так далее. В конце он посещает город номер 6 и возвращается в город номер 0. Вышеуказанная последовательность была сгенерирована РГАПК для работы с 30 городами. 

Из таблиц I и II ясно видно, что предложенный нами РГАПК работает лучше, чем алгоритм генетики с реальным кодированием в каждом случае.

VIII. Заключение

Из результатов, представленных в таблицах I и II, можно сделать вывод, что предложенный РГАПК работает лучше, чем существующий алгоритм генетики (ГА). Нет конкретного значения вероятности кроссовера, при котором можно получить наилучшие результаты для задачи коммивояжера (ЗК). Это зависит от числа городов и маршрута. Процедура, описанная Хемантом Нагпуре и др., состоит в генерации популяции в соответствии с алгоритмом, затем создается последовательность маршрута и стоимость, связанная с этой последовательностью. Каждый индивид и вектор последовательности маршрута обновляются с использованием операторов кроссовера, наблюдателя и разведчика. Этот процесс повторяется снова и снова до достижения максимального числа циклов. 

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

VIII. Ссылки

[1]. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm: By Dervis Karaboga · Bahriye Basturk Received: 31 May 2006 / Accepted: 12 February 2007 / Published online: 13 April 2007 © Springer Science+Business Media B.V. 2007.

[2]. L.P. Wong, M.Y. H. Low and C.S. Chong, «Bee Colony Optimization with Local Search for Travelling Salesman Problem,» International Journal on Artificial Intelligence Tools (IJAIT), vol. 19, pp. 305–334, 2010.

[3]. D. Karaboga and B. Akay, «Artificial Bee Colony (ABC), Harmony Search and Bees Algorithms on Numerical Optimization,» pp. 1–6.

[4] A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems: By J. Li, Q. Pan, S. Xie, S.Wang (Int. J. of Computers, Communications & Control, ISSN 1841–9836, E-ISSN 1841–9844 Vol. VI (2011), No. 2 (June), pp. 286–29.

[5] G. Zhao, W. Luo, H. Nie, C. Li, «A Genetic Algorithm Balancing Exploration and Exploitation for the Travelling Salesman Problem,» in Proceedings of the 2008 Fourth International Conference on Natural Computation, 2008, pp. 505–509.

[6] Dervis Karaboga · Bahriye Basturk, «A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm» J Glob Optim (2007), pp 459–471.

[7] W.-L. Zhong, l Zhang, W.-N. Chen, «A Novel Discrete Particle Swarm Optimization to Solve Traveling Salesman Problem,» in Proc. IEEE Int. Conf. Evol. Comput. (CEC), 2007, pp. 3283–3287.

[8] L.-P. Wong, M.Y. Hean Low, C.S. Chong, «A Bee Colony Optimization Algorithm for Traveling Salesman Problem,» Second Asia International Conference on Modelling & Simulation, 2008, pp. 818–823.

[9] S. Nonsiri, S. Supratid, «ModifYing Ant Colony Optimization,» IEEE Conference on Soft Computing in Industrial Applications, 2008, pp.95–100.

[10] D. Karaboga, «An idea based on honey bee swarm for numerical optimization,» Erciyes University, Engineering Faculty, Computer Engineering Department, Turkey, Technical Report-TR06, 2005.

[11] D. Karaboga, B. Akay, «A Survey: Algorithms Simulating Bee Swarm Intelligence,» Artificial Intelligence Review., vol. 31, pp. 68–85, 2009.

[12] Z. Michalewicz, «Genetic algorithm + data structure = evolution pmgram», Springer-Verlag, Inc., Heidelberg, Berlin, 1996.

[13] G-. G. Jin, S-. R. Joo, «A Study on a Real-Coded Genetic Algorithm, «Journal of Control, Automation, and Systems Engineering, vol. 6, no. 4, pp. 268–274, April 2000.

[14] L.J. Eshelman, R.A. Caruana, and J.D. Schaffer, «Bases in the crossover landscape,» Pmc. 3rd Int. Con$ on Genetic Algorithms, J. Schaffer (Ed.), Morgan Kaufmann Publishers, LA, pp.10–19, 1989.

[15] Chaotic Bee Swarm Optimization Algorithm for Path Planning of Mobile Robots Jiann-Horng Lin and Li-Ren Huang Department of Information Management I-Shou University, Taiwan 2009.

[16] V.Singh, D.Singh R.Tiwari, A.Shukla, «RGBCA -Genetic Bee Colony Algorithm for Travelling Salesman Problem«IEEE Information & Communication Technologies (WICT),2011pp.1002–1008.

[17]. P.W. Tsai1, J.S. Pan1, B.Y. Liao1, and S.C. Chu, «Enhanced Artificial Bee Colony Optimization,» International Journal of Innovative Computing, Information and Control, vol. 5, pp. 1–14, Dec. 2009.

Habrahabr.ru прочитано 9331 раз