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