Posibniki.com.ua Інформатика Прикладні системи штучного інтелекту Тема 17. ЕВОЛЮЦІЙНІ ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ ТА МОДЕЛІ


< Попередня  Змiст  Наступна >

Тема 17. ЕВОЛЮЦІЙНІ ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ ТА МОДЕЛІ


ЕВОЛЮЦІЯ БІОЛОГІЧНИХ ІНФОРМАЦІЙНИХ СИСТЕМ

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

ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК

Після опанування теми студент має знати:

• принципи еволюції;

• світові наукові школи еволюційного моделювання;

• основні еволюційні алгоритми;

• особливості еволюційних алгоритмів;

• основні поняття, принципи і передумови генетичних алгоритмів;

• різновиди мутацій;

• переваги та недоліки генетичних алгоритмів.

Має вміти:

• аналізувати галузі досліджень еволюційної кібернетики;

• розрізняти генетичні методи від еволюційного програмування;

• виділити етапи генетичного алгоритму;

• характеризувати генетичні оператори відбору, схрещування і мутації.

ЗМІСТ ПИТАНЬ З ТЕМИ

17.1. Еволюційні моделі (ЕМ) та стратегії штучного життя

У 60-ті роки Інго Рехенберг (I. Rechenberg), якого надихнув метод «органічної еволюції», висунув ідею розв’язання оптимізаційних проблем в аеродинаміці, застосовуючи мутації до вектора дійсних параметрів. Ця процедура стала відома під назвою ево-

Розділ 6

Приблизно в той самий час у США незалежно виконувалися дослідження Лоуренсом Фогелем (Lawrence Fogel) еволюції штучного інтелектуального автомату з кінцевим числом станів, використовуючи метод, названий еволюційним програмуванням (Evolutionary Programming).

Джон Холланд (John Holland) аналізував клас репродуктивних систем методом (Genetic Algorithms).

Джон Коза (John Koza) запропонував метод, який назвали генетичним програмуванням (Genetic Programming). Існує кілька варіантів класифікації класичних методів, використовуваних для прийняття рішень. Значну їх частину становлять методи оптимізації, які використовуються для розв’язання задач лінійного, нелінійного, цілочисельного, опуклого, динамічного стохастичного, геометричного програмування та ін., а є ще теорія ігор тощо.

ЕМ відрізняються одна від одної, але всі вони базуються на принципах еволюції:

1. Особини мають кінцевий час життя.

2. Розмноження необхідне для продовження роду.

3. Нащадки деякою мірою відрізняються від батьків.

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

5. За допомогою природної селекції краще адаптовані особини мають тенденцію до тривалішого життя і відтворення більшої кількості нащадків.

6. Нащадкам властиво успадковувати корисні характеристики своїх батьків, що сприяє збільшенню пристосованості особин у часі.

17.2. Світові наукові школи еволюційного моделювання

Відомою світовою школою, що представляє новий напрям в еволюційному моделюванні, є школа Dr. Candida Ferreira у Великобританії (www.gene-expression-programming.com). Основний напрям досліджень зосереджений у програмуванні генети-

люційної стратегії (Evolution Strategies). У 1981 році Швефель (H. Schwefel) під час дослідження гідродинамічних задач увів рекомбінації в ПСШІ, виконав порівняльний аналіз з класичними методами оптимізації.

