Итак, я написал небольшую программу, цель которой — научить несколько машин (красные и синие прямоугольники) «ездить» с помощью генетического алгоритма. Он работает хорошо, и я не видел ошибок, но программа очень медленная. Поскольку я в значительной степени начинающий, я уверен, что есть множество вещей, которые можно улучшить.
Автомобили могут оставаться прямо или повернуть направо / налево на 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
```