Programmieren lernen

ackage ch.programmieraufgaben.simulation.mutanten;

import java.util.*;

/**
 * @author Philipp Gressly (phi@gressly.ch)
 * Programmieraufgaben.ch: Aufgabe Mutanten
 * Darwin hatte also recht. Die geschlechtliche Selektion ist so stark, dass (wie hier) eine schlechte Mutation, eine Schlechte Mutationsrate oder gar eine nicht mal so tolle
 * Fitnes-Funktion immer noch zum göttlichen Ziel führen. Einzig ein stabiler Cross-Over wurde in diese Lösung eingebaut.
 * Nach wenigen tausend Generationen kann so ziemlich jede Gen-Sequenz selektioniert werden; was Haustierzüchter schon lange wissen: Bei besserer Selektionsfunktion reichen teilweise
 * sogar schon fünf Generationen aus. 
 */
/*
 * History: first Implementation: Jan 24, 2013
 * Bugs   :
 */
public class Mutant implements Comparator<StringBuilder> {

  
    public static void main(String[] args) {
           new Mutant().top();
    }

    int    maxWoerter    =        100;
    int    mutationsrate =         10; // # zu mutierende Wörter pro Generation.
    String gesuchtesWort = "MUTANTEN";
    
    Random random = new Random();
    
    ArrayList<StringBuilder> wortFamilie = new ArrayList<StringBuilder>(maxWoerter);
    void top() {
       int debugGenerationsNummer = 0;
       initRandomFamilie();
       while(! gefunden()) {
          debugGenerationsNummer++;
          System.out.print("Generation " + debugGenerationsNummer + ": ");
          sortNachGuete();
          debugAusgabe();
          killSchlechte(maxWoerter / 2);
          crossOver(maxWoerter / 2);
          mutation(3);
       }
    }
    
    /**
     * Gib das beste Wort der aktuellen Generation aus
     */
    void debugAusgabe() {
        System.out.println(wortFamilie.get(wortFamilie.size() - 1));
    }
    
    /**
     * Mutiere eine gegebene Anzahl (count) Elemente.
     */
    void mutation(int count) {
        for(int i = 1; i <= count; i++) {
            mutation();
        }
    }
    
    void mutation() {
        StringBuilder s = wortFamilie.get(random.nextInt(wortFamilie.size()));
        mutation(s);
    }
    
    /**
     * Mutiere ein Wort durch anfügen, löschen oder verändern eines einzelnen Buchstabens.
     */
    void mutation(StringBuilder s) {
        //System.out.println("debug olds: " + s);
        // Beliebiges Zeichen löschen
        if(random.nextFloat() < 0.25) {
            // remove a random char
            s.deleteCharAt(random.nextInt(s.length()));
            return;
        }
        // Am Anfang oder am Schluss anbauen
        if(random.nextFloat() < 0.3) {
            s.insert(0, zufallsBuchstabe());
            return;
        } 
        if(random.nextFloat() < 0.5) {
           s.append(zufallsBuchstabe());
           return;
        }
        // Buchstaben ertetzen
        int pos = random.nextInt(s.length());
        s.replace(pos, pos+1, ""+zufallsBuchstabe());
    }
    
    /**
     * Wähle :count" mal zwei beliebige Wörter und führe den Cross-Over durch.
     */
    void crossOver(int count) {
       for(int i = 1; i <= count; i++) {
           StringBuilder elter1 = getZufallsWort();
           StringBuilder elter2 = getZufallsWort();
           StringBuilder kind   = crossOver(elter1, elter2);
           wortFamilie.add(kind);
       }
    }
    
    /*
     * Bringe die beiden Wörter übereinander, dabei wird das kürzere Wort mit ' ' (Space)
     * aufgefüllt. Beite Wörter sind danach gleich lang. 
     * Danach wird für jede Position zufällig ein Buchstabe des ersten oder des zweiten 
     * Wortes gewählt.
     */
    StringBuilder crossOver(StringBuilder s1, StringBuilder s2) {
      s1 = new StringBuilder(s1.toString().trim());
      s2 = new StringBuilder(s2.toString().trim());
      StringBuilder kind = new StringBuilder();
      StringBuilder kurzwort, langwort;
      if(s1.length() < s2.length()) {
          kurzwort = s1;
          langwort = s2;
      } else {
          kurzwort = s2;
          langwort = s1;
      }
      int diff  = langwort.length() - kurzwort.length();
      int shift = random.nextInt(diff+1);
      int fill  = diff - shift;
      for(int i = 1; i <= shift; i++) {
          kurzwort.insert(0, " ");
      }
      for(int i = 1; i <= fill; i++) {
          kurzwort.append(" ");
      }
      // eigentlicher cross-over
      for(int i = 0; i < langwort.length(); i++) {
          char c;
          if(random.nextFloat() < 0.5) {
              c = kurzwort.charAt(i);
              if(c < 'A') {
                  c = langwort.charAt(i);
              }
          } else {
              c = langwort.charAt(i);
          }
          kind.append(c);
      }
      kind = new StringBuilder(kind.toString().trim());
      return kind;
    }
    
   
    /**
     * Wähle aus der aktuellen Familie von Wörtern ein zufälliges aus.
     */
    StringBuilder getZufallsWort() {
        return wortFamilie.get(random.nextInt(wortFamilie.size()));
    }
    
