Umwandeln von Verified Women in Sexy Girls

[snafu]

Wo ist eigentlich der Mod, wenn man ihn mal braucht...?

[snafu]

Dieser Thread kann gerne auch gelöscht werden, versteht ja nun eh keiner mehr.

[__blackjack__]

Na dann machen wir was verständliches daraus. Richard Dawkin's Weasel program.

Code: Alles auswählen

#!/usr/bin/env python3
import random
from string import ascii_letters

ALPHABET = ascii_letters + " "
MUTATION_CHANCE = 0.05  # per character.
COPY_COUNT = 100  # per generation.


def copy(text):
    return "".join(
        (
            random.choice(ALPHABET)
            if random.random() <= MUTATION_CHANCE
            else character
        )
        for character in text
    )


def calculate_score(text_a, text_b):
    assert len(text_a) == len(text_b)
    return sum(
        character_a == character_b
        for character_a, character_b in zip(text_a, text_b)
    )


def main():
    text = "Verified Women"
    target = "Sexy Girls    "
    assert len(text) == len(target)
    assert set(target) <= set(ALPHABET)

    while text != target:
        text = max(
            (copy(text) for _ in range(COPY_COUNT)),
            key=lambda candidate: calculate_score(candidate, target),
        )
        print(text)


if __name__ == "__main__":
    main()

Code: Alles auswählen

Verified Wom n
Veryfied Wom n
VehyGted Wom n
VehyGted Wom n
VexyGted Wom n
VexyGted W m n
VexyGted W m n
VexyGted W m n
VexyGfed W m n
Sexylfed Q m n
Sexylfed Q m n
Sexylfed Q m n
Sexylfid Q m n
Sexylfid Q m n
SexylfidbQ m n
SexylfidbQ m n
Sexy fidbQ m n
Sexy fidbQ m n
Sexy fidbQ m  
Sexy fidbs m  
Sexy fidbs m  
Sexy fidbs m  
Sexy fidbs m  
Sexy fidbs m  
Sexy fidPs m  
Sexy fidls m  
Sexy fidls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy firls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls R  
Sexy Girls

[nezzcarth]

@__blackjack__: Interessante Idee! Mir erscheint es hier nur evtl. leicht verständlicher, den Hamming-Abstand zwischen den beiden Strings zu minimieren, statt einen davon abgeleiteten Fitness-Score zu maximieren (auch wenn das bei genetischen Algorithmen üblicher sein mag); man will ja einen String, der möglichst wenige Unterschiede aufweist.

[__blackjack__]

@nezzcarth: Ich habe mich halt an die Vorgaben von der Wikipediaseite gehalten. Der hat das ursprüngliche Programm 1986 in BASIC geschrieben. Und ich denke gerade die Einfachheit trägt zu seinem Argument bei, das weder die Mutation noch die Fitness-Funktion besonders schlau sind, und sich trotzdem relativ schnell das Ergebnis einstellt.

[snafu]

Phänomenal.

[__blackjack__]

Da Dawkins das zuerst in BASIC hatte, wollte ich das auch mal machen (CBM BASIC auf dem VIC-20):

Code: Alles auswählen

4 L=RND(-TI)
5 TI$="000000"
10 A$="VERIFIED WOMEN"
20 B$="SEXY GIRLS    "
30 L=LEN(A$)
40 DIM A(L),B(L),C(L),D(L)
50 FORI=1TOL
60 A(I)=ASC(MID$(A$,I,1))
70 B(I)=ASC(MID$(B$,I,1))
80 NEXT:GOSUB1000
90 BS=-1
100 FORI=1TO100
110 FORJ=1TOL
120 IFRND(1)>.05THENC=A(J):GOTO160
130 C=INT(RND(1)*27)
140 IFC=26THENC=32:GOTO160
150 C=C+65
160 C(J)=C:NEXT
170 S=0:FORJ=1TOL
180 S=S-(B(J)=C(J)):NEXT
190 IFS<BSTHEN210
200 BS=S:FORJ=1TOL:D(J)=C(J):NEXT
210 NEXT
220 FORJ=1TOL:A(J)=D(J):NEXT
230 GOSUB1000
240 IFBS<LTHEN100
250 PRINTTI$
999 END
1000 FORI=1TOL:PRINTCHR$(A(I));:NEXT:PRINT
1010 RETURN