Найвідомішою школою, в якій досліджують (ТА), еволюційні стратегії, генетичне програмування і еволюційне програмування, є лабораторія еволюційних обчислень Департаменту комп’ютерних наук в університеті Джорджа Мейсона в США (http://www. cs.gmu.edu). Зараз керівництво школою здійснює учень Джона Холланда Dr. K. De Jong.

Загальні моделі еволюції розроблялися порівняно давно. У 1910—1930-х роках класичними роботами Р. Фішера (R. A. Fisher), Дж. Холдейна (J. B. S. Haldane), і С. Райта (S. Wright) були закладені основи генетики, популяції. Класична теоретична генетика популяції була заснована на синтетичній теорії еволюції, тобто на синтезі Дарвінівської концепції природного відбору і Медельовської дискретної генетики. Згідно із синтетичною теорією еволюції головний механізм прогресивного розвитку — природний відбір тих організмів, які змогли отримати вигідні мутації.

Еволюційні інтелектуальні системи — це науковий напрям, що тільки формується та активно розвивається. Схему розвитку еволюційних інтелектуальних систем подано на рис. 6.1.

Рухаючись у цьому напрямі, незалежно різними ученими були запропоновані парадигми, що базуються на ідеях і принципах природної еволюції за Ч. Дарвіном. До них відносять методи еволюційного моделювання (ЕМ), названі ще еволюційними алгоритмами (ЕА).

Галузь, що вже достатньо відбулася, — еволюційне моделювання (рис. 6.1), в якому можна виділити: 1) моделі виникнення молекулярно-генетичних інформаційних систем, 2) моделювання загальних закономірностей еволюції, 3) еволюційні моделі штучного життя, 4) прикладне еволюційне моделювання (ПЕМ), або еволюційні алгоритми.

Рис. 6.1. Галузі досліджень еволюційних інтелектуальних систем ПСШІ .

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

Рис. 6.1. Галузі досліджень еволюційних інтелектуальних систем ПСШІ .

17.3. Еволюційні алгоритми

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

У кількох модифікаціях подібні ідеї виникали у авторів. У 1966 році Л. Фогель (L. J. Fogel), А. Оуєнс (A. J. Owens), М. Уолш (M. J. Walsh) запропонували схему еволюції логічних автоматів, які вирішували завдання прогнозу. Дослідження з прикладного ЕМ, ідейно близькі до робіт Л. Фогеля із співробітниками, були різносторонньо розвинені в роботах І. Л. Букатової. У 1975 р. вийшла основоположна книга Дж. Холланда (J. H. Holland) «Адаптація в природних і штучних системах», в якій був запропонований генетичний алгоритм, досліджений надалі учнями і колегами Дж. Холланда у Мічіганскому університеті. Приблизно в цей же час група німецьких учених (І. Рехенберг (I. Rechenberg), Г.-П. Швефель (G.-P. Schwefel) та ін.) почала розроблення так званої еволюційної стратегії. Ці роботи заклали основи прикладного еволюційного моделювання або еволюційних алгоритмів (ЕА).

У загальному вигляді ЕА — це оптимізаційний метод, що базується на еволюції популяції «особин». Кожна особина характеризується пристосованістю f(S) — багатовимірною функцією її «генів» S = (S

1 , S

2 ,...,S N ). Завдання оптимізації полягає в максимізації функції пристосованості f(S). У процесі еволюції в результаті відбору, рекомбінацій і мутацій геномів особин відбувається пошук особин з високими пристосуваннями.

Основні ЕА:

1) генетичний алгоритм (ГА), призначений для оптимізації функцій дискретних змінних і акцентує увагу на рекомбінаціях геномів;

2) еволюційне програмування (ЕП), орієнтоване на оптимізацію безперервних функцій без використання рекомбінацій;

3) еволюційна стратегія (ЕС), орієнтована на оптимізацію безперервних функцій з використанням рекомбінацій;

4) генетичне програмування (ГП), що використовує еволюційний метод для оптимізації комп’ютерних програм.

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

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

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

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

Порівняно зі звичайними оптимізаційними методами еволюційні алгоритми (ЕА) мають такі особливості: паралельний пошук, випадкові мутації і рекомбінації вже знайдених прийнятних

Еволюційне програмування орієнтоване на оптимізацію неперервних функцій без використання оператора схрещування. Інший напрям ЕП пов’язаний з пошуком залежності цільових параметрів від інших змінних у формі функцій якогось певного вигляду. Наприклад, в одному з найбільш вдалих методів цього типу — методі групового врахування аргументів — залежність шукають у формі поліномів.

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

