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

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

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

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

Комплексно проаналізовано стан царини практичного застосування сучасного еволюційного програмування, а також визначено світові тенденції і перспективи розвитку еволюційних технологій.

Проведено комплексний аналіз стану царини практичного застосування сучасних еволюційних алгоритмів, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій.

Описано розробку та реалізацію паралельного генетичного алгоритму (ГА) побудови розкладу ВНЗ на основі моделі "фермер-робітники" з елементами евристики для вибору аудиторій та пар під час ініціалізації, застосування нового (додаткового) оператора мутації, додання вдалих підрозв'язків в популяцію під час інціалізації початкової популяції. У алгоритмі введено специфічний спосіб кодування хромосоми, запропоновано функцію оцінки хромосоми з урахуванням низки обмежень, що накладаються на результуючий розклад-хромосому, а також розроблено спеціальні оператори кросинговеру та мутації. На основі експериментів запропоновано оптимальні значення параметрів ГА.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж69331 Пошук видання у каталогах НБУВ