Метады аптымізацыі аднамерных задач

1. 13.1 Метад агульнага пошуку
2. 13.2 Метад палавіннага дзялення (падзел адрэзка напалову)
3. 13.3 Метад дыхатаміі
4. 13.4 Метад "залатога сячэння"
5. 13.5 Метад Фібаначы

Працэс аптымізацыі ляжыць у аснове ўсёй інжынернай дзейнасці, паколькі класічныя функцыі інжынера складаецца ў тым, каб, з аднаго боку, праектаваць новыя, больш эфектыўныя і менш дарагія тэхнічныя сістэмы, а з другога - распрацоўваць метады павышэння якасці функцыянавання існуючых сістэм. Эфектыўнасць метадаў аптымізацыі, якія дазваляюць выбіраць лепшы варыянт без праверкі ўсіх магчымых варыянтаў, цесна звязаная з шырокім выкарыстаннем дасягненняў у галіне матэматыкі шляхам рэалізацыі ітэрацыйныя вылічальных схем, якія абапіраюцца на досыць абгрунтаваныя метады і алгарытмы з ужываннем вылічальнай тэхнікі.

У цяперашні час, у сувязі з даступнасцю персанальных кампутараў, вялікая ўвага надаецца выкарыстанню лікавых метадаў аптымізацыі ў інжынернай практыцы, якія можна падзяліць на дзве вялікія групы: метады безумоўнай і ўмоўнай аптымізацыі. Дадзеная частка звязаны з розным апісаннем прасторы праектавання. Вобласць даследаванні, гэта значыць вобласць, у якой інжынер спрабуе вызначыць оптымум пэўнай задачы, называюць прасторай праектавання.

Прастору праектавання, які вызначаецца праектнымі параметрамі, звычайна абмежаваны побач умоў, звязаных з фізічным сутнасці задачы і разглядаецца ў ў выглядзе двух варыянтаў:

1) калі праектны параметр адзін, то звычайна абмежаванні звязаны з яго значэннямі, гэта значыць вобласць праектавання звужаецца да адрэзку даследаванні [a, b];

2) калі праектных параметраў некалькі, то абмежаванні могуць накладвацца або на іх значэнне, абмяжоўваючы вобласць даследаванні, або ў выглядзе ўзаемазалежнасці паміж праектнымі параметрамі, якія павінны ўлічвацца пры пошуку рашэнні (гэтыя залежнасці ў рэальных задачах могуць адлюстроўваць законы прыроды, эканомікі, права, наяўнасць неабходных матэрыялаў і т. д.).

У дадзеным раздзеле разглядаюцца метады безумоўнага аднамернага пошуку оптымуму мэтавай функцыі, заснаваныя на выкарыстанні першага варыянту прадстаўлення прасторы праектавання, дзе мэтавая функцыя - гэта выраз (функцыя), значэнне якога інжынер спрабуе мінімізаваць або максымізаваць. Пры гэтым мяркуецца, што мэтавыя функцыі, якія даследуюцца з'яўляецца унимодальных, гэта значыць маюць інтэрвале даследаванні, які разглядаецца толькі адзін оптымум (мал. 13.1). Такое абмежаванне на характар ​​мэтавай функцыі не з'яўляецца жорсткім, як можа здацца, так як многія задачы, з якімі інжынер сутыкаецца ў сваёй практыцы, аказваюцца унимодальных.

Лікавыя метады, якія арыентуюцца на рашэнне задач безумоўнай аптымізацыі, можна падзяліць на тры класа:

- метады прамога пошуку, заснаваныя на вылічэнні толькі значэнняў мэтавай функцыі;

Малюнак 13.1 - унимодальных мэтавая функцыя

Малюнак 13.2 - Мэтавая функцыя з лакальным і глабальным оптымумам

- градыентныя метады, у якіх выкарыстоўваюцца дакладныя значэння першых вытворных f (x)

- метады другога парадку, у якіх разам з першымі вытворнымі выкарыстоўваюцца таксама іншыя вытворныя функцыі f (x).