    /**
     * @param i wie viele sind zu löschen.
     */
    private void killSchlechte(int count) {
       ArrayList<StringBuilder> neueWortFamilie = new ArrayList<StringBuilder>();
       for(int i = count; i < wortFamilie.size(); i++) {
           neueWortFamilie.add(wortFamilie.get(i));
       }
       wortFamilie = neueWortFamilie;
    }

    private void sortNachGuete() {
       Collections.sort(wortFamilie, this);
    }

    /**
     * Das Gesuchte Wort ist irgendwo in der Wortliste vorhanden.
     */
    boolean gefunden() {
        for(StringBuilder wort: wortFamilie) {
            if(wort.toString().trim().equals(gesuchtesWort.trim())) {
                return true;
            }
        }
        return false;
    }
   
    /**
     * Initialisiere mit einem zufälligen Wortschatz.
    
     */
    private void initRandomFamilie() {
        for(int i = 1; i <= maxWoerter; i++) {
            wortFamilie.add(zufallsWort());
        }
    }
    
    /**
     * Erzeuge ein zufälliges Wort einer zufälligen Länge
     */
    StringBuilder zufallsWort() {
        // Keine wirklich gute Zufallslänge, doch auch sehr lange Wörter können auftauchen.
        int zufallsLaenge = (int) (random.nextGaussian() * 100.0);
        if(zufallsLaenge <= 0) {
            zufallsLaenge = 1 + (-zufallsLaenge);
        }
        StringBuilder s = new StringBuilder();
        for(int i = 1; i <= zufallsLaenge; i++) {
           s = s.append(zufallsBuchstabe());
        }
        return s;
    }
    
    /**
     * Großbchstabe von 'A' - 'Z'
     */
    char zufallsBuchstabe() {
      char c = (char) ('A' + random.nextInt('Z' - 'A' + 1));
      return c;
    }

    /*
     * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
     */
    @Override
    public int compare(StringBuilder s1, StringBuilder s2) {
        return guete((StringBuilder) s1)  - guete((StringBuilder) s2);
    }
    
    /**
     * Mehr oder weniger sinnvolle Güte-Funktion. Aufpassen: Die Länge ist eines der wichtigen Kriterien.
     */
    int guete(StringBuilder s) {
       return 100*gueteLaenge(s) + 20 * gueteBuchstaben(s) + 50 * gueteBuchstabenPosition(s);
    }
    
    int gueteBuchstabenPosition(StringBuilder s) {
      int guete = 0;
      for(int i = 0; i < gesuchtesWort.length(); i++) {
          char a = gesuchtesWort.charAt(i);
          char b = ' ';
          if(s.length() >= gesuchtesWort.length()) {
              b = s.charAt(i);
          }
          if(a == b) {
              guete ++;
          }
      }
      return guete;
    }
    
    int gueteLaenge(StringBuilder s) {
       return gesuchtesWort.length() - Math.abs((s.length() - gesuchtesWort.length())); 
    }
    
    int gueteBuchstaben(StringBuilder s) {
        int guete = 0;
        for(int i = 0; i < gesuchtesWort.length(); i++) {
           char c = gesuchtesWort.charAt(i);
           if(s.indexOf(""+c) >= 0) {
               guete ++;
           }
        }
        return guete;
    }
    
    
} // end of class Mutant
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

// Autor:				Andy Großhennig
// Solution for task:	Mutanten (Simulationen)

#include <iostream>
#include <string>
#include <Windows.h>
#include <vector>
#include <deque>

using namespace std;