Еволюційне програмування у вигляді еволюції логічних автоматів, що розв’язує задачі прогнозування, діагностики, розпізнавання та класифікації образів, а також задачі керування об’єктом з невідомим характером, було запропоновано Л. Фогелем, А. Оуенсом і М. Уолшем.

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

Еволюційна програма реалізує моделювання процесів природної еволюції моделей-автоматів, причому в кожний момент часу зберігається особина, яка найкращим чином може упоратися з даною задачею. Батьківський організм оцінюється залежно від здатності приймати необхідне рішення на основі наявних даних. Цей організм піддається мутації і породжує нащадка, якому ставиться та сама задача і який оцінюється так само. Автомат, який демонструє найкращу здатність виконувати необхідні функції, зберігається і породжує нащадків, які переходять у наступне покоління. Процес завершується, коли одержано достатньо пристойну програму або вичерпані ресурси часу. Щоразу, коли надходить нова інформація, відбувається еволюційний пошук

рішень. Вони добре підходять як простий евристичний метод оптимізації багатовимірних, погано визначених функцій. Формуються навіть цілі області застосування ЕА. Наприклад, кілька років тому з’явився термін «Еволюційна роботика», котрий відображає можливості формування нейронної мережі робота, що управляє природним еволюційним шляхом.

17.4. Етапи еволюційного програмування

Узагальнена послідовність виконання ЕП включає такі кроки.

Крок 1. Виконати ініціалізацію параметрів методу.

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

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

Крок 3. Виконати тестування особин початкової популяції шляхом розв’язання поставленого завдання (на вхід моделі подається задана вибірка даних) і оцінювання отриманих результатів на основі обраної fitness-function.

Крок 4. Відібрати рішення з кращими значеннями fitness-function.

Крок 5. На основі випадкового застосування оператора мутації до особин-батьків згенерувати нащадків, які перейдуть у нову популяцію.

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

Крок 7. Відібрати найбільш перспективних нащадків.

Крок 8. Перевірити умови закінчення процесу еволюції, якими можуть бути: досягнення оптимального значення fitness-function або досягнення граничних значень, що обмежують тривалість процесу. Якщо умови закінчення пошуку задоволено, тоді виконати перехід до кроку 9, в іншому випадку виконати повернення до кроку 5, де особини останньої згенерованої популяції виступають як батьки.

Крок 9. Зупинення.

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

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

Викладене вище демонструє один із методів досліджень еволюційної кібернетики — метод математичного і комп’ютерного моделювання.

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

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

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

ГА й інші формальні еволюційні аналоги обумовлюють найбільш точне розв’язання задачі за рахунок операції над популяціями кандидатів на роль рішення.

Вирішення завдань за допомогою ГА включає три стадії.

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

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

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

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

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

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

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

17.5. Моделі виникнення молекулярно-генетичних кібернетичних систем

Як виникли перші кібернетичні системи, найпростіші молекулярно-генетичні інформаційні системи в процесі походження життя? У 60—80 роки ХХ ст. подібні проблеми заінтригували багато учених. Ціла плеяда Нобелівських лауреатів (Ф. Крік (F. H. C. Crick), М. Ейген (M. Eigen), Ф. Дайсон (F. J. Dyson), Ф. Андерсон (P. W. Anderson)) спробували представити і промоделювати сценарії виникнення передбіологічних інформаційних систем.

Чому ж виник такий інтерес до проблеми виникнення молекулярно-генетичних кібернетичних систем?

У 50—60-х роках у молекулярній біології було зроблено низку приголомшливих відкриттів:

1) розшифровано хімічну структуру ДНК (Уотсон і Крік, 1953) і стали відомі основні принципи кодування генетичної інформації;

2) стали відомі основні принципи функціонування молекулярно-генетичних систем живих клітин, що самовідтворюються;

3) розшифровано генетичний код.

Ці відкриття зробили революцію в науках про життя. Особливо вражає своєю «продуманістю» схема функціонування молекулярно-генетичних систем, що самовідтворюються (рис. 6.2).

Рис. 6.2. Схема молекулярно-генетичної системи живої клітини, що самовідтворюється

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

