ИИ учится управлять автомобилем (упрощенно), требуя оптимизации

Итак, я написал небольшую программу, цель которой – научить несколько машин (красные и синие прямоугольники) «ездить» с помощью генетического алгоритма. Он работает хорошо, и я не видел ошибок, но программа очень медленная. Поскольку я в значительной степени начинающий, я уверен, что есть множество вещей, которые можно улучшить.

Автомобили могут оставаться прямо или повернуть направо / налево на 1 градус. Если они касаются черной линии (называемой в программе линиями смерти), они «умирают». Обнаружение столкновения зависит от того, касаются ли две диагонали прямоугольника / автомобиля определенной линии.

Машины обозначены тремя точками и углом. Синие автомобили – это те, кто лучше всех проявил себя в предыдущем поколении.

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

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

Вот код (использует Python 3 и библиотеку Pygame):

main.py:

import pygame
import random
from neuron import Population
from car import Car

def sortBests(elem):
    return elem[1]

class Population_cars:
    def __init__(self, PopNumber,id=0,prevBest=[]):


        self.id=id

        self.initialnumber=PopNumber
        self.still_alive=PopNumber
        self.actual_score=0

        self.death_records=[]

        self.death_lines=[
            [[200, 100], [600, 100],[900, 300],[850, 600],[560, 340],[250, 340],[250,390],[480,390],[500,530],[520,350],[850, 610]],
            [[200, 250], [600, 250],[750, 300],[750, 400],[600, 290],[200, 290],[200,460],[400,460],[520,650],[560,450],[850, 650]]
        ]


        self.checkpoints=[[self.death_lines[0][i],self.death_lines[1][i]] for i in range(len(self.death_lines[0]))]

        self.brains= Population(PopNumber,[5,4,4,3],prevBest)
        self.population=[]
        for i in range(PopNumber):
            self.population.append(Car(self.brains.population[i]))
        while True:
            self.actual_score+=1

            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    pygame.quit()
                    quit()

            self.draw()

            deleted=0
            for i in range(len(self.population)):
                car=self.population[i-deleted]

                car.advance_car()

                car.takeDecision(self.death_lines)

                if car.detectCollision(self.death_lines,self.checkpoints):
                    self.death_records.append((car.brain,car.fitness(self.checkpoints)))
                    self.still_alive-=1
                    self.population.pop(i-deleted)
                    deleted+=1

            if self.still_alive==0:
                self.nextGeneration()



            pygame.display.flip()

    def draw(self, color_car=(255, 0, 0)):
        global screen
        screen.fill((255, 255, 255))
        for car in self.population:
            if not car.isAlive:
                continue
            full_car = car.positions.copy()
            last_x = full_car[2][0] + (full_car[0][0] - full_car[1][0])
            last_y = full_car[2][1] + (full_car[0][1] - full_car[1][1])
            full_car.append([last_x, last_y])
            pygame.draw.polygon(screen, color_car, full_car, 0)
            #pygame.draw.circle(screen,[0,0,0],tuple(map(int,car.getCenter())),100,1)
        for death_line in self.death_lines:
            for i in range(len(death_line) - 1):
                pygame.draw.line(screen, [0, 0, 0], death_line[i], death_line[i+1], 3)
        for check_line in self.checkpoints:
            pygame.draw.line(screen, [100, 200, 100], check_line[0], check_line[1], 1)



    def nextGeneration(self):
        global pop
        self.death_records.sort(key=sortBests)
        thisBests = self.death_records[-5:]
        print(thisBests)
        pop=Population_cars(self.initialnumber,self.id+1,thisBests)










        # --------------------------------------------------------------------------------------------------



WINDOW_WIDTH = 1500
WINDOW_HEIGHT = 750
WINDOW_SIZE = [WINDOW_WIDTH, WINDOW_HEIGHT]


pygame.init()
screen = pygame.display.set_mode(WINDOW_SIZE)
pygame.display.set_caption("Car AI")

pop=Population_cars(100)

car.py:

import math

def ccw(A, B, C):
    return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])


def intersect(A, B, C, D):
    return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)


def point_intersect(A, B, C, D):
    first_vector = (B[0] - A[0], B[1] - A[1])
    second_vector = (D[0] - C[0], D[1] - C[1])

    dist_x = (A[0] - C[0]) / (second_vector[0] - first_vector[0])
    dist_y = (A[1] - C[1]) / (second_vector[1] - first_vector[1])

    x = A[0] + first_vector[0] * dist_x
    y = A[1] + first_vector[1] * dist_y
    return (x, y)

