15252

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА

Научная статья

Информатика, кибернетика и программирование

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА Студент гр. В наши дни всё чаще даёт о себе знать проблема низкой производительности каких-либо расчётов. Вот и транспортная задача не стала ис...

Русский

2013-06-11

96.5 KB

54 чел.

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА

Студент гр. 07-ИУ-1 Степанов М.М.

Руководитель: д.т.н., доц. Новицкий В.О.

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

Поэтому, перед нами встаёт задача убыстрить, насколько это возможно, расчёты маршрутов автотранспорта.

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

Генетические алгоритмы применяются для решения следующих задач:

  1.  Оптимизация функций
  2.  Оптимизация запросов в базах данных
  3.  Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
  4.  Настройка и обучение искусственной нейронной сети
  5.  Задачи компоновки
  6.  Составление расписаний
  7.  Игровые стратегии 
  8.  Искусственная жизнь

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

Общая схема алгоритма(рис. 1):

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

Рис.1 Схема работы генетического алгоритма

Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

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

Генетические операторы:

  1.  Инициализация.

Задача для генетического алгоритма формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора("генотипа") генов, где каждый ген может быть битом, числом или неким другим объектом[3]. Затем гены заполняются случайным образом в соответствии с выбранным представлением.

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

  1.  Оценка.

Особи в поколении оцениваются с учётом их приспособленности(английский термин – fitness[1]). Оценка происходит по заранее заданным критериям.

  1.  Отбор.

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными) для последующего скрещивания.

  1.  Скрещивание.

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

  1.   Мутация.

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

Работа операторов скрещивания:

Одноточечное скрещивание: случайным образом выбираются точки разрыва родительских хромосом, которые потом «склеиваются» для получения потомства.

Многоточечное скрещивание: случайным образом выбираются две точки разрыва, в которых «разрываются» родительские хромосомы, и из которых образуются дочерние.

Мутация выполняется в соответствии с определёнными операциями, которые задаются в зависимости от конкретной задачи.

Задача коммивояжёра.

Наша задача - это геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает только расстояния между точками на плоскости, без учёта стоимости, времени маршрута и т.д.). Наш критерий отбора очень прост - получить кратчайший маршрут. 

Скрещивание в задаче коммивояжёра:

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

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

Как поступить в этой ситуации?

А поступаем мы очень просто. Не добавляем те точки из родительского гена, которые уже есть в гене ребёнка.

Таким образом, соблюдается условие нашей задачи.

Та же самая проблема возникает при проведении скрещивания в нескольких местах. Нарушается условие задачи.

Существует несколько способов решения проблемы перекрёстного скрещивания.

Первое решение - частично отображаемое скрещивание.

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

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

Третий вариант - это скрещивание циклическое.

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

Для чего же нужно столько различных способов мутации?

Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Это — один из способов борьбы с таким нежелательным эффектом.

Мутации в задаче коммивояжёра.

Так же, как и в случае со скрещиванием, мы не можем просто изменить одну "хромосому" и ожидать от этого адекватного результата.

Что делать в этой ситуации?

Так как нельзя просто изменить одну хромосому в условиях нашей задачи, то можно просто поменять их местами(рис. 8.2). Таким образом, минимальное число хромосом, участвующих в мутации, будет равняться двум.

Мутация множества городов. Заключается в следующем: Случайным образом выбираем две точки разрыва, а затем меняем местами  "хромосомы" между этими двумя точками, конечно, тоже случайным образом.

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

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

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

Литература:

[1] Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 2003. — С. 432. — ISBN 5-9221-0337-7

[2] Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. — М: Физматлит, 2006. — С. 272. — ISBN 5-9221-0749-6

[3] Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд.. — М: Физматлит, 2006. — С. 320. — ISBN 5-9221-0510-8

[4] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд.. — М: Горячая линия-Телеком, 2008. — С. 452. — ISBN 5-93517-103-1

 


 

А также другие работы, которые могут Вас заинтересовать

29577. Коммерческая и социальная реклама в СМК 15.24 KB
  Функции выполняемые социальной и коммерческой рекламы посредством СМК: 1. Коммерческая реклама: В соответствие с современным подходом к изучению рекламы коммерческая реклама входит в комплекс маркетинговых коммуникаций в который помимо рекламы входят такие инструменты как стимулирование сбыта PR пропаганда и личные продажи. Социальная реклама вид некоммерческой рекламы направленной на изменение моделей общественного поведения и привлечения внимания к проблемам социума. В 1993 году был образован негосударственный Рекламный Совет в...
