Специальный алгоритм планирования (расширение шаблона)

Question

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

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

Спасибо за любые советы о том, как структурировать вещи и прибить это правильно.

Проблема
Я ищу хороший алгоритм планирования для решения следующей реальной проблемы.

У меня есть последовательность с 15 слотами (цифры могут варьироваться от 0 до 20):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

(а всего существует 10 различных последовательностей этого типа)

Каждая последовательность должна расширяться в массив, где каждый слот может занимать 1 позицию.

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

Ограничения на матрицу таковы:

• [по строкам, то есть по горизонтали] Количество размещенных должно быть либо 11, либо 111
• [по строкам] Расстояние между двумя последовательностями, равными 1, должно быть не менее 00
• Сумма каждого столбца должна соответствовать исходному массиву.
• Количество строк в матрице должно быть оптимизировано.

Затем массиву необходимо выделить одну из 4 разных матриц, которые могут иметь разное количество строк:

A, B, C, D

A, B, C и D являются реальными отделами. В течение 10 дней нагрузка должна быть достаточно разумной, чтобы не мешать другим целям отдела.

Каждая матрица сравнивается с расширением 10 различных исходных последовательностей, поэтому вы получаете:

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

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

Сумма каждой строки (например, всех А) должна быть примерно одинаковой в пределах 2%. т.е. сумма (от А1 до А10) должна быть примерно такой же, как (от В1 до В10) и т. д.

Количество строк может варьироваться, например, у вас есть:

А1: 5 строк A2: 5 строк A3: 1 строка, где эта строка может быть, например:

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

и т.д ..

Подзадача *

Я был бы очень рад решить только часть проблемы. Например, возможность ввода:

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

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

Answer 1

Попытка решения подзадачи

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

Базисные векторы

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

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

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

a*v1 + b*v2 + c*v3

где a, b и c - положительные целые числа. Для последовательности [1 2 1] решение имеет вид v1 = 1, v2 = 1, v3 = 0. Первое, что вы хотите сделать, - это найти все возможные базисные векторы длины 15. Из моих грубых вычислений я думаю, что где-то между 300-400 базисных векторов длины 15. Я могу дать вам несколько советов по их генерации, если хотите.

Поиск решений

Теперь, что вы хотите сделать, это отсортировать эти базисные векторы по их суммам / величинам. Затем в поиске вашего решения вы начинаете с базисных векторов, которые имеют самые большие суммы. Мы начнем с векторов, которые имеют наибольшие суммы, потому что они приводят к меньшему количеству строк. У нас также есть массив veccoefs, который содержит запись для линейного коэффициента для каждого базисного вектора. В начале поиска решения все значения veccoef равны 0.

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

Я не уверен в эффективности / точности этого метода, но он может, по крайней мере, дать вам некоторые идеи.

Другие возможные решения

Другая идея для решения этой проблемы заключается в использовании базисных векторов и формировании задачи в качестве задачи оптимизации / наименьших квадратов. Вы формируете матрицу базисных векторов так, что основной проблемой будет минимизация Sum [(Ax - b) ^ 2], где A - матрица базисных векторов, b - входная последовательность, а x - коэффициенты базисного вектора. Однако вы также хотите минимизировать количество строк, поэтому вы можете добавить такой термин, как x ^ T * x, в функцию минимизации, где x ^ T - транспонирование x. Сложная часть, на мой взгляд, - это найти дифференцируемые термины, которые будут добавлять целые векторные коэффициенты. Если вы можете придумать способ сделать это, тогда оптимизация вполне может быть хорошим способом сделать это.

Кроме того, вы могли бы рассмотреть решение Монте-Карло типа Метрополис. Вы можете выбрать случайным образом: добавить вектор, удалить вектор или заменить вектор на каждом шаге. Вектор, который будет добавлен / удален / заменен, будет выбран случайным образом. Вероятность того, что это изменение будет принято, будет отношением пригодности решений до изменения и после изменения. Пригодность может быть равна разности между текущим решением и последовательностью, возведенной в квадрат и суммированной, минус число строк / базисных векторов, участвующих в решении. Вы должны были бы ввести соответствующие константы для различных условий, чтобы попытаться получить приемлемый уровень около 50%. Я сомневаюсь, что это будет работать очень хорошо, но я подумал, что вы все равно должны учитывать это при поиске возможных решений.

Answer 2

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

1. Представление решения - как вы будете представлять возможное решение? Использование матрицы кажется наиболее простым. Возможно использование коллекции одномерных массивов. Но у вас есть некоторые ограничения, так что, может быть, стоит рассмотреть концепцию SuperGene?
2. Вы должны использовать правильные операторы мутации / кроссовера для данного представления гена.
3. Как вы будете применять ограничения на решения? Уничтожить те, которые не подходят? Что если они содержат ценную информацию? Может быть, позволить им остаться в популяции, но добавить некоторое наказание в фитнес, чтобы они способствовали потомству, но не будут переходить в следующие поколения?

В любом случае, я думаю, что GA можно применить к этой проблеме. Стоит ли? Обычно GA не лучший алгоритм, но они достойный алгоритм, если другие терпят неудачу. Я бы пошел с GA, просто потому что это было бы очень весело, но я бы искал альтернативное решение (на всякий случай).

P.S. Личное понимание: я решал проблему N королев, для 70