การค้นหาเส้นทาง Genetic Algorithm

Oct 01 2020

เพื่อให้คุ้นเคยกับคลาสใน Python มากขึ้นฉันได้เขียนอัลกอริทึมทางพันธุกรรมซึ่งใช้ระดับโดยมีจุดเริ่มต้นและจุดสิ้นสุดและค้นหาเส้นทาง (ไม่จำเป็นต้องเป็นเส้นทางที่ดีที่สุด) ผลลัพธ์จะแสดงระดับพื้นฐานและเมื่อพบโซลูชันระดับที่มีเส้นทาง:

Level:
############
O....#.....#
#.#.#.#.#..#
#........#.O
############

Solution:
############
O*...#.****#
#*#*#*#*#**#
#********#**
############

ฉันสนใจที่จะปรับปรุงโครงสร้างของโค้ด (เช่นไม่ใช่ของอัลกอริทึมเองก็ต่อเมื่อมีข้อผิดพลาด) เนื่องจากฉันต้องการปรับปรุงความรู้ทั่วไปเกี่ยวกับการเขียนโปรแกรมใน Python

มีปัญหาบางอย่างที่ฉันทราบ:

พารามิเตอร์ในตอนต้นสามารถเขียนเป็น enums ได้ แต่ฉันไม่สามารถมั่นใจได้ว่าตัวเองจะได้เปรียบอะไร (นอกเหนือจากการสร้างมลพิษให้กับเนมสเปซทั่วโลก) ฉันคิดว่าวิธีการเขียน "N" หรือ "WALL" ที่กระชับกว่าแทนที่จะเป็น เพิ่ม "Direction.N" หรือ "Object.Wall" เพื่อให้อ่านโค้ดได้ง่ายขึ้น
คลาส "ระดับ": โดยหลักการแล้วฉันต้องการให้แอตทริบิวต์เป็นแบบอ่านอย่างเดียว แต่ฉันไม่แน่ใจว่าจะกำหนดอย่างไรให้ถูกต้อง นอกจากนี้ฉันไม่เห็นประเด็นในการเขียน getters และ setters ที่นี่
ในคลาสเดียวกันฉันไม่ต้องการเขียน __move_dict และ __text_map สองครั้งใน test_route และ print_route ดังนั้นฉันจึงกำหนดเป็นตัวแปรคลาส ฉันไม่แน่ใจว่านี่เป็นสำนวนหรือไม่
ในทำนองเดียวกัน test_route และ print_route ใช้รหัสเดียวกัน ฉันคิดว่ามันจะเป็นไปได้ไหมที่จะแยกวงรอบทั่วไปออกไป แต่ฉันไม่รู้ว่าจะทำอย่างไรใน Python

""""Simple implementation of a genetic algorithm:
    Searching for a possible route from a given start point
    to an end point."""
import random
from dataclasses import dataclass
from typing import List
from collections import namedtuple
from operator import attrgetter

# PARAMETERS
# direction constants
N = 0
E = 1
S = 2
W = 3

# level constants
EMPTY = 0
WALL = 1
DOOR = 2

L1 = [[WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL],
      [DOOR, EMPTY, EMPTY, EMPTY, EMPTY, WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL],
      [WALL, EMPTY, WALL, EMPTY, WALL, EMPTY, WALL, EMPTY, WALL, EMPTY, EMPTY, WALL],
      [WALL, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, WALL, EMPTY, DOOR],
      [WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL]]

L1_WIDTH = 12
L1_HEIGHT = 5

# DATATYPES
Point = namedtuple("Point", "x y")


