ИЗСЛЕДВАНЕ НА ЕВРИСТИЧНИ АЛГОРИТМИ ЗА МНОГОМЕРНА ОПТИМИЗАЦИЯ С УСКОРЕНА СХОДИМОСТ
Д. Борисов
INVESTIGATION OF HEURISTIC ALGORITHMS FOR MULTYDIMENSIONAL OPTIMIZATION WITH ACCELERATED CONVERGENCE
D. Borisov
Химикотехнологичен и металургичен университет – София
Бул. Климент Охридски, 8, София 1756
Abstract. A new heuristic optimization algorithm with accelerated convergence is proposed for search a maximum of multidimensional, unimodal objective functions without constraints. The algorithm is a combination of the random direction method and the random search method with the penalty of chance. Comparative analysis has been made with other known methods and its effectiveness and accelerated convergence have been demonstrated for cases where the uncertainty interval in the search is very large. The efficiency of the algorithm compared to other known algorithms is based on the number of the objective function evaluation to find the optimum with different accuracy requirements for localization the maximum (or minimum) of the function. The method and proposed algorithm is suitable for parameters estimation in mathematical models.
Key Words: multidimensional optimization, heuristic algorithms, parameter estimation, accelerated convergence, random directions, random search with penalty of chance, efficiency of algorithm
ВЪВЕДЕНИЕ
Задачата за многомерна оптимизация при унимодални целеви функции без ограничения се смята за решена, но все още съществуват практически проблеми, които се нуждаят от повишаване на скоростта на сходимост на методите за намиране на оптималното решение при зададена точност. Такива проблеми се срещат в задачите за оценка на параметри в сложни математични модели на технологични процеси и системи, за които границите на търсеното решение са много големи или въобще не са зададени.
В литературата са описани десетки методи за решаване на задачата на нелинейното програмиране [1, 2, 3] и всеки един то тях не може да претендира за универсалност и максимална ефективност при решаване на всички практически задачи. При голяма част от оптимизационните методи и алгоритми с произволна по вид целева функция скоростта на сходимост съществено зависи от началната точка. Изборът на оптимална начална точка е един от проблемите в многомерната оптимизация. Много изследвания на различни разработени методи и доказването на редица предимства на един или друг метод подсказва идеята за създаване на евристични алгоритми с оптимално комбиниране на безградиентни и градиентни методи [1,2,3]. При многомерните оптимизационни задачи се прилагат два класа методи: градиентни и безградиентни. Безградиентните методи, какъвто е и предложеният в настоящата статия, имат много предимства: лесни са за алгоритмизация, удовлетворят много от инженерните изисквания за минимална начална информация; критериите за спиране са търсенето са строго регламентирани; няма изисквания за вида на целевата функция и нейните производни.
Анализът на различни методи за многомерна оптимизация показва, че много от тях имат както положителни, така и отрицателни страни [1, 2, 3]. Въвеждането на нови евристични правила, изведени в резултат на развитието и изследването на някои алгоритми, може да доведе до съществено ускоряване на алгоритмите.
Евристичните правила, които могат да се използват в създаването на ускорени алгоритми за многомерна оптимизация са следните:
⦁ Оптимален метод за многомерна оптимизация е този, при който се получава сходимо решение, съобразно зададена точност, за минимално време;
⦁ Ако няма зададена начална информация относно областта на екстремума, той с еднаква вероятност се намира във всяка точка от допустимото пространство;
⦁ Повърхностите на постоянни стойности за целевата функция разделя допустимото пространство на две области: с по-добри резултати („успешни“ области) и с по-лоши или еднакви резултати („неуспешни“ области) за целевата функция;
⦁ Вероятността да се направи стъпка в „успешна “ или „неуспешна“ област не зависи от размерността n на пространството на управляващите параметри;
⦁ Ако е направена стъпка в „неуспешна“ област, вероятността да се попадне в „успешна“ чрез стъпка в обратно направление е значителна;
⦁ При няколко точки в допустимото пространство с определени стойности за целевата функция, очакваната посока на най-голямото изменение на Q(X) е в направлението определено от най-лошия резултат и най-добрият резултат за Q(X);
⦁ Ефективността на търсенето нараства, ако отначало се направи грубо локализиране на екстремума и по следващото уточнение съобразно зададена точност;
⦁ В областта близко до екстремума ефективността на градиентните методи нараства, тъй като целевата функция може да се апроксимира точно с квадратична функция;
⦁ Търсенето на екстремума при областни ограничения тип неравенство е по-просто от колкото при функционални ограничения тип равенство.
На основата на гореописаните евристични правила могат да се организират комбинирани алгоритми с повишена сходимост.
Основна цел на настоящото изследване е комбиниране на предимствата на методите за случайно търсене на екстремум на унимодални функции. Тези методи спадат към класа на безградиентните методи и се основават на изследване на целевата функция в допустимата област на управляващите параметри по случаен признак. Методите са изключително прости и са с минимални ограничения при приложението им, тъй като не се изисква като условие целевата функция да е непрекъсната.
СТРАТЕГИЯ НА НОВ МЕТОД ОТ МНОЖЕСТВО СЛУЧАЙНИ НАПРАВЛЕНИЕ С АДАПТИВНА КОРЕКЦИЯ НА СТЪПКАТА
В настоящата статия се предлага един бързо сходим комбиниран алгоритъм, който обединява положителните качества на методите на случайните направления и на случайно търсене с наказание на случайност.
Основната идея на метода на случайните направления се състои в това, ако дадена точка лежи на една повърхнина на постоянни стойности за целевата функция в допустимото пространство на управляващите параметри ΓX, точката разделя пространството на две области – успешна и неуспешна, в зависимост от посоката към екстремума [4, 5]. Ако се направи стъпка от тази точка в случайно направление има три възможности: стъпка в успешната област, стъпка в неуспешната област и стъпка в неутралната област.
Стратегията на новия метод е, от дадена начална точка да се създаде „облак” от последователно направени успешни случайни направления с еднаква дължина на случайния вектор, след което направлението, в което функцията има най-добър резултат да се избере като базово. От базовото направление да се локализира екстремума, използвайки идеята на метода на случайното търсене с наказание за случайност до получаване на неуспешен резултат, но с променлива нарастваща стъпка. Последният най-добър резултат да се приеме като нова начална точка.
АЛГОРИТЪМ НА МЕТОДА
⦁ Задават се: брой управляващи параметри (n); целевата функция Q(Х), на която ще се търси максимум; критерия за спиране на търсенето по целева функция, ; границите на допустимата област Xi: Xmini и Xmaxi, i = 1,2,..,n; началните стойности и минималните стойности , i = 1, 2, …, n на управляващите параметри.
⦁ Изчисляват се помощните параметри: брой последователно успешни направления за избор на най-добро направление М1 = 2n + 4 при n ≤ 3 или М1 = 2n + 4 при n > 3 и брой на последователните неуспешни направления М2 = 2n, след което се намаляват началните стойности на параметрите на стъпката hi за всеки един от управляващите параметри (h0i , i = 1, 2, …, n).
⦁ Генерира се начална точка, по един от следните три начина:
⦁ Генериране на случайна начална точка по формулата:
, i = 1, 2, …, n; (1)
където е равномерно разпределено случайно число в границите [0, +1].
⦁ Използване на центъра на тежестта на допустимото пространство за начална точка: , i = 1, 2, …, n; (2)
⦁ Генериране на множество (облак) от Mn случайни точки, където Мn = 2n + 4, при , или Мn = 2n + 4, при n > 3. Изчислява се целевата функция Q(X) във всяка точка. За начална точка се избира точката с най-добър резултат за целевата функция и търсенето започва от нея.
⦁ Изчислява се целевата функция в началната точка: Q0 = Q(X0i), i = 1, 2, …, n;
⦁ Параметрите на стъпката се инициализират с началните им стойности: hi = h0i, i = 1, 2, …, n;
⦁ Генерира се облак от M1 успешни случайни направления по следния алгоритъм:
⦁ На идентификатора, отчитащ успешните случайни направления (J) се присвоява стойност 1: J = 1;
⦁ На идентификатора, отчитащ последователно неуспешните случайни направления (K) се присвоява стойност 0: К = 0;
⦁ Генерира се единичен случаен вектор ξ. От началната точка се прави стъпка в случайно направление, определенo от единичния случаен вектор ξ:
, (i = 1, 2, …, n) (3)
⦁ Изчислява се стойността на целевата функция . Ако Q1 > Q0, съхраняват се: данните за управляващите параметри, стойността на целевата функция и параметрите на случайния вектор: , , .
Идентификаторът J се увеличава с 1 ( ). Проверява се дали са генерирани M1 на брой успешни случайни направления. Ако са генерирани предварително изчисления брой успешни случайни направления алгоритъмът продължава от т. (6.11), в противен случай ( ако J < M1) от т. (6.2);
⦁ Ако случайното направление е неуспешно (Q1 ≤ Q0), прави се стъпка в обратна посока на същото направление (със същите стойности на случайния вектор);
, (i = 1, 2, …, n) (4)
⦁ Изчислява се стойността на целевата функция в тази точка: ;
⦁ Ако стъпката в обратна посока е успешна (Q1>Q0), се съхраняват данните за управляващите параметри, стойността на целевата функция и параметрите на случайния вектор: , , . Идентификаторът J се увеличава с 1 ( ). Проверява се дали са генерирани M1 на брой успешни случайни направления. Ако са генерирани предварително изчисления брой случайни направления алгоритъмът продължава от т. (6.11), в противен случай (ако J < M1) от т. (6.2);
⦁ Ако и обратната посока на случайното направление е неуспешна (Q1 ≤ Q0), идентификаторът, отчитащ последователно неуспешните направления К се увеличава с 1
( ).
⦁ Проверява се дали K ≥ М2. Ако условието е изпълнено, проверява се дали всички параметри на началните стойности на стъпките са достигнали минималната и стойност, т.е. условията (h0i ≤ hmini, i = 1, 2, …, n). Ако условието е изпълнено, алгоритъмът продължава от т. (6.10), в противен случай, началните стойности на тези параметрите на стъпката (h0i), за които е в сила h0i > hmini,
i = 1, 2, …, n се намаляват Kr пъти: ,
(Kr = 2, 3, и 4) за h0i > hmini, i = 1, 2, …, n.
На идентификатора, отчитащ успешните случайни направления (J) се присвоява стойност 1: J = 1. Алгоритъмът се продължава от т. (6.1);
⦁ Ако са генерирани една или повече точки, в които стойността за целевата функция е по-голяма от най-добрата намерена до момента, най-добрата точка се приема за екстремална и алгоритъмът се продължава от т.(14).
⦁ Когато всичките М1 успешни точки са генерирани, алгоритъмът се продължава от т.(7).
⦁ Избира се най-добият резултат от M1 успешни случайни направления, съхранява се информацията за управляващите параметри
( ), стойността на целевата функция ( ) и параметрите на случайния вектор ( ).
⦁ Параметрите на стъпката се увеличават два пъти
( );
⦁ Осъществява се стъпка в същото направление с увеличена стъпка:
; (5)
⦁ Изчислява се стойността на целевата функция в тази точка: ;
⦁ Ако стъпката е успешна, резултатът се приема за най-добри (Q(extr) = Q1 и , i = 1, 2, …, n). Алгоритъмът се продължава от т. (8);
⦁ Ако стъпката е неуспешна (Q1 ≤ Q(extr)), проверява се критерият за локализация на екстремума на целевата функция: .
⦁ Ако условието в т.(12) е изпълнено, алгоритъмът продължава от т. (14). В противен случай последната най-добра стъпка се приема за начална, т.е.
, i = 1, 2, …, n и Q0 = Q(extr).
Алгоритъмът се продължава от т.(6).
⦁ Отпечатват се резултатите за Xi(extr), i = 1, 2, …, n и Q(extr). Алгоритъмът се прекратява.
ИЗСЛЕДВАНЕ НА АЛГОРИТЪМА
За изследваните 3 класически алгоритми са приети следните означения:
СН – Метод на случайните направления;
СТОС 2 – Метод на случайно търсене с обратна стъпка;
СТНС 2 – Случайно търсене с „наказание на случайност“.
За разработените 3 нови алгоритми, с критерии за спиране само по минимална стойност на параметрите на стъпката, са приети следните означения:
НМСТ 1 – с кратност на намаляване на началната стойност на стъпката 2;
НМСТ 2 – с кратност на намаляване на началната стойност на стъпката 3;
НМСТ 3 – с кратност на намаляване на началната стойност на стъпката 4.
За алгоритмите НМСТ 1, 2 и 3, коефициент на увеличение на стъпката при успешна стъпка е 2.
СТОС 1 – Метод на случайно търсене с обратна стъпка.
СТНС 1 – Случайно търсене с „наказание на случайност“.
За алгоритмите СТОС 1 и СТНС 1, критерии на спиране на търсенето е достигане на М на брой последователни неуспешни направления, след последната най-добра стойност за целевата функция. Стойността за M се определя по емпирична формула.
За изследванe на ефективността на всички алгоритми са избрани илюстративни многомерни целеви функции с малка и голяма размерност, като за всички алгоритми, сходимостта към решението е изследвана със зададена желана абсолютна точност от 1.10-1 до 1.10-5 от областта на всеки един от управляващите параметри за локализиране на максимума на Q(х), като е отчетен броят на изчисленията S на целевите функции Q(х) за всяка точност в интервалите на неопределеност и всеки изследван алгоритъм.
За илюстрация на ефективността на предложените методи, в настоящата статия е представено изследване, направено от една и съща начална точка, генерирана по случаен начин по формула (1) и начална точка в центъра на тежестта на допустимото пространство (2) за целева функция
Q(x1, x2) → max (6)
Получените резултати от сравнителния анализ на класическите и предложените нови алгоритми за две области на управляващите параметри са дадени на фиг. 1 до фиг. 4.
* Изследвана област на управляващите параметри:
и
(1) Начална точка: x1 = 1984.3197 и x2 = 6292.7062;
(2) Начална точка (централна): x1 = 5800 и x2 = 5800
** Изследвана област на управляващите параметри:
и
⦁ Избор на случайна точка: x1 = -1115.3635 и
x2 = -1987.5623
⦁ Централна точка: x1 = -750,00 и x2 = -750, 00.
Фиг. 1. Брой изчисления и зададената точност за всеки метод при случайна начална точка
Фиг. 2. Брой изчисления и зададената точност за всеки метод при централна начална точка
Фиг. 3. Брой изчисления и зададената точност за всеки метод при случайна начална точка
Фиг. 4. Графична зависимост на броя изчисления и зададената точност за всеки метод
при централна начална точка
ЗАКЛЮЧЕНИЕ
От направеното изследване и получените резултати, представени на фиг. 1 до фиг. 4 се вижда, че предложеният нов алгоритъм, дава много по-бързо съкращаване на интервала на неопределеност в сравнение с останалите методи, базирани на случайното търсене. Това се изразява най – силно при голям интервал на неопределеност и при целеви функции с голям брой управляващи параметри.
ЛИТЕРАТУРА
1. С. Стоянов, Методи и алгоритми с ускорена сходимост при оптимизация на технологични обекти и системи, Дисертация за д-ртн, ХТМУ, София, 1990.
2. С. Стоянов, Методи и алгоритми за оптимизация“, Техника, София, 1990.
3. С. Стоянов, Оптимизация на технологични процеси, Техника, София, 1993.
4. L. A. Rastrigin, Methods and programs random searching, Riga, Zinatie, 1969.
5. L. A. Rastrigin, K. K. Ripa, G. S. Tarasenko, Adaptive random searching, Riga , Zinatie, 1978.
Leave a Reply