如何解决禅园问题中遗传算法的局部最优停滞问题？

云上老周

2026-6-17

禅园问题遗传算法局部最优突破方案

问题背景

我用遗传算法求解禅园问题时陷入了局部最优困境，无论增加迭代代数或种群规模，算法都无法找到可行解。尝试调整突变概率、更换选择策略后，仍无法突破瓶颈，相关实现代码如下：

import random

class ZenGarden:
    def __init__(self, width, height, rocks):
        self.width = width
        self.height = height
        self.rock_count = len(rocks)
        self.base_grid = [[0] * width for _ in range(height)]  # Initialize a base grid

        # Place rocks in the base grid as -1
        for x, y in rocks:
            self.base_grid[y][x] = -1

        self.grid = self.copy_garden()
        self.max_fitness = width * height - len(rocks)

        # Place rocks in the garden as -1
        for x, y in rocks:
            self.grid[y][x] = -1  # -1 represents a rock

    def copy_garden(self):
        """Create a copy of the garden grid for each genome."""
        return [row[:] for row in self.base_grid]

    def display_garden(self, grid=None):
        """Display the garden grid."""
        if grid is None:
            grid = self.grid
        for row in grid:
            print(" ".join(f"{' K ' if cell == -1 else f'{cell:3}'}" for cell in row))
        print()

class Gene:
    def __init__(self, garden):
        # Choose a random edge to start from
        width = garden.width
        height = garden.height
        edge = random.randrange(garden.width + garden.width + garden.height +garden.height)

        # Starting from the top edge
        if edge < width:
            self.start = (0, edge)
            self.direction = 'down'

        # Starting from the bottom edge
        elif width <= edge < height + width :
            self.start = (edge - width, width - 1)
            self.direction = 'left'

        # Starting from the left edge
        elif width + height <= edge < width + width + height:
            self.start = (height - 1, 2 * width + height - edge - 1)
            self.direction = 'up'

        # Starting from the right edge
        else:
            self.start = (2 * (height + width) - edge - 1, 0)
            self.direction = 'right'

        self.generate_rotation()

    def generate_rotation(self):
        self.rotation = [
            int(a) for a in bin(random.randrange(1024))[2:].zfill(10)
        ]

class Genome:
    def __init__(self, garden, initialize = True):
        self.original_garden = garden  # Keep a reference to the original garden
        self.garden = ZenGarden(garden.width, garden.height, [(x, y) for y in range(garden.height) for x in range(garden.width) if garden.base_grid[y][x] == -1])
        self.fitness = 0
        self.genes = []

        if initialize:
            for _ in range(garden.width + garden.height + garden.rock_count):
                gene = Gene(self.original_garden)  # Pass the reference to original garden
                self.genes.append(gene)
            self.rake()
            
    def rake(self):
        """Use each gene to rake the garden and calculate fitness."""
        g = self.garden
        monk_id = 0  # Start monk ID from 1

        # Go through each gene (monk)
        for gene in self.genes:
            pos = list(gene.start)  # Current position of the monk
            direction = gene.direction  # The direction the monk is moving in
            ri = 0  # Rotation index

            if g.grid[pos[0]][pos[1]] !=0:
                continue
            monk_id +=1

            # Start raking cells
            while True:
                # If the cell is a rock (-1), stop raking
                g.grid[pos[0]][pos[1]] = monk_id

                if direction == 'up':
                    pos[0] -= 1
                elif direction == 'down':
                    pos[0] += 1
                elif direction == 'left':
                    pos[1] -= 1
                else:
                    pos[1] += 1
                
                if pos[0] not in range(g.height) or pos[1] not in range(g.width):
                    break

                if g.grid[pos[0]][pos[1]] == 0:
                    continue

                # 遇到障碍物则退回
                if direction == 'up':
                    pos[0] += 1
                elif direction == 'down':
                    pos[0] -= 1
                elif direction == 'left':
                    pos[1] += 1
                else:
                    pos[1] -= 1

                # 选择其他可行单元格
                if direction == 'up' or direction == 'down':
                    n = (
                        [pos[0], pos[1] - 1],
                        [pos[0], pos[1] + 1],
                    )
                else:
                    n = (
                        [pos[0] - 1, pos[1]],
                        [pos[0] + 1, pos[1]],
                    )
                nv = []
                for p in n:
                    try:
                        nv.append(g.grid[p[0]][p[1]])
                    except IndexError:
                        nv.append('e')

                # 只有一个未耙单元格则选择它
                if nv.count(0) == 1:
                    pos = n[nv.index(0)]

                # 有两个未耙单元格则选择一个
                elif nv.count(0) == 2:
                    # 创建方向到n索引的映射
                    direction_map = {
                    'up': 0,    # 'up'选择n的第一个元素
                    'down': 1,  # 'down'选择n的第二个元素
                    'left': 0,  # 'left'选择n的第一个元素
                    'right': 1  # 'right'选择n的第二个元素
                    }

                    # 使用direction_map获取正确索引
                    pos = n[direction_map[gene.direction]]
                    ri += 1
                    if ri == len(gene.direction):
                        ri = 0

                # 没有未耙单元格则停止
                else:
                    # 如果在地图中间卡住，无法继续处理后续基因
                    if 'e' not in nv:
                        self.set_fitness()
                        return
                    break

                # 设置新的移动方向
                if direction in ('up', 'down'):
                    direction = 'left' if n.index(pos) == 0 else 'right'
                else:
                    direction = 'up' if n.index(pos) == 0 else 'down'

            self.set_fitness()

    def set_fitness(self):
        """Calculate the fitness as the number of raked cells."""
        self.fitness = sum(1 for x in sum(self.garden.grid, []) if x > 0 )  # Count only raked cells

    def crossover(self, other):
        """Create a new genome by crossing over genes from two parents."""
        new = Genome(self.original_garden)

        # 随机选择交叉类型
        p = random.random()
        if p < 0.30:
            # 单点交叉：从第一个父本取前半，第二个父本取后半
            point = random.randrange(len(self.genes))
            new.genes = self.genes[:point] + other.genes[point:]
        elif p < 0.60:
            # 均匀交叉：随机选择每个基因来自哪个父本
            new.genes = [random.choice([self.genes[i], other.genes[i]]) for i in range(len(self.genes))]
        else:
            # 完全复制：取其中一个父本的所有基因
            new.genes = random.choice([self.genes, other.genes])

        # 突变：生成新基因或重置旋转序列
        for i in range(len(new.genes)):
            p = random.random()
            if p < 0.2:  # 5%概率生成新基因
                new.genes[i] = Gene(self.original_garden)
            elif p < 0.05:  # 10%概率重置旋转序列
                new.genes[i].generate_rotation()

        # 交叉后用新基因组耙地
        new.rake()

        return new