// Function: Execute the selection
void selection(vector<string>&(vsWords))
{
	string sWord; //Word to be testing
	short shAmountLetters = 0, shAmountLettersLast = 0; //Amount of correct letters
	deque<string>(dsSort); //Deque to sort
	short shStep = 0; //Steps: 0-Sort by length, 1-Sort by amount of correct letters, 2-Sort by amount of letters at the correct position
	unsigned short shTarget = vsWords.size() / 2; //Amount of words to decrease
	
	// If: Sort the words by length
	if(shStep == 0)
	{
		shStep = 1;

		// Loop: Check word for word and filter by length
		for(unsigned short shFirst = 0;shFirst < vsWords.size();shFirst++)
		{
			if(vsWords.size() > 0 && vsWords.size() >= shTarget)
			{
				sWord = vsWords.at(shFirst);
			
				if(sWord.length() != 8)
				{	
					vsWords.erase(vsWords.begin() + shFirst);
					shStep = 0;
				}
			}
		}
	}

	if((vsWords.size() / 2) >= 1)
		shTarget = vsWords.size() / 2;
	else
		shTarget = 1;

	// If: Sort the words by amount of right letters
	if(shStep == 1)
	{
		shStep = 2;
		sWord = vsWords.at(0);
		dsSort.push_back(sWord);

		// Loop: Check the first word
		for(unsigned short shFirst = 0;shFirst < sWord.length();shFirst++)
		{
			switch(sWord.at(shFirst))
			{
				case 'm': shAmountLetters++;
						  break;
				case 'u': shAmountLetters++;
						  break;
				case 't': shAmountLetters += 2;
						  break;
				case 'a': shAmountLetters++;
						  break;
				case 'n': shAmountLetters += 2;
						  break;
				case 'e': shAmountLetters++;
			}

			// Loop: Check the rest of words
			for(unsigned short shFirst = 1;shFirst < vsWords.size();shFirst++)
			{
				shAmountLetters = 0;

					sWord = vsWords.at(shFirst);

					for(unsigned short shSecond = 0;shSecond < sWord.length();shSecond++)
					{
						switch(sWord.at(shSecond))
						{
							case 'm': shAmountLetters++;
									  break;
							case 'u': shAmountLetters++;
									  break;
							case 't': shAmountLetters += 2;
									  break;
							case 'a': shAmountLetters++;
									  break;
							case 'n': shAmountLetters += 2;
									  break;
							case 'e': shAmountLetters++;
						}
					}

					if((shAmountLetters < shAmountLettersLast) || (shAmountLetters == shAmountLettersLast))
						dsSort.push_back(sWord);
					else if(shAmountLetters > shAmountLettersLast)
						dsSort.push_front(sWord);

					shAmountLettersLast = shAmountLetters;

					if(shAmountLetters != 8)
						shStep = 1;
			}

			for(unsigned short shFirst = 0;shFirst < vsWords.size();shFirst++)
				vsWords.at(shFirst) = dsSort.at(shFirst);
		}

		// Loop: Remove the most inopportune words
		while(vsWords.size() > 0 && vsWords.size() > shTarget)
			vsWords.pop_back();
	}

	if((vsWords.size() / 2) >= 1)
		shTarget = vsWords.size() / 2;
	else
		shTarget = 1;

	// If: Sort the words by amount of letters on the right position
	if(shStep == 2)
	{
		shAmountLettersLast = 0;
		shAmountLetters = 0;
		sWord = "";
		dsSort.clear();

		sWord = vsWords.at(0);
		dsSort.push_back(sWord);

		// Loop: Check the first word
		for(unsigned short shFirst = 0;shFirst < sWord.length();shFirst++)
		{
			switch(sWord.at(shFirst))
			{
				case 'm': if(shFirst == 0)
						  {
							  shAmountLettersLast++;
							  break;
						  }

				case 'u': if(shFirst == 1)
						  {
							  shAmountLettersLast++;
							  break;
						  }
				case 't': if((shFirst == 2) | (shFirst == 5))
						  {
							  shAmountLettersLast++;
							  break;
						  }
				case 'a': if(shFirst == 3)
						  {
							  shAmountLettersLast++;
							  break;
						  }
				case 'n': if((shFirst == 4) | (shFirst == 7))
						  {
							  shAmountLettersLast++;
							  break;
						  }
				case 'e': if(shFirst == 6)
						  {
							  shAmountLettersLast++;
							  break;
						  }
			}

			// Loop: Check the rest of words
			for(unsigned short shFirst = 1;shFirst < vsWords.size();shFirst++)
			{
				sWord = vsWords.at(shFirst);

				for(unsigned short shSecond = 0;shSecond < sWord.length();shSecond++)
				{
					switch(sWord.at(shSecond))
					{
						case 'm': if(shSecond == 0)
								  {
									  shAmountLetters++;
									  break;
								  }

						case 'u': if(shSecond == 1)
								  {
									  shAmountLetters++;
									  break;
								  }
						case 't': if((shSecond == 2) | (shSecond == 5))
								  {
									  shAmountLetters++;
									  break;
								  }
						case 'a': if(shSecond == 3)
								  {
									  shAmountLetters++;
									  break;
								  }
						case 'n': if((shSecond == 4) | (shSecond == 7))
								  {
									  shAmountLetters++;
									  break;
								  }
						case 'e': if(shSecond == 6)
								 {
									  shAmountLetters++;
									  break;
								 }
						}

					if((shAmountLetters < shAmountLettersLast) | (shAmountLetters == shAmountLettersLast))
						dsSort.push_back(sWord);
					else if(shAmountLetters > shAmountLettersLast)
						dsSort.push_front(sWord);

					shAmountLettersLast = shAmountLetters;
				}

				for(unsigned short shFirst = 0;shFirst < vsWords.size();shFirst++)
				vsWords.at(shFirst) = dsSort.at(shFirst);
			}

			// Loop: Remove the most inopportune words
			while(vsWords.size() > 0 && vsWords.size() > shTarget)
			vsWords.pop_back();
		}	
	}
}

