遗传算法解决八数码问题MATALB

### 使用MATLAB实现遗传算法解决八数码问题

#### 1. 定义适应度函数
为了评估每个个体的表现，定义一个适应度函数来计算当前状态与目标状态之间的差异。通常采用曼哈顿距离作为衡量标准。

function fitness = calculateFitness(individual)
    goalState = [1, 2, 3; 4, 5, 6; 7, 8, 0]; % 目标状态
    currentState = reshape(individual, 3, 3);
    
    [~, idxGoal] = find(goalState); % 获取目标位置索引
    [~, idxCurrent] = find(currentState); % 获取当前位置索引
    
    rowDiff = abs(idxGoal(1) - idxCurrent(1));
    colDiff = abs(idxGoal(2) - idxCurrent(2));
    
    fitness = sum(rowDiff(:)) + sum(colDiff(:)); % 曼哈顿距离之和
end

#### 2. 初始化种群
创建初始种群，随机生成多个可能的状态组合，并确保这些状态合法（即不重复且包含空白格）。

function population = initializePopulation(popSize)
    population = zeros(popSize, 9);
    for i = 1:popSize
        temp = randperm(9)-1;
        while ~isSolvable(temp) || any(sum(abs(diff(sortrows([temp;population])), [], 2))==0)
            temp = randperm(9)-1;
        end
        population(i,:) = temp;
    end
end

#### 3. 实现交叉操作
通过交换两个父代的部分基因片段形成新的子代个体。

function offspring = crossover(parents)
    point = randi([2, length(parents)/2]);
    offspring = parents;
    offspring(:,point:end) = fliplr(offspring(:,point:end));
end

#### 4. 进行变异操作
以一定概率改变某些位上的数值，引入多样性。

function mutatedIndividual = mutate(individual, mutationRate)
    nGenes = numel(individual);
    mask = rand(size(individual)) < mutationRate;
    swapIndices = find(mask & individual ~= 0);
    numSwaps = min(length(swapIndices), floor(nGenes * mutationRate));

    if numSwaps > 0
        indicesToSwap = datasample(swapIndices, numSwaps);
        shuffledValues = individual(indicesToSwap(randperm(numSwaps)));
        individual(indicesToSwap) = shuffledValues;
    end
    
    mutatedIndividual = individual;
end

#### 5. 主循环逻辑
迭代执行选择、交叉、变异等过程直到找到最优解或达到最大迭代次数为止。

maxGenerations = 1e3;
mutationRate = 0.01;
populationSize = 100;

% Initialize the first generation of solutions.
currentGeneration = initializePopulation(populationSize);

for gen = 1:maxGenerations
    % Evaluate all individuals' fitness values.
    scores = arrayfun(@calculateFitness, currentGeneration)';
    
    % Select top performers as parents based on their fitness score.
    [~, sortedIdx] = sort(scores);
    eliteCount = round(eliteRatio*length(sortedIdx));
    elites = currentGeneration(sortedIdx(1:eliteCount), :);
    
    nextGeneration = [];
    while size(nextGeneration, 1) < populationSize - eliteCount
        parentPair = randsample(currentGeneration, 2, false);
        child = crossover(parentPair');
        
        % Apply mutations to introduce variation into children.
        childMutated = mutate(child', mutationRate);
        
        nextGeneration(end+1, :) = childMutated';
    end
    
    % Combine elites with newly generated offsprings.
    currentGeneration = [elites; nextGeneration];
    
    bestScoreThisGen = min(scores);
    fprintf('Generation #%d Best Fitness Score=%.2f\n', gen, bestScoreThisGen);
    
    if bestScoreThisGen == 0
        break;
    end
end