Локален оптимум

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Областите на подразпределение на пространството на решенията с посочени локалните оптимуми във всяка област
Локални и глобални максимуми и минимуми на функцията cos(3πx)/x, 0.1≤ x ≤1.1

Локален оптимум е термин от областта на математическата оптимизация, с който се означава валидно решение на оптимизационна задача, което е оптимално (максимално или минимално) в рамките на ограничена област на съседство от кандидат-решения. За разлика от глобалния оптимум, който представлява оптималното измежду множество от всички решения, локалният оптимум е оптимален само над някакво подмножество от всички решения.

Когато оптимизираната функция е непрекъсната, със средствата на математическия анализ е възможно локалният оптимум да бъде открит. Ако функцията е навсякъде диференцируема (т.е. във всяка точка има дефинирана първа производна), необходимото условие една точка да бъде локален оптимум е производната ѝ да е равна на 0. Проверката на втората производна осигурява достатъчното условие точката да бъде локален максимум или локален минимум.

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

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

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

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Local optimum“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.