I cannot to get a right answer with genetic algorithm in python

Question

i'm trying to write a simple generation algorithm with python, which should give to me asnwer "Hello World". It's work fine, but it cannot give me corect answer with "max iteration" constant. It just works in infinite loop.

Here is my code belowe:

import random

class GAHello():
    POPULATION_SIZE = 1000
    ELITE_RATE = 0.1
    SURVIVE_RATE = 0.5
    MUTATION_RATE = 0.2
    TARGET = "Hello World!"
    MAX_ITER = 1000

    def InitializePopulation(self):
        tsize: int = len(self.TARGET)
        population = list()

        for i in range(0, self.POPULATION_SIZE):
            str = ''
            for j in range(0, tsize):
                str += chr(int(random.random() * 255))

            citizen: Genome = Genome(str)
            population.append(citizen)
        return population

    def Mutation(self, strng):
        tsize: int = len(self.TARGET)
        ipos: int = int(random.random() * tsize)
        delta: chr = chr(int(random.random() * 255))

        return strng[0: ipos] + delta + strng[ipos + 1:]

    def mate(self, population):
        esize: int = int(self.POPULATION_SIZE * self.ELITE_RATE)
        tsize: int = len(self.TARGET)

        children = self.select_elite(population, esize)

        for i in range(esize, self.POPULATION_SIZE):
            i1: int = int(random.random() * self.POPULATION_SIZE * self.SURVIVE_RATE)
            i2: int = int(random.random() * self.POPULATION_SIZE * self.SURVIVE_RATE)
            spos: int = int(random.random() * tsize)

            strng: str = population[i1][0: spos] + population[i2][spos:]
            if(random.random() < self.MUTATION_RATE):
                strng = self.Mutation(strng)

            child = Genome(strng)
            children.append(child)

        return children

    def go(self):
        popul = self.InitializePopulation()

        for i in range(0, self.MAX_ITER):
            popul.sort()
            print("{} > {}".format(i, str(popul[0])))

            if(popul[0].fitness == 0):
                break
            popul = self.mate(popul)

    def select_elite(self, population, esize):
        children = list()
        for i in range(0, esize):
            children.append(population[i])

        return children



class Genome():
    strng = ""
    fitness = 0

    def __init__(self, strng):
        self.strng = strng
        fitness = 0
        for j in range(0, len(strng)):
            fitness += abs(ord(self.strng[j]) - ord(GAHello.TARGET[j]))

        self.fitness = fitness

    def __lt__(self, other):
        return self.fitness - other.fitness

    def __str__(self):
        return "{} {}".format(self.fitness, self.strng)

    def __getitem__(self, item):
        return self.strng[item]

Thank you for an advice. I am realy noob and such things and i just training and experiment with such algorithms and optimization things to explore an ai methods.

UPDATE

The place, where it runs

if __name__ == '__main__':
    algo = GAHello()
    algo.go()

My output:

0 > 1122 Ü<pñsÅá׺Ræ¾
1 > 1015  ÷zËÔ5AÀ©«
2 > 989 "ÆþõZi±Pmê
3 > 1076 ­ ØáíAÀ©«
4 > 1039 #ÆþÕRæ´Ìosß
5 > 946 ×ZÍG¤'ÒÙË
6 > 774 $\àPÉ
7 > 1194 A®Ä§ö
ÝÖ Ð
8 > 479 @r=q^Ü´{J
9 > 778 X'YþH_õÏÆ
10 > 642 z¶$oKÐ{
...
172 > 1330 ê¸EïôÀ«ä£ü
173 > 1085 ÔOÕÛ½e·À×äÒU
174 > 761 OÕÛ½¤¯£+} 
175 > 903 P½?-´ëÎm|4Ô
176 > 736 àPSÈe<1
177 > 1130 ªê/*ñ¤îã¹¾^
178 > 772 OÐS8´°jÓ£
...
990 > 1017 6ó¨QøÇ?¨Úí
991 > 1006 |5ÇÐR·Ü¸í
992 > 968 ×5QÍË?1V í
993 > 747 B ªÄ*¶R·Ü$F
994 > 607  `ªLaøVLº
995 > 744 Ìx7eøi;ÄÝ[
996 > 957 ¹8/ñ^ ¤
997 > 916 Ú'dúý8}û« [
998 > 892 ÛWòeTùv­6ç®
999 > 916 õg8g»}à³À

And sample output, that should be:

0 > 419 Un~?z^Kr??p┬
1 > 262 Un~?z^Kr?j?↨
2 > 262 Un~?z^Kr?j?↨
…
15 > 46 Afpdm'Ynosa"
16 > 46 Afpdm'Ynosa"
17 > 42 Afpdm'Ynoia"
18 > 27 Jfpmm↓Vopoa"
…
33 > 9 Ielmo▼Wnole"
34 > 8 Ielmo▲Vopld"
35 > 8 Ielmo▲Vopld"
…
50 > 1 Hello World"
51 > 1 Hello World"
52 > 0 Hello World!

Answer 1

Your list sort is your main problem here I believe.

popul.sort()

Try

popul.sort(key=lambda x: x.fitness)

That will sort them by their fitness levels, which is what I believe you intended.

I also changed all the int(random.random()*255) to random.randint(30, 125) to only get valid characters because I was having trouble running.