Фитнес-функция в генетическом алгоритме для коммивояжера - PullRequest
0 голосов
/ 10 марта 2012

Я пытаюсь написать генетический алгоритм для задачи коммивояжера (TSP).Для выбора я использую Выбор колеса рулетки: http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/

Это означает, что вероятность выбора для спаривания пропорциональна значению фитнес-функции.
Наиболее распространенная пригодностьФункция для TSP - длина маршрута.Однако чем «короче» маршрут, тем лучше.

Как написать фитнес-функцию, описывающую краткость маршрута?
Или как преобразовать истинную длину каждого маршрута ввероятность?

Ответы [ 2 ]

6 голосов
/ 10 марта 2012

У вас есть функция стоимости (чем ниже, тем лучше), которую вы хотите преобразовать в фитнес-функцию (чем выше, тем лучше).

Используйте обратное. Если стоимость (расстояние) составляет x, тогда ваша физическая форма может стать 1/x.

4 голосов
/ 11 марта 2012

На самом деле это не проблема для функции пригодности, а для шага выбора. Вы также должны использовать окна в пропорциональном выборе, чтобы вы масштабировали значения пригодности. В противном случае оператор будет оказывать слишком небольшое давление выбора: просто представьте, что значения 573 и 579 очень близки и, следовательно, будут иметь примерно одинаковую пропорцию. Как правило, вы масштабируете их по текущей лучшей и худшей пригодности.

Вы можете взглянуть на ProportionalSelector, который мы реализовали в HeuristicLab . Вы даже можете попробовать и поэкспериментировать с этим программным обеспечением и изучить различные методы выбора, кроссоверы, операторы мутаций и т. Д.

...