Рис. 6.2. Схема молекулярно-генетичної системи живої клітини, що самовідтворюється

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

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

Але які могли бути механізми виникнення такої схеми в процесі походження життя? Фактично спробам осмислити це питан-

, Д, , Ц,

У моделі квазівидів аналізується еволюція популяції послідовностей символів (інформаційних аналогів ланцюжків ДНК або РНК). Послідовності володіють певними селективними цінностями. У процесі еволюції відбуваються відбір послідовностей відповідно до їх селективних цінностей і мутації — випадкові заміни символів у послідовностях.

Математична генетика популяції на базі синтетичної теорії еволюції інтенсивно розвивалася до 60-х років ХХ ст., коли виникли певні труднощі, пов’язані з експериментальними досягненнями молекулярної генетики (оцінки швидкості еволюційної заміни амінокислот у білках і поліморфізму білків). Щоб проінтерпретувати експериментальні результати, М. Кімура запропонував так звану теорію нейтральної еволюції. Основне припущення теорії М. Кімури: мутації на молекулярному рівні (заміни нуклеотидів у ДНК і амінокислот у білках) переважно нейтральні, або слабо невигідні. Використовуючи математичні методи генетики, популяції, М. Кімура вивів низку наслідків теорії нейтральності, які перебувають у досить тісній прив’язаності з експериментальними даними. Образно кажучи, теорія нейтральності — це генетика, популяції, на базі досягнень молекулярної біології.

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

ня були присвячені дослідження М. Ейгена і Ф. Кріка зі співробітниками. Ф. Крік зі співробітниками ретельно досліджував можливі біомолекулярні механізми походження генетичного коду. М. Ейген пішов шляхом побудови математичних моделей, які ілюструють (але далеко не відтворюють) можливі процеси походження простих молекулярно-генетичних систем, що самовідтворюються. І на цьому шляху М. Ейген провів вражаючі дослідження. Він, зокрема, запропонував і проаналізував модель «квазівидів», що описує досить просту еволюцію полінуклеотидних (інформаційних) послідовностей, і модель «гіперциклів», що описує систему каталітично взаємодіючих ферментів і полінуклеотидів. Дуже цікава модель — модель «сайзерів» (syser від System of self-reproduction), була запропонована новосибірськими вченими В. А. Ратнером і В. В. Шаміним.

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

Сама назва методу підкреслює аналогію цього методу з процесом еволюції та природного відбору в природі. Спочатку мета досліджень, розпочатих у Мічіганському університеті Джоном Холландом (Holland, 1975), формулювалася як, по-перше, чітке пояснення процесів пристосовності, що мають місце в природі, і, по-друге, створення ПСШІ, які моделюють основні принципи функціонування природних систем.

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

Секрети адаптації і виживання краще вивчати на біологічних прикладах. Творцям ПСШІ (як устаткування, так і програмного забезпечення для нього) залишається тільки захоплюватися стійкістю, гнучкістю і ефективністю біологічних систем. Такі властиві біологічним системам функції, як відтворення, самовідновлення, самокерованість є умовою їх існування, але такі функції або повністю відсутні, або мають місце в зародкових формах навіть у найскладніших штучних системах. Створена в кінці 80-х років ХХ ст. парадигма ГА певною мірою дозволяє підвищити адаптованість штучних систем.

лекулярно-генетичної системи управління живої клітини, при цьому кожен логічний елемент інтерпретується як регулятор синтезу певного ферменту. Примітно, що в дослідженні автоматів Кауффмана застосовуються високоефективні математичні методи статистичної фізики. Моделі Кауффмана дозволяють зробити низку прогнозів щодо «програм» життєдіяльності клітин. Зокрема, продемонстровано, що для одночасного забезпечення стійкості та гнучкості програми число входів логічних елементів має бути обмежене певним інтервалом, а саме становити величину, що приблизно дорівнює 2—3.

17.6. Етапи генетичного алгоритму

Розрізняють такі етапи ГА:

1. Створити початкову популяцію.

2. Цикл за поколіннями, допоки не виконано умову зупинки.

