Повышение эффективности работы генетического алгоритма в процессе решения задачи покрытия множеств

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