Этот пост - еще один учебник по генетическим алгоритмам с добавлением DFO примерно на полпути! Если вы хотите увидеть другие сообщения в блоге, вы можете найти их здесь.
- Теорема о запрете бесплатного обеда
- Оптимизация нейронных сетей с помощью биомимикрии
- Тонкая настройка, оптимизация дисперсионных мух
- Представляем стохастический диффузионный поиск
- Развивающиеся решения с помощью генетических алгоритмов
Этот пост решает различные проблемы с помощью метаэвристики, и я рассматриваю его как небольшое упражнение на хлеб с маслом. Надеюсь, вам тоже понравится работать над ними.
Разминка
Хотя я предпочел бы потратить некоторое время на то, чтобы пообщаться с "Очень странными вещами" на Netflix, мой профессор имел благосклонность поставить перед нами, ленивыми студентами, следующую задачу.
У меня есть 10 карточек с номерами от 1 до 10. Вас просят разделить карточки на две группы, где сумма чисел на карточках в первой группе максимально приближена к 36, а произведение чисел во второй группе максимально близко к 360. Найдите способ получение хороших решений.
Закатав рукава вокруг своих тощих рук ботаника, давайте рассмотрим проблему. Учитывая набор из десяти уникальных карт, это означает, что существует 10 возможных перестановок. Другими словами, в поисковой сфере 3 628 800 потенциальных решений. Очевидно, что это множество потенциальных решений, и на их жадный поиск уйдет очень много времени. Случайный поиск, вероятно, немного ускорит процесс, но приближение к этому с помощью метаэвристики, помогающей руководствоваться стохастикой, такой как генетический алгоритм, будет работать еще лучше.
Каждый генотип в этом контексте будет списком (размер десять) уникальных целочисленных значений в диапазоне от одного до десяти. Мы можем создать случайный набор перетасованных карт следующим образом:
Некоторые решения будут лучше, чем другие, поскольку в задаче говорится, что нам нужны две группы карточек из набора с двумя разными целями. Чтобы упростить задачу, мы можем сделать группы карточек одинаковыми по размеру. Первая половина генотипа будет использоваться для первой группы, а вторая половина - для второй группы. Для первой группы мы берем абсолютную разницу (L1) между суммой группы и 36. Для второй группы мы берем абсолютную разницу между продуктом. Мы считаем эту проблему решенной, когда сумма комбинированных разностей L1 равна нулю.
Далее следует мутация и кроссовер. Для мутации мы перебираем генотип и бросаем кости против вероятности скорости мутации. Если нам нужно изменить, позиция карты в списке меняется на другую случайно выбранную карту. Кроссовер берет случайный выбор карт для первой колоды и берет оставшиеся необходимые карты из второй колоды, чтобы завершить генотип новой ДНК, сохраняя порядок там, где это возможно, и объединяет две вместе.
Затем мы можем взять все это и запустить GA. Итеративный код для этого выглядит следующим образом. Обратите внимание на аргументы метода. Размер популяции и частота мутаций должны быть довольно очевидными, но обратите внимание на элитарность, количество итераций и параметры количественных экспериментов. Элитарность - это параметр, который пользователь может настроить, решая свои проблемы с помощью GA, и помогает выбрать баланс между эксплуатацией и исследованием. Элитизм резервирует процент наиболее подходящих генотипов и предотвращает применение к ним какого-либо кроссовера или мутации для следующего раунда оптимизации. Количество итераций в этом случае - это максимальное количество раундов оптимизации, которое должно быть выполнено в одном эксперименте, а количество экспериментов означает количество раз, которое мы должны повторить эксперимент, чтобы определить, насколько хорошо в среднем идет оптимизация.
Мы можем запустить этот ГА в двух модальностях: ГА для поколений и ГА для устойчивого состояния. Это просто более причудливый способ сказать, есть или нет элитарность в GA - GA поколений не имеет элитизма, а GA устойчивого состояния имеет некоторую элитарность, хотя будьте осторожны, применяя слишком много, иначе вы найдете только локальные минимумы! Сначала мы проводим 50 экспериментов в установившемся режиме.
Выполнение приведенного выше дает график и дисперсию 24,57 того, сколько итераций потребовалось для каждого эксперимента, чтобы найти оптимальное решение. Каждый эксперимент находил оптимальное решение до того, как было выполнено максимальное количество итераций. Первое решение имело такой порядок [2 10 7 9 8 1 3 5 4 6]. Мы можем проверить это вручную в качестве быстрой проверки работоспособности, суммируя первые пять элементов и убедившись, что они равны 36. И, конечно же, 2 + 10 + 7 + 9 + 8 = 36! Затем мы можем вычислить произведение последних пяти элементов и проверить, равно ли оно 360. Естественно, мы видим, что 1 * 3 * 5 * 4 * 6 = 360. Из-за большого размера популяции 30% экспериментов (15 / 50) нашли оптимальное решение в первом раунде оптимизации.
Повторный запуск функции, но на этот раз как генеральный GA (без элитарности), дает дисперсию 22,12, и мы можем видеть на гистограмме, что у генерального GA было более удачное начало с нулевыми итерациями для поиска оптимального решения. Кроме того, для некоторых выбросов потребовалось немного больше времени, чем в установившемся состоянии, чтобы найти оптимальное решение с нулевой разницей, что более типично для того, что мы ожидаем от генеральной GA, которая отдает предпочтение разведке перед эксплуатацией.
Воск на, воск без
Мы также можем использовать другую метаэвристику для решения той же проблемы с картой. Хотя DFO был разработан для непрерывного поиска, мы можем аккуратно сделать его подходящим для этой проблемы с помощью нескольких небольших правок. Самая интересная часть - фитнес-функция; как взять непрерывный вектор чисел с плавающей запятой и превратить его в вектор неповторяющихся целых чисел?
Код документирует метод, поэтому я не буду вдаваться в подробности. Оттуда мы применяем обычный алгоритм DFO и получаем результат, оставленный в комментариях внизу кода.
Немного ручного труда никому не повредит
Вытянув атлетические конечности на предыдущей разминке, мы переходим к следующей задаче. Возвращаясь к генетическим алгоритмам, мы сначала будем решать эту задачу вручную, чтобы получить интуитивное понимание лежащих в основе механик.
Проблема имеет следующий сценарий. У нас есть хромосомы из восьми элементов, где каждый элемент может принимать любое целое число от нуля до девяти (включительно). Пригодность каждого генотипа может быть рассчитана как функция его элементов, как указано в третьей строке ниже. Это задача максимизации, поэтому чем выше фитнес, тем лучше.
Предположим, у нас есть четыре следующих генотипа.
Мы можем вычислить приспособленность, передав каждый генотип в функцию приспособленности.
В генетическом алгоритме, когда мы знаем, какие особи наиболее приспособлены, мы можем применить кроссовер. Мы можем взять двух наиболее приспособленных индивидуумов, 1 и 2, и применить разные типы кроссовера. Самой простой формой кроссовера будет однородный кроссовер. Мы разделяем каждую хромосому пополам и скрещиваем четыре полученные половинки друг напротив друга, в результате чего получаем два новых генотипа.
Затем предположим, что во время отбора выбираются вторая и третья наиболее подходящие хромосомы (генотип один и генотип три) (это хорошо, чтобы способствовать разнообразию для исследования пространства признаков) и что на этот раз мы используем двухточечный кроссовер. Допустим, мы переходим после второго и шестого элемента.
Наконец, давайте проигнорируем тот факт, что мы создаем больше хромосом, чем размер популяции на начальном этапе, чего не делают классические генетические алгоритмы, и сделаем еще один однородный кроссовер генотипов один и три.
Теперь у нас шестой размер населения. Затем мы вычисляем приспособленность каждого нового генотипа, от шести до десяти, следующим образом.
В первом раунде пригодности для генотипов с первого по четвертый средний показатель приспособленности составил -0,75. Во втором раунде для генотипов с пятого по десятый есть среднее значение 3, что является хорошим шагом в правильном направлении. Но насколько мы на самом деле в правильном направлении? Чтобы понять это, нам нужно взглянуть на функцию приспособленности и значения, которые x может принимать, и определить хромосому, которая была бы оптимальным решением с максимальной приспособленностью, а именно:
Итак, имея это в виду, возможно ли с помощью нашей нынешней методологии достичь этого глобального оптимума? Ответ - нет, потому что кроссовер не разбивается на нечетные интервалы, а это означает, что мы никогда не сможем распространить нули и девятки (которые все расположены на четных индексы в популяции) на нечетные индексы в генотипе. Это может быть отсортировано с помощью оператора случайного пересечения и / или оператора мутации.
Если вам нужен код для этого упражнения, его выполнение вернет правильные результаты. Обратите внимание, я настроил кроссовер.
NP Complete Problems - Задача о рюкзаке
Итак, давайте перейдем к более серьезной задаче - задаче о рюкзаке, которая является проблемой комбинаторной оптимизации. Он является NP-полным, что означает, что не существует известного алгоритма как правильного, так и быстрого (полиномиального времени) для всех случаев. Проблема ставится следующим образом:
Представьте, что вы выезжаете и имеете только рюкзак (или рюкзак) фиксированной вместимости. У вас есть набор объектов, каждый из которых имеет вес и ценность. Вы можете положить часть предметов в свой рюкзак, если вы не превышаете общий вес, который вы можете нести. Ваша цель - максимизировать ценность подмножества предметов, которые вы будете носить с собой.
Наборы данных весов предметов и их значений, используемые в приведенном ниже коде, были жестко закодированы из наборов данных, найденных здесь. На этот раз я построю класс как GA, как в моем предыдущем сообщении в блоге о GA.
Этот класс работает менеджером населения; он создает популяцию в начале эксперимента, а затем передает их извне для оценки с точки зрения соответствия генотипу. Население - это двоичный список из единиц и нулей. На этот раз стохастика немного отличается: мутация работает, перебирая генотип и просто случайным образом сбрасывая элемент, если случайная выборка находится в пределах скорости мутации. Кроссовер копирует один генотип и случайным образом перемешивает значения другого генотипа, чтобы получить новую ДНК.
Таким образом, важным вопросом является фитнес - как мы можем оценить задачу с рюкзаком? Хотя это делает довольно уродливый код, я жестко закодировал решения в функцию, которая принимает генотип и текущую задачу (я решил от одного до пяти на вышеупомянутом веб-сайте), а затем возвращает пригодность. Обратите внимание, что если мы превысим пороговый вес, наша физическая форма автоматически станет отрицательной.
Затем мы можем запустить этот код и получить решение для каждой задачи следующим образом, и мы можем увидеть сокращенную версию вывода в комментариях к коду внизу.
На этом я закончил - спасибо, что прочитали. Дайте мне знать, если у вас возникнут какие-либо вопросы, в комментариях ниже, или напишите мне в твиттере!
