Могу ли я использовать эту функцию фитнеса?

Question

Я работаю над проектом с использованием генетического алгоритма, и я пытаюсь сформулировать функции пригодности, мои вопросы:

• Что такое эффект пригодности формулы выбора на GA?

• Возможно, что функция фитнеса равна прямому числу нарушений (в случае минимизации)?

Answer 1

Что такое эффект пригодности формулы выбора на

фитнес-функции GA играет очень важную роль в руководстве ГА.

Хорошие функции фитнеса помогут GA эффективно и эффективно исследовать пространство поиска. С другой стороны, плохие фитнес-функции могут легко заставить GA попасть в локальное оптимальное решение и потерять силу обнаружения.

К сожалению, у каждой проблемы есть своя функция фитнеса.

Для целей классификации задачи широко применяются меры измерения (евклидовы, манхэттен ...). Вы также можете использовать энтропийные подходы.

Для проблем с оптимизацией вы можете использовать грубую модель функции, которую вы исследуете.

Обширная литература доступна по характеристикам функции фитнеса (например, {2}, {3}, {5}).

С точки зрения реализации необходимо учитывать некоторые дополнительные механизмы: линейное масштабирование, усечение сигмы, масштабирование мощности ... (см. {1}, {2}).

Также функция фитнеса может быть динамичной: изменение во время эволюции, чтобы помочь найти исследование космоса.

Можно сделать функцию фитнес равно непосредственно число нарушений (в случае минимизации)?

Да, это возможно, но вы должны учитывать, что это может быть слишком грубая зернистая функция фитнеса.

Если функция фитнес слишком грубая (*), у нее недостаточно выразительности, чтобы вести поиск, а генетический алгоритм будет зависеть от локальных минимумов намного чаще и никогда не сможет сходиться на решении.

В идеале хорошая функция фитнеса должна иметь возможность рассказать вам, какое лучшее направление для перехода от данной точки: если фитнес-объект хорош, подмножество его окрестности должно быть лучше.

Так что не большой плато (широкая плоская область, которая не дает направления поиска и вызывает случайное блуждание).

(*) С другой стороны, совершенно гладкая функция пригодности может быть признаком того, что вы используете неправильный тип алгоритма.

---

Наивный пример: вы посмотрите параметры a, b, c таким образом, что

g(x) = a * x/(b + c * sqrt(x)) 

является хорошим приближением n заданных точек данных (x_i, y_i)

Вы могли бы свести к минимуму эту приспособленность функция:

 | 0 if g(x_i) == y_i     
E1_i = | 
     | 1 otherwise 

f1(a, b, c) = sum (E1_i) 
       i 

и он может работать, но поиск не предназначен. Лучшим выбором является:

E2_i = (y_i - g(x_i))^2 

f1(a, b, c) = sum (E2_i) 
       i 

Теперь у вас есть «направление поиска» и большая вероятность успеха.

---

Дальнейшие детали:

1. Genetic Algorithms: what fitness scaling is optimal? Владика Крейнович, Крис Кинтан
2. Генетические алгоритмы в поисковой оптимизации, и машинное обучение по Голдберг, D. (1989, Addison-Wesley)
3. The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance Мелани Митчелл, Стефани Форрест, Джон Х Холланд.
4. Avoiding the pitfalls of noisy fitness functions with genetic algorithms по Fiacc Ларкин, Конор Райан (ISBN: 978-1-60558-325-9)
5. Essentials of Metaheuristics Шоном Люком