Функція допасованості

Фу́нкція допасо́ваності[1] (англ. fitness function) — це особливий тип цільової функції, який застосовують як порівняльний показник якості[en] для підбивання підсумку того, наскільки близьким є задане конструктивне рішення до досягнення поставлених цілей. Функції допасованості застосовують в генетичному програмуванні та генетичних алгоритмах, щоби скеровувати симуляції до оптимальних конструктивних рішень.

Генетичне програмування та алгоритмиРедагувати

Зокрема, в галузях генетичного програмування та генетичних алгоритмів кожне конструктивне рішення, як правило, представляють як стрічку чисел (яку називають хромосомою). Ідея полягає в тім, щоби після кожного кола тестування або моделювання вилучати n найгірших конструктивних рішень, і розводити n нових із найкращих. Кожне конструктивне рішення, таким чином, потребує присуджування порівняльного показника якості, що вказував би, наскільки близько воно підійшло до того, щоби відповідати загальним умовам, і цей показник породжується застосуванням функції допасованості до результатів тестування або моделювання, отриманих від цього рішення.

Причина, чому генетичні алгоритми неможливо розглядати як ледачий спосіб виконання конструкторської праці, полягає саме в зусиллях, потрібних для конструювання працездатної функції допасованості. Незважаючи на те, що тим, хто виходить з кінцевим конструкторським рішенням, є вже не людина, а комп'ютер, тим, хто має сконструювати функцію допасованості, все ще лишається саме людина. Якщо її сконструйовано погано, то алгоритм або збігатиметься на неприйнятному рішенні, або зазнаватиме труднощів у тому, щоби збігтися взагалі.

Функція допасованості повинна не лише тісно корелювати з метою конструктора, але повинна також бути обчислювально ефективною. Швидкість виконання є дуже важливою, оскільки типовий генетичний алгоритм, щоби виробити корисний результат для нетривіальної задачі, мусить ітеруватися багато разів.

Може бути доцільним і наближування допасованості[en], особливо в наступних випадках:

  • Обчислення допасованості одного рішення є надзвичайно витратним
  • Точної моделі обчислення допасованості немає
  • Функція допасованості є непевною або зашумленою.

Існує два основні класи функцій допасованості: такий, у якому функція допасованості не змінюється, як в оптимізації незмінної функції або тестуванні за незмінним набором тестових прикладів; і такий, у якому функція допасованості є мінливою, як у розмежуванні ніш[en] або коеволюції набору тестових прикладів.

На функції допасованості можливо також дивитися в термінах адаптивного ландшафту, який показує допасованість для кожної можливої хромосоми.

В багатьох випадках означення функції допасованості не є прямолінійним, і часто виконується ітеративно, якщо найдопасованіші рішення, вироблені генетичними алгоритмами, не є тим, що потрібно. Інтерактивні генетичні алгоритми[en] беруться за це ускладнення, віддаючи оцінювання зовнішнім агентам (зазвичай, людям).

Див. такожРедагувати

ПриміткиРедагувати

  1. fitness // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.

ПосиланняРедагувати