3. Задача пошуку

Перший крок при вирішенні задачі пошуку полягає в тому, щоб визначитися щодо об’єктів цієї безлічі. Будемо називати цю безліч об’єктів простором об'єктів і позначимо його O. ПрикладомOможе служити простірn-мірних векторів дійсних чисел.

Другий крок, що повинний передувати процедурі пошуку заключається у виборі деякого представлення об’єктів із простору O. Представлення визначається безліччюS- простором представлень.Sвибирається з таким розрахунком, щоб алгоритм пошуку легше маніпулював членамиS, чимO.

На відміну від простору об'єктів, простір представлень обов’язково кінцевий. У реальних задачах у реальному часі замість Oприйнято розглядати його кінцеву підмножинуO'. Відображення між елементамиOіSбуде називати представленням. Представлення описує зв’язок між досліджуваними об’єктами, що виступають як потенційні рішення задачі пошуку, і об’єктами, керуванням і маніпулюванням яких займається пошуковий алгоритм. Представлення - це функція кодування

e: O -> S

Для oзOіsзSзаписs=e(o)буде позначати те, щоsє представленнямo. У загальному випадкуe(o)може описувати ціла безліч представлень, однак цей випадок нами не розглядається. Зворотне відношення будемо записувати якe^-1(функція декодування)

e^-1: S -> O.

Серед різних типів задач пошуку найбільший інтерес для нас представляє задача, в якій потрібно знайти кращий, на скільки це можливо при існуючих обмеженнях, об’єкт o*. При цьому на безлічі об’єктівOповинна бути визначена функція метиf(o), що дозволяє порівнювати рішення

f: O -> R

така, що для будь-яких двох o₁,o₂зO, якщоf(o₁)>f(o₂), тоo₁вважається рішенням краще, ніжo₂.R- безліч дійсних чисел. Тоді про оптимальність того чи іншого рішення можна говорити лише тоді, коли досліджений весь простір представлень S.

Для реалізації алгоритму пошуку в просторі представлень можна увести функцію оцінки представлень, аналогічно функції f, визначеної на елементах з безлічіO. Визначимо її як

m: S -> R

де R- безліч дійсних чисел.

За допомогою mможна визначити порядок уSтаким чином, щоб представникам кращих об’єктів у розумінніfвідповідало більше значенняm. Тобто якщо для будь-яких двох об’єктівo₁,o₂зOуSвизначені різними представникамиs₁=e(o₁)іs₂=e(o₂),s₁не дорівнюєs₂і якщоf(o₁)>f(o₂), тоm(s₁)>m(s₂). У загальному випадку функцієюm(s)може бути будь-яка функціяM, що задовольняє цій умові.

m(s) =M(f(e^-1(s)))

Однак, як правило, цілком достатньо зробити

m(s) =f(e^-1(s))

Представлені міркування дозволяють сформулювати задачу пошуку найкращого об’єкта o* з безлічіOу такий спосіб

o* = argmaxf(e^-1(s))

sзS

Її рішення здійснюється пошуком у просторі Sоптимального представленняs*:

s* = argmax m(s)

s з S

3.1 Постановка задачі

Розглядається загальна задача беззупинної оптимізації

max f(x), де D = {x= (x₁,x₂, ... ,x_N) |x_iна [a_i,b_i],i=1, 2,:N}

x з D

f(x) - цільова скалярна багатопараметрична функція, що може мати декілька глобальних екстремумів, прямокутна область D - область пошуку, D - підмножина R^N.

Передбачається, що про функцію f(x) відомо лише те, що вона визначена в будь-якій точці областіD. Ніяка додаткова інформація про характер функції і її властивості не враховується в процесі пошуку.

Під рішенням задачі будемо розуміти вектор x= (x₁,x₂, ... ,x_N).

Оптимальним рішенням задачі (1) будемо вважати вектор x*, при якому цільова функціяf(x) приймає максимальне значення. Виходячи з припущення про можливий багатоекстрімальністьf(x), оптимальне рішення може бути не єдиним.

У прийнятих раніше позначеннях під об'єктом будемо розуміти точкуxу багатопараметричному просторіO=DуR^N. Роль функції цілі буде грати максимізуємо функціяf(x).