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

Анотація наукової статті з математики, автор наукової роботи - Афонін Павло Володимирович, Ламскова Ольга Юріївна


NEURAL NETWORK BASED SIMULATION OPTIMIZATION ALGORITHMS OF COMPLEX SYSTEMS

This paper is dedicated to the developing and researching of metamodel-assisted simulation optimization algorithms. The two global optimization algorithms based on neural network approximation metamodels are proposed. The results of the algorithms implementation for three standard test functions as well as for the bank system with several cash registers are presented.


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

  • Математика

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


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


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

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

    ?УДК 004. 421. 6

    П.В. Афонін, О.Ю. Ламскова АЛГОРИТМИ ОПТИМІЗАЦІЇ імітаційні моделі СКЛАДНИХ СИСТЕМ НА ОСНОВІ нейронних мереж *

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

    Складна система; імітаційна модель; оптимізація; апроксимація; нейронна мережа; метамодель.

    P.V. Afonin, O.Y. Lamskova

    NEURAL NETWORK BASED SIMULATION OPTIMIZATION ALGORITHMS

    OF COMPLEX SYSTEMS

    This paper is dedicated to the developing and researching of metamodel-assisted simulation optimization algorithms. The two global optimization algorithms based on neural network approximation metamodels are proposed. The results of the algorithms implementation for three standard test functions as well as for the bank system with several cash registers are presented.

    Complex system; simulation; optimization; approximation; neural network; metamodel.

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

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

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

    Відзначимо основні складнощі, що виникають при вирішенні завдань оптимізації на основі імітаційного моделювання:

    * Робота виконана за підтримки: РФФД (гранти № 08-07-00337, № 08-07-00343). 226

    1. Проблема багатовимірного простору пошуку (для багатьох складних систем число факторів велике).

    2. Проблема тривалості прогонів імітаційної моделі.

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

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

    Перевагами НС є [2]:

    1) хороша здатність апроксимації складних залежностей;

    2) простота вибору моделі.

    Існують два підходи до використання метамоделей в алгоритмах оптимізації на основі імітаційного моделювання [3]: статичний підхід (off-line learning) і динамічний підхід (on-line learning). Статичний підхід полягає в послідовному застосуванні ІМ, метамоделі і блоку оптимізації. Спочатку реалізують прогін ІМ в точках, які використовуються для побудови метамоделі. Далі до метамоделі застосовується алгоритм оптимізації. Потім рішення (точки в просторі пошуку), які отримані за допомогою алгоритму оптимізації, розраховуються на основі ІМ. У динамічному підході застосовують принцип перестроювання метамоделі в процесі оптимізації.

    Алгоритми оптимізації на основі імітаційного моделювання та нейромережевих метамоделей. Розглянемо базовий алгоритм глобального пошуку [4], який заснований на ідеї побудови локальних метамоделей в контексті статичного підходу.

    Базовий алгоритм на основі локальних метамоделей.

    1. Побудова глобальної метамоделі в заданій області пошуку.

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

    3. Побудова локальних метамоделей в областях локальних оптимумів.

    4. Оптимізація функції відгуку в локальних областях на основі оптимізаційного алгоритму і локальних метамоделей (окремо для кожної локальної області).

    5. Розрахунок отриманих рішень в локальних областях за допомогою імітаційної моделі.

    6. Вибір кращого рішення серед усіх локальних областей за результатами розрахунку за допомогою імітаційної моделі.

    У розвиток даного підходу розглянемо два алгоритму глобального пошуку [5], які в якості метамоделей використовують нейронні мережі на основі багатошарового персептрона.

    На рис. 1 представлена ​​ілюстрація до алгоритму визначення мінімальних значень функції відгуку по метамоделі (алгоритм 1). Нейронна мережа навчається на основі прогону заданого числа конфігурацій системи (точок в просторі пошуку). За допомогою метамоделі визначається безліч точок з наближеним значенням функції відгуку. З даного безлічі вибирається заданий число точок з мінімальним значенням функції, для яких реалізується прогін ІМ. На основі отриманих точних значень функції відгуку визначається точка з мінімальним значенням функції.

    Г (у)

    функція відгуку ІМ функція метамоделі

    Мал. 1. Визначення мінімальних значень функції по метамоделі (алгоритм 1)

    На рис. 2 представлена ​​ілюстрація до алгоритму виявлення локальних оп-тімумов по метамоделі (алгоритм 2), а на рис. 3 показана блок-схема алгоритму 2.

    рункція метамоделі

    Мал. 2. Виявлення локальних оптимумів по метамоделі (алгоритм 2)

    Мал. 3. Блок-схема алгоритму виявлення локальних оптимумів по метамоделі

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

    Результати досліджень алгоритмів на тестових функціях. Дослідження проводилися на трьох класичних тестових функціях: Ackley, Rastrigin і Rosenbrock в середовищі Майа 7.1. Побудова нейронних мереж здійснювалося за допомогою Toolbox Neural Network (середовищі Ма ^ аЬ 7.1).

    Розглянемо аналітичний вид тестових функцій.

    | Ackley function:

    f I 1 n 1 f

    f (x) = -20 • exp

    -0.2

    exp

    1 n 1

    -V cos (2 ^ x,) 1 + 20 + e; n ~~ t I

    | Rastrigin function:

    f (x) = 10 • n + V (100 • (x2 -10 • cos (2 ^ • xi)));

    i = 1

    | Rosenbrock function:

    f (x) = V (100 • (x "-x ') 2 + (x, -1) 2).

    i = 1

    Параметри алгоритмів і тестових функцій: число змінних (для всіх функцій) - 5; число точок для побудови метамоделей (навчання НС) - 500; область оптимізації (інтервали по всім змінним): [-1; 1] - для функції Rastrigin, [-3; 3] - для функції Ackley, [-2; 2] - для функції Розенброка; число точок по метамоделі для визначення областей локальних оптимумів: 59049 -для функцій Rastrigin і Ackley клі, 100000 - для функції Rosenbrock; спосіб розташування точок навчання - довільним чином в просторі пошуку (області оптимізації) тестової функції; параметри метамоделі (нейронної мережі): тришаровий персептрон з 15-ю нейронами в прихованому шарі.

    Для оцінки ефективності розроблених алгоритмів було проведено порівняння результатів з одним з найбільш поширених алгоритмів глобальної оптимізації - еволюційної стратегією (ЕС) [6]. Результати досліджень представлені в табл. 1.

    Таблиця 1

    Результати досліджень

    Тестова функція № точки по А1 № точки по А2 Число розрахунків ЦФ по А2 Число розрахунків ЦФ по ЕС Результат по ЕС

    Ackley 24 22 1084 1084 2 * 10-5

    Rastrigin 12 7 998 400 0.99

    Rosenbrock 2 2 897 1500 3.9 * 10-2

    Аналіз результатів показує, що обидва алгоритму знаходять глобальний мінімум для всіх тестових функцій на заданому інтервалі. Алгоритм 2 дозволяє скоротити число розрахунків цільової функції (ЦФ) приблизно в 1.5 рази по

    порівняно з алгоритмом 1. Для функцій Rastrigin і Ackley в деяких випадках алгоритм 2 знаходить точку глобального мінімуму швидше, ніж алгоритм 1, т. е. в масиві точок мінімумів для алгоритму 2 точка глобального мінімуму знаходиться ближче до початку масиву (№ точки по А2) , ніж в масиві для алгоритму 1 (№ точки по А1). Отже, алгоритм 2 є більш ефективним в порівнянні з алгоритмом 1.

    Для функції Ackley алгоритм 2 знаходить точне значення глобального мінімуму при 1084 розрахунках ЦФ. При цих же умовах (1084 розрахунків ЦФ) ЕС знаходить значення близьке до оптимального.

    Для функції Rastrigin збіжність ЕС відбувається при 400 розрахунках ЦФ, але глобальний мінімум знаходиться в середньому в одному з трьох експериментів. Алгоритм 1 і алгоритм 2 завжди знаходять глобальний мінімум на заданому інтервалі.

    Для функції Rosenbrock, щоб отримати значення функції, близьке до оптимального, ЕС необхідно 2000 ітерацій. Алгоритм 2 знаходить оптимальне значення в середньому за 89б розрахунків ЦФ.

    Апробація розроблених алгоритмів для системи банку з декількома касами. Розглянемо імітаційну модель системи банку з декількома касами (рис. 4). Є б кас, в яких можуть працювати фахівці 7-ми кваліфікацій. Банк спеціалізується на двох операціях: прийом платежів і операції по вкладах. Закон приходу клієнтів в банк - експонентний із середнім значенням t = 2 хв. по першій операції і t = З хв. по другій операції. Банк відкривається о 10:00 ранку і закривається в б вечора, однак каси продовжують працювати до тих пір, поки всі клієнти, що знаходилися в банку, не будуть обслужені.

    Мал. 4. Система банку з декількома касами

    До кожної касі формується окрема черга, що складається не більше ніж з 5-ти осіб; 6-ий клієнт в черзі змушений покинути приміщення. При цьому банк втрачає свій престиж. Прибулий клієнт приєднується до найбільш короткої черги по своїй операції. Можливий перехід клієнта з довгій черзі в коротку. Закон обслуговування клієнтів - нормальний з математичним сподівання-

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

    Таблиця 2

    Параметри імітаційної моделі

    Кваліфікація 1 операція 2 операція Зар. плата,

    спеціаліста (обслуговування) (обслуговування) у.о. / день

    д, хв о, хв д, хв о, хв

    1 5 0.2 700

    2 5.5 0.2 650

    3 6 0.2 9 0.5 800

    4 6.5 0.2 8.5 0.5 800

    5 7 0.2 8 0.5 800

    6 7.5 0.5 700

    7 7 0.5 750

    Для побудови метамоделі і проведення експериментів з ІМ було обрано такі параметри плану експерименту: загальне число точок плану: п = 117649; число точок навчання: а = 729; число перевірочних точок: Ь = 4096; число експериментів (імітаційних прогонів) в одній точці: ь = 5; спосіб розташування точок: рівномірний; число областей апроксимації: одна; тип НС: персептрон з одним прихованим шаром; функція активації: для прихованого шару - сігмоідной, для вихідного - лінійна; число входів мережі: 6 (відповідає числу кас в системі); число нейронів: в прихованому шарі - 10, в вихідному шарі - один; спосіб навчання НС: метод зворотного поширення помилки.

    В результаті рішення задачі оптимізації на основі алгоритму 1 і алгоритму 2 була знайдена однакова розсадження фахівців в каси (рис. 5), при якій витрати банку мінімальні. У разі застосування алгоритму 1 почали вимагати 1000 прогонів ІМ, а разі застосування алгоритму 2 - 320 прогонів ІМ. Таким чином, алгоритм 2 виявився ефективнішим.

    Можна бачити, що для мінімізації витрат банку необхідні 3 фахівця 2-ий кваліфікації і 3 фахівця 6-ий кваліфікації. При цьому мінімальні витрати банку становлять 4668 у.о. в день.

    6 6 2 2 2 6

    Каса 1 Каса 2 Каса 3 Каса 4 Каса 5 Каса 6

    Мал. 5. Результат оптимізації (конфігурація ІМ)

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

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Лоу А., Кельтон Д. Імітаційне моделювання: Пер. з англ. (3-тє вид.) - СПб .: BHV, 2004.

    2. Haykin S. Neural Networks - A Comprehensive Foundation. Prentice-Hall, 1994.

    3. Jin Y. A comprehensive survey of fitness approximation in evolutionary computation // Soft Computing. - 2005. - Vol. 1, № 9. - P. 3-12.

    4. Афонін П.В., Ламскова О.Ю. Алгоритм оптимізації на основі локальних нейромережі -вих метамоделей в реалізації для банківської системи // Зб. наукових праць наукової сесії МІФІ-2008. - М .: МІФІ, 2008. - Т. 3. - С. 122-123.

    5. Афонін П.В., Ламскова О.Ю. Алгоритми оптимізації на основі імітаційного моделювання та нейромережевих метамоделей // Праці Міжнародних науково-технічних конференцій «Інтелектуальні системи» (AIS'08) і «Інтелектуальні САПР (CAD'2008). - М .: Физматлит, 2008. - Т. 3. - С. 30-36.

    6. Hansen N., Ostermeier A. Completely derandomized self-adaptation in evolution strategies // Evolutionary Computation. - 2001. Vol. 2, № 9. - P. 159-196.

    Афонін Павло Володимирович

    Московський Державний Технічний Університет ім. Н.е. Баумана.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    105005, г. Москва, 2-я Бауманська вул., Буд.5.

    Кафедра комп'ютерних систем автоматизації виробництва, к.т.н..

    Afonin Pavel Vladimirovich

    Bauman Moscow State Technical University.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    7b, ap. 178, Muranovskaya Street, Moscow, Russia.

    Department of Computer-aided Manufacturing Systems, Cand.Tech.Sci.

    Ламскова Ольга Юріївна

    Московський Державний Технічний Університет ім. Н.е. Баумана.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    г. Москва, ул. Червоного Маяка, 15/4, кв. 60.

    Кафедра комп'ютерних систем автоматизації виробництва, здобувач.

    Lamskova Olga Yurievna

    Bauman Moscow State Technical University.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    15/4, ap. 60, Red Lighthouse Street, Moscow, Russia.

    Department of Computer-aided Manufacturing Systems; competitor.


    Ключові слова: Складні СИСТЕМА /ІМІТАЦІЙНА МОДЕЛЬ /ОПТИМІЗАЦІЯ /апроксимації /НЕЙРОННА МЕРЕЖА /метамоделі /COMPLEX SYSTEM /SIMULATION /OPTIMIZATION /APPROXIMATION /NEURAL NETWORK /METAMODEL

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

    Завантажити