Генетический алгоритм решения задач квадратичного присваивания (QAP)

Генетические алгоритмы - это биологически вдохновленная стохастическая метаэвристика для комбинаторного поиска и оптимизации, и я обещаю вам, это проще, чем кажется.

Вступление

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

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

Я создал это решение, используя язык программирования Python, поэтому было бы неплохо, если бы вы имели представление о том, как работает Python или программирование в целом.

Весь код из этой статьи можно найти в этом репозитории.

И со всем этим, мы в порядке.

Квадратичная задача о назначении

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

Чтобы объяснить QAP в терминах непрофессионала, я хочу, чтобы вы представили, что существует 5 местоположений, и у вас есть значение расстояния между каждым из этих 5 местоположений. Я хочу, чтобы вы также представили, что есть 5 объектов и значение расхода / веса (например, количество людей, перемещаемых между двумя объектами) для каждого из этих объектов. Теперь у нас есть 5 локаций и 5 объектов, идея состоит в том, чтобы выяснить, как лучше всего разместить эти 5 объектов в этих 5 местах, чтобы сэкономить наибольшие затраты, исходя из расстояния между этими местоположениями и расхода / веса между этими объектами.

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

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

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

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

Введите —Генетические алгоритмы.

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

Генетические алгоритмы

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

Это определение означает, что ГА:

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

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

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

На мой взгляд, это просто причудливый способ проб и ошибок.

GA включает в себя:

Население - совокупность возможных решений.
Хромосома - одно из возможных решений

Этапы генетического алгоритма включают:

Генетическое кодирование.
Создание населения.
Оценка пригодности.
Выбор.
Кроссовер.
Мутация.

Я расскажу о каждом этапе и его реализации для решения проблемы QAP.

Генетическое кодирование

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

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

Это также проблема один на один, поэтому мы можем назначить только один объект для одного места. Далее я поясняю пример ниже

chromosome = [5, 2, 3, 1, 0, 4]

В приведенном выше примере размер нашей задачи / ввода равен 6. Наши местоположения - это индексы 0–5, а объекты - значения и индекс 0–5. Итак, в местоположении 0 у нас есть предприятие 5, в местоположении 1 у нас есть предприятие 2 и так далее.

И это действительно все, что касается генетического кодирования. Далее нужно сгенерировать нашу начальную популяцию.

Создание начальной популяции

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

Есть несколько способов сделать это, но я создал список хромосом со случайными значениями от 0 до N-1 с произвольными индексами без повторения значений. Таким образом, у меня будет случайный набор хромосом.

Вот пример кода и вывод.

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

Initial Population -
[[[0, 3, 2, 4, 5, 1], 0], [[2, 1, 3, 5, 4, 0], 0], [[5, 3, 0, 4, 1, 2], 0], [[4, 0, 2, 1, 5, 3], 0], [[1, 4, 3, 5, 0, 2], 0], [[3, 4, 1, 5, 2, 0], 0], [[2, 0, 1, 5, 4, 3], 0], [[2, 0, 4, 1, 5, 3], 0], [[0, 1, 2, 4, 3, 5], 0], [[2, 3, 5, 1, 0, 4], 0], [[2, 1, 3, 5, 4, 0], 0], [[2, 4, 1, 5, 3, 0], 0], [[2, 5, 0, 4, 3, 1], 0], [[5, 2, 4, 3, 1, 0], 0], [[0, 4, 3, 1, 5, 2], 0], [[4, 2, 3, 1, 5, 0], 0], [[0, 1, 4, 5, 3, 2], 0], [[2, 4, 0, 3, 5, 1], 0], [[1, 4, 0, 5, 2, 3], 0], [[4, 3, 1, 0, 2, 5], 0]]

Оценка пригодности

Пригодность хромосомы означает, насколько «подходит» или насколько «хорошее» решение для рассматриваемой проблемы. В формальном определении QAP есть формула для вычисления функции стоимости решения. Эта функция стоимости - это то, что мы будем использовать для расчета нашего показателя пригодности. В конце концов, решение с наименьшей оценкой пригодности является наиболее подходящим.

Вот формальное определение и формула функции стоимости:

Проще говоря, это означает вычислить общую сумму расстояния между точками A и B, умноженную на вес / поток между объектами A [i] и B [i] для каждого A и B в нашей хромосоме.

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

Я создал вспомогательную функцию, чтобы помочь получить значение расстояния между местоположениями и потоков между объектами. Расстояние и потоки генерировались случайным образом. Расстояние между диапазоном от 0 до 20 и расходом от 0 до 4.

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