@dataclass
class Level:
    """Class for representing a level with a start and end point."""
    map: list
    width: int
    height: int
    start: Point
    end: Point

    __move_dict = {N: Point(0, 1),
                   E: Point(1, 0),
                   S: Point(0, -1),
                   W: Point(-1, 0)}

    __text_map = {WALL: "#", EMPTY: ".", DOOR: "O"}

    def test_route(self, genome):
        """Test a route encoded in a genome and return the final distance to the exit."""
        def distance(point_a, point_b):
            return abs(point_a.x - point_b.x) + abs(point_a.y - point_b.y)

        position = self.start

        for gene in genome.genes:
            delta = self.__move_dict[gene]

            new_pos = Point(position.x + delta.x,
                            position.y + delta.y)

            if 0 <= new_pos.x < self.width:
                if 0 <= new_pos.y < self.height:
                    if self.map[new_pos.y][new_pos.x] != WALL:
                        position = new_pos

            if position == self.end:
                break

        return 1 / (1 + distance(position, self.end))

    def print_level(self):
        """Print a text representation of a level."""
        for row in self.map:
            print("".join((self.__text_map[elem] for elem in row)))

    def print_route(self, genome):
        """Print the route through the level."""
        text_level = []

        for row in self.map:
            text_level.append([self.__text_map[elem] for elem in row])

        position = self.start

        for gene in genome.genes:
            delta = self.__move_dict[gene]

            new_pos = Point(position.x + delta.x,
                            position.y + delta.y)

            if 0 <= new_pos.x < self.width:
                if 0 <= new_pos.y < self.height:
                    if self.map[new_pos.y][new_pos.x] != WALL:
                        position = new_pos
                        text_level[new_pos.y][new_pos.x] = "*"

            if position == self.end:
                break

        for row in text_level:
            print("".join(row))


@dataclass
class Genome:
    """Class for representing the genome of running through a level."""
    fitness: float
    genes: List[int]


class GenomePool:
    """Class implementing the genetic algorithm."""
    def __init__(self, level, pool_size, num_genes, crossover_rate, mutation_rate):
        self.__level = level
        self.__pool_size = pool_size
        self.__num_genes = num_genes
        self.__crossover_rate = crossover_rate
        self.__mutation_rate = mutation_rate

        self.__pool = [Genome(0, [random.randint(0, 3) for i in range(0, num_genes)])
                       for _ in range(self.__pool_size)]
        self.__update_fitness()

    def __select_genome(self):
        """Do a roulette wheel selection and return a genome."""
        total_fitness = sum((genome.fitness for genome in self.__pool))

        cut = random.uniform(0, total_fitness)
        partial_fitness = 0
        idx = 0

        while partial_fitness < cut:
            partial_fitness += self.__pool[idx].fitness
            idx += 1

        return self.__pool[idx] if idx < len(self.__pool) else self.__pool[self.__pool_size - 1]

    def __crossover(self, mother, father):
        """Do a crossover of two genomes and return an offspring."""
        if random.random() > self.__crossover_rate:
            return mother

        crossover_point = int(random.uniform(0, self.__num_genes))

        offspring = Genome(0, [])
        offspring.genes = mother.genes[0:crossover_point] + father.genes[crossover_point:]

        return offspring

    def __mutate(self, genome):
        for i in range(self.__num_genes):
            if random.random() < self.__mutation_rate:
                genome.genes[i] = int(round(random.uniform(0, 3)))

    def __update_fitness(self):
        """Update the fitness score of each genome."""
        for genome in self.__pool:
            genome.fitness = self.__level.test_route(genome)

    def get_best_genome(self):
        """Return the genome with the best fitness."""
        sorted_pool = sorted(self.__pool, key=attrgetter("fitness"), reverse=True)

        return sorted_pool[0]

    def run(self, verbose=False):
        """Run the genetic algorithm until a solution has been found."""
        iteration = 0

        while all((x.fitness != 1 for x in self.__pool)):
            if verbose:
                best_fitness = self.get_best_genome().fitness
                print(f"Iteration {iteration}: Best fitness = {best_fitness}")

            iteration += 1
            self.step()

    def step(self):
        """Run one time step of the evolution."""
        new_pool = []

        for i in range(self.__pool_size):
            mother = self.__select_genome()
            father = self.__select_genome()

            offspring = self.__crossover(mother, father)
            self.__mutate(offspring)

            new_pool.append(offspring)

        self.__pool = new_pool

        self.__update_fitness()


