Улучшенный генетический алгоритм для проблемы мультикнакака

Question

Недавно я улучшил традиционный генетический алгоритм для проблемы мультикнакса. Итак, мой улучшенный генетический алгоритм работает лучше, чем традиционный генетический алгоритм. Я тестировал. (я использовал публично доступный из OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html) для тестирования GA.) Знает ли кто-нибудь другой улучшенный GA. Я хотел сравнить с другим улучшенным генетическим алгоритмом. На самом деле я искал в Интернете. Но не удалось найти хороший алгоритм для сравнения.

Answer 1

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

С другой стороны, если функция пригодности одинаков, то имеет смысл сравнивать результаты с различными параметрами, такими как разная скорость мутации, различные реализации кроссовера или даже совершенно разные эволюционные парадигмы, такие как коэволюция, гена, по сравнению со стандартными ГА и т. д.

Answer 2

Должно быть любое количество достойных методов GA, против которых вы можете сравнить. Однако вы должны сначала четко определить, какой именно «традиционный» метод GA вы уже тестировали.

Одним из эффективных методов, который я могу порекомендовать, является NSGA-II algorithm, который был разработан для многоцелевой оптимизации.

Взгляните на следующие другие идеи:

• Genetic Algorithm - Wikipedia
• Carlos A. Коэльо Коэльо (1999). "A Comprehensive Survey of Evolutionary-Based Multiobjective Optimization Techniques", Knowledge and Information Systems, Vol. 1, pp. 269-308.
• Carlos A. Coello Coello et al (2005). "Current and Future Research Trends in Evolutionary Multiobjective Optimization", Обработка информации с эволюционными алгоритмами, Springer.

Answer 3

Вы пытаетесь улучшить современное состояние в многокристальных решателях с помощью генетических алгоритмов? Или вы пытаетесь продвинуть метод генетического алгоритма, используя multiknapsack в качестве тестовой платформы? (Уточните?)

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

Против основных генетических алгоритмов были незначительные скачки. Лучшим улучшением в решении мультикнаксака с использованием генетических алгоритмов было бы улучшить кодирование операторов мутации и кроссовера, которые могут сделать порядки разницы в получаемой производительности и выдувать из воды любые настройки фундаментального генетического алгоритма , Существует много возможностей сделать ваши мутации и кроссовер операторов, адаптированных к multiknapsack.

Сначала я бы рассмотрел литературу по мультикнапсу, чтобы узнать, какие различные виды поисковых пространств и методы решения люди использовали на мультикнапсе. В своих оптимальных или субоптимальных методах (независимо от генетических алгоритмов), какие виды поисковых операторов они используют? Что они кодируют как переменные и что они кодируют в качестве значений? Какие эвристические функции оценки используются? Какие ограничения они проверяют?Затем вы будете адаптировать свои кодировки к вашим операторам мутации и кроссовера и посмотреть, насколько они эффективны в ваших генетических алгоритмах.

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