Задача аднамернай аптымізацыі ставіцца такім чынам: значэнне параметра Х мэтавай функцыі f (x), які называюць праектным параметрам, знаходзяцца на інтэрвале даследаванні [a, b]. У працэсе пошуку оптымуму мэтавай функцыі гэты інтэрвал, які называецца інтэрвалам нявызначанасці, пастаянна змяншаецца (звужаецца), таму метады аднамернай аптымізацыі часам называюць метадамі звужэння інтэрвалу нявызначанасці.

Выбар колькаснага метаду ў першую чаргу залежыць ад выгляду мэтавай функцыі, якая можа быць однопараметрическим і многопараметрической (мал. 13.3, 13.4).

Малюнак 13.3 - однопараметрическим мэтавая функцыя

Малюнак 13.4 - двухпараметрического мэтавая функцыя

Некаторыя алгарытмы аптымізацыі прыстасаваныя да пошуку максімуму, а іншыя - для пошуку мінімуму.

Аднак, незалежна ад тыпу задачы, якая вырашаецца на экстрэмуму (оптымум) можна карыстацца адным і тым жа алгарытмам, так як задачу мінімізацыі можна лёгка перарабіць у задачу на пошук мінімуму, змяніўшы знак мэтавай функцыі на супрацьлеглы (мал. 13.5).

Малюнак 13.5 - зменай знака мэтавай функцыі на супрацьлеглы задача на мінімум ператвараецца ў задачу на максімум

Агульная пастаноўка задачы для метадаў аднамернай аптымізацыі ставіцца наступным чынам: хай параметр Х знаходзіцца нa адрэзку [a, b], а мэтавая функцыя унимодальнa ў галіне, якую даследуем. Большасць лікавых метадаў аднамернай аптымізацыі - гэта метады звужэння адрэзка, а менавіта: метад падзелу адрэзку напалову, метад дыхатаміі, метад залатога перасеку, метад Фібаначы.

У працэсе аднамернай аптымізацыі мэтавай функцыі на ЭВМ можна вылучыць два этапы:

1) устанаўленне межаў адрэзка, на якім рэалізуецца працэдура пошуку оптымуму;

2) памяншэнне адрэзка зададзенай хібнасці вылічэнні .

Першы этап рэалізуецца з дапамогай эўрыстычных метадаў пошуку і вельмі складана. Другі - называюць правілам выключэння адрэзкаў, рэалізуюць алгарытм пошуку, дазваляе знайсці кропку оптымуму шляхам паслядоўнага выключэння частак зыходнага абмежаванага адрэзка [a, b], гэта значыць з дапамогай ітэрацыйныя алгарытмаў. У якасці ўмовы заканчэння ітэрацыйныя працэсу выкарыстоўваецца момант, калі подинтервал пакінуты паменшыцца да досыць малых памераў (звычайна для гэтага задаюць значэнне зададзенай хібнасці вылічэнні ).

13.1 Метад агульнага пошуку

Відавочна, найбольш натуральным спосабам звужэння інтэрвалу нявызначанасці для аднамернай унимодальной функцыі з'яўляецца дзяленне яго на некалькі роўных частак з наступным вылічэннем значэнняў мэтавай функцыі ў вузлах атрыманай сеткі (мал. 13.6).

Малюнак 13.6 - метад агульнага пошуку

У выніку інтэрвал нявызначанасці звужаецца да двух крокаў сеткі. Звычайна кажуць аб драбненні інтэрвалу нявызначанасці, якое характарызуецца каэфіцыентам f. Падзяліўшы інтэрвал нявызначанасці на N частак, атрымаем N + 1 вузел, і тады

.

Каб атрымаць значэнне f = 0,01, неабходна вылічыць мэтавую функцыю ў 199 кропках, а пры f = 0,001 N = 1999. Адсюль відаць, што эфектыўнасць гэтага метаду пры памяншэнні інтэрвалу нявызначанасці хутка падае. Напрошваецца іншы варыянт: каб атрымаць f = 0,01, неабходна вылічыць спачатку функцыю ў 19 кропках і атрымаць f = 0,1, а затым вылічыць яшчэ 19 значэнняў функцыі на скарочаным інтэрвале нявызначанасці, атрымаць f = 0,01, зрабіўшы пры гэтым усяго 38, а не 199 вылічэнняў. Такім чынам, пры некаторай вынаходлівасці эфектыўнасць пошуку можна рэзка павялічыць.

