Эволюционный алгоритм для угадывания строки, испорченный репликацией - PullRequest
Новая
       1

Эволюционный алгоритм для угадывания строки, испорченный репликацией

1 голос
/ 14 июня 2011

Я работаю над сценарием Python, чтобы проверить генетическое программирование.В качестве упражнения я создал простой скрипт, который пытается угадать строку без целой части населения.

Мой код: 

# acts as a gene
# it has three operations:
# Mutation   : One character is changed
# Replication: a sequencepart is duplicated
# Extinction : A sequencepart is lost
# Crossover  : the sequence is crossed with another Sequence
import random
class StringGene:
  def __init__(self, s):
    self.sequence = s
    self.allowedChars = "ABCDEFGHIJKLMOPQRSTUVWXYZ/{}[]*()+-"

  def __str__(self):
    return self.sequence

  def Mutation(self):
    x = random.randint(0, len(self.sequence)-1)
    r = random.randint(0, len(self.allowedChars)-1)
    d = self.sequence
    self.sequence =  d[:x-1]+ self.allowedChars[r] + d[x:]

  def Replication(self):
    x1 = random.randint(0, len(self.sequence)-1)
    x2 = random.randint(0, len(self.sequence)-1)
    self.sequence =self.sequence[:x1]+ self.sequence[x1:x2] + self.sequence[x2:]
    self.sequence = self.sequence[:32]

  def Extinction(self):
    x1 = random.randint(0, len(self.sequence)-1)
    x2 = random.randint(0, len(self.sequence)-1)
    self.sequence =     self.sequence[:x1] + self.sequence[x2:]

  def CrossOver(self, s):
    x1 = random.randint(0, len(self.sequence)-1)
    x2 = random.randint(0, len(s)-1)
    self.sequence = self.sequence[:x1+1]+ s[x2:]
    #x1 = random.randint(0, len(self.sequence)-1)
    #self.sequence = s[:x2             ] + self.sequence[x1+1:]

if __name__== "__main__":
  import itertools
  def hamdist(str1, str2):
    if (len(str2)>len(str1)):
      str1, str2 = str2, str1
    str2 = str2.ljust(len(str1))
    return  sum(itertools.imap(str.__ne__, str1, str2))


  g = StringGene("Hi there, Hello World !")
  g.Mutation()
  print "gm: " + str(g)
  g.Replication()
  print "gr: " + str(g)
  g.Extinction() 
  print "ge: " + str(g)
  h = StringGene("Hello there, partner")
  print "h: " + str(h)
  g.CrossOver(str(h))
  print "gc: " + str(g)
  change = 0
  oldres = 100
  solutionstring = "Hello Daniel. Nice to meet you."
  best = StringGene("")
  res = 100
  print solutionstring
  while (res > 0):
      g.Mutation()
      g.Replication()
      g.Extinction()
      res = hamdist(str(g), solutionstring)   
      if res<oldres:      
        print "'"+ str(g) + "'"
        print "'"+ str(best) + "'"
        best = g
        oldres = res
      else :
        g = best 

      change = change + 1
  print "Solution:" + str(g)+ " "  + str(hamdist(solutionstring, str(g))) + str (change)

У меня есть грубое расстояние Хемминга в качестве меры, насколько далеко строка решения отличается от текущей.Однако я хочу иметь возможность иметь различную длину в угадывании, поэтому я ввел репликацию и удаление частей строки.

Теперь, однако, строка растет бесконечно, и строка решения никогда не найдена.Можете ли вы указать, где я ошибся?

Можете ли вы предложить улучшения?

ура

Ответы [ 4 ]

1 голос
/ 20 июня 2011

Ваши StringGene объекты являются изменяемыми, что означает, что когда вы выполняете такую ​​операцию, как best = g, вы заставляете и g, и best ссылаться на один и тот же объект. Поскольку после этого первого шага у вас есть только один объект, каждая мутация применяется постоянно, независимо от того, успешна она или нет, и все сравнения между g и best являются сравнениями между одним и тем же объектом.

Вам нужно либо реализовать оператор копирования, либо сделать экземпляры неизменяемыми, и чтобы каждый оператор мутации возвращал измененную версию 'гена'.

Кроме того, если первая мутация не может улучшить строку, вы устанавливаете g в best, что является пустой строкой, полностью отбрасывая вашу начальную строку.

Наконец, каноническая тестовая строка - «Мне кажется, это как ласка».

0 голосов
/ 20 июня 2011

Прежде всего, то, что вы делаете, это генетический алгоритм, а не генетическое программирование (которое является родственным, но другим понятием).

Я не знаю Python, но, похоже, у вас есть серьезная проблема в функции вымирания. Насколько я могу судить, если x1> x2, то размер строки увеличивается, а не уменьшается (часть между x1 и x2 фактически удваивается). Что произойдет в функции репликации, когда x1> x2, я не могу сказать, не зная Python.

Также имейте в виду, что поддержание населения является ключом к эффективному решению проблем с генетическими алгоритмами. Кроссоверы являются неотъемлемой частью алгоритма, и они не имеют большого смысла или вообще не имеют смысла, если они не сделаны между членами группы населения (кроме того, чем больше популяция, тем лучше в большинстве случаев). Код, который вы представили, зависит от мутаций одного экземпляра для достижения ожидаемого результата и, следовательно, вряд ли даст что-то полезное быстрее, чем простой метод грубой силы.

0 голосов
/ 14 июня 2011

Я думаю, что ваша фитнес-функция слишком проста.Я бы поиграл с использованием двух переменных, одной из которых является размерное расстояние, а другой - ваш «хамдист».Чем больше разница в размерах, тем больше она влияет на общую пригодность.Так что сложите их вместе с некоторой процентной константой.

Я также не очень знаком с python, но мне кажется, что это не то, что вы делаете.

0 голосов
/ 14 июня 2011

Самое простое - ограничить допустимую длину предполагаемой строки.Не позволяйте догадкам выше определенной длины.

Я посмотрел ваш код, и я не достаточно хорош в Python, чтобы найти какие-либо ошибки, но, возможно, вы просто ссылаетесь или индексируетеневерный массив, в результате чего всегда добавляет новые символы в строку предположения, поэтому длина вашей строки всегда увеличивается ... Я не знаю, является ли это ошибкой, но подобные вещи произошли со мнойдо этого, так что дважды проверьте ваш массив показателей.;)

...