def rank_selection(population):
    """基于适应度的排名选择法选择父本"""
    # 按适应度降序排序种群
    sorted_population = sorted(population, key=lambda x: x.fitness, reverse=True)
    
    # 分配排名并计算选择概率
    total_ranks = sum(range(1, len(population) + 1))  # 所有排名的总和
    probabilities = [rank / total_ranks for rank in range(1, len(population) + 1)]

    # 根据排名概率选择基因组
    selected = random.choices(sorted_population, weights=probabilities, k=2)
    return selected[0], selected[1]  # 返回两个选中的父本用于交叉


def solve_hybrid_selection(rocks, width=12, height=10):
    """用混合选择法（排名选择+交叉）求解禅园问题"""
    garden = ZenGarden(width, height, rocks)
    population_size = 100
    generations = 1000  # 运行1000代
    population = [Genome(garden) for _ in range(population_size)]
    
    for gc in range(generations):
        best = max(population, key=lambda x: x.fitness)
        next_generation = [best]  # 保留最优基因组
        
        # 混合策略：60%交叉，40%直接排名选择
        num_crossover = int(0.6 * (population_size - 1))
        num_rank_selected = population_size - 1 - num_crossover
        
        # 通过交叉生成后代（60%）
        for _ in range(num_crossover):
            parent1, parent2 = rank_selection(population)
            child = parent1.crossover(parent2)
            next_generation.append(child)
        
        # 通过排名选择直接保留个体（40%）
        for _ in range(num_rank_selected):
            parent, _ = rank_selection(population)
            next_generation.append(parent)
        
        population = next_generation

        # 打印世代统计信息
        print(f'Generation: {gc + 1}, Best Fitness: {best.fitness}/{garden.max_fitness}')

        # 检查最优基因组是否解决了问题
        if best.fitness == garden.max_fitness:
            print("Solution found!")
            garden.display_garden(best.garden.grid)
            break
    else:
        print(f"No solution found after {generations} generations. Missing {garden.max_fitness - best.fitness}")
        garden.display_garden(garden.grid)
        garden.display_garden(best.garden.grid)

# 示例使用
rocks = [(5, 3), (2, 6), (9, 1), (3, 1), (8, 6), (9, 6)]
solve_hybrid_selection(rocks)

核心问题分析

突变逻辑完全失效：代码中if p < 0.2生成新基因，elif p < 0.05重置旋转序列，由于0.05小于0.2，重置旋转的分支永远不会触发，丢失了关键的基因多样性来源。
Rotation序列未被利用：Gene类生成了rotation序列，但在耙地转向时完全没用到，固定按初始方向选择，导致基因的决策能力被浪费。
基因数量冗余：初始基因数量设为width + height + rock_count，远超过实际需要的monk数量，大量基因重复覆盖已耙区域，降低算法效率。
适应度函数单一：仅统计耙过的单元格数，无法引导算法优先覆盖连续区域，容易陷入零散覆盖的局部最优。
种群收敛过快：每代保留最优个体+40%直接选择，导致种群多样性快速下降，难以跳出局部最优。