// Function: Execute the Cross Over
void cross_Over(vector<string>&(vsWords))
{
	srand(GetTickCount());
	string s_arrWords[3] = {"", "", ""};
	char c_arrLetters[6] = {'a', 'e', 'm', 'n', 't', 'u'};
	vector<char>(vcNewWord);

	s_arrWords[0] = vsWords.at(rand() % vsWords.size());

	s_arrWords[1] = vsWords.at(rand() % vsWords.size());

	// If: Set the longer word of those to the rear position
	if(s_arrWords[0].length() > s_arrWords[1].length())
	{
		s_arrWords[2] = s_arrWords[1];
		s_arrWords[1] = s_arrWords[0];
		s_arrWords[0] = s_arrWords[2];
	}

	for(unsigned int shFirst = 0;shFirst < s_arrWords[0].length();shFirst++)
	{
		switch(s_arrWords[0].at(shFirst))
		{
			case 'm': if(shFirst == 0)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			case 'u': if(shFirst == 1)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			case 't': if(shFirst == 2 || shFirst == 5)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			case 'a': if(shFirst == 3)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			case 'n': if(shFirst == 4 || shFirst == 7)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			case 'e': if(shFirst == 5)
					  {
						  vcNewWord.push_back(s_arrWords[0].at(shFirst));
						  break;
					  }
			default:  vcNewWord.push_back(s_arrWords[1].at(shFirst));
		}
	}

	// Loop: Trim the size of the new word to eight
	while(vcNewWord.size() != 8)
	{
		if(vcNewWord.size() < 8)
			vcNewWord.push_back(c_arrLetters[rand() % 6]);

		if(vcNewWord.size() > 8)
			vcNewWord.erase(vcNewWord.end() - 1);
	}

	for(unsigned short shFirst = 0;shFirst < vcNewWord.size();shFirst++)
		s_arrWords[2] += vcNewWord.at(shFirst);

	vsWords.push_back(s_arrWords[2]);
}

