Нечітким відношенням R (велике з хвилькою між двома непустими множинами називається нечітка множина яка визначена як підмножина декартового добутку Х/У (НФ1)
Іншими словами нечітке відношення – це множина пар (НФ2) де М від р це функція належності яка кожній парі Х,У ставить у відповідність її ступінь належності ммю е ХУ яка інтерпритується як сила звязку між елементами х що належить Х та у що належить У
Носій нечіткого відношення R ( з хвилькою) на множинах х і у називається звичайне відношення що повязує всі пари НФ3 «всі пари які належать декартовому добутку» для яких ступінь виконання нечіткого відношення не дорівнює нулю.
Альфа перерізом нечіткого відношення Р називається звичайне відношення яке повязує всі пари НФ3 для яких ступінь виконання нечіткого відношення Р не менше альфи.
Властивості нечіткіх відношень:
· Рефлексивність
· Антирефлексивність
· Симетричність
· Асиметричність
· Обернена
Операції:
1. Масимінна композиція
2. Мінімаксел композиції
3. Максимультиплекативна композиція
_______________________________________________________________________________
12.11.2012
Д/З Лабораторна робота прислати на почту (якщо зробити то на першу пару не приходити)
Генетичні оператори
Selection –задяки даному оператору відбуважться відбір особи для схрещування.
Способи селекції – пропорційний метод , для початку для кожної особини деякої популяції розраховується її функції пристосованості та знаходиться середня пристосованість по даній популяції особини як середньо арефметичне функції пристосованості всіх особин що входять до цієї популяції. Розраховується відношення значення функції пристосованості конкретної особини до середньої пристосованості по популяції. Ціла частина числа що є цього відношення показує скільки разів гарантовано дона особина може взяти участь у схрещуванні на даному кроці еволюції. Дробова частина цього числа покахує імовірність з якою може взяти участь у наступному схрещованні дана особина на даному кроці генетичного алгоритму (ГА).Найпростіший метод – метод рулетки.
Турнірний метод - Всі особини популяції розбиваються на підгрупи. З наступним вибором кожен з них особин з найкращою пристосованістю. Існують два способи цого вибору: детермінований =1, та випадковий( здійснюється з імовірністю меншою за 1). До таких підгруп як правило включають по дві або 3 особини. Якщо підгруппа складається з пари особин то говорят про парний турнір. Кількість особин підгруппи називають чисельністю турніру. Даний мето дозволяє змінювати кількість особин в підгруппі. Турнірний метод не втрачає своєї вибіркованості коли в ході еволюції всі особини популяції стають приблихно рівними за значення функції пристосованості.
Репродукція – елітарні стратегії репродукціії полягає у хахисті найкращих хромосом для наступних ітерацій. Ця стратегія застосовується з метою не втратити на наствпному кроці ГА найкраще пристосовані хромосоми.
ГА з частковою заміною популяції (ГА з зафіксованим станом)
Характеризується тим що частина популяції поточного покоління без будь-яких змін преходить до популяції нового покоління.
Схрещування – для кожної пари відібраних особин певним чином ( як привило винаждковим) визначається позиція гена ( локус ) в хромосомі яка визнаячає так звану точку схрещування . В дані й точці обидві хромосоми діляться на дві частини і обмінюються ними. У результата утворюються нові хромосоми які називаються нащадками. Даний вид схрещування нахивається одноточковим схрещенням. При двоточковому обирається дві точки схрещування. Обидві хромосоми діляться на 3 частини і обмінюються середніми частинами. Багатоточковий спосіб схрещування – відбувається шахматним чином
Рівномірне схрещуванн – випадковим чином вибирається маска схрещування що складається з нулів та одиниць та дорівнює довжині хромосом. Маска показує чкі гени потрібно наслідувати від першої батьківської хромосоми, а які від другої. Одиниця на конкретній позиції в массі позначає що елемент що знаходиться на тому ж місці в першій батьківській хромосомі необхідно помістити на цьому ж місці в вершому нащадку. Нуль на цій позиції означає що елемент який знаходиться на другомі місці в батьківській хромосомі то її потрібно помістити на ці ж місще нащадку
Мутація – суть операції полягає у зміні гена у середині хромосоми з метою підвищення різноманітності пошуку і ведення нових хромосом у популяцію.
Інверсія – згідно з цим оператором змінюється послідовність алеїв між двома випадково обраними позиціями ( локусами) в хромосомі. Пр. здійснюється інверсія для хромосоми 001100111 з третьго по сьомого бітів результат буде таким 001001111 тобто послідовність 0 і 1 з 3 по 7 біт записану послідовність з права на ліво записуємо з ліва на право. Інший спосіб: Хромосома випадковим чином ділиться на 2 частини які змінюються між собою місцями.
Схемою називають підмножину множин всіх можливих генотипів що можливі в даній популяції що задано у вигляді хромосоми з фіксованим значенням деяких бітів решта бітів можуть приймати будь- які значення .
Для визначення схеми використовують алгоритм 0 1 * , де* означає значення 0 або1 .
Пр. 0*1 Входять 001 та 011
Схема *11*01 Пдмножина складається з таких множин 111101:011101:01101:111001
Шима – схема
Кількість фіксованих бітів називається порядковою схемою, а відстані між крайніми фіксованими позиціями ( тобто різниця їх номерів ) називається визначаючою довжиною схеми ( або обхватом схеми ) В першому випадку 2 в другому 5 ХЗ
Функія пристосованості схеми це середнє значення функції пристосованості всіх її видів
Припустимо що існує популяція Р (t) які ХРОМОСОМИ ЗАДАНІ У ВИГЛЯДІ двійкового кодування де т = 1, 2 і тд
T – це ітерація ГА, поточне покоління.
Довжина бінарних рядків ( хромосом )= L,
імовірність схрещування = рс,
імовірність мутації рm визначена ( визначаюча)
довжина схеми S L(S) Порядок схеми
Значення функції пристосованості схеми S для t-ї ітерації ГА = f(S,t)
Середнє зхначення всієї популяції для даної ітерації –
Кількість хромосом популяції П ві Т що є прикладом схеми С в поточному поколінні м(С,т) тоді кількість хромосом м(С,т+1) популяції П(т+1) що будуть прикладом схеми С в наступному поколінні т+1 можна оцінити таким чином m(S,t+1)>=(S,t)*f(s,t
Де п це імовірність руйнування схеми під дією генетиних операторів
Теореми про схеми. Схеми малого порядку, з малою визначаючою довжиною і пристосованістю що є вищою за середню пристосованість за популяцію, формують експоненціальну зростаючу кількість своїх прикладів у наступних поколіннях ГА.
Пр. За допомогою ГА знайти максимум функції в діапазоні хзмінюється від 0 до 31, якщо розмір популяції = 4 f(x) = x2
1 5 9 16 кодування бінарне, критерії зупинки ГА є побудова третього покоління.
Побудова джругого покоління відбувається за допомогою одноточкового схрещування після другого біту. Третього покоління двоточкового сх після першого та другого бітів.
00001 f(x) = 1
00101 f(x) =25
01001 f(x) = 81
10000 f(x) =256
Функція пристосованості х
19.11.2012
==