Läuft so zwischen 20 und 30 Minuten bis die Umwandlung komplett ist. Das Beispiel ist deutlich kürzer als der Spruch mit dem Wiesel, aber er hatte 1986 wahrscheinlich schon deutlich leistungsfähigere Hardware dafür.

[nezzcarth]

@__blackjack__: Ja, ich verstehe, dass es auf Wikipedia anders beschrieben wird. Allerdings ändern sich durch meinen Vorschlag nur zwei Zeilen in der Python-Version. Aber wie gesagt, fänd' ich nur logischer, das muss für einen Biologen ja nicht gelten. Zur Performance frage ich mich auch, auf was für einen Rechner Dawkins wohl 1986 als Biologe so Zugriff hatte; insb. falls sich die Angabe von 11 Sekunden für eine Pascal-Version auch auf dasselbe Jahr bezieht.

[DeaD_EyE]

Hmmmmm Python ist sexy, wir brauchen keine ...

[__blackjack__]

Auf dem PC wäre das so die Zeit von TurboPascal 3. Ohne speziell auf Geschwindigkeit geachtet zu haben:

Code: Alles auswählen

program Weasel;
type
  TInstance = String[14];
const
  Source: TInstance = 'Verified Women';
  Target: TInstance = 'Sexy Girls    ';

function RandomCharacter: Char;
var
  n: Byte;
begin
  n := Random(53);
  if n < 26 then n := n + Ord('a')
            else if n < 52 then n := n - 26 + Ord('A')
                           else n := Ord(' ');
  RandomCharacter := Chr(n);
end;

procedure Copy(var source: TInstance; var target: TInstance);
var
  i: Byte;
begin
  for i := 1 to Length(source) do
    if Random <= 0.05 then target[i] := RandomCharacter
                      else target[i] := source[i];
end;

function CalculateScore(var instance: TInstance): Integer;
var
  i: Byte;
  score: Integer;
begin
  score := 0;
  for i := 1 to Length(instance) do
    if instance[i] = Target[i] then score := score + 1;
  CalculateScore := score;
end;

procedure Mutate(var instance: TInstance);
var
  i, j: Byte;
  bestScore, score: Integer;
  mutated, best: TInstance;
begin
  bestScore := -1;
  for i := 1 to 100 do
    begin
      Copy(instance, mutated);
      score := CalculateScore(mutated);
      if score > bestScore then
        begin
          bestScore := score;
          best := mutated;
        end;
    end;
  instance := best;
end;

begin
  Randomize;
  repeat
    Mutate(Source);
    WriteLn(Source);
  until Source = Target;
end.

Braucht so 30 bis 40 Sekunden auf einem XT-Klon mit etwas unter 10 Mhz. Und auch wenn es zu der Zeit schon AT-Rechner mit 286er gab, denke ich eher nicht, dass das bei ihm ein IBM-PC war. Wobei natürlich auch so Sachen wie die Mutationsrate Einfluss auf die Laufzeit haben können. Wir wissen ja nicht wie das Programm exakt ausgesehen hat.

Ich bin auch immer wieder fasziniert wie langsam GW-BASIC auf so einem Rechner ist. Verglichen mit der 8-Bit-Konkurrenz zwar schneller, aber wenn man sich den Prozessortakt und den Preisunterschied anschaut, sieht das schon irgendwie schlecht aus. Das hier braucht so zwischen 9 und 15 Minuten:

Code: Alles auswählen

10 DEFINT A-Z:RANDOMIZE(TIMER):T1!=TIMER
20 A$="Verified Women":B$="Sexy Girls    ":IF LEN(A$)<>LEN(B$) THEN STOP
25 C$=SPACE$(LEN(A$)):Z$=" ":FOR I=0 TO 25:Z$=Z$+CHR$(65+I)+CHR$(97+I):NEXT
30 PRINT A$:WHILE A$<>B$:BS=-1:FOR I=1 TO 100:FOR J=1 TO LEN(A$)
40 IF RND>.05 THEN X$=MID$(A$,J,1) ELSE X$=MID$(Z$,INT(RND*53)+1,1)
50 MID$(C$,J,1)=X$:NEXT:S=0:FOR J=1 TO LEN(A$):S=S-(MID$(C$,J,1)=MID$(B$,J,1))
60 NEXT:IF S>BS THEN BS=S:D$=C$
70 NEXT:A$=D$:PRINT A$:WEND:PRINT TIMER-T1!