// Function: Execute the mutation
void mutation(vector<string>&(vsWords))
{
	srand(GetTickCount());
	short shWord = rand() % vsWords.size(), shOldLetter;
	string s_arrWords[3] = {"", "", ""};
	char c_arrLetters[6] = {'a', 'e', 'm', 'n', 't', 'u'};
	string sWord = "";
	vector<char>(vcNewWord);

	// First part similar to Cross-Over

	if(vsWords.size() > 3)
	{
		s_arrWords[0] = vsWords.at(rand() % vsWords.size());

		s_arrWords[1] = vsWords.at(rand() % vsWords.size());

		if(s_arrWords[0].length() > s_arrWords[1].length())
		{
			s_arrWords[2] = s_arrWords[1];
			s_arrWords[1] = s_arrWords[0];
			s_arrWords[0] = s_arrWords[2];
		}

		for(unsigned int shFirst = 0;shFirst < s_arrWords[0].length();shFirst++)
		{
			switch(s_arrWords[0].at(shFirst))
			{
				case 'm': if(shFirst == 0)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				case 'u': if(shFirst == 1)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				case 't': if(shFirst == 2 || shFirst == 5)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				case 'a': if(shFirst == 3)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				case 'n': if(shFirst == 4 || shFirst == 7)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				case 'e': if(shFirst == 5)
						  {
							  vcNewWord.push_back(s_arrWords[0].at(shFirst));
							  break;
						  }
				default:  vcNewWord.push_back(s_arrWords[1].at(shFirst));
			}
		}

		while(vcNewWord.size() != 8)
		{
			if(vcNewWord.size() < 8)
			{
				vcNewWord.push_back(c_arrLetters[rand() % 6]);
			}

			if(vcNewWord.size() > 8)
			{
				vcNewWord.erase(vcNewWord.end() - 1);
			}
		}

		for(unsigned short shFirst = 0;shFirst < 8;shFirst++)
			s_arrWords[2] += vcNewWord.at(shFirst);
	}
	else
	{	
		shWord = rand() % vsWords.size();
		s_arrWords[2] = vsWords.at(shWord);
		vsWords.erase(vsWords.begin() + shWord);
	}

	// End of Cross-Over part

	// Start of mutation part

	sWord = s_arrWords[2];

	shOldLetter = rand() % 8;

	switch(shOldLetter)
	{
		case 0: sWord[shOldLetter] = 'm';
				break;
		case 1: sWord[shOldLetter] = 'u';
				break;
		case 2: sWord[shOldLetter] = 't';
				break;
		case 3: sWord[shOldLetter] = 'a';
				break;
		case 4: sWord[shOldLetter] = 'n';
				break;
		case 5: sWord[shOldLetter] = 't';
				break;
		case 6: sWord[shOldLetter] = 'e';
				break;
		case 7: sWord[shOldLetter] = 'n';
				break;
	}

	vsWords.push_back(sWord);
}

// Function: Show and check the array for the sought word
void checkWords(vector<string>(vsWords), bool &bMutantenExist, const int &iLoops)
{
	HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);

	for(unsigned short shFirst = 0;shFirst < vsWords.size();shFirst++)
	{
		SetConsoleTextAttribute (hcon,15|0);
		
		if(vsWords.at(shFirst) == "mutanten")
		{
			SetConsoleTextAttribute (hcon,12|0);
			bMutantenExist = true;
		}
		cout << vsWords.at(shFirst) << endl;
	}

	
}

// Function: Generate 100 words
void generateWords(vector<string>&(vsWords))
{
	char c_arrLetters[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
	srand(GetTickCount());
	
	for(short shFirst = 0;shFirst < 100;shFirst++)
	{
		string sWord;

		for(short shSecond = 0;shSecond < ((rand() % 12) + 5);shSecond++)
		{
			sWord += c_arrLetters[rand() % 26];
		}
		vsWords.push_back(sWord);
	}
}

// Function: Runs the evolution
void mutant()
{
	HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);
	vector<string>(vsWords);
	bool bMutantenExist = false;
	int iLoops = 0;
	char cMutation;
	
	generateWords(vsWords);
	checkWords(vsWords, bMutantenExist, iLoops);

	while(bMutantenExist == false && vsWords.size() > 3)
	{
		iLoops++;

		Sleep(50);

		selection(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);

		cross_Over(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);
		
		mutation(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);
	}

	while(bMutantenExist == false && vsWords.size() > 1)
	{
		iLoops++;

		Sleep(50);

		selection(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);
		
		mutation(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);
	}

	while(bMutantenExist == false && vsWords.size() > 0)
	{
		iLoops++;

		Sleep(50);

		mutation(vsWords);
		checkWords(vsWords, bMutantenExist, iLoops);
	}

	if(bMutantenExist == true)
	{
		SetConsoleTextAttribute (hcon,15|0);
		cout << "\nDie Evolutuion hat das Wort Mutanten hervorgebracht\n";
		cout << "\nEvolutionsstufen: (100) + " << iLoops;
		cMutation = 'n';
		return;
	}
}

int main()
{
	mutant();
	
	cout << "\n\n";
	system("Pause");
	return 0;
}
                

Lösung von: Andy Großhennig (Bundeswehr)

from random import randint as rrandint
from random import sample as rsample

"""ERZEUGEN DER ZUFALLSWORTE"""
def zufallswort(maxL,abc):
    """
    gibt ein Zufallswort der maximalen Laenge I:maxL
    aus dem Alphabet I:abc zurueck.
    """
    L=rrandint(1,maxL)
    temp=""
    for index in range(L):
        temp=temp + str(abc[rrandint(0,len(abc)-1)])
    return temp

