<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>遗传算法解决迷宫问题 - 不定长染色体</title>
<style>
body {
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
max-width: 1200px;
margin: 0 auto;
padding: 20px;
background-color: #f5f5f5;
color: #333;
}
h1 {
text-align: center;
color: #2c3e50;
}
.container {
display: flex;
flex-wrap: wrap;
gap: 20px;
margin-bottom: 20px;
}
.controls {
flex: 1;
min-width: 300px;
background: white;
padding: 20px;
border-radius: 8px;
box-shadow: 0 2px 10px rgba(0,0,0,0.1);
}
.visualization {
flex: 2;
min-width: 500px;
display: flex;
flex-direction: column;
gap: 20px;
}
.maze-container {
background: white;
padding: 20px;
border-radius: 8px;
box-shadow: 0 2px 10px rgba(0,0,0,0.1);
position: relative;
}
.stats-container {
background: white;
padding: 20px;
border-radius: 8px;
box-shadow: 0 2px 10px rgba(0,0,0,0.1);
}
canvas {
border: 1px solid #ddd;
margin: 0 auto;
display: block;
}
button {
background-color: #3498db;
color: white;
border: none;
padding: 10px 15px;
margin: 5px;
border-radius: 4px;
cursor: pointer;
transition: background-color 0.3s;
}
button:hover {
background-color: #2980b9;
}
button:disabled {
background-color: #95a5a6;
cursor: not-allowed;
}
.control-group {
margin-bottom: 15px;
}
label {
display: block;
margin-bottom: 5px;
font-weight: bold;
}
input[type="number"], input[type="range"] {
width: 100%;
padding: 8px;
border: 1px solid #ddd;
border-radius: 4px;
}
.stat {
display: flex;
justify-content: space-between;
margin-bottom: 8px;
}
.stat-value {
font-weight: bold;
}
.best-path {
margin-top: 15px;
padding: 10px;
background-color: #f9f9f9;
border-radius: 4px;
font-family: monospace;
}
.speed-control {
display: flex;
align-items: center;
gap: 10px;
}
.legend {
display: flex;
flex-wrap: wrap;
gap: 10px;
margin-top: 10px;
}
.legend-item {
display: flex;
align-items: center;
font-size: 12px;
}
.legend-color {
width: 15px;
height: 15px;
margin-right: 5px;
border: 1px solid #ddd;
}
</style>
</head>
<body>
<h1>遗传算法解决迷宫问题 - 不定长染色体</h1>
<div class="container">
<div class="controls">
<div class="control-group">
<h3>迷宫设置</h3>
<label for="mazeRows">迷宫行数:</label>
<input type="number" id="mazeRows" value="10" min="5" max="30">
<label for="mazeCols">迷宫列数:</label>
<input type="number" id="mazeCols" value="10" min="5" max="30">
<label for="wallDensity">墙壁密度:</label>
<input type="range" id="wallDensity" min="10" max="50" value="30">
<span id="wallDensityValue">30%</span>
<button id="regenerateMazeBtn">重新生成迷宫</button>
</div>
<div class="control-group">
<h3>算法参数</h3>
<label for="populationSize">种群大小:</label>
<input type="number" id="populationSize" value="100" min="10" max="1000">
<label for="minChromosomeLength">最小基因长度:</label>
<input type="number" id="minChromosomeLength" value="10" min="5" max="50">
<label for="maxChromosomeLength">最大基因长度:</label>
<input type="number" id="maxChromosomeLength" value="50" min="10" max="200">
<label for="mutationRate">变异率:</label>
<input type="range" id="mutationRate" min="0" max="100" value="5">
<span id="mutationRateValue">5%</span>
<label for="crossoverRate">交叉率:</label>
<input type="range" id="crossoverRate" min="0" max="100" value="70">
<span id="crossoverRateValue">70%</span>
<label for="maxGenerations">最大迭代次数:</label>
<input type="number" id="maxGenerations" value="100" min="10" max="10000">
<label for="immigrationRate">移民率:</label>
<input type="range" id="immigrationRate" min="0" max="50" value="5">
<span id="immigrationRateValue">5%</span>
<label for="immigrationInterval">移民间隔:</label>
<input type="number" id="immigrationInterval" value="10" min="1" max="50">
</div>
<div class="control-group">
<h3>控制</h3>
<button id="startBtn">开始</button>
<button id="pauseBtn" disabled>暂停</button>
<button id="resetBtn">重置</button>
<div class="speed-control">
<label for="animationSpeed">动画速度:</label>
<input type="range" id="animationSpeed" min="1" max="10" value="5">
</div>
</div>
</div>
<div class="visualization">
<div class="maze-container">
<h3>迷宫可视化</h3>
<canvas id="mazeCanvas" width="500" height="500"></canvas>
<div class="legend">
<div class="legend-item"><div class="legend-color" style="background-color:#27ae60;"></div>起点</div>
<div class="legend-item"><div class="legend-color" style="background-color:#e74c3c;"></div>终点</div>
<div class="legend-item"><div class="legend-color" style="background-color:#3498db;"></div>路径</div>
<div class="legend-item"><div class="legend-color" style="background-color:#f1c40f;"></div>探索点</div>
<div class="legend-item"><div class="legend-color" style="background-color:#9b59b6;"></div>最优路径</div>
</div>
</div>
<div class="stats-container">
<h3>算法统计</h3>
<div class="stat">
<span>当前迭代:</span>
<span id="currentGeneration" class="stat-value">0</span>
</div>
<div class="stat">
<span>最佳适应度:</span>
<span id="bestFitness" class="stat-value">0</span>
</div>
<div class="stat">
<span>平均适应度:</span>
<span id="avgFitness" class="stat-value">0</span>
</div>
<div class="stat">
<span>找到解决方案:</span>
<span id="solutionFound" class="stat-value">否</span>
</div>
<div class="stat">
<span>探索率:</span>
<span id="explorationRate" class="stat-value">0%</span>
</div>
<div class="stat">
<span>最佳路径长度:</span>
<span id="bestPathLength" class="stat-value">0</span>
</div>
<div class="stat">
<span>平均染色体长度:</span>
<span id="avgChromosomeLength" class="stat-value">0</span>
</div>
<div class="best-path">
<strong>最佳路径:</strong>
<div id="bestPath"></div>
</div>
</div>
</div>
</div>
<script>
// 迷宫表示：0=路径，1=墙壁，S=起点，E=终点
let maze = [];
let rows = 10;
let cols = 10;
let wallDensity = 0.3;
// 遗传算法参数
let populationSize = 100;
let minChromosomeLength = 10;
let maxChromosomeLength = 50;
let mutationRate = 0.05;
let crossoverRate = 0.7;
let maxGenerations = 100;
let immigrationRate = 0.05;
let immigrationInterval = 10;
let currentGeneration = 0;
let animationSpeed = 5;
// 算法状态
let population = [];
let bestIndividual = null;
let bestFitness = 0;
let avgFitness = 0;
let solutionFound = false;
let animationId = null;
let isRunning = false;
let bestPathHistory = [];
// 方向编码：U=上，D=下，L=左，R=右
const directions = ['U', 'D', 'L', 'R'];
// 获取起点坐标
function findStartPosition() {
for (let i = 0; i < maze.length; i++) {
for (let j = 0; j < maze[i].length; j++) {
if (maze[i][j] === 'S') return { x: i, y: j };
}
}
return { x: 1, y: 1 }; // 默认起点
}
// 获取终点坐标
function findEndPosition() {
for (let i = 0; i < maze.length; i++) {
for (let j = 0; j < maze[i].length; j++) {
if (maze[i][j] === 'E') return { x: i, y: j };
}
}
return { x: maze.length - 2, y: maze[0].length - 2 }; // 默认终点
}
let startPos = { x: 1, y: 1 };
let endPos = { x: 1, y: 1 };
// 生成随机迷宫
function generateMaze() {
rows = parseInt(document.getElementById('mazeRows').value);
cols = parseInt(document.getElementById('mazeCols').value);
wallDensity = parseInt(document.getElementById('wallDensity').value) / 100;
// 创建空迷宫（全路径）
maze = Array(rows).fill().map(() => Array(cols).fill(0));
// 设置边界为墙
for (let i = 0; i < rows; i++) {
maze[i][0] = 1;
maze[i][cols-1] = 1;
}
for (let j = 0; j < cols; j++) {
maze[0][j] = 1;
maze[rows-1][j] = 1;
}
// 随机添加墙壁
for (let i = 1; i < rows-1; i++) {
for (let j = 1; j < cols-1; j++) {
if (Math.random() < wallDensity) {
maze[i][j] = 1;
}
}
}
// 设置起点和终点
startPos = { x: 1, y: 1 };
endPos = { x: rows-2, y: cols-2 };
maze[startPos.x][startPos.y] = 'S';
maze[endPos.x][endPos.y] = 'E';
// 确保起点和终点之间有路径
maze[1][1] = 'S';
maze[rows-2][cols-2] = 'E';
maze[1][2] = 0;
maze[2][1] = 0;
maze[rows-2][cols-3] = 0;
maze[rows-3][cols-2] = 0;
return maze;
}
// 个体类
class Individual {
constructor(chromosome = null) {
if (chromosome) {
this.chromosome = chromosome;
} else {
this.chromosome = this.generateRandomChromosome();
}
this.fitness = this.calculateFitness();
this.exploredCells = 0;
this.pathLength = 0;
this.reachedEnd = false;
}
// 生成随机染色体（路径） - 不定长
generateRandomChromosome() {
const length = Math.floor(Math.random() * (maxChromosomeLength - minChromosomeLength + 1)) + minChromosomeLength;
let chromosome = [];
for (let i = 0; i < length; i++) {
chromosome.push(directions[Math.floor(Math.random() * directions.length)]);
}
return chromosome;
}
// 计算适应度
calculateFitness() {
let x = startPos.x;
let y = startPos.y;
let steps = 0;
this.reachedEnd = false;
let visited = Array(rows).fill().map(() => Array(cols).fill(false));
let uniqueCellsVisited = 0;
this.path = [{x, y}]; // 记录路径
// 起点已访问
visited[x][y] = true;
uniqueCellsVisited++;
for (let gene of this.chromosome) {
let newX = x;
let newY = y;
switch (gene) {
case 'U': newX--; break;
case 'D': newX++; break;
case 'L': newY--; break;
case 'R': newY++; break;
}
// 检查移动是否有效
if (newX >= 0 && newX < maze.length &&
newY >= 0 && newY < maze[0].length &&
maze[newX][newY] !== 1) {
x = newX;
y = newY;
steps++;
// 记录路径点
this.path.push({x, y});
// 探索奖励：访问新格子
if (!visited[x][y]) {
visited[x][y] = true;
uniqueCellsVisited++;
}
// 检查是否到达终点
if (x === endPos.x && y === endPos.y) {
this.reachedEnd = true;
break;
}
}
}
// 记录路径长度
this.pathLength = steps;
// 计算到终点的曼哈顿距离
const distance = Math.abs(x - endPos.x) + Math.abs(y - endPos.y);
// 探索率：访问的格子占总可访问格子的比例
const explorationRate = uniqueCellsVisited / (rows * cols * (1 - wallDensity));
this.exploredCells = uniqueCellsVisited;
// 适应度计算：
// 1. 优先考虑是否到达终点
// 2. 其次考虑距离终点距离
// 3. 对探索新格子给予奖励
// 4. 对路径长度给予惩罚（奖励短路径）
if (this.reachedEnd) {
// 到达终点：基础奖励 + 探索奖励 - 路径长度惩罚
return 1000 + (explorationRate * 200) - (steps * 2);
} else {
// 未到达终点：距离惩罚 + 探索奖励
return (100 / (distance + 1)) + (explorationRate * 50);
}
}
}
// 初始化种群
function initializePopulation() {
population = [];
for (let i = 0; i < populationSize; i++) {
population.push(new Individual());
}
}
// 选择操作 - 轮盘赌选择
function selection() {
// 计算总适应度
const totalFitness = population.reduce((sum, individual) => sum + individual.fitness, 0);
// 计算每个个体的选择概率
const selectionProbabilities = population.map(
individual => individual.fitness / totalFitness
);
// 选择新种群
const newPopulation = [];
for (let i = 0; i < populationSize; i++) {
let rand = Math.random();
let sum = 0;
for (let j = 0; j < population.length; j++) {
sum += selectionProbabilities[j];
if (sum >= rand) {
newPopulation.push(population[j]);
break;
}
}
}
population = newPopulation;
}
// 交叉操作 - 适应不定长染色体
function crossover() {
const newPopulation = [];
for (let i = 0; i < populationSize; i += 2) {
if (i + 1 < populationSize && Math.random() < crossoverRate) {
const parent1 = population[i];
const parent2 = population[i + 1];
// 选择交叉点 - 基于较短染色体的长度
const minLength = Math.min(parent1.chromosome.length, parent2.chromosome.length);
const crossoverPoint = Math.floor(Math.random() * minLength);
// 创建子代
const child1 = new Individual([
...parent1.chromosome.slice(0, crossoverPoint),
...parent2.chromosome.slice(crossoverPoint)
]);
const child2 = new Individual([
...parent2.chromosome.slice(0, crossoverPoint),
...parent1.chromosome.slice(crossoverPoint)
]);
newPopulation.push(child1, child2);
} else {
// 不进行交叉，直接保留父代
newPopulation.push(population[i]);
if (i + 1 < populationSize) {
newPopulation.push(population[i + 1]);
}
}
}
population = newPopulation;
}
// 变异操作 - 适应不定长染色体
function mutation() {
for (let individual of population) {
if (Math.random() < mutationRate) {
// 随机选择变异类型
const mutationType = Math.random();
if (mutationType < 0.7) {
// 70%概率：基因变异（改变一个基因）
const mutationPoint = Math.floor(Math.random() * individual.chromosome.length);
individual.chromosome[mutationPoint] = directions[Math.floor(Math.random() * directions.length)];
} else if (mutationType < 0.85 && individual.chromosome.length < maxChromosomeLength) {
// 15%概率：插入新基因
const insertionPoint = Math.floor(Math.random() * (individual.chromosome.length + 1));
const newGene = directions[Math.floor(Math.random() * directions.length)];
individual.chromosome.splice(insertionPoint, 0, newGene);
} else if (mutationType < 1.0 && individual.chromosome.length > minChromosomeLength) {
// 15%概率：删除一个基因
const deletionPoint = Math.floor(Math.random() * individual.chromosome.length);
individual.chromosome.splice(deletionPoint, 1);
}
individual.fitness = individual.calculateFitness(); // 重新计算适应度
}
}
}
// 随机移民操作
function immigration() {
if (currentGeneration > 0 && currentGeneration % immigrationInterval === 0) {
const numImmigrants = Math.floor(populationSize * immigrationRate);
// 替换最差的个体
population.sort((a, b) => a.fitness - b.fitness);
for (let i = 0; i < numImmigrants; i++) {
population[i] = new Individual();
}
}
}
// 更新统计信息
function updateStatistics() {
// 找到最佳个体
bestIndividual = population.reduce((best, current) =>
current.fitness > best.fitness ? current : best, population[0]);
bestFitness = bestIndividual.fitness;
// 计算平均适应度
avgFitness = population.reduce((sum, individual) => sum + individual.fitness, 0) / populationSize;
// 计算平均探索率
const totalExplored = population.reduce((sum, individual) => sum + individual.exploredCells, 0);
const avgExplored = totalExplored / populationSize;
const totalCells = rows * cols * (1 - wallDensity);
const explorationRate = (avgExplored / totalCells * 100).toFixed(1);
// 计算平均染色体长度
const totalLength = population.reduce((sum, individual) => sum + individual.chromosome.length, 0);
const avgLength = (totalLength / populationSize).toFixed(1);
// 检查是否找到解决方案
solutionFound = bestIndividual.reachedEnd;
// 记录最佳路径历史
if (solutionFound && (!bestPathHistory.length || bestIndividual.pathLength < bestPathHistory[bestPathHistory.length - 1].pathLength)) {
bestPathHistory.push({
generation: currentGeneration,
path: bestIndividual.chromosome.join(''),
pathLength: bestIndividual.pathLength,
fitness: bestFitness
});
}
// 更新统计显示
document.getElementById('explorationRate').textContent = explorationRate + '%';
document.getElementById('bestPathLength').textContent = bestIndividual.pathLength;
document.getElementById('avgChromosomeLength').textContent = avgLength;
}
// 绘制迷宫
function drawMaze() {
const canvas = document.getElementById('mazeCanvas');
const ctx = canvas.getContext('2d');
const cellSize = Math.min(canvas.width / cols, canvas.height / rows);
// 清除画布
ctx.clearRect(0, 0, canvas.width, canvas.height);
// 绘制迷宫
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
const x = j * cellSize;
const y = i * cellSize;
if (maze[i][j] === 1) {
ctx.fillStyle = '#333';
ctx.fillRect(x, y, cellSize, cellSize);
} else if (maze[i][j] === 'S') {
ctx.fillStyle = '#27ae60';
ctx.fillRect(x, y, cellSize, cellSize);
} else if (maze[i][j] === 'E') {
ctx.fillStyle = '#e74c3c';
ctx.fillRect(x, y, cellSize, cellSize);
} else {
ctx.fillStyle = '#ecf0f1';
ctx.fillRect(x, y, cellSize, cellSize);
}
// 绘制网格线
ctx.strokeStyle = '#bdc3c7';
ctx.strokeRect(x, y, cellSize, cellSize);
}
}
// 绘制最佳路径
if (bestIndividual && bestIndividual.path) {
let x = startPos.x;
let y = startPos.y;
let visited = Array(rows).fill().map(() => Array(cols).fill(false));
// 绘制探索点
for (let point of bestIndividual.path) {
if (!visited[point.x][point.y]) {
visited[point.x][point.y] = true;
ctx.fillStyle = '#f1c40f';
ctx.beginPath();
ctx.arc(
point.y * cellSize + cellSize / 2,
point.x * cellSize + cellSize / 2,
cellSize / 6, 0, Math.PI * 2
);
ctx.fill();
}
}
// 绘制路径
ctx.strokeStyle = '#3498db';
ctx.lineWidth = 2;
ctx.beginPath();
ctx.moveTo(
bestIndividual.path[0].y * cellSize + cellSize / 2,
bestIndividual.path[0].x * cellSize + cellSize / 2
);
for (let i = 1; i < bestIndividual.path.length; i++) {
ctx.lineTo(
bestIndividual.path[i].y * cellSize + cellSize / 2,
bestIndividual.path[i].x * cellSize + cellSize / 2
);
}
ctx.stroke();
// 如果到达终点，用不同颜色标记最优路径
if (bestIndividual.reachedEnd) {
ctx.strokeStyle = '#9b59b6';
ctx.lineWidth = 3;
ctx.beginPath();
ctx.moveTo(
bestIndividual.path[0].y * cellSize + cellSize / 2,
bestIndividual.path[0].x * cellSize + cellSize / 2
);
for (let i = 1; i < bestIndividual.path.length; i++) {
ctx.lineTo(
bestIndividual.path[i].y * cellSize + cellSize / 2,
bestIndividual.path[i].x * cellSize + cellSize / 2
);
}
ctx.stroke();
}
}
}
// 更新UI统计信息
function updateUI() {
document.getElementById('currentGeneration').textContent = currentGeneration;
document.getElementById('bestFitness').textContent = bestFitness.toFixed(2);
document.getElementById('avgFitness').textContent = avgFitness.toFixed(2);
document.getElementById('solutionFound').textContent = solutionFound ? '是' : '否';
// 显示最佳路径
if (bestIndividual) {
document.getElementById('bestPath').textContent = bestIndividual.chromosome.join('');
}
}
// 运行一代遗传算法
function runGeneration() {
selection();
crossover();
mutation();
immigration();
updateStatistics();
currentGeneration++;
drawMaze();
updateUI();
// 检查终止条件 - 不再因找到解决方案而停止，继续寻找更优解
if (currentGeneration >= maxGenerations) {
stopAlgorithm();
return;
}
// 继续运行
if (isRunning) {
const speed = 1000 / animationSpeed;
animationId = setTimeout(runGeneration, speed);
}
}
// 开始算法
function startAlgorithm() {
if (!isRunning) {
isRunning = true;
document.getElementById('startBtn').disabled = true;
document.getElementById('pauseBtn').disabled = false;
// 如果是一代开始，需要初始化
if (currentGeneration === 0) {
initializePopulation();
updateStatistics();
drawMaze();
updateUI();
}
runGeneration();
}
}
// 暂停算法
function pauseAlgorithm() {
if (isRunning) {
isRunning = false;
clearTimeout(animationId);
document.getElementById('startBtn').disabled = false;
document.getElementById('pauseBtn').disabled = true;
}
}
// 停止算法
function stopAlgorithm() {
isRunning = false;
clearTimeout(animationId);
document.getElementById('startBtn').disabled = false;
document.getElementById('pauseBtn').disabled = true;
}
// 重置算法
function resetAlgorithm() {
stopAlgorithm();
currentGeneration = 0;
bestPathHistory = [];
initializePopulation();
updateStatistics();
drawMaze();
updateUI();
}
// 初始化页面
function initializePage() {
// 设置事件监听器
document.getElementById('startBtn').addEventListener('click', startAlgorithm);
document.getElementById('pauseBtn').addEventListener('click', pauseAlgorithm);
document.getElementById('resetBtn').addEventListener('click', resetAlgorithm);
document.getElementById('regenerateMazeBtn').addEventListener('click', function() {
generateMaze();
resetAlgorithm();
});
// 参数变化监听
document.getElementById('mutationRate').addEventListener('input', function() {
mutationRate = this.value / 100;
document.getElementById('mutationRateValue').textContent = this.value + '%';
});
document.getElementById('crossoverRate').addEventListener('input', function() {
crossoverRate = this.value / 100;
document.getElementById('crossoverRateValue').textContent = this.value + '%';
});
document.getElementById('immigrationRate').addEventListener('input', function() {
immigrationRate = this.value / 100;
document.getElementById('immigrationRateValue').textContent = this.value + '%';
});
document.getElementById('wallDensity').addEventListener('input', function() {
wallDensity = this.value / 100;
document.getElementById('wallDensityValue').textContent = this.value + '%';
});
document.getElementById('populationSize').addEventListener('change', function() {
populationSize = parseInt(this.value);
resetAlgorithm();
});
document.getElementById('minChromosomeLength').addEventListener('change', function() {
minChromosomeLength = parseInt(this.value);
resetAlgorithm();
});
document.getElementById('maxChromosomeLength').addEventListener('change', function() {
maxChromosomeLength = parseInt(this.value);
resetAlgorithm();
});
document.getElementById('maxGenerations').addEventListener('change', function() {
maxGenerations = parseInt(this.value);
});
document.getElementById('immigrationInterval').addEventListener('change', function() {
immigrationInterval = parseInt(this.value);
});
document.getElementById('animationSpeed').addEventListener('input', function() {
animationSpeed = parseInt(this.value);
});
// 初始化迷宫和算法
generateMaze();
initializePopulation();
updateStatistics();
drawMaze();
updateUI();
}
// 页面加载完成后初始化
window.addEventListener('load', initializePage);
</script>
</body>
</html>Test
·
《 “Test” 》 有 4 条评论
-
Test
-
Test #2
-
Test #3
-
-
Test #4
-
发表回复