Genetik algoritmlarning asoslari

Genetik algoritmlar (GAs) evolyutsion algoritmlarning ko'p qismiga tegishli bo'lgan adaptiv evristik qidiruv algoritmlari. Genetik algoritmlar tabiiy tanlanish va genetika g'oyalariga asoslangan. Bu tarixiy ma'lumotlar bilan ta'minlangan tasodifiy qidiruvdan aqlli foydalanish bo'lib, qidiruvni yechim maydonidagi eng yaxshi ishlash maydoniga yo'n altiradi. Ular odatda optimallashtirish va qidirish muammolari uchun yuqori sifatli echimlarni yaratish uchun ishlatiladi.

Genetik algoritmlar tabiiy tanlanish jarayonini taqlid qiladi, ya'ni atrof-muhitdagi o'zgarishlarga moslasha oladigan turlar omon qolishi, ko'payishi va keyingi avlodga o'tishi mumkin. Oddiy so'zlar bilan aytganda, ular muammoni hal qilish uchun keyingi avlod shaxslari orasida "eng moslashganlarning omon qolishiga" taqlid qilishadi. Har bir avlod shaxslar populyatsiyasidan iborat bo'lib, har bir shaxs qidiruv maydonidagi nuqta va mumkin bo'lgan echimni anglatadi. Har bir shaxs belgilar qatori / butun sonlar / suzuvchi nuqta / bitlar bilan ifodalanadi. Ushbu satr xromosomaga o'xshaydi.

Genetik algoritmlarning asoslari

Genetik algoritmlar populyatsiya xromosomalarining genetik tuzilishi va xatti-harakatlariga o'xshashlikka asoslangan. Quyida ushbu o'xshashlikka asoslangan GAs asoslari keltirilgan –

Populyatsiyadagi shaxslar resurslar uchun raqobatlashadi va juftlashadi
Muvaffaqiyatli (eng moslashuvchan) shaxslar keyinchalik boshqalarga qaraganda ko'proq nasl berish uchun juftlashadi
"Eng mos" ota-onaning genlari butun avlod davomida tarqaladi, ya'ni ba'zida ota-onalar har qanday ota-onadan yaxshiroq nasl yaratadilar.
Shunday qilib, har bir keyingi avlod o'z muhitiga ko'proq mos keladi.
Qidiruv maydoni

Shaxslar populyatsiyasi qidiruv maydonida saqlanadi. Har bir inson ma'lum bir muammo uchun qidiruv maydonida echimni taqdim etadi. Har bir shaxs komponentlarning cheklangan uzunligi vektori (xromosomaga o'xshash) sifatida kodlangan. Ushbu o'zgaruvchan komponentlar genlarga o'xshaydi. Shunday qilib, xromosoma (individual) bir nechta genlardan (o'zgaruvchan komponentlar) iborat.

Muvofiqlikni baholash

Har bir shaxsga fitnes bahosi beriladi, bu shaxsning "raqobatlashish"qobiliyatini ko'rsatadi. Jismoniy tayyorgarlikning maqbul ko'rsatkichiga ega bo'lgan (yoki optimal ko'rsatkichga yaqin) shaxs qidirilmoqda.

GAs populyatsiyani qo'llab-quvvatlaydi n shaxslar (xromosomalar / eritmalar) ularning fitnes ko'rsatkichlari bilan birga.Jismoniy tayyorgarlikning yaxshi ko'rsatkichlariga ega bo'lgan shaxslar ko'payish ehtimoli boshqalarga qaraganda ko'proq. Jismoniy tayyorgarlikning eng yaxshi ko'rsatkichlariga ega bo'lgan shaxslar tanlanadi, ular juftlashadi va ota-onalarning xromosomalarini birlashtirish orqali eng yaxshi nasl tug'diradi. Aholi soni statik, shuning uchun yangi kelganlar uchun xona yaratish kerak. Shunday qilib, ba'zi shaxslar o'lib, ularning o'rnini yangi kelganlar egallaydi va oxir-oqibat eski populyatsiyaning barcha juftlashish imkoniyatlari tugagach, yangi avlodni yaratadi. Umid qilamanki, keyingi avlodlarda yaxshiroq echimlar paydo bo'ladi, eng kam mos bo'lganlar esa o'ladi.

Har bir yangi avlod o'rtacha oldingi avlodlarga qaraganda ko'proq "yaxshi genlar" ga ega. Shunday qilib, har bir yangi avlod oldingi avlodlarga qaraganda yaxshiroq "qisman echimlar" ga ega. Ishlab chiqarilgan nasl oldingi populyatsiyalar tomonidan ishlab chiqarilgan nasldan sezilarli farq qilmasa, populyatsiya konvergent bo'ladi. Algoritm muammoning echimlari to'plamiga qisqartirilishi aytiladi.

Genetik algoritm operatorlari

Dastlabki avlod yaratilgandan so'ng, algoritm quyidagi operatorlar yordamida avlodni rivojlantiradi –