def dist_intersect(A, B, C, D,reach):
    if not intersect(A,B,C,D):
        #print("flag",A,B,C,D)
        return 1

    first_vector = (B[0] - A[0], B[1] - A[1])
    second_vector = (D[0] - C[0], D[1] - C[1])


    dist_x = (A[0] - C[0]) / (second_vector[0] - first_vector[0])
    dist_y = (A[1] - C[1]) / (second_vector[1] - first_vector[1])

    x = first_vector[0] * dist_x
    y = first_vector[1] * dist_y

    output = (x**2+y**2)**0.5

    return 1-output/reach-0.1

class Car:
    def __init__(self,brain):
        #self.positions=[[300, 300], [300, 360], [320, 360]]
        #self.positions=[[200, 160], [200, 220], [220, 220]]
        self.positions=[[260, 160], [260, 180], [200, 180]]
        self.angle=0
        self.isAlive=True
        self.brain=brain

        self.checkpoints_passed=1

    def getCenter(self):
        return [(self.positions[0][0] + self.positions[2][0]) / 2, (self.positions[0][1] + self.positions[2][1]) / 2]
    def advance_car(self, speed=1):
        advance_x = math.cos(math.radians(self.angle))
        advance_y = math.sin(math.radians(self.angle))
        # print(angle,advance_x,advance_y)
        for point in self.positions:
            point[0] += advance_x * speed
            point[1] -= advance_y * speed

    def turn_car(self,turn):
        self.angle-=turn
        center = self.getCenter()
        for i in self.positions:
            i[0] -= center[0]
            i[1] -= center[1]

            i[0] = i[0] * math.cos(math.radians(turn)) - i[1] * math.sin(math.radians(turn))
            i[1] = i[0] * math.sin(math.radians(turn)) + i[1] * math.cos(math.radians(turn))

            i[0] += center[0]
            i[1] += center[1]

    def detectCollision(self, death_lines, checklines):
        last_x = self.positions[2][0] + (self.positions[0][0] - self.positions[1][0])
        last_y = self.positions[2][1] + (self.positions[0][1] - self.positions[1][1])

        nextCheck=checklines[self.checkpoints_passed]
        if intersect(self.positions[0], self.positions[2], nextCheck[0], nextCheck[1]) or intersect(self.positions[1], (last_x,last_y), nextCheck[0], nextCheck[1]):
            self.checkpoints_passed+=1
        for death_line in death_lines:
            if self.checkpoints_passed>1:
                intersect_prev=intersect(self.positions[0], self.positions[1], death_line[self.checkpoints_passed-2], death_line[self.checkpoints_passed-1]) or intersect(self.positions[2], (last_x,last_y), death_line[self.checkpoints_passed-2], death_line[self.checkpoints_passed-1])
            else:
                intersect_prev=False
            intersect_next=intersect(self.positions[0], self.positions[1], death_line[self.checkpoints_passed-1], death_line[self.checkpoints_passed]) or intersect(self.positions[2], (last_x,last_y), death_line[self.checkpoints_passed-1], death_line[self.checkpoints_passed])
            if intersect_next or intersect_prev:
                self.isAlive=False
                self.deathPoint=self.positions[0]
                return True
        return False

    def range_points(self,leng):
        center=self.getCenter()
        output=[]

        for i in range(-2,3):
            ang=self.angle+i*30
            x,y=math.cos(math.radians(ang))*leng , math.sin(math.radians(ang))*leng
            output.append((int(center[0]+x),int(center[1]-y)))

        return output
    def collision_distances(self,death_lines,reach):
        center=self.getCenter()
        #print(self.range_points())
        out=[]
        for A in self.range_points(reach):
            add=1
            for death_line in death_lines:
                for i in range(len(death_line)-1):
                    add=min(add,dist_intersect(A,center,death_line[i],death_line[i+1],reach))
            out.append(add)
        return out

    def takeDecision(self,death_lines=None,reach=100):

        data=self.collision_distances(death_lines,reach)
        decision=self.getMaxResult(self.brain.feedAll(data))
        if decision==1:
            self.turn_car(1)
        elif decision==2:
            self.turn_car(-1)

    def fitness(self,checkpoints):
        line_to_reach=checkpoints[self.checkpoints_passed]
        point_to_reach=((line_to_reach[0][0]+line_to_reach[1][0])/2,(line_to_reach[0][1]+line_to_reach[1][1])/2)

        distance_to_point=((point_to_reach[0]-self.deathPoint[0])**2+(point_to_reach[1]-self.deathPoint[1])**2)**0.5

        #print(self.checkpoints_passed , distance_to_point, (self.checkpoints_passed*10)**2-distance_to_point*10)
        return (self.checkpoints_passed*1000)-distance_to_point
    def getMaxResult(self,results):
        return results.index(max(results))

