algoritmi genetici

ALGORITMI GENETICIALGORITMI GENETICI

Comanici Nadia

ContinutContinut

Notiuni de GeneticaNotiuni de Genetica

Programe EvolutivePrograme Evolutive

Algoritmi GeneticiAlgoritmi Genetici

Utilizari Practice ale Algoritmilor GeneticiUtilizari Practice ale Algoritmilor Genetici

Demo-uriDemo-uri

Maximizarea unei functii de o variabilaMaximizarea unei functii de o variabila

Problema OraruluiProblema Orarului

Algoritmi

Genetica

Solutii

Aproximare a realitatii

Optimizare

Calcule

Pasi / etape

- Finititudine- Corectitudine- Generalitate

Gena

Cromozom

Evolutie

Genotip

Fenotip

Recombinare

Mutatie

Ce este evolutia?Ce este evolutia?

Notiuni de Genetica - 1Notiuni de Genetica - 1

Gena – unitate de baza purtatoare a ereditatii in Gena – unitate de baza purtatoare a ereditatii in organismele viiorganismele vii

Cromozom – colectie de geneCromozom – colectie de gene

Individ – organism care se identifica in mod unic Individ – organism care se identifica in mod unic prin combinatia sa de cromozomiprin combinatia sa de cromozomi

Populatie – multime de indivizi dintr-o anume Populatie – multime de indivizi dintr-o anume specie care interactioneaza intre eispecie care interactioneaza intre ei

Notiuni de Genetica - 2Notiuni de Genetica - 2

Evolutie – procesul prin care o populatie de Evolutie – procesul prin care o populatie de organisme isi schimba trasaturile mostenite de la organisme isi schimba trasaturile mostenite de la o generatia la generatia urmatoareo generatia la generatia urmatoare

Mostenire – un organism-copil dobandeste Mostenire – un organism-copil dobandeste trasaturi ale organismului-parinte trasaturi ale organismului-parinte

Mutatie – schimbare in materialul genetic al unui Mutatie – schimbare in materialul genetic al unui organism organism

Incrucisare – procesul prin care doua Incrucisare – procesul prin care doua organisme-parinte fac schimb de informatie organisme-parinte fac schimb de informatie genetica si in urma caruia rezulta organisme-genetica si in urma caruia rezulta organisme-copilcopil

Programe EvolutivePrograme Evolutive

Algoritmi probabilistici Algoritmi probabilistici

Pastreaza o populatie de indiviziPastreaza o populatie de indivizi, pentru fiecare iteratie. , pentru fiecare iteratie.

Fiecare individ :Fiecare individ :

Reprezinta o Reprezinta o potentiala solutie la problema potentiala solutie la problema

Este reprezentat sub forma Este reprezentat sub forma unei structuri de date unei structuri de date specifice problemeispecifice problemei

Este evaluat pe baza unei functii de fitnessEste evaluat pe baza unei functii de fitness

Se aplica operatori genetici: selectie, incrucisare si Se aplica operatori genetici: selectie, incrucisare si mutatiemutatie

Programe Evolutive Programe Evolutive

+ +

Structuri de Date Structuri de Date

= =

Algoritmi GeneticiAlgoritmi Genetici

Structura unui Algoritm GeneticStructura unui Algoritm Genetic

Pasul 1 : se alege populatia initialaPasul 1 : se alege populatia initiala

Pasul 2 : se evalueaza fiecare individ din populatiePasul 2 : se evalueaza fiecare individ din populatie

Pasul 3 : Pasul 3 :

repetarepeta– Pasul 3.1 : se selecteaza cei mai buni indivizi Pasul 3.1 : se selecteaza cei mai buni indivizi pentru urmatoarea pentru urmatoarea

generatiegeneratie– Pasul 3.2 : pe baza unor probabilitati, se aplica operatorii de Pasul 3.2 : pe baza unor probabilitati, se aplica operatorii de

ıncrucisare si ıncrucisare si mutatie indivizilor selectati anterior mutatie indivizilor selectati anterior pentru a pentru a forma forma noua populatienoua populatie

– Pasul 3.3 : se evalueaza fiecare individ din noua populatie pe Pasul 3.3 : se evalueaza fiecare individ din noua populatie pe baza functiei de fitnessbaza functiei de fitness

pana cand (conditie de oprire)pana cand (conditie de oprire)

Elemente definitorii ale Elemente definitorii ale Algoritmilor GeneticiAlgoritmilor Genetici

Structura genetica a unui individStructura genetica a unui individ

Crearea populatia initialaCrearea populatia initiala

Functia de evaluare a fitness-ului fiecarui Functia de evaluare a fitness-ului fiecarui individ (simuleaza mediul)individ (simuleaza mediul)

Operatori genetici: selectie, incrucisare, Operatori genetici: selectie, incrucisare, mutatiemutatie

Parametrii specifici algoritmuluiParametrii specifici algoritmului

ConstrangeriConstrangeri

Constrangeri hard (de corectitudine) care Constrangeri hard (de corectitudine) care sunt asigurate pentru fiecare individ al sunt asigurate pentru fiecare individ al populatieipopulatiei

