Theory  for  Heuris-c  Op-miza-on  Con-nued:      

Gene-c  Algorithms  

There  is  a  handout,  which  is  pages  28-­‐33  in  Goldberg’s  book  on  Gene-c  

Algorithms    

1  

Next  Topic  is  Theory  for  Gene-c  Algorithms  

•  A  basic  defini-on  in  Gene-c  Algorithms  is  the  SCHEMA.  

•  A  schema  is  a  set  of  genes  that  make  up  a  par-al  solu-on  to  our  op-miza-on  problem.      

•  Plural  of  schema  is  “schemata”.  •  Schemata  defining  subsets  of  similar  chromosomes.  •  We  denote  a  building  block  as  {1*0***}  where  the  *  indicates  it  can  be  either  0  or  1.  

2  

Let  H1,  H2,  H3,  H4,  be  four  schemata  represented  by  the  following  strings  

3  

Average  fitness  and  Disrup-on  from  Crossover  •  The  average  fitness  is  f(H)    •  For  example:  (Previous  slide)  

•  During  crossover,  a  schema  may  be  cut  (disrupted),    which  occurs  when  a  crossover  point  is  selcted  within  it  defining  length.  

•  What  affects  the  probability  of    disrupDon??  

4  

Order  and  Length  of  Schema  •  The  order  of  a  schema  H  denoted  by  o(H)  is  the  number  of  non-­‐*  symbols  it  contains  

•  The  defining  length  denoted  by  δ(H)  is  the  distance  from  the  first  non*  to  the  last  non*posi-on.  

•  So  for  *1*0*110,  the  order  o(H)  is  5  and  its  defining  length  δ(H)  is  6  (=8-­‐2)  

•  During  a  crossover  a  schema  may  be  cut,  so  that  is  why    the  GA  theory  depends  on  schema.  

•  The  symbols  in  the  decision  variable  are  some-mes  called    “metasymbols”,  which  for  binary  strings  are  0’s  and  1’s.  

5  

Effect  of  Reproduc-on  Without  Crossover  on  Schema  

•  Let  S[j]  be  the  jth  individual  in  the  gene-c  algorithm  popula-on  and  assume  j=1,…,M.  

•  Let  f  ,  j=1,…,M  be  the  fitness  of  S[j].  •  Let    Avgf  be  the  average  fitness  in  the  whole  popula-on.  (Avgf  is  

called  f  in  text.)  

Avgf=    •  The  probability  of  S[j]  being  selected  as  a  parent  (roulege  wheel)  is  

f/Avgf  •  Let  m(Hi,  g)  be  the  expected  number  of  Hi  schemas  present  in  the  

GA  popula-on  in  the  gth  genera-on.    So  what  is  the  expected  value  of    m(Hi,  g)?  (see  board)  

6  

Individual  and  Average  Fitness  •  M=  number  of  individual  strings    in  popula-on  •  S[j]=  an  individual  string  in  the  popula-on,  j=1,…,M      

•  f  is  the  fitness  of  S[j]    •  avg  f    =  average        fitness  of  S[j]  =  

•  The  probability  of  S[j]  being  selected  as  a  parent  (roulege  wheel)  is  f/Avgf  

•  P(t)=  popula-on  in  t  itera-on    (  P(t))={S[j],  j=1,…,M},  a  set)  

•  f(H)=  average  fitness  of  all  S[j]  in  schema  H.  

•  m(H,t)=  expected  number  of    S[j]  contained  in  schema  H  in  itera-on  t  

Defini-ons  •  Probability  a  string  S[j]  from  P(t)  is  selected  to  be  a  parent  (by  roulege)  is                

•  The  expected  value  of  m(H,t+1)  is    

9  

Effect  of  Crossover  

•  Does  the  Schema  structure  tell  us  something  about  the  likelihood  that  the  Schema  will  survive  cross  over?  

•  Example:    H1=[11****]  of  length  6  with  defining  length  

•  Where  can  the  crossover  occur  and  not  disrupt  the  schema  (i.e.  the  parent’s  por-on  is  s-ll  consistent  with  H1)?    Let  ps(Hi)  be  the  probability  of  survival  of  the  schema  through  one  itera-on  or  opera-on.  

•  What  is  the  probability  that  the  schema  is  disrupted?  10  

A  general  Rule  for  ps  -­‐-­‐Disrup-on  of  Schema  

•  Consider  H2=[1***0*]  with      (H2)=4.  

•  There  are  5  cross  over  points.    How  many  of  them  destroy  the  schema?  

•  What  is  ps(H2)?  

•  How  do  we  express  this  if  we  know  one  crossover  is  done?  

•  How  do  we  express  this  if  there  is  a  probability  pc  that  one  cross  over  is  done?  

11  

Average  fitness  and  Disrup-on  from  Crossover  •  The  average  fitness  is  f(H)  =  •  For  example  

•  During  crossover,  a  schema  may  be  cut  (disrupted),    which  occurs  when  a  crossover  point  is  selcted  within  it  defining  length.  

•  What  affects  the  probability  of    disrupDon??  