def main():
    level_one = Level(L1, L1_WIDTH, L1_HEIGHT, start=Point(0, 1),
                      end=Point(11, 3))
    print("Level:")
    level_one.print_level()

    genome_pool = GenomePool(level_one, pool_size=30, num_genes=70,
                         crossover_rate=0.7, mutation_rate=0.01)
    genome_pool.run()

    print()
    print("Solution:")
    level_one.print_route(genome_pool.get_best_genome())


if __name__ == "__main__":
    main()

คำตอบ

5 G.Sliepen Oct 04 2020 at 18:27

คำตอบสำหรับคำถามของคุณ

พารามิเตอร์ในตอนต้นสามารถเขียนเป็น enums ได้ แต่ฉันไม่สามารถมั่นใจได้ว่าตัวเองจะได้เปรียบอะไร (นอกเหนือจากการสร้างมลพิษให้กับเนมสเปซทั่วโลก) ฉันคิดว่าวิธีการเขียน "N" หรือ "WALL" ที่กระชับกว่าแทนที่จะเป็น เพิ่ม "Direction.N" หรือ "Object.Wall" เพื่อให้อ่านโค้ดได้ง่ายขึ้น

โดยทั่วไป Enums เป็นความคิดที่ดีเนื่องจากมีคุณสมบัติที่ดี โดยเฉพาะอย่างยิ่งพวกเขาอยู่ในคลาสที่แตกต่างกันและคุณไม่สามารถเปรียบเทียบ enum กับสิ่งที่ไม่ใช่ enum โดยบังเอิญได้ ยกตัวอย่างเช่นในรหัสของคุณทั้งสองEและWALLเป็นเพียง1เพื่อE == WALLจะส่งผลTrueที่ไม่ได้เป็นสิ่งที่คุณคาดหวัง ดังนั้นฉันจะใช้ enums ที่นี่อย่างแน่นอน

ตอนนี้คุณคิดถูกแล้วที่การใช้ enums ทำให้เกิดรหัส verbose มากขึ้น แต่คุณยังสามารถสร้างตัวแปรด้วยชื่อสั้น ๆ ที่คุณกำหนด enums ให้และได้รับสิ่งที่ดีที่สุดจากทั้งสองโลก ตัวอย่างเช่น:

class Tile(enum.Enum):
    EMPTY = 0
    WALL = 1
    DOOR = 2

EMPTY = Tile.EMPTY
WALL = Tile.WALL
DOOR = Tile.DOOR

L1 = [[WALL, WALL, ...], [DOOR, EMPTY, ...], ...]

โปรดทราบว่า enums ใน Python ไม่ต้องการให้คุณมีค่าตัวเลขคุณสามารถทำสิ่งต่อไปนี้:

class Direction(enum.Enum):
    N = Point(0, 1)
    E = Point(1, 0)
    S = Point(0, -1)
    W = Point(-1, 0)

class Tile(enum.Enum):
    EMPTY = "."
    WALL = "#"
    DOOR = "O"

นี้จากนั้นจะหลีกเลี่ยงความจำเป็นสำหรับและ__move_dict__text_map

คลาส "ระดับ": โดยหลักการแล้วฉันต้องการให้แอตทริบิวต์เป็นแบบอ่านอย่างเดียว แต่ฉันไม่แน่ใจว่าจะกำหนดอย่างไรให้ถูกต้อง นอกจากนี้ฉันไม่เห็นประเด็นในการเขียน getters และ setters ที่นี่

ดูคำถามนี้เพื่อหาคำตอบที่เป็นไปได้

ในคลาสเดียวกันฉันไม่ต้องการเขียน __move_dict และ __text_map สองครั้งใน test_route และ print_route ดังนั้นฉันจึงกำหนดเป็นตัวแปรคลาส ฉันไม่แน่ใจว่านี่เป็นสำนวนหรือไม่

นี่มันสมบูรณ์ดี! การหลีกเลี่ยงการทำซ้ำเป็นสิ่งสำคัญมากในการทำให้โค้ดของคุณรัดกุมและดูแลรักษาได้

