Эффективность генетических алгоритмов определяется степенью выполнения требований к показателям точности и вычислительных затрат. Точность характеризуется погрешностью полученного результата
δ() = (F()-F())/F(),
где — решение, полученное с помощью ГА, — точное значение экстремума, F() — значение целевой функции в точке . Поскольку в практически решаемых задачах точка неизвестна, оценку точности разных алгоритмов выполняют на тестовых задачах и в качестве принимают лучшее из известных решений.
Вычислительные затраты включают затраты процессорного времени и памяти на решение задачи, причем основное значение имеют затраты времени.
Хотя из теоремы шаблонов вытекает, что увеличение числа разрывов хромосом при кроссовере способствует разрушению формирующихся шаблонов, практический опыт показывает, что при решении многих задач многоточечный кроссовер оказывается более эффективным. Де Джонг и Спирс еще в 1992 г. внесли вклад в объяснение такой несогласованности теории и практических результатов, показав, что многоточечный кроссовер в отличие от одноточечного способствует сохранению длинных шаблонов, состоящих из частей, располагающихся только в четных (или только в нечетных) участках разрываемой хромосомы [1].
В работе [2] введено понятие поисковой способности ГА, как способности получить в процессе поиска любую заданную хромосому. Исследована поисковая способность алгоритмов с операторами скрещивания и мутации при бинарной кодировке хромосом. Сделан вывод о том, что кроссовер с большими возможностями разрушения хромосом способствует более быстрому смешиванию и более активному поиску за счет большего разнообразия хромосом в популяции. Однако вопрос об итоговой эффективности однородного кроссовера, как сильно разрушающего оператора, остался открытым.
Список литературы
1. De Jong K.A., Spears W.M.. A Formal Analysis of the Role of Multi-point Crossover in Genetic Algorithms. Annals of Mathematics and Artificial Intelligence, 1992.
2. Цой Ю.Р. О поисковых способностях эволюционных алгоритмов. — http://qai.narod.ru/GA/easearch.pdf