Constrangeri soft (de valoare) pe baza Constrangeri soft (de valoare) pe baza carora se realizeaza evolutia indivizilor carora se realizeaza evolutia indivizilor

Functia de evaluare Functia de evaluare a fitness-uluia fitness-ului

Joaca rol de mediu, Joaca rol de mediu, evaluand indivizii si evaluand indivizii si asociind fiecarui individ asociind fiecarui individ o valoare (un fitness)o valoare (un fitness)

Reprezinta functia Reprezinta functia pentru care se doreste pentru care se doreste optimizarea cu ajutorul optimizarea cu ajutorul algoritmilor geneticialgoritmilor genetici

SelectiaSelectia

IncrucisareaIncrucisarea

Incrucisare cu mai multe puncte de taiereIncrucisare cu mai multe puncte de taiere

Incrucisare ‘taie si adauga’Incrucisare ‘taie si adauga’

Incrucisare cu un punct de taiereIncrucisare cu un punct de taiere

Parinte 1:Parinte 1:


Copil 1:Copil 1:

Copil 2:Copil 2:



Copil 1:Copil 1:

Copil 2:Copil 2:



Copil 1:Copil 1:

Copil 2:Copil 2:

Utilizari ale Algoritmilor GeneticiUtilizari ale Algoritmilor Genetici

Designul topologiilorDesignul topologiilor

Spargerea codurilorSpargerea codurilor

Optimizarea structurii moleculelor Optimizarea structurii moleculelor

PredictiiPredictii

Planificari (orare, programari etc)Planificari (orare, programari etc)

Retele neuronale recurenteRetele neuronale recurente

More: More: http://en.wikipedia.org/wiki/Genetic_algorithm#Applicatiohttp://en.wikipedia.org/wiki/Genetic_algorithm#Applicationsns

Problema 1: Maximizarea unei Problema 1: Maximizarea unei functii functii

Structuri de date specialeStructuri de date speciale– O gena (celula) = un bit (0 sau 1)O gena (celula) = un bit (0 sau 1)– Un individ = un cromozom = un numar in binar, Un individ = un cromozom = un numar in binar,

reprezentat pe k biti (sir de biti)reprezentat pe k biti (sir de biti)– O populatie de NR indivizi = o colectie de siruri de bitiO populatie de NR indivizi = o colectie de siruri de biti

Fitness-ul unui individ = valoarea functiei in acel punct Fitness-ul unui individ = valoarea functiei in acel punct (care se obtine din reprezentarea binara)(care se obtine din reprezentarea binara)

Problema 1: Maximizarea unei Problema 1: Maximizarea unei functii functii

Operatori specialiOperatori speciali– Pentru generarea indivizilor initiali – se genereaza Pentru generarea indivizilor initiali – se genereaza

aleator o populatie din NR indivizi, fiecare avand k aleator o populatie din NR indivizi, fiecare avand k genegene

– Pentru incrucisare – pe baza unei probabilitati de Pentru incrucisare – pe baza unei probabilitati de incrucisare, se considera doi indivizi si se creeaza alti incrucisare, se considera doi indivizi si se creeaza alti indivizi noi folosind o singura taieturaindivizi noi folosind o singura taietura

– Pentru mutatie – pe baza unei probabilitati de mutatie Pentru mutatie – pe baza unei probabilitati de mutatie (PM), se schimba un bitul cu valoarea 0 in 1 sau cu (PM), se schimba un bitul cu valoarea 0 in 1 sau cu valoarea 1 in 0valoarea 1 in 0

Demo : Problema maximizarii unei Demo : Problema maximizarii unei functiifunctii

Problema 2: Problema OraruluiProblema 2: Problema Orarului

Este NP-completaEste NP-completa

Presupune numeroase constrangeri Presupune numeroase constrangeri (pentru profesori, grupe, cursuri, sali sau (pentru profesori, grupe, cursuri, sali sau facultati)facultati)

Presupune diferite tipuri de cursuriPresupune diferite tipuri de cursuri– SaptamanaleSaptamanale– BisaptamanaleBisaptamanale– PartajatePartajate

Solutia Problemei folosind Algoritmi Solutia Problemei folosind Algoritmi GeneticiGenetici

Structuri de date specialeStructuri de date speciale– O gena (celula) = un container care poate contine O gena (celula) = un container care poate contine

diferite tipuri de activitati de tip curs (saptamanale, diferite tipuri de activitati de tip curs (saptamanale, bisaptamanale sau partajate)bisaptamanale sau partajate)

– Un individ = un orarUn individ = un orar– O populatie de indivizi = o colectie de orareO populatie de indivizi = o colectie de orare

Operatori specialiOperatori speciali– Pentru generarea indivizilor initialiPentru generarea indivizilor initiali– Pentru incrucisarePentru incrucisare– Pentru mutatiePentru mutatie

Demo : Problema orarului - evolutieDemo : Problema orarului - evolutie

Q&AQ&A

algoritmi genetici

Documents