Генетический алгоритм - стратегии для оптимизации переменной длины

Question

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

Я хочу оптимизировать автопарк компании, то есть количество машин и моделей автомобилей. У меня уже есть фитнес-функция calcFitness(carList) который оценивает данные настройки, такие как "бизнес-автомобиль, транспортер" или "бизнес-автомобиль, бизнес-автомобиль, транспортер". Теперь вопрос в том, как мне решить эту проблему переменной длины с помощью GA.

У меня есть четыре идеи, как вы можете решить эти проблемы в целом:

1. Возможно, каким-то образом реализовать GA, позволяющий хромосомы переменной длины, и решить проблему за один проход (не уверен, если это возможно?)
2. Оцените максимально возможное количество автомобилей (например, 20) и запустите GA фиксированной длины для каждого номера слота автомобиля от 1 до 20 и сравните 20 результатов.
3. Аналогично #2, но без фиксированного верхнего предела: вы начинаете с 1 машины и увеличиваете количество слотов до тех пор, пока лучшее решение для увеличенного числа не окажется хуже предыдущего решения (подход на основе градиента)
4. Два сложенных GA фиксированной длины: родительский GA несет единоличную ответственность за оптимизацию количества автомобильных слотов, а в своей функции пригодности называется еще один GA, оптимизирующий назначение этих слотов.

Что вы думаете об этих общих подходах? Любые другие идеи или, возможно, альтернативы GA для этих случаев переменной длины?

Answer 1

Переменная длина, безусловно, возможна, и, кажется, это наиболее естественное представление этой проблемы. Почему это будет проблемой? Единственная существенная разница будет в операции кроссовера. В то время как одна точка тривиальна (вы просто выбираете точку в a, точка в пределах bи автоматически получать потомство переменной длины), часто лучше иметь непрерывный кроссовер, который требует большей интуиции с переменной длиной. Но это может быть реализовано позже, после тщательного отдельного тестирования.

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