Перспективні архітектури генетичного пошуку

В.В Курейчик

Останнім часом з'явилися нові «нестандартні» архітектури генетичного пошуку, що дозволяють в більшості випадків вирішувати проблему попередньою збіжності алгоритмів. Це методи міграції та штучної селекції [1], метагенетіческой параметричної оптимізації [2], стохастичних-ітераційні генетичні та пошукові [3],? переривчастого рівноваги? [4], об'єднання генетичного пошуку і моделювання відпалу [5]. В [1] на відміну від звичайних ГА виконується макроеволюція, тобто створюється не одна популяція, а деякий безліч популяцій. Генетичний пошук тут здійснюється шляхом об'єднання батьків з різних популяцій. На відміну від [1-5] пропонується модифікована архітектура генетичного пошуку з міграцією і штучною селекцією (рис.1.). Тут блоки 1 - 3 представляють собою простий або модифікований ГА. Відзначимо, що в кожному блоці виконується своя штучна селекція. У першому блоці селекція на основі рулетки. Під другому блоці використовується селекція на основі заданої шкали. У третьому блоці -- елітна селекція. До блоку міграції щоразу відправляється кращий представник з популяції. Зв'язок між блоками 1 - 3 здійснюється шляхом послідовної ланцюжка 1 - 2, 2 - 3.Отметім, що можна організувати різну кількість зв'язків між блоками, такого типу, як за принципом повного графа, за принципом зірки і т.д. Така схема селекції в випадку наявності великої кількості обчислювальних ресурсів може бути доведена до N блоків. Причому N-1 блоків можуть паралельно здійснювати еволюційну адаптацію і через блоки міграції обмінюватися кращими представниками рішень. Останній блок збирає кращі рішення, може закінчити результат роботи або продовжити генетичну оптимізацію. Така схема оптимізації на відміну від існуючих дозволяє під багатьох випадках виходити з локальних оптимумів. Для підвищення ефективності такої архітектури в САПР використовують метагенетіческую оптимізацію (МГО). Вона полягає в наступному (мал. 2). Основним є перший блок, в якому здійснюється реалізація генетичного алгоритму, генерація нових рішень, визначення моделюючої функції та використання попередніх рішень для створення кращих результатів. Другий блок дозволяє використовувати «історію» попередніх рішень для генерації кращого безлічі параметрів. У третьому блоці генерується нове безліч оптимізаційних параметрів. Використовуючи МГО оптимізаційний процес в САПР, можна випадковим, спрямованим або випадково-спрямованим способом генерувати початкові популяції, моделювати кожну індивідуальність за допомогою виконання ГА на основі реалізації генетичних операторів. Можна випадково вибирати батьків з популяції з вірогідністю селекції кожного елемента пропорційно його значенню. Причому, ймовірність виконання кожного оператора може визначатися пропорційно його