def zufallswoerter(anz,maxL,abc):
    """
    gibt ein Array aus Zufallsworten zurueck
    """
    temp=[]
    for i in range(anz):
        temp.append(zufallswort(maxL,abc))
    return temp


"""SELEKTION"""

# Guetepruefung der Laenge
def gueteLaenge(testwort,zielwort,gewicht=1.0):
    """
    Gibt die Guete der Laenge mit der Wichtung I:gewicht zurueck
    """
    delta=int(abs(len(testwort)-len(zielwort)))
    Glan=1.0
    for i in range(delta):
        Glan-=1.0/float(len(zielwort))/float(gewicht)
        if Glan < 1.0/float(len(zielwort)):
            Glan=0
            break
    return Glan


# Guetepruefung der korrekten Buchstaben
def pruefAnz(bstbe,wort):
    """
    Prueft wie oft I:bstbe in I:wort enthalten ist
    und gibt die Anzahl zurueck.
    """
    temp=0
    for el in wort:
        if bstbe == el:
            temp+=1
    return temp

def gueteKorr(testwort,zielwort,gewicht=1.0):
    """
    Gibt die Guete der korrekten Buchstaben mit einer
    Wichtung von I:gewicht zurueck.
    """
    Gkorr=1.0
    if len(zielwort)<len(testwort):
        temp=testwort
    else:
        temp=zielwort
    for el in temp:
        tempDelta=abs(pruefAnz(el,zielwort) - pruefAnz(el,testwort))
        Gkorr-=tempDelta/float(len(zielwort))/float(gewicht)
        if Gkorr < 1.0/float(len(zielwort)):
            Gkorr=0
            break
    return Gkorr


# Guetepruefung der korrekten Position von Buchstaben
def guetePos(testwort, zielwort, gewicht=1.0):
    """
    Gibt die Guete der korrekten Position von Buchstaben mit       einer
    Wichtung von I:gewicht zurueck.
    """
    Gpos=0.0
    if len(zielwort)>len(testwort):
        temp=testwort
    else:
        temp=zielwort
    for i in range(len(temp)):
        if zielwort[i] == testwort[i]:
            Gpos+=1/float(len(zielwort))/float(gewicht)
    return Gpos


# Selektion der Wortliste
def selektion(testliste, zielwort,gewicht=[1.0, 1.0, 1.0]):
    """
    Fuehrt die Selektion nach den Kriterien:
        Laenge
        Buchstaben
        Position
    durch und gibt die besten 50 Prozent wieder.
    """
    #Fuellen eines dicts mit (wort:bewertung)
    bewertung={}
    for wort in testliste:
        bewertung[wort]=gueteLaenge(wort, zielwort, gewicht[0]) + gueteKorr(wort, zielwort, gewicht[1])+ guetePos(wort, zielwort, gewicht[2])

    #sortieren des dicts nach den Bewertungen
    bestenliste=[]
    temp=sorted(bewertung.items(), key=lambda item:item[1], reverse=True)
    for el in temp:
        bestenliste.append(el[0])

    #Ausgabe der besten 50 Prozent (aufgerundet)
    return bestenliste[:int(len(bestenliste)/2.0 + 0.5)]



"""MUTATION"""
def mutWort(wort,abc):
    """
    Zufaellig soll eine Mutation an I:wort ausgefuehrt werden. Die Mutationen
    sind hierbei:
        Entfernen eines beliebigen Buchstabens
        Hinzufuegen eines bel. Buchstabens aus I:abc
        Austauschen eines bel. Buchstabens durch einen aus I:abc
    """
    #Auswahl der Mutationsmethode
    meth=rrandint(1,3)
    #Auswahl der Position
    pos=rrandint(0,len(wort)-1)
    #Auswahl des zufaelligen Buchstabens
    zufBstbe=abc[rrandint(0,len(abc)-1)]
    if meth==0:
        #Einfuegen
        temp=wort.replace(wort[pos],wort[pos] + zufBstbe )
    elif meth==1:
        #Entfernen
        if len(wort)==1:
            temp=wort
        else:
            temp=wort.replace(wort[pos],"")
    else:
        #Austauschen
        temp=wort.replace(wort[pos],zufBstbe)

    return temp