13.2 Метад палавіннага дзялення (падзел адрэзка напалову)

Сутнасць метаду заключаецца ў пастаянным дзяленні адрэзка даследаванні мэтавай функцыі [a, b] напалову і вызначэнні на ім каардынатаў трох кропак х1, х2, хm. Прычым значэнне іх вызначаюцца як:

L = ba, , .

Малюнак 13.7 - геаметрычная інтэрпрэтацыя метаду палавіннага дзялення

пункту , Падзяляюць адрэзак [a, b] на чатыры роўныя часткі (мал. 13.6), вылічаем значэнне мэтавай функцыі Затым параўноўваем значэнне і , калі , То выключаем з даследавання адрэзак і пакладзем . Тады сярэдняй кропкай новага адрэзка [a, b] становіцца . але калі , То параўноўваем значэнне мэтавай функцыі і ; калі , То выключаем адрэзак , пакладзем ; калі , То выключаем адрэзак і , пакладзем , Гэта значыць фарміруем новы адрэзак даследавання. Вылічаем L = b - a, калі , Калі няма, то зноў вяртаемся да пачатку.

Дадзены алгарытм ітэрацыйныя, таму звычайна ў якасці ўмовы заканчэння ітэрацыйныя працэсу выбіраюць ўмова , Гэта значыць звужэнне адрэзку выконваецца да таго часу, пакуль яго велічыня не паменшыцца да зададзенай вылічальнай хібнасці . Алгарытм метаду прадстаўлены на мал. 13.8.

Малюнак 13.8 - Схема алгарытму метаду палавіннага дзялення

Гэты метад адрозніваецца вялікай эфектыўнасцю.

13.3 Метад дыхатаміі

Вылічэнні мэтавай функцыі ў двух кропках інтэрвалу нявызначанасці дазваляе яго звузіць. Можна такім чынам выбраць гэтыя кропкі, інтэрвал нявызначанасці будзе мінімальным. На мал. 13.9 паказаны абазначэння, якія выкарыстоўваюцца ў гэтай схеме.

Малюнак 13.9 - абазначэнне, якія выкарыстоўваюцца ў метадзе дыхатаміі

Калі значэнне мэтавай функцыі пры х1 больш, чым пры х2, то новы інтэрвал нявызначанасці роўны Z1 = z1 + z2. У адваротным выпадку ён вызначаецца выразам Z2 = z2 + z3. Задача складаецца ў тым, каб адначасова мінімізаваць Z1 i Z2, задаволіўшы умовам

z1 + z2 + z3 = Z,

z1> 0,

z2> 0,

z3> 0.

З роўнасці можна выключыць z2. тады

Z - z3 = min, Z - z1 = min.

Бо велічыня Z зададзена, то правыя часткі гэтых раўнанняў будуць тым менш, чым больш z1 i z3. Такім чынам, оптымум адпавядае умове

z1 = z3 = 0,5Z.

Але тады z2 = 0, што супярэчыць умове z2> 0.

Малюнак 13.10 - метад дыхатаміі

Хай z2 мае некаторы вельмі маленькае значэнне . Тады з z1 i z3 аднімем па . У выніку пасля вылічэнні першай пары значэнняў мэтавай функцыі пры блізкіх значэннях х інтэрвал нявызначанасці звузіцца, як паказана на мал. 13.10, і каэфіцыент дзялення будзе роўны

.

У межах, пры , . У далейшым пры выкарыстанні метаду дыхатаміі выконваюцца тыя аперацыі, што і пры выкарыстанні метаду дзялення адрэзка напалову.

13.4 Метад "залатога сячэння"

З кожных трох значэнняў мэтавай функцыі, якія былі вылічаныя ў інтэрвале нявызначанасці ў далейшым выкарыстоўваюцца толькі два, а трэцяе не дае дадатковай інфармацыі і ў далейшым не выкарыстоўваецца. У метадзе залатога перасеку мэтавая функцыя вылічаецца ў кропках інтэрвалу нявызначанасці, якія размешчаны такім чынам, каб кожнае вылічанае значэнне мэтавай функцыі давала новую карысную інфармацыю.

