Hoe de kubus van Rubik op te lossen met behulp van genetische algoritmen

Invoering
Als experiment besloot ik een Rubiks kubus op te lossen met behulp van genetische algoritmen (GA). Hun basisconcept is om een ​​oplossing te vinden door natuurlijke selectie en evolutie te simuleren. Over het algemeen moeten we deze stappen volgen:

Maak een populatie van beslissingsopties (meestal willekeurig gegenereerd).
Bepaal een geschiktheidsscore om te beoordelen hoe dicht een optie bij het bereiken van een doel is.
Evalueer alle oplossingsopties en sorteer ze op geschiktheid.
Bepaal de strategie van bevolkingsontwikkeling. Meestal blijven de best presterende personen behouden en worden willekeurige wijzigingen aangebracht, zoals een kleine wijziging in een oplossing of een combinatie van twee oplossingen.
Ga na het verschijnen van een nieuwe populatie verder met de zuivering en herhaal de stappen totdat er een oplossing is gevonden (ga terug naar stap 3).
Soms is de “genetische pool” niet voldoende om een ​​oplossing te vinden. In dit geval is de meest gebruikelijke benadering om de bevolking weg te vagen en opnieuw te beginnen.
Maar laten we, voordat we ingaan op de implementatiedetails, eens kijken naar de basistheorie van de Rubiks kubus.

Rubiks kubusnotatie
Afzonderlijke letters worden met de klok mee gedraaid.
De primaire rotaties zijn tegen de klok in.
Om de draairichting te bepalen, moet je direct naar de aangegeven kant kijken. Stel je voor D en D ‘bijvoorbeeld de onderkant voor je voor.
U2 is vergelijkbaar met twee rotaties van U.
Merk op dat in sommige gevallen (x, y, z) de hele kubus roteert, niet slechts één kant.
U U ’U2 D D’ D2
R R ‘R2 L L’ L2
F F ‘F2 B B’ B2
M M ’M2 E E’ E2
s S ’S2 x y z
Rubiks kubus implementatie
Facetten
Er zijn veel benaderingen om een ​​kubus weer te geven, maar ik besloot een eenvoudig woordenboek te gebruiken met zes numpy 3 × 3 matrices (één voor elk vlak):

self.faces = {
VOOR: np. Volledig ((3, 3), GROEN),
LINKS: np. Volledig ((3, 3), ORANJE),
RECHTS: np. Volledig ((3, 3), ROOD),
BOVEN: np. Volledig ((3, 3), WIT),
ONDERAAN: np. Volledig ((3, 3), GEEL),
ACHTERKANT: np. Volledig ((3, 3), BLAUW),
}
Voor de voorkant is het intuïtief duidelijk dat [0, 0] de linkerbovenhoek zal zijn. De waarden voor achter [0, 0], links [0, 0] en onder [0, 0] hangen echter af van de kant van waar je naar de kubus kijkt. De onderstaande afbeelding helpt verwarring te voorkomen. Positie [0, 0] wordt in paars aangegeven. Het patroon is consistent met hoe de rotatiemethode wordt bepaald.

Rotatie
Numpy bevat veel handige methoden, zoals rot90 en flip, die geweldig zijn voor het implementeren van kubusrotatie. Laten we R als voorbeeld analyseren:

Zoals u kunt zien, roteren we eerst de rechterkant van de matrix en veranderen vervolgens de waarden van respectievelijk de onderste, voorste, bovenste en achterste matrices.

def R (zelf):
self.faces [RIGHT] = np.rot90 (self.faces [RIGHT], axes = MET DE KLOK MEE)
# __swap_y krijgt vier waarden uit driecijferige tupels
# Elk van deze tuple bestaat uit:
# – index 0 = gezicht
# – index 1 = kolom
# – index 2 = omgekeerde waarden (boolean)
#
# Het betekent:
# – verplaats kolom “onder” 2 naar kolom “voorzijde” 2
# – verplaats kolom “front” 2 naar kolom “top” 2
# – verplaats kolom “top” 2 naar kolom “terug” 0, waarbij waarden worden omgedraaid
# – verplaats kolom “terug” 0 naar kolom “onder” 2, waarbij u de waarden omdraait
self .__ swap_y ((BOTTOM, 2, False), (FRONT, 2, False), (TOP, 2, True), (BACK, 0, True))
De enige complicatie is dat wanneer u met de achterkant werkt, u de waarden moet omkeren, zoals weergegeven in de afbeelding:

TOP [0, 2] -> BACK [2, 0]
TOP [1, 2] -> TERUG [1, 0]
TOP [2, 2] -> TERUG [0, 0]
De volledige implementatie is te zien in de broncode.

Genetisch algoritme
Bevolking creatie
Zoals hierboven vermeld, moet je voor deze simulatie een populatie van Rubiks kubus maken. We zullen de volgende scramble gebruiken van deze online scrambler.

D ‘B2 D2 L2 U’ L R ‘F L2 R2 U’ L2 B ‘L D’ B2 R2 B ‘R F U2 R B2 F’ L ‘B2 L2 R F2 L’
Overigens heb ik deze coole kubussimulator gebruikt om te experimenteren, debuggen, testcaseresultaten te controleren, afbeeldingen te maken en meer.

rubik’s cube kopen