def mutation(Gen,abc,anteil=0.3):
    """
    Fuehrt eine Mutation der Individuen der Generation I:Gen aus dem Alphabet
    I:abc mit einer Wahrscheinlichkeit von I:anteil durch
    """
    auswahl=rsample(range(len(Gen)),int(len(Gen)*anteil))
    for el in auswahl:
        Gen[el]=mutWort(Gen[el],abc)
    return Gen


"""CROSSOVER"""
def erstelleSeq(Aeins,Anull):
    """
    Erstellt eine Sequenz der Laenge I:Aeins aus Einsen und Nullen,
    welche zufaellig auf die Sequenz verteilt werden. Dabei ist die
    Anzahl der Nullen eine zufaellige Zahl zwischen 1 und I:Anull
    """
    if Aeins < Anull:
        print "!!!FALSCHE ANORDNUNG DER WORTE!!!"
    indexe=rsample(range(Aeins), rrandint(1,Anull))

    seq=[]
    for i in range(Aeins):
        seq.append(1)

    for el in indexe:
        seq[el] = 0

    return seq


def erstelleKind(papa,mama):
    """
    Erzeugt mit Hilfe von Crossover ein Kind-String aus den beiden
    Input-Strings.
    """
    if len(papa) > len(mama):
        lang=papa
        kurz=mama
    else:
        lang=mama
        kurz=papa
    Seq=erstelleSeq(len(lang), len(kurz))

    kind=""
    for index in range(len(lang)):
        if Seq[index]:
            kind+=lang[index]
        else:
            kind+=kurz[0]
            kurz=kurz[1:]

    return str(kind)

def crossover(altGen,anz):
    neuGen=[]
    for i in range(anz):
        paar=rsample(range(len(altGen)),2)
        kind=erstelleKind(altGen[paar[0]],altGen[paar[1]])
        neuGen.append(kind)
    return neuGen



"""EVOLUTION"""
def evolution(ersteGeneration, ziel,abc,selecGewicht=[1.0,1.0,1.0],mutaAnteil=0.0):
    neueGen=ersteGeneration
    laufIndex=0.0
    while True:
        tempSelec=selektion(neueGen,ziel,selecGewicht)
        tempGen=crossover(tempSelec,len(ersteGeneration))
        neueGen=mutation(tempGen,abc,mutaAnteil)
        laufIndex+=1
        print laufIndex
        if laufIndex > 1000000:
            print "Ueberlauf!!"
            break
        if neueGen[0]==ziel:
            return laufIndex


if __name__ == "__main__":

    # erste Generation erzeugen:
    anzahl=100
    maximalL=10
    alphabet="abcdefghijklmnopqrstuvwxyz"
    Gen=zufallswoerter(anzahl,maximalL,alphabet)

    ziel="mutant"

    #Evolution
    ende=evolution(Gen,ziel,alphabet,[5.0,5.0,5.0],0.5)
    print "Das Ziel ist nach",int(ende) , "Schritten erreicht."

                

Lösung von: Uwe Hernandez Acosta (TU Dresden)

var CROWN_OF_CREATION = "MUTANTEN", // ............... zu evolutionierendes wort
    MAX_LENGTH_OF_INDIVIDUAL = CROWN_OF_CREATION.length * 2,// .. mögliche länge
    IMPORTANCE_OF_WORD_LENGTH = 1, // ................. gewichtung der wortlänge
    IMPORTANCE_OF_MATCHING_CHARS = 1, // .... gewichtung der enthaltenen zeichen
    IMPORTANCE_OF_CHAR_POSITION = 1, // ......... bedeutung der genauen position
    MAX_SIZE_OF_POPULATION = 100, // ................. höchstzahl der individuen
    PERCENTAGE_OF_MUTATIONS = 10, // ............ mutationen in einer generation
    LIMIT_OF_GENERATIONS = 3000, // ........ höchstgrenze der evolutionsschritte
    DISPLAY_EVERY_NTH_GENERATION = 10, // ... ausgabe jeder generation ohne fund
    
    generation = 0,
    population = [],
    individual = "",
    found = false,
    i, j;

function rnd(min, max) { // . zufallszahlen in bestimmtem bereich (kurznotation)
   return (Math.round((Math.random() * max) + min));
}

function rndChar() { // .......................... zufallszeichen (kurznotation)
   var c = String.fromCharCode(rnd(65, 24));
   return c;
}