1) tanlov operatori: g'oya jismoniy tayyorgarligi yaxshi bo'lgan shaxslarga ustunlik berish va ularning genlarini keyingi avlodlarga o'tkazishiga imkon berishdir.
2) krossover operatori: bu shaxslar o'rtasidagi juftlikni anglatadi. Ikkita shaxs selection operatori yordamida tanlanadi va chatishtirish joylari tasodifiy tanlanadi. Keyin bu chatishtirish joylaridagi genlar almashadi va shu bilan butunlay yangi shaxs (nasl) hosil qiladi. Masalan, –

3) mutatsiya operatori: asosiy g'oya-erta konvergentsiyani oldini olish uchun populyatsiyadagi xilma-xillikni saqlab qolish uchun naslga tasodifiy genlarni kiritish. Masalan, –

Butun algoritm quyidagicha umumlashtirilishi mumkin –

1) Randomly initialize populations p

2) Determine fitness of population
3) Until convergence repeat:
a) Select parents from population
b) Crossover and generate new population
c) Perform mutation on new population
d) Calculate fitness for new population
Genetik algoritmlardan foydalangan holda muammo va echimga misol

Maqsad satrini hisobga olgan holda, maqsad bir xil uzunlikdagi tasodifiy qatordan boshlab maqsad satrini yaratishdir. Keyingi amalga oshirishda quyidagi o'xshashliklar amalga oshiriladi –

A-Z, a-z, 0-9 va boshqa maxsus belgilar genlar sifatida qaraladi
Ushbu belgilar tomonidan yaratilgan satr xromosoma / yechim / shaxs sifatida qaraladi
Muvofiqlikni baholash-bu ma'lum bir indeksga ega bo'lgan maqsad satridagi belgilardan farq qiladigan belgilar soni. Shunday qilib, kamroq mos keladigan shaxsga ko'proq imtiyozlar beriladi.

// C++ program to create target string, starting from

// random string using Genetic Algorithm

#include

using namespace std;

// Number of individuals in each generation

#define POPULATION_SIZE 100

// Valid Genes

const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}";

// Target string to be generated

const string TARGET = "I love GeeksforGeeks";

// Function to generate random numbers in given range

int random_num(int start, int end)
{
int range = (end-start)+1;
int random_int = start+(rand()%range);
return random_int;
}

// Create random genes for mutation

char mutated_genes()
{
int len = GENES.size();
int r = random_num(0, len-1);
return GENES[r];
}

// create chromosome or string of genes

string create_gnome()
{
int len = TARGET.size();
string gnome = "";
for(int i = 0;ignome += mutated_genes();
return gnome;
}

// Class representing individual in population

class Individual
{
public:
string chromosome;
int fitness;
Individual(string chromosome);
Individual mate(Individual parent2);
int cal_fitness();
};

Individual::Individual(string chromosome)

{
this->chromosome = chromosome;
fitness = cal_fitness();
};

// Perform mating and produce new offspring

Individual Individual::mate(Individual par2)
{
// chromosome for offspring
string child_chromosome = "";

int len = chromosome.size();

for(int i = 0;i{
// random probability
float p = random_num(0, 100)/100;

// if prob is less than 0.45, insert gene

// from parent 1
if(p < 0.45)
child_chromosome += chromosome[i];

// if prob is between 0.45 and 0.90, insert

// gene from parent 2
else if(p < 0.90)
child_chromosome += par2.chromosome[i];

// otherwise insert random gene(mutate),

// for maintaining diversity
else
child_chromosome += mutated_genes();
}

// create new Individual(offspring) using

// generated chromosome for offspring
return Individual(child_chromosome);
};

// Calculate fitness score, it is the number of

// characters in string which differ from target
// string.
int Individual::cal_fitness()
{
int len = TARGET.size();
int fitness = 0;
for(int i = 0;i{
if(chromosome[i] != TARGET[i])
fitness++;
}
return fitness;
};

// Overloading < operator

bool operator<(const Individual &ind1, const Individual &ind2)
{
return ind1.fitness < ind2.fitness;
}

// Driver code

int main()
{
srand((unsigned)(time(0)));

// current generation

int generation = 0;

vector population;

bool found = false;

// create initial population

for(int i = 0;i
{
string gnome = create_gnome();
population.push_back(Individual(gnome));
}

while(! found)

{
// sort the population in increasing order of fitness score
sort(population.begin(), population.end());

// if the individual having lowest fitness score ie.

// 0 then we know that we have reached to the target
// and break the loop
if(population[0].fitness <= 0)
{
found = true;
break;
}

// Otherwise generate new offsprings for new generation

vector new_generation;

// Perform Elitism, that mean 10% of fittest population

// goes to the next generation
int s = (10*POPULATION_SIZE)/100;
for(int i = 0;inew_generation.push_back(population[i]);

// From 50% of fittest population, Individuals

// will mate to produce offspring
s = (90*POPULATION_SIZE)/100;
for(int i = 0;i{
int len = population.size();
int r = random_num(0, 50);
Individual parent1 = population[r];
r = random_num(0, 50);
Individual parent2 = population[r];
Individual offspring = parent1.mate(parent2);
new_generation.push_back(offspring);
}
population = new_generation;
cout<< "Generation: " << generation << "\t";
cout<< "String: "<< population[0].chromosome <<"\t";
cout<< "Fitness: "<< population[0].fitness << "\n";

generation++;

}