12  

Probability  of  Schema  DisrupBon:  Consider  two  schema  and  their  defining  length  δ  and  order:  

 

13  

Effect  of  Crossover  

•  Does  the  Schema  structure  tell  us  something  about  the  likelihood  that  the  Schema  will  survive  cross  over?  

•  Example:    H1=[11****]  of  length  6  with  defining  length  

•  Where  can  the  crossover  occur  and  not  disrupt  the  schema  (i.e.  the  parent’s  por-on  is  s-ll  consistent  with  H1)?      

•  Let  ps(Hi)  be  the  probability  of  survival  of  the  schema  through  one  itera-on  or  opera-on.  

•  What  is  the  probability  that  the  schema  is  disrupted?  

14  

Defini-ons  •  M=  number  of  individual  strings    •  S[j]=  an  individual  string  in  the  popula-on,  j=1,…,M    (book  is  S[j]=p[j])  •  H=  a  schema  •  f    &  f    =  f      fitness  of  S[j]  and  f    =  •  f(H)=  average  fitness  of  all  S[j]  in  schema  H.  •  P(t)=  popula-on  in  t  itera-on    (  P(t))={S[j],  j=1,…,M},  a  set)  •  m(H,t)=  number  of    S[j]  contained  in  schema  H  in  itera-on  t  •                 Probability  a  string  S[j]  from  P(t)  is  selected  to  be  a  parent  (by  roulege)  is                

•  The  expected  value  of  m(H,t+1)  is    

15  

Effect  of  Crossover  •  Does  the  Schema  structure  tell  us  something  about  the  

likelihood  that  the  Schema  will  survive  cross  over?  •  Example:    H1=[11****]  of  length  6  with  defining  length  

•  Where  can  the  crossover  occur  and  not  disrupt  the  schema  (i.e.  the  parent’s  por-on  is  s-ll  consistent  with  H1)?    Let  ps(Hi)  be  the  probability  of  survival  of  the  schema  through  one  itera-on  or  opera-on.  

•  What  is  the  probability  that  the  schema  is  disrupted?  

16  

Effect  of  Muta-on,    

•  What  determines  if  a  schema  H  survives  mutaBon?        •  For  example,  what  if  H1=  [10*******1***1].    How  is  it  

disturbed  by  muta-on?  

•  Let  pm,  be  the  probability  that  one  bit  is  mutated.  

•  Then  the  probability  that  schema  H1  survives  muta-on  is    

•  What  is  the  combined  effect  of  Crossover  Muta-on  and  Reproduc-on?  

17  

Surviving  Muta-om  

•  For  a  schema  to  survive,  none  of  the  o(H)  fixed  bit  posi-ons  must  be  affected  by  muta-on.  

•  Let  pm  be  the  probability  of  muta-on.  •  Then  probability  of  a  single  bit  not  being  mutated  is  1-­‐  pm    

•  Then  the  probability  of  x  in  H  not  being  mutated  out  of  H  is  (1-­‐  pm  )o(H)  

Surviving  Muta-on  

Assume  there  exists  an  U>1  for  all  itera-ons  t  up  to  K  such  that  At  >U  

What  happens  as  t  increases?  •  Now  we  replace  the  At  expression  by  U  in  the  inequality  so  then    

•  m(H,t+1)>  m(H,t)U>  m(H,t-­‐1)*U2    etc.  so    •  Therefore,    •  m(H,t+1)  >  m(H,0)  U  t+1      •  Since  U>  1  this  means  that  up  to  K  itera-ons  the  expected  number  of  members  in  the  popula-ons  will  increase.  

•  If  no  such  U  exists,  then  the  schema  H  will  gradually  die  out.  

Schema  Theorem:      

•  Schema  Theorem:    Highly  fit,  short-­‐defining  length  schemata  are  most  likely  undisturbed  and  are  propagated  from  generaDon  to  generaDon.    These  schemata  receive  exponenDally  increasing  number  of  trials  in  subsequent  generaDons.  

•  This  “Theorem  is  controversial.    What  do  you  think  about  it?  

24  

So  is  this  a  Theorem?  

•  No  this  is  not  a  rigorous  proof  and  in  fact  people  have  developed  counter  examples  that  show  that  GA  can  converge  to  the  wrong  solu-on.  

•  What  is  wrong  with  it?    (My  idea)  

Recall  assump-on:  there  exists  an  U>1  for  all  itera-ons  t  up  to  K  such  that  At  

>U  

What  happens  with  convergence?  What  is  the  difference  between  f(H,t)  and  Avgf(t)?    Will  there  always  be  a  U>1    for  which  all  t,  At    >U?  

Problems  with  “theorem”  

•  Hence  it  is  not  possible  that  there  exists  a  U>1  for  all  t.  

•  Thus,  just  because  an  author  calls  something  a  “theorem”  does  not  mean  it  is  mathema-cally  true.  

•  In  this  case  it  is  more  of  an  explana-on  of  why  things  work  for  a  finite  number  of  evalua-ons  rather  than  a  “mathema-cal”  theorem.