function selection() { // ............................................ SELEKTION
   
   function strQuality(str) { // . . . . . . qualitätsprüfung für die sortierung
      var quality = 0, temp = 0, s = [];
      
      // qualität nach länge
      quality = 100 - (Math.abs(str.length - CROWN_OF_CREATION.length) / 
         (MAX_LENGTH_OF_INDIVIDUAL-1) * 100) * IMPORTANCE_OF_WORD_LENGTH;
      
      // qualität nach vorhandenen buchstaben 
      s = str.split("");
      for (i = 0; i <= CROWN_OF_CREATION.length; i++) {
         if (s.indexOf(CROWN_OF_CREATION[i]) > -1) {
            s.splice(s.indexOf(CROWN_OF_CREATION[i]), 1);
            temp++;
         }
         temp *= IMPORTANCE_OF_MATCHING_CHARS;
      }
      quality += (temp / CROWN_OF_CREATION.length * 100);
      
      // qualität nach buchstaben an der richtigen stelle
      temp = 0;
      for (i = 0; i < Math.min(str.length, CROWN_OF_CREATION.length); i++) 
         if (str[i] == CROWN_OF_CREATION[i]) temp++;
      temp *= IMPORTANCE_OF_CHAR_POSITION;
      quality += temp / CROWN_OF_CREATION.length * 100;
      return quality;
   }
   
   // POPULATION SORTIEREN UND DIE UNTERE HÄLFTE VERWERFEN ///////////////////// 
   population.sort(function(a, b) {
      return strQuality(b) - strQuality(a);
   });
   population = population.splice(0, Math.round(MAX_SIZE_OF_POPULATION / 2));
   /////////////////////////////////////////////////////////////////////////////
}

function crossOver() { // ............................................ CROSSOVER
   var ind1, ind2,                  // für bessere übersicht
       pl = population.length - 1;  // bremse für erbkrankheiten
   while (population.length < MAX_SIZE_OF_POPULATION) {
      ind1 = population[rnd(0, pl)]; ind2 = population[rnd(0, pl)];
      ind1 = ind1.replace(ind1[rnd(0, ind1.length-1)], 
         ind2[rnd(0, ind2.length-1)]);
      population.push(ind1);
   }
}

function mutation() { // .............................................. MUTATION
   for (
      i = 0; i <= Math.round(population.length * PERCENTAGE_OF_MUTATIONS / 100); 
      i++
   ) {
      j = rnd(0, population.length-1); 
      individual = population[j];
      switch (rnd(1,3)) {  //............. (1) ändern (2) löschen (3) hinzufügen
         case 1:  individual = 
                     individual.replace(individual[rnd(0,individual.length-1)], 
                        rndChar());
                  break;
         case 2:  if (individual.length > 1)
                  individual = 
                     individual.replace(individual[rnd(0,individual.length-1)], 
                        "");
                  break;
         case 3:  if (individual.length < MAX_LENGTH_OF_INDIVIDUAL) {
                     if (rnd(1,2) == 1) individual = rndChar() + individual; 
                     else individual += rndChar();
                  }
      }
      population[j] = individual;
   }
}

function monitor() { // ......................................... visualisierung
   var arr = [];
   // auf schöpfungskrone prüfen
   if (population.indexOf(CROWN_OF_CREATION) > -1) {
      document.write('<h1>Krone der Schöpfung gefunden!</h1>');
      found = true;
   }
   // generationen-überschreitung
   if (generation >= LIMIT_OF_GENERATIONS) {
      document.write(
         '<h2>Überschreitung der maximalen Generationenzahl</h2>'
      );
      found = true; // => abbruch
   }
   // ausgabe: generationsnummer, top 10, flop 10
   if (found || (generation % DISPLAY_EVERY_NTH_GENERATION == 0)) {
      document.write('<h2>Generation ' + generation + 
         '</h2><p><b>Top 10:</b> ');
      arr = population.slice(0, 10);
      document.write(arr.join(" ~ ") + '<br><b>Flop 10:</b> ');
      arr = population.slice(population.length-10, population.length).reverse();
      document.write(arr.join(" ~ ") + '</p>');
   }
   generation++;
}

// ********************************************************* POPULATION ERZEUGEN
for (i = 0; i < MAX_SIZE_OF_POPULATION; i++) {
   individual = "";
   for (j = 0; j < rnd(0, MAX_LENGTH_OF_INDIVIDUAL); j++)
      individual += rndChar();
   population[i] = individual;
}

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ MAIN ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
                                while (!found) 
                                     {
                                selection();
                                 monitor();
                                crossOver();
                                 mutation();
                                     }
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lissalanda@gmx.at ~ */
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)