Najpoznatije P-metaheuristike su:

Genetski algoritam (GA)

GA je zasnovan na simuliranju procesa biološke evolucije populacije jedinki, pri čemu proces pretraživanja skupa dopustivih rešenja odgovara procesu evolucije populacije jedinki.

60-ih godina prošlog veka korišćene su heuristike sa elementima evolutivnih principa, međutim teorijske i praktične osnove genetskih algoritama su postavljene 1975. godine sa pojavom knjige Džona Holanda „Adaptacija u prirodnim i veštačkim sistemima”.

Genetski algoritam se primenjuje na konačnom skupu jedinki koji se naziva populacija. Svaka jedinka u populaciji je predstavljena nizom karaktera (genetskim kodom) i odgovara nekom rešenju u pretraživačkom prostoru. Kodiranje je najčešće binarno, ali se mogu koristiti i skupovi veće kardinalnosti (kodiranje nad celim/realnim brojevima). Kodiranje rešenja je važan korak GA jer neadekvatan izbor koda može dovesti do loših rezultata bez obzira na ostalu strukturu algoritma.

Inicijalna populacija se može generisati na slučajan način čime se obezbeđuje raznovrsnost genetskog materijala. Moguće je korišćenje neke heuristike za generisanje početne populacije, ili jednog njenog dela, pri čemu treba obratiti pažnju na efikasnost, kao i da se ne smanji značajno raznovrsnost genetskog materijala. Svakoj jedinki se na određen način dodeljuje funkcija prilagođenosti koja je merilo kvaliteta jedinke (odnosno odgovarajućeg rešenja). Najčešće se za određivanje prilagođenosti jedinke koristi vrednost funkcije cilja rešenja koje je kodirano tom jedinkom. Operatorom selekcije vrši se izbor jedinki koje će ucestvovati u stvaranju nove generacije. Selekcija se primenjuje u skladu sa vrednostima funkcije prilagođenosti. Pretpostavlja se da će bolje prilagođene jedinke preneti dobar genetski materijal na svoje potomke, pa se one favorizuju čime se smanjuje šansa prolaska loših jedinki u narednu generaciju. Operator ukrštanja predstavlja postupak razmene delova genetskog koda dve (ili više) jedinke-roditelja i tako se dobijaju kodovi novih (jedne ili više) jedinki-potomaka. Operator mutacije vrši promenu koda jedinke. Koristi se da bi se unela raznovrsnost medu jedinkama populacije budući da one vremenom mogu postati jako slične. Svaki gen genetskog koda može mutirati sa unapred određenom malom verovatnoćom $p_m$.

Pseudokod:

P <- Inicijalna_popuacija()
while Nije_ispunjen_kriterijum_zaustavljanja 
			for jedinka in P
					pi <- funkcija_cilja()
			end
			Izracunaj_funkciju_prilagodjenosti()
			Selekcija()
			Ukrstanje()
			Mutacija()
end

Operatori genetskog algoritma se uzastopno primenjuju do zadovoljenja nekog od kriterijuma zaustavljanja: maksimalan broj generacija, maksimalno vreme izvršavanja, nepromenjen kvalitet rešenja posle unapred zadatog broja generacija...

Prost GA (Simple Genetic Algorithm - SGA)

Kodiranje: binarno

Selekcija: rulet selekcija (verovatnoća izbora jedinke proprocionalna je njenoj prilagođenosti)