Область наук:

  • Математика

  • Рік видавництва: 2001


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритми еволюційного моделювання з динамічними операторами'

    Текст наукової роботи на тему «Алгоритми еволюційного моделювання з динамічними операторами»

    ?тримає рівно S одиниць; тобто у всій матриці буде рівно SN одиниць. Це і є .

    Результатом одного циклу аналізу всіх 3-х алгоритмів є значення ширини стрічки матриці (або значення критерію К), обирається як оцінка гіршого з кращих варіантів для серії генеруються випадковим чином матриць (ук ^ анного вище типу) з фіксованими значеннями S і N. Наприклад , задається S = 3, N = 10 і випадковим чином генерується М = 100 матриць, в кожному рядку якої рівно по 3 одиниці. Потім кожна з М матриць піддається обробці з

    (*) -

    (**). 3 . -

    (* **). -фектівность алгоритму 3 в порівнянні з 1 і 2. На жаль, поширення описаної методики на випадок N>>30 сильно утруднено через істотно нелінійного подовження часу отримання результату чергового циклу і зниження його достовірності через неминуче через це зменшення значення M (числа випадковим чином генеруються матриць).

    Однак загальна тенденція все ж піддається екстраполяції. Вона видно з графіка на рис.5. (Тут оцінюється тільки Алгоритм 3).

    1. Тьюарсон Д. Розріджені матриці. М .: Мир, 1975.

    2. Кодачігов В.К, Бондарєв Л.І. Мінімальні матриці і деякі їх застосування, ст. «Автоматизація проектування, програмування і конструювання». Таганрог: Изд-во ТРТІ, 1982.

    3. Курейчик В.М. Генетичні алгоритми, Таганрог: Изд-во ТРТУ, 1998..

    УДК 681.32

    В.М. Курейчик, Л.А. Зінченко, І.В. Хабарова1

    АЛГОРИТМИ ЕВОЛЮЦІЙНОГО МОДЕЛЮВАННЯ з динамічним ОПЕРАТОРАМИ

    Однією з тенденцій розвитку еволюційного моделювання є пере-

    [1,2].

    підходу пояснюється тим, що в природі відсутні жорсткі зв'язку. можливість

    1 Робота виконана за підтримки РФФД, гранти №99-01-0050, 00-01-00125).

    До

    N

    рис.5

    ЛІТЕРАТУРА

    динамічної зміни правил репродукції, селекції і редукції дозволяє популяції адаптуватися до змін навколишнього середовища.

    Аналогії з процесами, що відбуваються в живій природі, можуть бути використовувані або чинені алгоритмами еволюційного пошуку. Їх ефективність залежить від безлічі факторів. Оптимальний вибір параметрів призводить до підвищення швидкості і стійкості пошуку. Швидкість еволюційного пошуку ,

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

    В даний час розробляються різні методи, що дозволяють підвищити ефективність еволюційного пошуку. Основним способом підвищення швидкості роботи стаціонарних генетичних алгоритмів є розпаралелювання [1]. -,

    моделі з динамічно змінюється структурою в залежності від розв'язуваної задачі. В поколінь генетичних алгоритмах розмір популяції може змінюватися в [1]. ІБК при незначному зниженні швидкості.

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

    Для вирішення цього завдання можуть бути використані алгоритми еволюційного моделювання з динамічними операторами редукції і селекції. Управління полягає у виборі певного оператора редукції «ішніх» хромосом і відбору елементів для репродукції.

    Відомо [1,2] кілька евристичних методів видалення:

    1.;

    2., ();

    3. [1];

    4. видалення хромосом на основі заданої турнірної стратегії.

    Однак форсоване видалення гірших хромосом призводить до втрати різноманітності генетичного матеріалу, і як наслідок, до явища передчасної .

    функцією призводить до збільшення числа неефективних рішень.

    У більшості алгоритмів еволюційного моделювання використовується процедура випадкового вибору параметрів для оператора кросинговеру. Використання евристичних правил дозволяє підняти ефективність пошуку.

    Механізм витіснення (crowding factor) [3] полягає у видаленні схожих індивідів. Механізм поділу (sharing) [4] вводить залежність цільової функції хромосоми від розподілу елементів в пошуковому просторі, що дозволяє

    . (Tagging)

    застосування операторів репродукції.

    У даній роботі розглядаються динамічні оператори редукції і се, ,

    .

    Рішення завдання розглядається для алгоритмів еволюційного моделювання з динамікою [2]. При цьому підході розмір популяції визначається користувачем шляхом завдання керуючих параметрів:

    P (n + 1) = P (n) * (1 + R (n + 1)) - D (n + 1),

    де P (n + 1), P (n) -р ^ заходів нової та вихідної популяції відповідно;

    R (n + 1) - рівень репродукції на (п + 1) -му кроці, задається користувачем; D (n + 1) - число видаляються елементів батьків і нащадків на (n + 1) -му кроці, .

    Час життя елементів популяції є змінним і визначається наступною формулою [2]:

    LTi = MinLT (n + 1) + s (n + 1) (fitness (Ct) - FitMin) / (FitMax-FitMin), (1)

    де MinLT (n + 1) - мінімальний час життя на (п + 1) -му кроці; s (n + 1) - константа, більше або дорівнює нулю; fitness (C) - цільова функція i-ro елемента популяції;

    FitMin, FitMax -

    .

    Порівняння може виконуватися для двох популяцій (між батьками і по). Його величина може бути обрано рівної як розміром популяції, так і менше або більше цієї величини. При фіксованому розмірі популяції видаляються елементи з найменшим часом життя. При довільному розмірі популяції,. дозволяє управляти процесом селекції і редукції при завданні різних параметрів MinLT (n + 1), s (n + 1) і розміру архіву.

    Для оптимізації чисельності популяції можуть бути використані методи управління чисельністю популяції, які використовуються в біології [5]. На їх основі можуть бути запропоновані наступні механізми управління:

    1.

    (Рис.1, а) .І тут користувач задає параметр репродукції R (n + 1). Управління полягає у видаленні елементів популяції відповідно до закону

    D (n +1) = trunc

    2 * Т

    R (n +1) * (1 -----------) * P (n)

    до

    де до - розмір пошукового простору,

    L - ,

    Р (п) - розмір популяції (Р (п) Е [Ь, 2 * Ь]).

    вдчал;

    Введення установок управління Я (1),

    Щ). рт

    X

    формування початкової

    ПОПУЛЯЦІЇ

    -год

    Зміна ПУ Я (п + 1), В (п + 1), Р (п + 1)

    Обчислення цільової функції

    ранжування

    Застосування ОК, ОМ Отримання розширеної

    ПОПУЛЯЦІЇ

    З

    з

    ?

    Введення параметра управління т

    7

    Застосування ОК, ОМ Отримання розширеної

    ПОПУЛЯЦІЇ

    Застосування ОК, ОМ до особин, досгмхітд Т разм

    Обчислення розміру нової популяції

    Формування наступної популяції

    Збільшення лічильника кроків ____________ п = п + 1 ____________

    З

    3

    початок

    п = 0

    кінець

    кінець

    а ь з

    Рис.1. Блок-схеми генетичного алгоритму: а - з логістичною моделлю, Ь - з логістичною моделлю з наслідком, з - з урізанням після заданого кроку

    2. -

    наслідком (ріс.1,6) відрізняється введенням часу післядії. Число видаляються елементів визначається наступним співвідношенням:

    D (n +1) = trunc

    R (n +1) * (1 - P (n) * (L h)) * P (n) до

    де h - час від моменту народження до моменту схрещування особини, що задається наступним співвідношенням:

    h = max [LT (n)] * k, к = 0,2 + 0,3.

    Тртм = TPoMu + h - номер генерації (покоління), в якій індивід обраний для

    ,

    Чіпай - номер генерації, в якій індивід з'явився в популяції.

    У зв'язку з тим, що оптимальний розмір популяції визначається наступним

    співвідношенням: P (n) E [L, 2 * L], узагальненням запропонованих алгоритмів є

    (.1,). ,

    кратному m, відбувається усічення популяції до вихідного розміру P (1), при цьому видаляються всі елементи, які мають мінімальний час життя.

    Запропоновані алгоритми використовують аналогії з процесами, що відбуваються в живій природі. Кожному індивіду відповідає індивідуальний час життя, яке визначається його ступенем придатності. До етапу репродукції допускаються елементи з більш високою цільовою функцією, які прожили кілька етапів.

    Відповідно до [1] , -

    , :

    П_і = [L - ВД + 1]. P (n) 3 = c * P (n) 3,

    де L (s) <(1 - Pk (s)) (L-1) +1 - певна довжина схеми;

    Pk (s) - ймовірність виживання після оператора кросинговеру.

    Для розглянутих алгоритмів число схем буде визначатися наступними:

    -

    n1 [s] = c * [P (n -1) * (1 + R (n)) - D (n)] 3;

    -

    2 * T

    n2 [s] = c * (P (n -1) * (1 + R (n)) - trun [R (n) * (1 ------) * P (n -1)]) 3 ;

    до

    -

    n3 [s] = c * (P (n -1) * (1 + R (n)) - trun [R (n) * (1 - P (n-1) * (L - h)) * P ( n-1)]) 3

    до

    -

    ф]

    n2 [s], при min [LT]) h; n3 [s], при min [LT] < h і s Ф m * k; c * (P (1)) 3, при s = m * k, k = 1,2,3,...

    Запропоновані алгоритми відрізняються від відомих в літературі введенням періоду між народженням і можливістю дати потомство. Це дозволяє відібрати для оператора репродукції елементи, які прожили кілька генерацій за рахунок більш високої цільової функції.

    ЛІТЕРАТУРА

    1. Курейчик В.М. Генетичні алгоритми. Таганрог: ТРТУ, 1998. 242 с.

    2. Курі йчік В.М., Зінченко Л.А. Еволюційний моделирован ие з динамічною зміною параметрів // Праці VII національної конференції по штучному інтелекту. М .: Физматлит, 2000. C.516-523.

    3. Chambers. Practical Handbook of Genetic Algorithms. Editor I. Washington, USA, CRC Press, 1999..

    4. Goldberg D. E., Richardson J. J. Genetic algorithms with sharing for multimodal function optimization. Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms, 1987. 41-49.

    5.. . . // . .

    і системи управління, 1995. № 2. C. 181-182.

    УДК 681.3.001.63

    В. Б. Лебедев1

    ПЛАНУВАННЯ НВІС НА ОСНОВІ багаторівневий ЕВОЛЮЦІЇ

    1. Постановка заду чи планування. Планування НВІС полягає в розміщенні на поле кристала модулів, що мають задану площу та не мають фіксованих розмірів [1]. Модулі і кристал мають форму прямокутників. В результаті планування вирішуються відразу два завдання: визначається взаємне розташування модулів один щодо одного, тобто їх розміщення, і фіксуються розміри кожного модуля.

    Проблема планування формулюється так [2].

    Є безліч модулів М = {так, | / '= 1,2, ..., п}. Кожен модуль характеризується трійкою <5 "4 /,>, де - площа модуля, а параметри ^ та задають нижню і верхню межу значення

    До До

    , ті. і < < і, (1)

    wi wi

    де К - це висота модуля; wi - ширина модуля; si = До wi .

    Як плану кристала будемо використовувати план, який отримують шляхом рекурсивного використання «гільйотини розрізу», тобто послідовного розрізання прямокутників на дві частини. Кожна область ^ має розміри і у { .

    ,

    Si Уi, Wi <, hi<Уi. (2)

    1 Робота виконана за підтримки РФФД, грант №99-01-00050


    Завантажити оригінал статті:

    Завантажити