Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Методи на нула, за

Оценка на ефективността на техники за оптимизация

Голямо разнообразие от итеративни алгоритми изправя задачата за избор на потребителя. За да направите това, определени критерии, въз основа на които един алгоритъм ще се счита за по-предпочитан от другия. За тази цел обикновено се използват следните оценки:

1. Точност Търсене - стойността на близост на местен оптимално, което води до алгоритъма след предварително определен брой повторения.

2. Ставката на конвергенция - броя на повторенията, необходими за постигане на дадена точност.

3. Време сметки - за търсене на местния оптимално компютъра с дадена точност, разделена на коефициента на сложност на проблема (или високоскоростна компютри).

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

5. Надеждност - собственост на алгоритъм резултата на оптималната търсенето под повтаря от различни отправни точки.

Алгоритми за сравнение на тези критерии трябва да се изчисли в същите или подобни условия. Оценка алгоритъм за степента на сближаване в някакъв смисъл на обратната страна на оценката на тяхната точност. Целева висока точност може значително да увеличи броя на повторения на метода за оптимизиране. Необоснована намаляване точност може да се счупят теоретичните допусканията на проблема (например, състоянието на ортогоналност в метода на конюгат градиент се разбива при ниска точност на избрания метод на едномерен минимизиране).

методи Класификация на непринуден оптимизация

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

· Методи за нулев порядък или търсене. В едномерен минимизирането - метод на разполовяване интервал, метод дихотомия, златен раздел, метод на Фибоначи и др многовариантно оптимизация -. Метод за конфигуриране (Хук-Jeeves), метод Rosenbrock, спрегнати посоки, и др.

· Първият метод цел - метода на градиент спускане (с постоянна стъпка, най-стръмната спускане), координира метод спускане, Гаус-Зайдел и други.

· Методи от втори ред - метод на Нютон, метод на Нютон-Raphson, и др.

1. Видове

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

стратегия за търсене

1. В интервала масива се формира от генератор на случайни числа стойностите на независимата променлива и функция ( ).



2. Между елементите на масива на функционални стойности е оптималната стойност ( ) И съответната стойност на променливата ( ).

3. Изчислява се нов интервал, в който се извършва последваща селекция стойности N

Той се използва за по-големи проблеми. Особено ефективен за характеристиките дерето.

- Методи за изключение интервали от време (обикновено Свен)

стратегия за търсене

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

2. Намаляване на интервала несигурност

3. Търсенето приключва, когато интервалът на несигурност е по-малко от зададената стойност

- Методи за полином сближаване

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

2. Методи за едномерен минимизиране

1. Метод униформа търсене. Сегментът е разделена на равни части, и е точката При които функцията стойност най-малките

2. Метод на разполовяване интервал. На всяка итерация изключва половината от интервала на неопределеност

3. Метод дихотомия. несигурност интервал е разделен на две и двете страни на средата, забавени от ,

4. Методът на златното сечение. Точка произвежда "Golden раздел" на сегмента, ако съотношението на дължината на интервала за по-голямата част, равен на съотношението на по-големите към по-малките ( ).

Алгоритъм: 0 - сложи , пресмятам , Поставете к = 1.

1 - когато Тогава спрете. ако След това отидете до 2, ако Тогава до 3.

2 - пут , Изчислете и преминете към 4.

3 - слагам , Изчислете и преминете към 4.

4 - замени к с к + 1 и преминете към 1.

5. метод на Фибоначи. Числата на Фибоначи: Последователността е дадена 1, 1, 2, 3, 5, 8, 13, 21, ...

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

,

,

,

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

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

· Начин на дихотомия: ;

· Начин на златното сечение: ;

· Фибоначи метод: ,

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

3. Методи за многомерен минимизиране

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

The предимство - простота, ниски изисквания за памет, сближаването с почти всяка първоначална приближение (с изключение на канализационни функции - фиксирана в метода на Rosenbrock).

Основният недостатък - бавно конвергенция. Методът на координатната спускане проблем минимизиране отделими функция е решен в N (брой координати) стъпки за общата форма на функцията - един безкраен процес.

2. Методът на конфигурация (търсене модел). Изследване Search + модел търсене. Като набор от насоки за избор на много координатни направления. Той улавя посока първа координира и е стъпка към намаляване на функция. След повтаряне през всички координати проучват търсенето е приключило. Получената точка - нова основа. Ако проучване на търсенето на даден размер стъпка е неуспешна, след това стъпка намалява. Търсене прекратява, когато текущата стойност на стъпката става по-малко от определена стойност.

Търсене на модела се движи в посока от старата към новата база. Ако стойността на най-доброто място, е по-малко от предходната, съвпадение модел е успешен, ако не, търсенето продължава разглеждането на по-малък терен.

3. Методът от гъвкав многостен на (Метод Nelder-Mead или метода на симплекс). Тя се основава на изграждането на последователност на N 1 посочва системи, които са върховете на изпъкнал Стол. В организацията на алгоритъм за търсене се използва симплекс важно имота - срещу всеки връх има един ръб.

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

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

4. Метод Rosenbrock. Режисьор на likidatsiyu един от недостатъците на метода на координатната спускане - силно чувствителна към избора на координатната система. Методът се състои по същество в намирането на "добър" координатна система чрез завъртане оригиналните оси. намаляваща функция Повтарящата посока търсене посредством променливи дискретни стъпки по линейно независими перпендикулярни направления. При успех в етапа на тест за неговата стойност се увеличава от следващата итерация чрез разтягане съотношение и в случай на повреда, се намалява, като се умножи по коефициента на компресия, където посоката на търсене е обърната. Ако, се случва всяка посока на неуспех търсене, след това изгради нов набор от линейно независими и перпендикулярни направления, кръгъл търсене в някои райони продължава. Нови посоки се завъртат спрямо предходната, така че те са изпънати, по протежение на дерето.

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

Определете началната точка и посоката, съвпадаща с координатната. Това е минимумът движение на последователни N + 1 зони с помощта на една от техниките на едномерни минимизиране. Получената минимална точка е взета като отправна точка за търсене на следващата посока на посоката Той се използва както в първата и последната търсенето ( ). Тя намира нова посока на научните изследвания, в съчетание с , Тя преминава през точките, получени при първото и последното търсене. Повтаря търсенето на N + 1 линии, които не съдържат посоки

<== Предишна лекция | На следващата лекция ==>
| Методи на нула, за

; Дата: 05.01.2014; ; Прегледи: 1086; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото попълнение
Page генерирана за: 0.019 сек.