Учебники

Генетические алгоритмы – условие прекращения

Условие завершения Генетического Алгоритма важно при определении, когда закончится работа GA. Было отмечено, что первоначально GA прогрессирует очень быстро, и лучшие решения приходят через каждые несколько итераций, но это имеет тенденцию насыщаться на более поздних этапах, когда улучшения очень малы. Обычно мы хотим, чтобы условие завершения было таким, чтобы наше решение было близко к оптимальному в конце цикла.

Обычно мы соблюдаем одно из следующих условий расторжения –

  • Когда не было никакого улучшения в населении для X итераций.
  • Когда мы достигнем абсолютного числа поколений.
  • Когда значение целевой функции достигло определенного заранее заданного значения.

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

Однако, если пригодность любого из источников лучше, тогда мы сбрасываем счетчик на ноль. Алгоритм завершается, когда счетчик достигает заданного значения.

Как и другие параметры GA, условие завершения также сильно зависит от проблемы, и разработчик GA должен попробовать различные варианты, чтобы увидеть, что лучше всего подходит для его конкретной задачи.