Выбор разреженного параметра с использованием генетического алгоритма

Question

Я столкнулся с проблемой выбора параметров, которую я хотел бы решить с помощью Генетического алгоритма (GA). Я должен выбрать не более 4 параметров из 3000 возможных. Использование представления бинарной хромосомы кажется естественным выбором. Функция оценки наказывает слишком много «выбранных» атрибутов, и если количество атрибутов приемлемо, оно затем оценивает выбор.

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

Кодирование проблемы с использованием индексов параметров также не работает. Это, скорее всего, связано с тем, что хромосомы являются направленными, тогда как проблема выбора не является (например, хромосомами [1, 2, 3, 4], [4, 3, 2, 1], [3, 2, 4, 1] и т. Д.)

Какое представление проблемы вы бы предложили?

P.S Если это имеет значение, я использую PyEvolve.

Answer 1

Я не знаком с с PyEvolve, но от того, что я могу вспомнить о генетических алгоритмов, вы беспокоитесь с 4 шагами,

1. Chormosome Evalutation (вы, наверное, уже это выяснили)
2. Хромосома Initialization
3. Хромосома Кроссовер
4. Хромосома Мутация

Я думаю, что вы можете d o это со списками просто отлично. Вам нужно будет перегрузить некоторые операторы, но похоже, что PyEvolve lets you do this Простейшей задачей было бы сохранить представление в виде списка, просто отсортируйте их численно, прежде чем возвращать хромосому.

Мне нужно знать больше о вашей проблеме, но вот мои предложения. Поскольку у вас есть переменное количество параметров, вам нужно придумать какое-то распределение вероятности для количества параметров в хромосоме. Я возьму здесь единый случайный случай на 1,2,3,4, но вы можете попробовать что-то еще, если вам это нравится. Я собираюсь назвать этот дистрибутив P_n.

2. Инициализация. Семя вашего населения (по крайней мере) 3000 хромосом. Назовите эти c_1, ..., c_3000. Нарисуйте n_j из P_n. поместите j в c_j. Выберем оставшиеся параметры n_j - 1 с равномерным случайным распределением от остальных параметров.
3. Кроссовер. Предположим, что у нас есть две хромосомы. C_1 и C_2. Мы собираемся создать (и вернуть) хромосому C_3. Выберем n_3 из {n_1, n_2} с вероятностью 1/2. Теперь поместите параметры C_1 и C_2 в один список (и уникальные их, поэтому, если и C_1 и C_2 содержат параметр 1, он только в списке один раз). Нарисуйте n_3 параметры из объединенного списка и поместите их в хромосому C_3.
4. Мутация. Учитывая Chromosome C_1, нарисуйте n_1 * из P_n. если n_1 * равно < n_1, случайным образом удалять элементы из C_1 до тех пор, пока не будет n_1 * элементов. Если n_1 * = n_1 случайным образом выбирает 1 элемент из C_1 и заменяет его параметром, случайным образом выбранным из тех, что не в C_1. Если n_1 *> n_1 случайным образом добавляет элементы в C_1 до тех пор, пока не будет размер n_1 *.

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

Answer 2

Я думаю, что декомпозиция сингулярного значения (http://en.wikipedia.org/wiki/Singular_value_decomposition) может быть здесь более уместной из-за ограничения на количество параметров.