Cruzamentos perigosos

O operador de cruzamento altera os indivíduos sem no entanto introduzir valores novos. Comecemos por por operadores genéricos, tipicamente usados com cadeias binárias e com vectores de reais. Se os pais forem válidos os filhos também o serão.

Um ponto de corte
Define um ponto aleatório e cruza.

def one_point_cross(cromo_1, cromo_2,prob_cross):
 value = random.random()
 if value < prob_cross:
  pos = random.randint(0,len(cromo_1))
  f1 = cromo_1[0:pos] + cromo_2[pos:]
  f2 = cromo_2[0:pos] + cromo_1[pos:]
  return [f1,f2]
 else:
  return [cromo_1,cromo_2]

Dois pontos de corte
Define dois pontos aleatórios e cruza.

def two_points_cross(cromo_1, cromo_2,prob_cross):
 print cromo_1, cromo_2
 value = random.random()
 if value < prob_cross:
  pc= random.sample(xrange(len(cromo_1)),2)
  pc.sort()
  pc1,pc2 = pc
  f1= cromo_1[:pc1] + cromo_2[pc1:pc2] + cromo_1[pc2:]
  f2= cromo_2[:pc1] + cromo_1[pc1:pc2] + cromo_2[pc2:]
  return [f1,f2]
 else:
  return [cromo_1,cromo_2]

Uniforme
Cada filho tem igual probabilidade de herdar de um dos pais.

def uniform_cross(cromo_1, cromo_2,prob_cross):
 value = random.random()
 if value < prob_cross:
  f1=[]
  f2=[]
  for i in range(0,len(cromo_1)):
   if random.random() < 0.5:
    f1.append(cromo_1[i])
    f2.append(cromo_2[i])
   else:
    f1.append(cromo_2[i])
    f2.append(cromo_1[i])

  return [f1,f2]
 else:
  return [cromo_1,cromo_2]

Qunado se trata de permutações temos que ter cuidados acrescidos para que do cruzamento resultem indivíduos inviáveis. Claro que, em muitas situações, a produção de indivíduos inviáveis é inevitável, e, em situações precisas, até pode ser desejável. Existem vários métodos para lidar com os indivíduos inviáveis que vão desde a sua penalização até à sua reparação. Mas regressemos aos operadores.

Ordem

Escolhem-se os mesmos dois pontos de corte nos dos pais P1 e P2. Trocam-se as partes do meio (as partes entre os dois pontos de corte: A parte do meio de P2 vai para F1 e a de P1 para F2. Em cada um dos filhos procura-se manter pela mesma ordem relativa, a partir do segundo ponto de corte os elementos do pai com o mesmo número de ordem. Por exemplo, No F1, que herda a parte do meio de P2, procura-se manter na mesma ordem os elementos de P1.

def order_cross(cr_1,cr_2,prob_cross):
 size = len(cr_1)
 value = random.random()
 if value < prob_cross:
  pc= random.sample(range(size),2)
  pc.sort()
  pc1,pc2 = pc
  f1 = [None] * size
  f2 = [None] * size
  f1[pc1:pc2+1] = cr_2[pc1:pc2+1]
  f2[pc1:pc2+1] = cr_1[pc1:pc2+1]
  indexes = range(pc2+1,size) + range(pc1)
  j = k = pc2 + 1
  for i in indexes:  
   while cr_1[j%size] in f1:
    j += 1
   f1[i%size] = cr_1[j%size]
   j += 1
   while cr_2[k%size] in f2:
    k += 1
   f2[i%size] = cr_2[k%size]
   k += 1
  return [f1,f2]
 else:
  return [cr_1,cr_2] 
  

Partial Mapped

Este operador começa também por determinar dois pontos de corte e trocar as partes do meio. De seguida procura manter o máximo de elementos fora da parte do meio nas suas posições iniciais. Nos casos em que tal não é possível, usa a correspondência desses elementos com os da outra parte do meio.





Não se assuste com o código.....

def pmx_cross(cromo_1,cromo_2,prob_cross):
 size = len(cromo_1)
 value = random.random()
 if value < prob_cross:
  pc= random.sample(xrange(size),2)
  pc.sort()
  pc1,pc2 = pc
  f1 = [None] * size
  f2 = [None] * size
  f1[pc1:pc2+1] = cromo_1[pc1:pc2+1]
  f2[pc1:pc2+1] = cromo_2[pc1:pc2+1]
  # primeiro filho
  # parte do meio
  for j in range(pc1,pc2+1):
   if cromo_2[j] not in f1:
    pos_2 = j
    g_j_2 = cromo_2[pos_2]
    g_f1 = f1[pos_2]
    index_2 = cromo_2.index(g_f1)
    while f1[index_2] != None:
     index_2 = cromo_2.index(f1[index_2])
    f1[index_2] = g_j_2
  # restantes
  for k in range(size):
   if f1[k] == None:
    f1[k] = cromo_2[k]
  # segundo filho 
  # parte do meio
  for j in range(pc1,pc2+1):
   if cromo_1[j] not in f2:
    pos_1 = j
    g_j_1 = cromo_1[pos_1]
    g_f2 = f2[pos_1]
    index_1 = cromo_1.index(g_f2)
    while f2[index_1] != None:
     index_1 = cromo_1.index(f2[index_1])
    f2[index_1] = g_j_1
  # parte restante
  for k in range(size):
   if f2[k] == None:
    f2[k] = cromo_1[k]    
  return [f1,f2]
 else:
  return [cromo_1,cromo_2]

Outros operadores

Existem muitos mais operadores de cruzamento. Uma vez mais, em muitos casos esses operadores estão ligados a problemas concretos. Deixamos aqui exemplos simples.

Aritmético

Cria dois descendentes baseado numa combinação linear dos seus pais.

def arithmetic(cromo_1,cromo_2,coef):
 off_1 = [ coef * cromo_1[index] + (1 - coef) * cromo_2[index] for index in range(len(cromo_1))]
 off_2 = [ coef * cromo_2[index] + (1 - coef) * cromo_1[index] for index in range(len(cromo_1))]
 return [off_1,off_2]

Heurístico

Cria apenas um descendente enviesado pelo valor do melhor dos pais.

def heuristic(cromo_1,cromo_2,coef,fit_func):
 """Just one offspring!."""
 fit_cr_1 = fitness(fit_func,cromo_1)
 fit_cr_2 = fitness(fit_func,cromo_2)
 if fit_cr_1 > fit_cr_2:
  off = [ coef* (cromo_1[index] - cromo_2[index]) + cromo_1[index] for index in range(len(cromo_1))]
 else:
  off = [ coef* (cromo_2[index] - cromo_1[index]) + cromo_2[index] for index in range(len(cromo_1))]
 return off