ในทำนองเดียวกัน test_route และ print_route ใช้รหัสเดียวกัน ฉันคิดว่ามันจะเป็นไปได้ไหมที่จะแยกวงรอบทั่วไปออกไป แต่ฉันไม่รู้ว่าจะทำอย่างไรใน Python

คุณสามารถสร้างเครื่องกำเนิดไฟฟ้าที่วนซ้ำบนเส้นทางและแต่ละจุดจะให้ตำแหน่งของจุดนั้น จากนั้นคุณสามารถใช้สิ่งนั้นเพื่อลดความซับซ้อนของลูปเข้าtest_route()และทำprint_route()ดังนี้:

def visit_route(self):
     ...
     for gene in genome.genes:
         ...
         position = new_pos
         yield position

def test_route(self, genome):
    last_position = self.start

    for position in self.visit_route():
        last_position = position

    return 1 / (1 + distance(last_position, self.end))

def print_route(self):
    text_level = [[self.__text_map[elem] for elem in row] for row in self.map]

    for position in self.visit_route():
        text_level[position.y][position.x] = "*")

    for row in text_level:
        print ("".join(row))

หลีกเลี่ยงการจัดเก็บข้อมูลที่ซ้ำซ้อน

คุณclass Levelร้านค้าwidthและheightแต่ข้อมูลนี้มีอยู่แล้วในmap: heightควรจะเท่ากับlen(map)และควรจะเท่ากับwidth len(map[0])แม้ว่าบางครั้งอาจมีเหตุผลในการเก็บสำเนาข้อมูลที่มีราคาแพงในการคำนวณ แต่ข้อเสียคือคุณต้องแน่ใจว่าข้อมูลมีความสอดคล้องกัน จะเกิดอะไรขึ้นถ้าฉันสร้างLevel([[EMPTY]], 100, 100)?

ในทำนองเดียวกันจะเกิดอะไรขึ้นถ้าstart_pointและend_pointไม่ตรงกับตำแหน่งที่DOORอยู่ในmap? อันนี้อาจจะยุ่งยากกว่า พิจารณาการสร้างตัวสร้างสำหรับclass Levelการตรวจสอบว่าไม่ว่าพารามิเตอร์ที่กำหนดมีความสอดคล้องหรือมีมันจะได้รับมาwidth, height, start_pointและจากend_pointmap

2 user985366 Oct 04 2020 at 19:20

การเป็นตัวแทน

############
O....#.....#
#.#.#.#.#..#
#........#.O
############

ฉันจะพบว่าการแสดงระดับนี้สามารถอ่านได้มากขึ้นหากพื้นที่ว่างถูกพิมพ์เป็นช่องว่าง แทนที่จะเป็น.

############
O    #     #
# # # # #  #
#        # O
############

ในโค้ดฉันจะใช้การแทนค่าเดียวกันกับอินพุตของโปรแกรมดังนั้นแทนที่จะเป็นแบบนี้

L1 = [[WALL, WALL, WALL, WALL, WALL,

คุณสามารถกำหนด

L1 = [
"############",
"O    #     #",
"# # # # #  #",
"#        # O",
"############",
]

จากนั้นคุณจะปล่อยให้ฟังก์ชันบางอย่างแปลสิ่งนั้นเป็นตรรกะภายในที่คุณต้องการสำหรับอัลกอริทึมของคุณ

ฉันจะเปลี่ยนสัญลักษณ์สำหรับเส้นทางที่เดินทางจาก*ไปเป็นอย่างอื่นที่ง่ายต่อการแยกแยะจาก#ผนังที่ใช้ บางทีอาจเปลี่ยนผนังด้วย

รหัส

if 0 <= new_pos.x < self.width:
    if 0 <= new_pos.y < self.height:
        if self.map[new_pos.y][new_pos.x] != WALL:
            position = new_pos

สิ่งนี้ไม่ผิด แต่โดยปกติจะเขียนโดยใช้andแทน ifs ที่ซ้อนกันหลาย ๆ อันเมื่อคุณไม่จำเป็นต้องใช้elseเคสหรือตัวเลือกอื่น ๆ