针对性优化方案

1. 修正突变逻辑

调整概率顺序，确保两个突变分支都能生效：

# 修正后的突变逻辑
for i in range(len(new.genes)):
    p = random.random()
    if p < 0.05:  # 5% 概率生成新基因
        new.genes[i] = Gene(self.original_garden)
    elif p < 0.15:  # 10% 概率重置旋转序列
        new.genes[i].generate_rotation()

2. 利用Rotation序列做转向决策

在耙地遇到两个可选方向时，用rotation序列决定选择：

# 当有两个可选方向时，使用rotation序列决策
elif nv.count(0) == 2:
    # 用rotation序列的当前索引位选择方向
    choice = gene.rotation[ri]
    pos = n[choice]
    ri += 1
    if ri >= len(gene.rotation):
        ri = 0

3. 优化基因数量

初始基因数量设为边界入口总数（2*width + 2*height），后续可根据未覆盖区域动态补充，避免冗余：

# Genome初始化时调整基因数量
if initialize:
    # 边界入口总数为2*宽 + 2*高
    gene_count = 2 * garden.width + 2 * garden.height
    for _ in range(gene_count):
        gene = Gene(self.original_garden)
        self.genes.append(gene)
    self.rake()

4. 改进适应度函数

加入连续区域奖励和孤立区域惩罚，引导算法优先覆盖大片区域：

def set_fitness(self):
    """改进后的适应度计算，加入连续区域奖励"""
    grid = self.garden.grid
    raked_cells = 0
    visited = set()
    bonus = 0

    for y in range(len(grid)):
        for x in range(len(grid[0])):
            cell = grid[y][x]
            if cell > 0 and (x,y) not in visited:
                raked_cells +=1
                # 广度优先搜索统计连续区域大小
                queue = [(x,y)]
                visited.add((x,y))
                region_size = 0
                while queue:
                    cx, cy = queue.pop(0)
                    region_size +=1
                    # 检查四个方向
                    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nx, ny = cx+dx, cy+dy
                        if 0<=nx<len(grid[0]) and 0<=ny<len(grid) and grid[ny][nx]==cell and (nx,ny) not in visited:
                            visited.add((nx,ny))
                            queue.append((nx,ny))
                # 连续区域越大，奖励越高
                bonus += region_size * 0.1
    
    # 惩罚孤立的未覆盖单元格（被包围的单个0）
    penalty = 0
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            if grid[y][x] ==0:
                # 检查四个方向是否都是非0（岩石或已耙）
                surrounded = True
                for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<len(grid[0]) and 0<=ny<len(grid):
                        if grid[ny][nx] ==0:
                            surrounded = False
                            break
                    else:
                        surrounded = False
                        break
                if surrounded:
                    penalty += 5
    
    self.fitness = raked_cells + bonus - penalty

5. 增加种群多样性

限制精英保留比例：每代只保留前5%的最优个体，而非全部保留最优。
引入随机移民：每代加入10%的全新随机个体，避免种群过早收敛。

# 修改solve_hybrid_selection中的下一代生成逻辑
def solve_hybrid_selection(rocks, width=12, height=10):
    garden = ZenGarden(width, height, rocks)
    population_size = 100
    generations = 1000
    population = [Genome(garden) for _ in range(population_size)]
    
    elite_ratio = 0.05  # 精英保留比例5%
    immigrant_ratio = 0.1  # 随机移民比例10%
    
    for gc in range(generations):
        population.sort(key=lambda x: x.fitness, reverse=True)
        best = population[0]
        next_generation = population[:int(elite_ratio*population_size)]  # 保留精英
        
        # 计算各部分数量
        num_immigrants = int(immigrant_ratio*population_size)
        num_crossover = population_size - len(next_generation) - num_immigrants
        
        # 生成交叉后代
        for _ in range(num_crossover):
            parent1, parent2 = rank_selection(population)
            child = parent1.crossover(parent2)
            next_generation.append(child)
        
        # 加入随机移民
        for _ in range(num_immigrants):
            next_generation.append(Genome(garden))
        
        #

如何解决禅园问题中遗传算法的局部最优停滞问题？

问题背景 #

核心问题分析 #

针对性优化方案 #

1. 修正突变逻辑 #

2. 利用Rotation序列做转向决策 #

3. 优化基因数量 #

4. 改进适应度函数 #

5. 增加种群多样性 #