[nezzcarth]

Wobei natürlich auch so Sachen wie die Mutationsrate Einfluss auf die Laufzeit haben können. Wir wissen ja nicht wie das Programm exakt ausgesehen hat.

Die ideale Mutationsrate für den ursprünglichen String und die Populationsgröße von 100 liegt bei meinen Tests zwischen 4-5%. Insofern sind die 5% evtl. nicht das absolute Optimum, aber schon sehr gut gewählt und die Unterschiede in der Anzahl der nötigen Generationen im Mittel sehr gering, sodass es auf die exakte Zahl aus dem Bereich vielleicht nicht so ankommt. Eine deutlich größere Population (ruhig um die 1000 oder mehr) sorgt aber tatsächlich für eine sehr viel schnellere Konvergenz

Für das Beispiel aus dem Thread hier bekomme ich mit einer etwas höheren Mutationsrate von 0.095 merklich bessere Ergebnisse, auch schon bei einer Population von 100. Das liegt daran, dass die sinnvolle Mutationsrate von der Zeichenkettenlänge abhängt (die tatsächlich genau die Hälfte des "Wiesel-Strings" ist.)

[__blackjack__]

Ein bisschen manuelles Code-Inlining, einfacherer Code zur Auswahl eines zufälligen Zeichens mit einer vorbereiteten Zeichenkette mit allen möglichen Zeichen, weniger Parameterübergaben, weniger Zeichenketten kopieren (dafür mehr auf einmal im Speicher), den Score merken und für die Endbedingung verwenden statt Zeichenkettenvergleich, und die Pascal-Version ist runter auf 14 bis 24 Sekunden:

Code: Alles auswählen

program Weasel;
type
  TInstance = String[14];
const
  Source: TInstance = 'Verified Women';
  Target: TInstance = 'Sexy Girls    ';
  InstancesPerGeneration = 100;
  LetterMutationChance = 0.05;
  AlphabetLength = 53;
var
  Alphabet: String[AlphabetLength];  { Lower- & uppercase letters & space. }
  instance: TInstance;
  score: Integer;

procedure InitAlphabet;
var
  i, j: Byte;
begin
  Alphabet[0] := Chr(AlphabetLength);
  for i := 0 to 25 do
    begin
      j := (i SHL 1) + 1;
      Alphabet[j] := Chr(Ord('a') + i);
      Alphabet[j + 1] := Chr(Ord('A') + i);
    end;
  Alphabet[AlphabetLength] := ' ';
end;

function MutateAndScore(var mutated: TInstance): Integer;
var
  i: Byte;
  score: Integer;
begin
  score := 0;
  mutated[0] := Chr(Length(instance));
  for i := 1 to Length(instance) do
    begin
      if Random <= LetterMutationChance
        then mutated[i] := Alphabet[Random(53) + 1]
        else mutated[i] := instance[i];

      if mutated[i] = Target[i] then score := score + 1;
    end;
  MutateAndScore := score;
end;

procedure MutateAndSelect;
var
  i, j: Byte;
  bestScore, mutatedScore: Integer;
  bestIndex: Byte;
  mutated: array[1..InstancesPerGeneration] of TInstance;
begin
  bestScore := score;
  for i := 1 to InstancesPerGeneration do
    begin
      mutatedScore := MutateAndScore(mutated[i]);
      if mutatedScore > bestScore then
        begin
          bestScore := mutatedScore;
          bestIndex := i;
        end;
    end;

  if bestScore > score then
    begin
      score    := bestScore;
      instance := mutated[bestIndex];
    end;
end;

begin
  Randomize; InitAlphabet;
  instance := Source; score := 0;
  repeat
    MutateAndSelect;
    WriteLn(instance);
  until score = Length(Target);
end.