Genetiska algoritmer

Genetiska algoritmer är heuristiska, stokastiska optimeringsmetoder som har föreslagits för första gången 1975, Holland. De bygger på idén om evolution genom naturligt urval, som även erbjuder Darwin.

Genetiska algoritmer arbetar med en mängd olika individer, är att en befolkning där varje individ kan fungera som en lösning på några särskilda problem. Varje individ måste bedömas på graden av anpassning, beroende på hur bra är den lösning som motsvarar det. Om vi anser att det i förhållande till verksamhetens art, är det uppskattade verkningsgrad i kroppen under konkurrens om resurser. Individer är mycket mer anpassat kan återge genom korsning med andra medlemmar av befolkningen. Detta orsakar uppkomsten av nya arter, som kombinerar vissa egenskaper som sänds som ett arv från föräldrar.

Mindre anpassade individer kommer att kunna reproducera avkomma är mindre troligt, så att egenskaperna som de besitter, gradvis försvinner under utvecklingen av hela befolkningen. Ibland finns det spontana förändringar i gener eller mutationer. Det visar sig att de goda egenskaperna från generation till generation kommer att distribueras i hela befolkningen. Korsningar individer som är bäst lämpade, vilket leder till vad som forskat sökwebbplatser som representerar den största tiden. I slutändan är det den lösning. Genetiska algoritmer har fördelen av det faktum att det är en relativt kort period av tid approximativa lösningar, som är optimala. Det är värt att överväga frågan om programmering.

Genetiska algoritmer består av följande komponenter:

- kromosomen som representerar en lösning på problemet i fråga består av gener. Denna population av kromosomer anses primär;

- en uppsättning av påståenden (konstruerade för att generera nya lösningar på grundval av ny population);

- målfunktionen (utformad för att utvärdera lämpligheten av lösningar).

För den genetiska algoritmen ger en standarduppsättning av operatörer: urval, mutation och crossover. Det är möjligt att överväga att använda genetiska algoritmer med hjälp klargöra vad varje enskild operatör. Operatör val väljer kromosomer i enlighet med vad värdena för lämplighetsfunktioner. Här är det presenteras åtminstone två av de mest populära operatören: turnering och roulette. roulette metod involverar utövandet av urvalet av individer genom n körningar. För varje medlem av befolkningen sysselsatta i rouletthjulet innehåller en sektor till önskat värde. Medlemmar av befolkningen med en betydligt högre grad av anpassning i detta val kommer att väljas oftare än representanterna som har låg kondition. När metoden genomförs turnering n Lag som tillåter individer att välja n. Grundval av varje händelse som prov k element av befolkningen, medan bland dem bör väljas den bästa individen.

Om du fortsätter att överväga att programmera algoritmer, är det nödvändigt att berätta om en metod som kallas korsningar. korsning operatör utbyts mellan paret av delar av kromosomer eller kromosom i en population.

Senast operatör - mutationer - den stokastiska variationen i kromosomen.

Specifik övervägande av användning av genetiska algoritmer är ett bulkmaterial än vad som ryms i artikeln, så det bör behandlas separat.