Малюнак 13.11 - абазначэнне, якія выкарыстоўваюцца ў метадзе залатога перасеку

Сутнасць гэтага метаду заключаецца ў наступным. Інтэрвал нявызначанасці дзеліцца на дзве няроўныя часткі, стаўленне даўжыні большага адрэзка да даўжыні ўсяго інтэрвалу роўная стаўленню даўжыні меншага адрэзка да даўжыні большага адрэзка. На мал. 13.11 паказаны інтэрвал нявызначанасці Z, які складаецца з адрэзкаў z1 i z2, стаўленне даўжынь якіх вызначаецца правілам залатога перасеку.

Акрамя таго, z1 + z2 = Z. З першага раўнання варта . Падставіўшы значэнне Z з другога раўнання і падзяліўшы абедзве часткі на , атрымаем

Вырашаючы гэта квадратнае раўнанне, знаходзім для станоўчага кораня значэнне

На мал. 13.12 паказана дзялення інтэрвалу нявызначанасці ў гэтых адносінах і нанесеныя адпаведныя значэння мэтавай функцыі, якія дазваляюць паменшыць інтэрвал нявызначанасці ў 1 / 0,618 раз.

Малюнак 13.12 - Метад залатога перасеку

На гэтай стадыі яшчэ не відаць пераваг метаду залатога перасеку ў параўнанні з метадам дыхатаміі, аднак іх добра відаць пры далейшым дзяленні інтэрвалу, так як аказваецца, што адно з значэнняў мэтавай функцыі, якое неабходна вылічыць на наступным кроку, ужо вядома. Таму, каб паменшыць нявызначанасць яшчэ ў 1 / 0,618 раз, трэба дадаткова вылічыць толькі адно значэнне мэтавай функцыі ў кропцы, вызначаецца правілам залатога перасеку.

Пры n> 2 эфектыўнасць метаду залатога перасеку вышэй, чым у метаду дыхатаміі, так як пры кожным вылічэнні мэтавай функцыі інтэрвал нявызначанасці скарачаецца ў 1 / 0,618 раз. Пасля вылічэнні N значэнняў мэтавай функцыі каэфіцыент драбнення інтэрвалу нявызначанасці складае

f = 0,618 N-1.

Метад залатога перасеку дазваляе адзначыць цікавую заканамернасць: найбольшая скарачэнне наступных інтэрвалаў нявызначанасці дасягаецца пры вылічэнні мэтавай функцыі ў кропках, роўнааддаленымі ад яго цэнтра. Калі працягваць такім чынам і кожны раз, вылічаючы мэтавую функцыю, скарачаць інтэрвал нявызначанасці, то будуць справядлівымі наступныя суадносіны:

ZJ-2 = ZJ-1 + ZJ, 1

дзе ZJ даўжыня інтэрвалу нявызначанасці пасля вылічэнні J-га значэння мэтавай функцыі.

На мал. 13.13 прадстаўлены алгарытм выбару наступнай пункту пошуку. Зададзеная дакладнасць можа, вядома, мяняцца выбарам значэння. для функцыі Пошук адбываўся ў інтэрвале (0, 2).

Малюнак 13.13 - паслядоўнасць этапаў выбару наступнай пункту пошуку

Праўдзівы мінімум знаходзіцца ў пункце 1,76322211, дзе значэнне функцыі роўна -0, 0972601313.

Малюнак 13.14 - Схема алгарытму метаду "залатога сячэння"

Пры распрацоўцы праграм для вырашэння задач однопораметричнои оптмизации выкарыстоўваюць наступныя суадносіны:

13.5 Метад Фібаначы

Выкажам здагадку, што трэба вызначыць мінімум мэтавай функцыі як мага дакладней, гэта значыць з найменшай магчымым інтэрвалам нявызначанасці, але пры гэтым можна выканаць толькі вылічэнняў функцыі. Як вынікае выбраць кропак, у якіх вылічаецца функцыя? З першага погляду здаецца ясным, што не варта шукаць рашэнні для ўсіх кропак, атрыманыя ў выніку эксперыменту. Наадварот, трэба паспрабаваць зрабіць так, каб значэнне функцыі, атрыманыя ў папярэдніх эксперыментах, вызначалі становішча наступных кропак. Сапраўды, ведаючы значэнне функцыі, мы тым самым маем інфармацыю пра самую функцыю і становішча яе мінімуму і выкарыстоўваем гэтую інфармацыю ў далейшым пошуку.

