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

Question

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

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

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

Какую проблему вы бы предложили?

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

Answer 1

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

1. Оценка хромосом (вы, вероятно, уже поняли это)
2. Инициализация хромосомы
3. Кроссовер с хромосомами
4. Хромосомная мутация

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

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

2. Инициализация. Семя населения с (по крайней мере) 3000 хромосом. Назовите эти c_1, ..., c_3000. Ничья n_j из P_n. положить j в c_j. Из оставшихся параметров выберите остальные параметры n_j - 1 с равномерным случайным распределением.
3. Crossover. Предположим, что у нас есть две хромосомы. 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. Мутация. Учитывая хромосому C_1, возьмите n_1 * из P_n. если n_1 * равно n_1 случайным образом добавлять элементы в C_1 до тех пор, пока он не будет иметь размер n_1 *.

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

Answer 2

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