32 lines
1.1 KiB
Python
32 lines
1.1 KiB
Python
import random
|
|
|
|
from .chromosome import Chromosome
|
|
from .node import swap_subtrees
|
|
|
|
|
|
def crossover_subtree(
|
|
parent1: Chromosome, parent2: Chromosome, max_depth: int
|
|
) -> tuple[Chromosome, Chromosome]:
|
|
"""Кроссовер поддеревьев.
|
|
|
|
Выбираются случайные узлы в каждом родителе, затем соответствующие им поддеревья
|
|
меняются местами. Если глубина результирующих хромосом превышает max_depth,
|
|
то их деревья обрезаются до max_depth.
|
|
"""
|
|
child1 = parent1.copy()
|
|
child2 = parent2.copy()
|
|
|
|
# Выбираем случайные узлы, не включая корень
|
|
if child1.root.get_depth() <= 1 or child2.root.get_depth() <= 1:
|
|
return child1, child2
|
|
|
|
cut1 = random.choice(child1.root.list_nodes()[1:])
|
|
cut2 = random.choice(child2.root.list_nodes()[1:])
|
|
|
|
swap_subtrees(cut1, cut2)
|
|
|
|
child1.prune(max_depth)
|
|
child2.prune(max_depth)
|
|
|
|
return child1, child2
|