визначається цільовою функцією: чим менше значення цільової функції, тим більш пристосованою є особина, тобто пробне рішення, що використовувалося як аргумент цільової функції.
Тепер приступимо до процесу розмноження: спробуємо на основі вихідної популяції створити нову, так щоб пробні рішення в новій популяції були б ближче до шуканого глобального мінімуму цільової функції. Для цього сформуємо з вихідної популяції шлюбні пари для схрещування. Поставимо у відповідність кожній особини вихідної популяції випадкове ціле число з діапазону від 1 до 4. Будемо розглядати ці числа як номери членів популяції. При такому виборі якісь з членів популяції не братимуть участь у процесі розмноження, так як утворюють пару самі з собою. Якісь члени популяції візьмуть участь у процесі розмноження неодноразово з різними особинами популяції. Процес розмноження (рекомбінація) полягає в обміні ділянками хромосом між батьками. Наприклад, нехай схрещуються дві хромосоми 111111 і 000000. Визначаємо випадковим чином крапку розриву хромосоми, нехай, це буде 3: 111 | 111000 | 000. Тепер хромосоми обмінюються частинами, що стоять після точки розриву, і утворюють двох нових нащадків: 111000 і 000111.
Наступним кроком у роботі генетичного алгоритму є мутації, тобто випадкові зміни отриманих в результаті схрещування хромосом. Нехай імовірність мутації дорівнює 0,3. Для кожного нащадка візьмемо випадкове число на відрізку [0; 1], і якщо це число менше 0,3, то інвертуємо випадково обраний ген (замінимо 0 на 1 або навпаки).
Як видно на прикладі, мутації здатні поліпшити (перший нащадок) або погіршити (четвертий нащадок) пристосованість особини-нащадка. В результаті схрещування хромосоми обмінюються «хвостами», тобто молодшими розрядами в двійковому представленні числа. У результаті мутацій зміни може піддатися будь розряд, в тому числі, старший. Таким чином, якщо схрещування призводить до відносно невеликим змінам пробних рішень, то мутації можуть призвести до суттєвих змін значень пробних рішень.
Тепер з чотирьох особин-батьків і чотирьох отриманих особин нащадків необхідно сформувати нову популяцію. У нову популяцію відберемо чотири найбільш пристосованих особин з числа «старих» особин і особин-нащадків.
У результаті одержимо нове покоління. Отриману популяцію можна буде знову піддати кросинговеру, мутації та відбору особин в нове покоління. Таким чином, через кілька поколінь ми отримаємо популяцію зі схожих і найбільш пристосованих особин. Значення пристосованості найбільш «хорошою» особини (або середня пристосованість по популяції) і буде рішенням нашої задачі. Слідуючи цьому, в даному випадку, взявши найбільш пристосовану особину 001 у другому поколінні, можна сказати, що мінімумом цільової функції є значення? 5,42, відповідне аргументу x=1. Тим самим попадання в локальний мінімум вдалося уникнути! На даному прикладі розібраний варіант простого генетичного алгоритму. При подальшому використання ГА до різним завданням можливо моделювання основних операторів алгоритму.
.2 Поняття мінімізації функції багатьох змінних
Градієнтом диференціюється f (x) в точці х [0] називається n-мірний вектор f (x [0]), компоненти якого є приватними похідними функції f (х), обчисленими в точці х [ 0], тобто f '(x [0])=(Дf (х [0])/дх 1, ..., Дf (х [0])/дх n) T.
Цей вектор перпендикулярний до площини, проведеної через точку х [0], і дотичної до поверхні рівня функції f (x), що проходить через точку х [0] .В кожній точці такої поверхні функція f (x ) приймає однакове значення. Прирівнюючи функцію різним постійним величинам З 0, С 1, ..., отримаємо серію поверхонь, що характеризують її топологію.
Вектор-градієнт спрямований убік найшвидшого зростання функції в даній точці. Вектор, протилежний градієнту (-f (х [0])), називається антіградіентом і спрямований у бік найшвидшого спадання функції. У точці мінімуму градієнт функції дорівнює нулю. На властивостях градієнта засновані методи першого порядку, звані також градієнтним і методами мінімізації. Використання цих методів в загальному випадку дозволяє визначити точку локального мінімуму функції.
Очевидно, що якщо немає додаткової інформації, то з початкової точки х [0] розумно перейти в точку х, лежачу в напрямку антіградіента - найшвидшого спадання функції. Вибираючи в якості напрямку спуску р [k] антіградіентом - f (х [k]) в точці х [k], отримуємо ітераційний процес виду х [k + 1]=x [k] - akf '(x [k]), а k gt; 0; k=0, 1, ...
У координатної формі цей процес записується таким чином:
xi [k + 1]=х i [k] - akf (x [k])/xi; i=1, ..., n; k=0, 1, 2, ...
В якості критерію зупину ітераційного процесу використ...