29578. Состояние медиарынка в кризисный и поскризисный период, тенденции дальнейшего развития 24.52 KB
  Те компании которые выжили в это время оказались в очень неплохой ситуации. Как отмечают специалисты основным принципом коммуникаций в кризисной ситуации не замалчивать события говорить все и как можно скорее. Однако на ранних стадиях кризисной ситуации не следует говорить вещей которых вы не знаете или в которых вы не уверены не следует включаться в догадки поскольку вы можете оказаться не правы. Американские специалисты предлагают учитывать следующие позиции в подобной ситуации [10 с.
29579. Телевидение XXI века: соотношение социальных, политических и коммерческих функций 13.23 KB
  Степень этой вовлеченности и мера воздействия ТВ на аудиторию в плоскости выполнения этой функции зависят от той системы в которой действует данное телевизионное СМИ. Особенно сильно подобное отношение к СМИ вообще и к ТВ в частности у населения постсоветских государств. Люди ждут реакции властей на критические выступления касающиеся тех или иных явлений жизни по инерции доставшейся от советской системы в то время как СМИ лишь способ донести информацию об этих явлениях до своей аудитории. Дальнейшее зависит уже не от СМИ выпадающего из...
29580. Интернет: история, возможности и прогнозы 16.93 KB
  Интернет: история возможности и прогнозы. Исторически интернет произошел от американской сети RPNET которая разрабатывалась как децентрализованное средство обмена информацией в случае ядерного удара. Прототип интернета RPNET в 1969 соединил сеть американских научно исследовательских университетов. Следующим значительным скачком в развитии интернета стал концепт всемирной паутины выдвинутый в 1989 Тимом БернсЛи идея создания универсального языка HTML Аштэмэйли протокола связи HTTPАштэтэпэ что позволило сделать интернет таким каким он...
29581. Информационное общество: основные характеристики, тенденции развития. Дискуссии в отношении позитивных изменений и негативных последствий всеобщей информатизации и глобализации мирового пространства 16.15 KB
  Информационное общество ступень в развитии современной цивилизации характеризующаяся увеличением роли информации и знаний в жизни общества; возрастанием доли инфокоммуникаций информационных продуктов и информационных услуг в валовом внутреннем продукте ВВП; созданием глобального информационного пространства обеспечивающего эффективное информационное взаимодействие людей их доступ к мировым информационным ресурсам и удовлетворение их социальных и личностных потребностей в информационных продуктах и услугах. Основные характеристики:...
29582. Массовое сознание 12.93 KB
  На общественное мнение влияют мнения людей признаваемых обществом авторитетными и компетентными личный опыт людей В формировании общественного мнения выделяются: субъект воздействия элитные группы стремящиеся к достижению или удержанию власти заказчики и исполнители государство аналитики журналисты и т.; объект воздействия массовое сознание изменение которого является целью субъекта; инструмент воздействия СМИ как массмедиа так и институты социализации культура и т. Формы и способы влияния общественного мнения на личность...
29583. Массовое сознание: Субъективистский и объективистский подходы 14.37 KB
  Массовое сознание включает в себя понятие массы: МассаОртега и Гаса это суждение некомпетентных низкое качество современной цивилизации; Масса Юнгер механизное общество в котором человек является придатком машины; Масса Зиммель Вебер Манхейм это бюрократическое общество которое отличается широко расчленненой организацией в которой принятие решений допускается на высших этапах иерархии; МассаЛенин совокупность трудящихся наименее организованных и просвещенных. МассаШарков это шаблонное Например когда в деревнях все...
29584. Стратегия и тактика планирования рекламной кампании 16.33 KB
  Стратегия и тактика планирования рекламной кампании. Планирование рекламной кампании это процесс в котором принимают участие все структурные подразделения рекламного агентства и маркетинговый отдел рекламодателя. Результат этого процесса составление плана рекламной кампании на определенный период. Главная задача планирования рекламной кампании определить как будет доноситься рекламное послание до потребителя: в какой форме с помощью каких средств массовой информации и в рамках какого бюджета.
29585. Основные понятия в медиапланировании (рейтинг, доля, HUT, PUT, PUR). Их расчет и соотношение в планировании рекламных кампаний 33.55 KB
  Home Using TV одним из базовых показателей в медиапланировании является число людей или домохозяйств в которых смотрят телевизор. Этот показатель описывает количество людей или домохозяйств использующих ТВ на определенный момент времени Иными словами это процент индивидуумов или домохозяйств использующих телевизор в данное время дня. Показатель HUT не включает людей смотрящих телевизор вне дома например в магазинах аэропортах отелях и т. То есть рекламное сообщение смогут увидеть те люди которые по крайней мере в данный момент...