Інтелектуальні інформаційні технології та системи генетичні алгоритми

Санкт-Петербурзький державний інженерно-економічний університет Філія в місті Череповці

Кафедра "общепрофессіональние і спеціальні дисципліни"

Реферат

З дисципліни "Інформаційні технології в економіці"

Тема "Інтелектуальні інформаційні технології та системи: генетичні алгоритми"

Студентки 3 курсу

групи 4ЕУП-05

Валігура Т.В.

Череповець, 2007

Зміст

1. Генетичні алгоритми

2. Простий генетичний алгоритм

3. Різновиди генетичних алгоритмів

1. Генетичні алгоритми

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

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

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

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

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

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

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

• Всі ознаки організму визначаються наборами генів;

• Гени - це елементарні одиниці спадкової інформації, які знаходяться в хромосомах;

• Гени можуть змінюватися - мутувати;

• Мутації окремих генів призводять до зміни окремих елементарних ознак організму, або фенів.

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

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

1. рекомбінація хромосомних і нехромосомних генів;

2. рекомбінація цільових негомологічному хромосом;

3. рекомбінація ділянок хромосом, представлених безперервними молекулами ДНК.

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

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

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

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

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

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

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

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

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

Інверсія, транцлокація, транспозиція, делеція і дуплікація відносяться до різновидів хромосомної мутації. При інверсії ділянку хромосоми повертається на 180 ^0. транслокацією називають перенесення частини однієї хромосоми в іншу. При переміщенні невеликих ділянок генетичного матеріалу в межах однієї хромосоми використовують термін транспозиція. Делеція - це випадання окремих ділянок хромосом, дуплікація - повторення ділянки генетичного матеріалу. Крім перерахованих, існують інші різновиди хромосомних мутацій.

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

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

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

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

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

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

• Абстрактне і формальне пояснення процесів адаптації в природних системах;

• Проектування штучних програмних систем, що відтворюють механізми функціонування природних систем.

Основні відмінності ГА від інших алгоритмів оптимізації:

• Використовуються не параметри, а закодована безлічі параметрів;

• Пошук здійснюється не з єдиної точки, а з популяції точок;

• У процесі пошуку використовуються значення цільової функції, а не її збільшення;

• Застосовуються ймовірні, а не детерміновані правила пошуку та генерації рішень;

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

2. Простий генетичний алгоритм

Згідно репродуктивного плану Холланда генетичні схеми пошуку оптимальних рішень включають наступні етапи процесу еволюції:

1. конструюється початкова популяція. Вводиться початкова точка відліку поколінь t = 0. обчислюються пристосованість хромосом популяції (цільова функція) і середня пристосованість всієї популяції.

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

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

4. оновлення поточної популяції шляхом заміни випадково вибраної хромосоми на А (t) /

5. визначення пристосованості А (t) і перерахунок середньої пристосованості популяції.

6. якщо t = t, де t - задане число кроків, то перехід до етапу 7, у противному випадку - перехід до етапу 2.

7. кінець роботи.

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

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

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

3. Різновиди генетичних алгоритмів

Генетичний алгоритм Девіса (25) включає наступні кроки:

1. ініціалізація популяції хромосом.

2. оцінка кожної хромосоми в популяції.

3. створення нових хромосом за допомогою зміни та схрещування поточних хромосом (застосування операторів мутації і кросинговеру).

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

5. оцінка нових хромосом і включення їх в популяцію.

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

Холланд (14,26) запропонував для генетичного алгоритму оператор інверсії, який реалізується за схемою:

1. стринг (хромосома) В = (b _1, b _2, ... .., b ₁₎ вибирається випадковим чином з поточної популяції.

2. з множини Y = (0,1,2, ...., L +1) випадковим чином вибираються два числа у ₁ і у ₂ і визначаються значення х1 = min (у _1, у _2).

3. з хромосоми У формується нова хромосома шляхом інверсії (зворотного порядку) сегмента, що лежить праворуч від позиції х ₂ в хромосомі В. Після застосування оператора інверсії рядок У набуде вигляду В = (b _1, ...., b _{x 1,} b _{x 2} = 1 , _{bx 2-2,} ..., b _{x 1} +1, b _{x 2,} ..., b _L).

Наприклад, для рядка В = (1,2,3,4,5,6) при виборі у ₁ = 6 і у ₂ = ₂ і відповідно х ₁ = 2, х ₂ = 6 результатом інверсії буде В = (1,2 , 3,4,5,6).

Операції кросинговеру і мутації, використовувані в простому ГА, змінюють структуру хромосом, у тому числі руйнують вдалі фрагменти знайдених рішень, що зменшує ймовірність знаходження глобального оптимуму. Для усунення цього недоліку в генетичних алгоритмах використовують схеми (схемати або шаблони), що представляють собою фрагменти рішень або хромосом, які бажано зберегти в процесі еволюції. При використанні схем в генетичному алгоритмі вводиться новий алфавіт (0,1,), де інтерпретується як "має значення 1 або 0". Наприклад:

Схема (* 0000) відповідає двом стрінгам (10000 і 00000);

Схема (* 111 *) відповідає чотирьом рядках (01110, 11110, 01111, 11111);

Схема (0 * 1 **) може відповідати восьми п'ятизначним стрінгам.

Загалом випадку хромосома довжиною L максимально може мати 3 ^L (Шаблонів), але тільки 2 ^L різних альтернативних стрінгів. Це випливає з факту, що схемі (**) у загальному випадку можуть відповідати ^{2 березня} = 9 стрінгів, а саме (**, * 1, * 0,1 *, 0 *, 00, 01, 10 11), і тільки ² лютого = 4 альтернативні рядки (00, 01, 10, 11), тобто однієї і тієї ж рядку може відповідати кілька схем.

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

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

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

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

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

• випадкове равновероятно видалення хромосом;

• видалення хромосом, що мають найгірші значення цільової функції;

• видалення хромосом на основі зворотного значення цільової функції;

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

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