3. Цикл життя одного покоління.

4. Оцінити пристосованість кожної особини.

5. Виконати відбір за пристосованістю.

6. Випадковим чином розподілити популяцію на дві групи пар.

7. Виконати фазу імовірнісної рекомбінації для пар популяції і замінити батьків.

8. Виконати фазу імовірнісної мутації.

9. Оцінити пристосованість нової популяції та обчислити умови зупинки.

10. Оголосити нащадків новим поколінням.

11. Кінець циклу за поколіннями.

Аналогія генетичних методів з поняттями генетики

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

Хромосоми — структурні елементи клітинного ядра біологічних організмів, є носіями генів у клітинному ядрі особини. У генетичних методах терміни «хромосома» та «особина» використовуються як синоніми.

Локус — місце, що займає ген у хромосомі.

Алелі — значення генів.

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

Дії генів виявляються в популяціях.

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

Отже, генетичні методи запозичили з біології понятійний апарат, ідею колективного пошуку екстремуму, способи подання ге-

У генетичних методах множині відповідає запис, який називається хромосомою, елементи хромосоми відповідають параметрам i x , їх називають генами, а значення генів — алелями. Кожен ген розміщується в хромосомі в деякій позиції — локусі. У разі геометричної інтерпретації кожному гену відповідає одна з осей координатного простору, а хромосомі — деяка точка пошукового простору.

Очевидно, що в більшості практично значущих завдань структурного синтезу число можливих альтернатив настільки велике, що явне подання безлічі альтернатив є неможливо. Тому в кожний момент пошуку ГА оперує підмножиною альтернатив потужності N, що становлять деякі N точок простору структурних параметрів. Цю підмножину називають популяцією, а N — розміром популяції. Хромосома, представлена конкретними значеннями своїх генів, є проектною альтернативою або примірником хромосоми.

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

Будь-який конкретний екземпляр хромосоми називають генотипом (комплекс усіх генів організму, які зумовлюють спадкові властивості), а сукупність характеристик, властивих індивіду на певній стадії розвитку, — фенотипом.

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

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

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

Члени вихідного покоління генеруються випадковим чином. При цьому для кожного гена задано область визначення, наприклад, у вигляді інтервалу [] maxmin ;xx , та значення генів вибираються з рівною імовірністю в його межах. Результатом кожного чергового витка зовнішнього циклу є нове покоління, про якість якого судять за примірником хромосоми з кращим значенням функції корисності F. Характер наближення до екстремуму зазвичай такий, що на початкових витках швидкість поліпшення цільової функції досить значна, але в міру наближення до екстремуму вона сповільнюється і може припинитися поліпшення F на деякому віддаленні від екстремальної точки.

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

У внутрішньому циклі базового ГА виконується така послідовність генетичних операторів: вибір батьків, кросовер (схрещування), мутації, формування нового покоління.

Формально методи генетичного пошуку можуть бути описані у вигляді такої функції:

ГМ = ГМ(P

0 , N, L, f, , , , T), де P

0 = {H

1

0 , H

2

0 , …, H N

0 } — початкова популяція — множина розв’язків задачі, поданих у вигляді хромосом; H j

0 = {h

1j

0 , h

2j

0 , …, h Lj


< Попередня  Змiст  Наступна >
Iншi роздiли:
17.10. Стандартний генетичний алгоритм
17.13. Узагальнена схема роботи генетичних методів
17.19. Джиніторний
Тема 18. ПРИКЛАДНІ СИСТЕМИ КОЛЕКТИВНОГО ІНТЕЛЕКТУ SWARM INTELLIGENCE
18.3. Різновиди методу мурашиних колоній
Дисциплiни

Медичний довідник новиниКулінарний довідникАнглійська моваБанківська справаБухгалтерський облікЕкономікаМікроекономікаМакроекономікаЕтика та естетикаІнформатикаІсторіяМаркетингМенеджментПолітологіяПравоСтатистикаФілософіяФінанси

Бібліотека підручників та статтей Posibniki (2022)