нейрон.py:

import random
import math
import copy
"""
def sigmoid(x):
    return .5 * (math.tanh(.5 * x) + 1)"""
def sigmoid(x):
    if x<-100:
        return 0
    if x>100:
        return 1
    return 1 / (1 + math.exp(-4.9*x))

class Neuron:
    def __init__(self,num_outputs, neuronindex,weights=[]):
        self.outputWeights=[]
        self.neuronIndex= neuronindex

        for i in range(num_outputs):
            if i<len(weights):
                self.outputWeights.append(weights[i])
            else:
                self.outputWeights.append(random.uniform(-1,1))
    def getOutputWeight(self,i):
        return self.outputWeights[i]
    def getOutputFromInputs(self,inputs,inputWeights):
        output=0
        for i in range(len(inputWeights)):
            output+=inputs[i]*inputWeights[i]
        if output<-200:
            print(inputs,inputWeights)
        return sigmoid(output)
class Net:
    def __init__(self,topology=[],model=False):
        self.topolgy = topology
        if model!=False:
            self.layers=model.layers.copy()
        else:
            self.layers=[]
            for i in range(len(topology)-1):
                layer=[]
                numOutputs=topology[i+1]
                for neuronNum in range(topology[i]):
                    layer.append(Neuron(numOutputs,neuronNum))
                self.layers.append(layer)
            layer = []
            for i in range(topology[-1]):
                layer.append(Neuron(0,i))
            self.layers.append(layer)
    def feedLayer(self,inputs,layerNum):
        layer=self.layers[layerNum]
        outputs=[]
        for i in range(len(layer)):
            neuronWeights=[]
            for a in self.layers[layerNum-1]:
                neuronWeights.append(a.getOutputWeight(i))
            outputs.append(layer[i].getOutputFromInputs(inputs,neuronWeights))
        return outputs
    def feedAll(self,inputs):
        prevOutputs=inputs.copy()
        for i in range(1,len(self.layers)):
            prevOutputs=self.feedLayer(prevOutputs,i)
        return prevOutputs
class Population:
    def __init__(self,PopNumber,topology=[],bestResults=[]):
        self.topology=topology
        if len(bestResults)>=1:
            self.population=[]
            for i,score in bestResults:
                self.population.append(copy.deepcopy(i))
            prev_brains=[item[0] for item in bestResults]
            prev_results=[item[1] for item in bestResults]
            num_mutate=PopNumber-len(bestResults)
            random_chosen=random.choices(population=prev_brains, weights=prev_results, k=num_mutate)
            for addNet in random_chosen:
                mutation = self.mutate(addNet)
                self.population.append(mutation)
            for i in range(PopNumber-num_mutate-len(bestResults)):
                combination=self.combine(random.sample(bestResults, 2))
                self.population.append(combination)


        else:
            self.population=[]
            for i in range(PopNumber):
                self.population.append(Net(self.topology))

    def choose(self,options):
        output=[]
        numChosen=random.randint(1,len(options))
        for i in range(numChosen):
            output.append(options[random.randint(0,len(options)-1)])
        return output

    def combine(self,chosen):
        output= copy.deepcopy(chosen[0])
        for layer in range(len(output.layers)-1):
            for neuron in range(len(output.layers[layer])):
                for weight in range(self.topology[layer+1]):
                    if random.randint(0,10)>=5:
                        output.layers[layer][neuron].outputWeights[weight]=copy.copy(chosen[1].layers[layer][neuron].outputWeights[weight])
        return output
    def mutate(self,chosen):
        output=copy.deepcopy(chosen)
        for layer in output.layers[:-1]:
            for neuron in layer:
                for weight in range(len(neuron.outputWeights)):
                    rand=random.randint(1,10)
                    if rand==1:
                        neuron.outputWeights[weight]=random.uniform(-1,1)
                    else:
                        neuron.outputWeights[weight] += random.gauss(0,1)/50
                        if neuron.outputWeights[weight]>1:
                            neuron.outputWeights[weight]=1
                        elif neuron.outputWeights[weight]<-1:
                            neuron.outputWeights[weight]=1
        return output

```

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *