基于进化算法的装箱问题优化与 SpecKit 规范驱动开发实践

@spec_compliant(version="1.0.0")
class PermutationEncoding:
    """
    排列编码：表示物品放入容器的顺序
    
    示例：[3, 1, 4, 2, 5] 表示物品按 3→1→4→2→5 顺序放入
    """
    
    def __init__(self, items: List[Item]):
        self.genes = list(range(len(items)))
        random.shuffle(self.genes)
    
    def decode(self) -> PackingSolution:
        """解码为装箱方案"""
        bins = []
        current_bin = Bin(capacity=self.capacity)
        
        for item_idx in self.genes:
            item = self.items[item_idx]
            if current_bin.can_fit(item):
                current_bin.add(item)
            else:
                bins.append(current_bin)
                current_bin = Bin(capacity=self.capacity)
                current_bin.add(item)
        
        bins.append(current_bin)
        return PackingSolution(bins=bins)

@spec_compliant(version="1.0.0")
class GroupEncoding:
    """
    分组编码：直接表示物品 - 容器分配
    
    示例：[0, 1, 0, 2, 1] 表示：
    - 物品 0,2 → 容器 0
    - 物品 1,4 → 容器 1
    - 物品 3 → 容器 2
    """
    
    def __init__(self, items: List[Item], max_bins: int):
        self.genes = [random.randint(0, max_bins-1) for _ in items]

def fitness(solution: PackingSolution) -> float:
    """
    多目标适应度函数
    
    优化目标：
    1. 最小化容器数量（权重 0.6）
    2. 最大化空间利用率（权重 0.3）
    3. 负载均衡（权重 0.1）
    """
    # 容器使用数量（主要目标）
    containers_used = len(solution.bins)
    containers_normalized = containers_used / len(solution.items)
    
    # 空间利用率（次要目标）
    total_used_space = sum(bin.used_space for bin in solution.bins)
    total_space = len(solution.bins) * solution.bin_capacity
    space_utilization = total_used_space / total_space if total_space > 0 else 0
    
    # 负载均衡（可选）
    bin_loads = [bin.used_space for bin in solution.bins]
    load_balance = 1 - (np.std(bin_loads) / np.mean(bin_loads)) if bin_loads else 0
    
    # 多目标加权
    fitness_score = (
        0.6 * (1 - containers_normalized) +
        0.3 * space_utilization +
        0.1 * load_balance
    )
    
    return fitness_score

class GeneticOperators:
    """遗传算子实现"""
    
    @staticmethod
    def tournament_select(population: Population, k: int = 3) -> Individual:
        """锦标赛选择"""
        candidates = random.sample(population, k)
        return max(candidates, key=lambda ind: ind.fitness)
    
    @staticmethod
    def order_crossover(parent1: Individual, parent2: Individual) -> Individual:
        """顺序交叉 (OX)"""
        size = len(parent1.genes)
        start, end = sorted(random.sample(range(size), 2))
        
        child_genes = [-1] * size
        child_genes[start:end] = parent1.genes[start:end]
        
        remaining = [g for g in parent2.genes if g not in child_genes]
        child_genes = [g if g != -1 else remaining.pop(0) for g in child_genes]
        
        return Individual(genes=child_genes)
    
    @staticmethod
    def swap_mutate(individual: Individual, rate: float) -> Individual:
        """交换变异"""
        genes = individual.genes.copy()
        for i in range(len(genes)):
            if random.random() < rate:
                j = random.randint(0, len(genes) - 1)
                genes[i], genes[j] = genes[j], genes[i]
        return Individual(genes=genes)

class EvolutionaryAlgorithm(Protocol):
    """进化算法基类接口"""
    
    @abstractmethod
    def initialize(self, config: Config) -> Population:
        """初始化种群"""
        pass
    
    @abstractmethod
    def evaluate(self, population: Population) -> FitnessResults:
        """评估适应度"""
        pass
    
    @abstractmethod
    def select(self, population: Population, n: int) -> Population:
        """选择操作"""
        pass
    
    @abstractmethod
    def crossover(self, parents: Population) -> Population:
        """交叉操作"""
        pass
    
    @abstractmethod
    def mutate(self, population: Population) -> Population:
        """变异操作"""
        pass
    
    @abstractmethod
    def run(self, max_generations: int) -> Solution:
        """运行算法"""
        pass

# tools/spec_version_checker.py
import semver
from pathlib import Path

class SpecVersionChecker:
    """规范版本检查器"""
    
    def check_compatibility(self, impl_version: str, spec_version: str) -> bool:
        """检查实现与规范的兼容性"""
        impl = semver.parse(impl_version)
        spec = semver.parse(spec_version)
        
        # 主版本必须匹配
        if impl['major'] != spec['major']:
            return False
        
        # 实现版本不能低于规范版本
        if impl['minor'] < spec['minor']:
            return False
        
        return True
    
    def validate_spec_file(self, spec_path: Path) -> ValidationResult:
        """验证规范文件格式"""
        required_fields = ['Spec ID', '版本', '状态', '生效日期']
        
        with open(spec_path, 'r') as f:
            content = f.read()
        
        missing = [field for field in required_fields if field not in content]
        
        return ValidationResult(
            valid=len(missing)==0,
            errors=[f"缺少字段：{field}" for field in missing]
        )

class DiversityMaintainer:
    """多样性保持机制"""
    
    def __init__(self, min_diversity: float = 0.1):
        self.min_diversity = min_diversity
    
    def check_and_adjust(self, population: Population) -> Population:
        """检查并调整种群多样性"""
        diversity = self.calculate_diversity(population)
        
        if diversity < self.min_diversity:
            # 增加变异率
            population = self.increase_mutation(population)
            # 引入随机个体
            population = self.introduce_random_individuals(population)
        
        return population