Population after cost function -
[[[0, 3, 2, 4, 5, 1], 213], [[2, 1, 3, 5, 4, 0], 223], [[5, 3, 0, 4, 1, 2], 240], [[4, 0, 2, 1, 5, 3], 242], [[1, 4, 3, 5, 0, 2], 189], [[3, 4, 1, 5, 2, 0], 213], [[2, 0, 1, 5, 4, 3], 228], [[2, 0, 4, 1, 5, 3], 231], [[0, 1, 2, 4, 3, 5], 218], [[2, 3, 5, 1, 0, 4], 187], [[2, 1, 3, 5, 4, 0], 223], [[2, 4, 1, 5, 3, 0], 268], [[2, 5, 0, 4, 3, 1], 220], [[5, 2, 4, 3, 1, 0], 206], [[0, 4, 3, 1, 5, 2], 230], [[4, 2, 3, 1, 5, 0], 200], [[0, 1, 4, 5, 3, 2], 237], [[2, 4, 0, 3, 5, 1], 221], [[1, 4, 0, 5, 2, 3], 165], [[4, 3, 1, 0, 2, 5], 219]]

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

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

Выбор

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

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

Существует несколько методов выбора, и все они имеют свои преимущества или недостатки в зависимости от типа проблемы, которую вы пытаетесь решить, или от того, насколько быстрым должен быть ваш алгоритм. Для этого GA я решил использовать метод выбора турнира.

Для выбора турнира вы хотите случайным образом выбрать k хромосом из популяции размера N. Это можно сделать, произвольно упорядочив популяцию N и выбрав первые k хромосом. Итак, на данном этапе вы выбрали k хромосом, но не удалили k хромосом из популяции размера N. Теперь вы хотите получить наиболее подходящую хромосому из k, и все.

Вот пример кода и вывод.

Я дважды запускал функцию выбора, и результат был примерно таким:

Parent 1 - 
[[2, 3, 5, 1, 0, 4], 187]
Parent 2 - 
[[3, 4, 1, 5, 2, 0], 213]

Примечание. Подробнее о методах выбора здесь.

Кроссовер

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

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

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

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

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

Вот пример кода и вывод

Я обрабатываю дубликаты, нахожу их в каждой хромосоме и переключаю их между хромосомами. Итак, если 4 и 2 дублируются в хромосоме 1, я удаляю их из хромосомы 1 и добавляю к хромосоме 2. То же самое для дубликатов в хромосоме 2. Это модификация, которую я придумал на лету и еще недостаточно протестировал, так что будьте осторожны при ее использовании 😅

Вот как выглядит результат -

Offspring 1 after crossover - 
[[3, 5, 1, 0, 4, 2], 0]
Offspring 2 after crossover - 
[[3, 1, 5, 2, 0, 4], 0]

Я сбрасываю оценку пригодности после кроссовера, поэтому, когда я мутирую и добавляю его в пул потомства, все начинается снова как новая популяция.

Примечание. Подробнее о методах кроссовера здесь .

Подробнее о методах кроссовера для QAP конкретно здесь.

Мутация

Мутация в биологии означает изменение генов ДНК. Идея здесь очень проста. Это немного похоже на кроссовер, поэтому иногда люди не делают этого в своем GA, но, как и в случае с кроссовером и отбором, есть несколько методов, которые вы можете использовать для мутации определенной хромосомы.

Для моего GA я решил использовать метод мутации swap, который меняет значения на 2 случайных индекса в хромосоме.

Довольно просто.

Вот пример кода и вывода:

Вот как выглядит результат -

Offspring after mutation - switched 4 and 5 at index 1 and 4.
[[3, 4, 1, 0, 5, 2], 0]
Offspring after mutation - switched 4 and 0 at index 4 and 5.
[[3, 1, 5, 2, 4, 0], 0]

Примечание. Подробнее о методах мутации здесь .

Собираем все вместе

Мы определили и внедрили все этапы нашей GA, и все, что осталось, - это собрать все воедино и заставить работать.

Вот простой алгоритм, как все это работает:

Создать начальную популяцию
Получите пригодность для каждой хромосомы в популяции
Воспользуйтесь функцией выбора, чтобы подготовить родителей
Используйте функцию кроссовера для получения новых потомков
Мутировать потомство.
Перенести потомство из 5 в пул потомства
Повторяйте шаги с 3 по 6 до тех пор, пока размер потомства не станет такого же размера, как и исходная популяция.
Подсчитайте приспособленность всего потомства.
Остановитесь, если достигнуты критерии остановки, в противном случае повторите шаги с 1 по 8.

Вот и все! Когда я начинал, мне было так сложно, но, в конце концов, это всего лишь набор функций, работающих вместе. Во всяком случае, это то, что есть в большинстве случаев.

Вот мой пример кода и результат:

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

Solution for iteration - 0
[[0, 3, 4, 5, 2, 1], 127]
Solution for iteration - 4
[[2, 3, 1, 4, 5, 0], 123]
Solution for iteration - 5
[[4, 3, 2, 0, 1, 5], 116]
Solution for iteration - 8
[[3, 4, 0, 2, 5, 1], 111]
Solution for iteration - 172
[[0, 4, 2, 5, 3, 1], 110]
Final solution after 1000 iterations = 
[[0, 4, 2, 5, 3, 1], 110]

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

Выводы

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

На этом моя напыщенная речь о рекламе Google Analytics и QAP заканчивается.

Спасибо за чтение! 😄