Algoritmos Geneticos
28897 palavras
116 páginas
CAPÍTULO 3INTRODUÇÃO AOS A LGORITMOS
GENÉTICOS
Estéfane G. M. de Lacerda
André Carlos P. L. F. de Carvalho
3.1 UM A LGORITMO GENÉTICO SIMPLES
A lg o ritm o s Gené tico s, A Gs, são m é to d o s d e o tim iz ação e busca insp irad o s no s m ecanism o s d e ev o lução d e p o p ulaçõ es d e seres v iv o s. Fo ram intro d uz id o s p o r Jo hn Ho lland (Ho lland ,
1975) e p o p ulariz ad o s p o r um d o s seus aluno s, Dav id
Go ld berg (Go ld berg , 1989). Estes alg o ritm o s seg ue m o p rincíp io d a seleção natural e so brev iv ê ncia d o m ais ap to , d eclarad o em 1859 p elo naturalista e f isio lo g ista ing lê s
Charles Darw in em seu liv ro A O rig em d as Esp écies. De aco rd o co m Charles Darw in, “ Quanto m elho r um ind iv íd uo se ad ap tar ao seu m eio am biente, m aio r será sua chance d e so brev iv er e g erar d escend entes” .
Otim iz ação é a busca d a m elho r so lução p ara um d ad o p ro blem a. Co nsiste em tentar v árias so luçõ es e utiliz ar a inf o rm ação o btid a neste p ro cesso d e f o rm a a enco ntrar so luçõ es cad a v ez m elho res. Um exem p lo sim p les d e o tim iz ação é a m elho ria d a im ag e m d as telev isõ es co m antena aco p lad a no p ró p rio ap arelho . A trav é s d o ajuste m anual d a antena, v árias so luçõ es são testad as, g uiad as p ela q ualid ad e d e im ag em o btid a na T V, até a o btenção d e um a resp o sta ó tim a, o u seja, um a bo a im ag e m .
Est fane Lacerda e Andr Carvalho
88
¡
A s t cnicas d e busca e o tim iz aç o , g eralm ente, ap resentam :
¢
•
Um esp aço d e busca, o nd e est o to d as as p o ssív eis so luç es d o p ro blem a;
•
Um a f unç o o bjetiv o (alg um as v ez es cham ad a d e f unç o d e ap tid o na literatura d e A Gs), q ue utiliz ad a p ara av aliar as so luç es p ro d uz id as, asso ciand o a cad a um a d elas um a no ta.
¢
£
¡
¢
¢
£
¢
Em term o s m atem tico s, a o tim iz aç o co