Генетичен алгоритъм

Генетичните алгоритми са клас адаптивни алгоритми за стохастична оптимизация, които включват търсене и итеративно оптимизиране на решението. За първи път са предложени от Holland (1975).

Основната идея на генетичния алгоритъм е да се наподоби в опростен вид процеса на естествен отбор (селекция), с цел да се открие възможно най-добър алгоритъм за решаване на дадена задача. Първата стъпка е да се мутира, т.е. измени на случаен принцип, даден набор примерни програми. На втората стъпка се извършва селекция, което обичайно изисква сравняване на набора програми спрямо целева функция, още наричана фитнес функция. Процесът се повтаря докато се открие подходящо решение.

Съществуват голям брой различни видове генетични алгоритми и много степени на свобода при решаване с тях на оптимизационни задачи. Стъпката, включваща мутация, зависи както от това как са представени примерните програми, така и дали разработчикът ползва различни техники на кръстосване. Как точно се формулира фитнес функцията, спрямо стойностите на която решенията се сравняват, също е въпрос на избор на разработчика.

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

Методология

Оптимизационни задачи

В генетичния алгоритъм, популация от кандидат-решения (наречени „индивиди“ или „фенотипи“) на дадена оптимизационна задача, е подложена на итеративен процес на еволюция в търсене на по-добри решения. Всяко кандидат-решение има набор от качества (аналог на биологичните „хромозоми“ или „генотип“), които могат да бъдат видоизменяни, т.е. мутирани; традиционно решенията се представят в двоичен вид като низове от нули и единици, но са възможни и други генетични представяния.

Еволюцията обичайно започва с популация, съставена от случайно генерирани индивиди, и продължава с итеративен процес, при който на всяка стъпка популацията се нарича „поколение“. Във всяко поколение се оценява „приспособимостта“ на всеки от индивидите; обичайно приспособимостта е формулирана като целева функция, още наречена фитнес функция на решаваната оптимизационна задача. По-приспособените индивиди, т.е. тези с по-високи изчислени стойности на фитнес функцията, биват избрани от текущата популация и геномите им биват модифицирани (кръстосани или случайно мутирани), за да формират новото поколение. Така на следващата итерация на алгоритъма се използва новото поколение от кандидат-решение.

Обичайно алгоритъмът завършва работа, когато или се достигне предварително зададения максимален брой поколения, или се получи поколени със задоволително ниво на фитнес функцията на индивидите в него.

Типичният генетичен алгоритъм се нуждае от:

1. генетично представяне на дефиниционната област от решения,
2. фитнес функция, съставена така че да може да оценява стойностите от дефиниционната област от решения.

Стандартно представяне на кандидат-решенията е чрез масиви от битове. Без съществени разлики могат да се използват и масиви от други типове данни или структури от данни. Основното свойство, което прави тези генетични представяния удобни за работа, е, че техните части са лесни за сравняване поради фиксирания им размер, което улеснява простите операции по кръстосване. Могат да се използват и масиви с променливи дължини, но в този случая реализацията на оператора кръстосване е по-сложна. Дървовидните генетични представяния са обект на разглеждане в т.нар. генетично програмиране, а с графовидни представяния се занимава еволюционното програмиране; възможно е разглеждане и на комбинация едновременно от линейно представени хромозоми и дървета.

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

Инициализация

Размерът на популацията зависи от характера на решаваната задача, но типично съдържа няколкостотин или няколко хиляди възможни решения. Често началната популация се генерира случайно, което позволява претърсването на цялата област от възможни решения (пространство на търсенето) Понякога решенията могат да бъдат „посадени“ в региони от пространството на търсене, в които е вероятно да се открият оптимални решения.

Селекция

По време на всяко поредно поколение част от съществуващата популация бива избрана да продължи напред като даде началото на следващо поколение. Индивидуалните решения се избират чрез процедури, базирани на приспособимостта им (т.е. на стойностите им на фитнес функцията на алгоритъма), като решенията с по-добри стойности на фитнес функцията биват избрани с по-голяма математическа вероятност да продължат процеса. Някои методи за селекция оценяват фитнеса на всички индивиди в поколението и с предимство избират най-добрите решения; а други избират случайна извадка от поколението, тъй като първия метод може да се окаже много времеемък.

Фитнес функцията се дефинира над определеното генетично представяне и измерва „качеството“ на представяното решение. Фитнес функцията винаги зависи от формулировката на решаваната оптимизационна задача. Например при Задачата за раницата може да искаме да максимизираме общата стойност на обектите, които избираме да сложим в раница с фиксиран капацитет. Едно възможно представяне на решението може да е битов низ, където всеки бит представя различен обект, а стойността на бита (0 или 1) означава дали обектът е в раницата или не. Не всяко такова представяне е валидно, тъй като размерът на обектите може да надвишава капацитета на раницата. Тук фитнесът на решението е сумата от стойностите на всички обекти в раницата, ако представянето е валидно, или 0 в противен случай.

Генетични оператори

^{Този раздел е празен или е мъниче. Можете да помогнете на Уикипедия, като го разширите.}

Край на алгоритъма

Процесът се повтаря, докато не бъде достигнато определено условие за край. Обичайни условия за край на генетичния алгоритъм са:

• Достигнато е решение, което удовлетворява определени минимални критерии,
• Достигнат е предварително определен брой поколения,
• Достигнат е предварително определен „бюджет“ (изчислително време или средства),
• Фитнес функцията е достигнала плато, т.е. по-новите итерации не произвеждат по-добри резултати,
• Ръчно спиране,
• Някаква комбинация от горните условия.

Източници

Тази страница частично или изцяло представлява превод на страницата Genetic algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​