Выкажам здагадку, што маецца інтэрвал нявызначанасці і вядома значэнне функцыі ўнутры гэтага інтэрвалу (гл. мал. 13.15).

Малюнак 13.15 - унимодальных мэтавая функцыя. Геаметрычная інтэрпрэтацыя метаду Фібаначы

Калі можна вылічыць функцыю ўсяго адзін раз у пункце , То дзе варта змясціць кропку Для таго каб атрымаць найменшы магчымы інтэрвал нявызначанасці?

выкажам здагадку і , прычым , Як паказана на мал. 13.15, і гэтыя значэнні будуць фіксаваныя, калі вядомыя і . калі знаходзіцца ў інтэрвале , То:

1. Калі , То новым інтэрвалам нявызначанасці будзе даўжынёй .

2. Калі , То новым інтэрвалам нявызначанасці будзе даўжынёй .

Бо невядома, якая з гэтых сітуацый будзе мець месца, абярэм такім чынам, каб зрабіць мінімальнай найбольшую з даўжынь і . Дасягнуць гэтага можна, зрабіўшы даўжыні і роўнымі, то ёсць змясціўшы ўнутры інтэрвалу сіметрычна адносна кропкі , Што ўжо ляжыць ўнутры інтэрвалу. Любое іншае становішча кропкі можа прывесці да таго, што атрыманы інтэрвал будзе больш . змясціўшы сіметрычна адносна , Мы нічым не рызыкуем у любым выпадку.

Калі апынецца, што можна выканаць яшчэ адно вылічэнне функцыі, то варта ўжыць апісаную працэдуру да інтэрвалу , У якім ужо ёсць значэнне функцыі, вылічанае ў кропцы . Такім чынам, стратэгія зразумелая з самага пачатку. Трэба змясціць наступную кропку ўнутры інтэрвалу нявызначанасці сіметрычна адносна кропкі, ужо знаходзіцца там. Парадаксальна, але, каб зразумець, як трэба пачынаць вылічэнні, неабходна разабрацца ў тым, як яго трэба заканчваць.

На n- ым вылічэнні n-ю кропку трэба змясціць сіметрычна па адносінах да ( - 1) -й кропкі. Палажэнні гэтай апошняй кропкі ў прынцыпе залежыць ад нас. Для таго каб атрымаць найбольшую памяншэнне інтэрвалу на дадзеным этапе, варта падзяліць папалам папярэдні інтэрвал. тады кропка будзе супадаць з пунктам . Аднак пры гэтым мы не атрымліваем ніякай новай інфармацыі. вядома пункту і знаходзяцца адзін ад аднаго на дастатковай адлегласці, каб вызначыць, у якой палове, левай ці правай, знаходзіцца інтэрвал нявызначанасці. Яны размяшчаюцца на адлегласці па абодва бакі ад сярэдзіны адрэзка ; можна самастойна задаць велічыню або выбраць гэтую велічыню роўнай мінімальна магчымым адлегласці паміж двума кропкамі. (Выкажам здагадку, што ў нашым прыкладзе інжынер можа рэгуляваць тэмпературу з інтэрвалам у 1С °, таму .)

Інтэрвал нявызначанасці будзе мець даўжыню , Такім чынам, (Мал. 13.16, ніжняя частка).

Малюнак 13.16 - геаметрычная інтэрпрэтацыя ітэрацыйныя працэсу Фібаначы

На папярэднім этапе пункту і павінны быць змешчаны сіметрычна ўнутры інтэрвалу з на адлегласці ад канцоў гэтага інтэрвалу. Такім чынам, (Мал. 13.16, сярэдняя частка).

Заўвагі. З малюнка зразумела, што на перадапошнім этапе застаецца ў якасці ўнутранай кропкі.

аналагічна

. (Мал. 13.16, верхняя частка)

У агульным выпадку