Эволюционные алгоритмы для решения задачи комивояжёра большой размерности

Было предложено несколько новых модификаций генетического алгоритма с видообразованием: ГА с разбиением видов на хищники и жертвы случайным образом, ГА с разбиением видов на хищники и жертвы с максимизацией энтропии при соблюдении баланса между хищниками и жертвами (далее оптимальное разбиение), ГА с оптимальным разбиением на хищники и жертвы и решением СЛАУ на фитнесы видов с и без пересчёта фитнесов индивидов. Предложенные модификации были протестированы на четырёх бенчмарках с различными размерами популяции, мутациями и кроссоверами. Для всех бенчмарков и всех наборов параметров, кроме кроссовера DPX для задачи rat195, модифицированный алгоритм показал более хорошие результаты, чем классический с тем же числом вычислений фитнеса. По сравнению с классическим ГА с большим числом скрещиваний модифицированный ГА смог достичь устойчиво более хороших результатов для задачи eil51. На остальных бенчмарках модифицированный ГА дал результаты хуже, но по-прежнему использовал значительно меньшее количество вычислений фитнеса. Было показано, что в условиях, когда классический генетический алгоритм сходится к локальному оптимуму, модифицированный генетический алгоритм с большей вероятностью пройдёт ближе к глобальному оптимуму. Также было отмечено, что модифицированный генетический алгоритм имеет меньший разброс результатов, чем классический, а значит понадобится меньше запусков, чтобы удостовериться, что найдено решение, близкое к наилучшему из тех, которое можно найти с помощью выбранного ГА.