基于遗传算法的图着色优化求解系统

资 源 简 介

本项目是一个利用MATLAB实现的针对图着色问题（Graph Coloring Problem, GCP）的高效求解工具。图着色问题是组合优化中的经典NP难问题，要求对图的顶点进行着色，使得相邻顶点颜色不同且使用颜色总数最少。本程序通过模拟自然进化过程的遗传算法来寻找最优解。详细功能包括：1. 图数据建模，通过邻接矩阵定义图的拓扑结构与连通性；2. 染色体编码与初始化，采用整数编码表示各顶点的颜色分配，并生成初始种群；3. 适应度函数设计，构建能够同时评估颜色冲突数（硬约束）和使用颜色数量（优化目标）的评价体系；4. 遗传操作实现，包括基于轮盘赌或锦标赛的选择算子、特定的交叉算子以及变异算子，以维持种群多样性并防止陷入局部最优；5. 冲突修复与局部搜索，集成贪婪算法策略对不可行解进行修正，加速收敛；6. 结果可视化，输出最终的图着色效果图（不同颜色标记节点）以及算法迭代过程中的适应度收敛曲线，便于用户分析算法性能。该项目适用于运筹学教学、算法研究以及地图着色、频率分配、排课表等实际调度问题的求解。

详 情 说 明

基于遗传算法的图着色问题求解系统

项目简介

本项目是一个使用 MATLAB 开发的组合优化工具，旨在求解经典的 图着色问题 (Graph Coloring Problem, GCP)。图着色问题要求对给定图的各个顶点进行着色，使得任意两个相邻的顶点颜色不同，同时尽可能减少使用的颜色总数。

该系统采用 混合遗传算法 (Hybrid Genetic Algorithm)，结合了全局搜索能力（进化计算）与局部启发式策略（贪婪修复），能够快速有效地在生成的随机图中找到近似最优的着色方案（即最小色数，Chromatic Number）。

功能特性

• 自动化图数据建模：系统能够根据预设的节点数量和连通密度，自动生成具有对称性的无向图邻接矩阵，并计算节点在二维平面的环形分布坐标以便于展示。
• 混合进化策略：在标准遗传算法的基础上，引入了特定于图着色问题的贪婪修复机制，显著提高了算法的收敛速度和解的质量。
• 多目标适应度评估：构建了加权评价体系，优先保证解的可行性（即消除相邻节点颜色冲突），其次优化解的质量（即减少颜色使用数量）。
• 精英保留策略：在每一代进化中强制保留全局最优解，防止优秀基因在使用交叉和变异算子时丢失。
• 全过程可视化：

* 收敛曲线：实时记录并绘制冲突数和颜色数量随迭代次数的变化趋势。 * 拓扑着色图：直观展示图的连接结构，并用不同颜色标记节点，清晰呈现最终的着色方案。

系统要求

• 运行环境：MATLAB (推荐 R2016b 及以上版本)
• 工具箱：本项目仅使用 MATLAB 基础函数，无需安装额外的工具箱。

使用方法

1. 直接在 MATLAB 中运行主程序文件 main.m。
2. 程序启动后将自动执行以下流程：

* 初始化参数并生成随机图数据。 * 进行种群初始化与初步修复。 * 进入遗传算法迭代循环（默认 200 代）。 * 在控制台输出关键迭代节点的冲突数、颜色数及适应度。

1. 运行结束后，系统将输出最终的最小颜色数和冲突检测结果，并弹出两个可视化窗口展示算法性能与着色结果。

算法原理与代码实现细节

本项目在一个脚本文件中完整实现了从数据生成到结果展示的全过程，核心逻辑如下：

1. 核心数据结构与编码

• 图模型：使用 $N times N$ 的邻接矩阵（Adjacency Matrix）表示图，其中矩阵元素为 1 表示节点间存在连接，0 表示无连接。矩阵被强制处理为对称矩阵且对角线为 0。
• 染色体编码：采用 整数编码 方案。每个个体是一个长度为 $N$ （节点数）的向量，向量中第 $i$ 个位置的整数代表第 $i$ 个节点的颜色索引。

2. 适应度函数设计

为了同时处理硬约束（相邻节点不同色）和优化目标（颜色数最少），系统采用了罚函数法构建适应度：

• 成本计算 (Cost)：$Cost = W_{conflict} times N_{conflicts} + W_{color} times N_{colors}$
• 权重设定：代码中设定 $W_{conflict} = 1000$， $W_{color} = 1$。这种巨大的权重差异确保了算法首先致力于寻找可行解（冲突数为 0），在此基础上再寻求颜色数量的最小化。
• 适应度值：$Fitness = 1 / (Cost + epsilon)$，将最小化问题转化为最大化问题。

3. 遗传操作算子

• 选择策略 (Selection)：采用 锦标赛选择法 (Tournament Selection)，每次随机选取 4 个个体进行竞争，选择适应度最高者进入下一代。
• 交叉操作 (Crossover)：采用 两点交叉 (Two-point Crossover)，随机选择两个断点交换父代基因片段，以保留某些局部着色模式。
• 变异操作 (Mutation)：采用 单点随机重置，以一定概率随机改变某个节点的颜色，增加种群多样性。

4. 局部搜索与贪婪修复 (关键特性)

代码中集成了一个关键的 greedy_repair 函数，贯穿于初始化和每一代进化过程：

• 冲突消除：对于产生颜色冲突的节点，算法会检索其所有邻居的颜色，并分配一个当前邻居可以接受的最小颜色索引（First Fit 策略）。
• 颜色空间压缩：如果个体没有冲突，或者修复完成后，算法会调用 compress_colors 函数，将离散的颜色索引（如 1, 5, 8）映射为连续的整数（1, 2, 3），从而准确计算使用的颜色总数。

5. 精英策略与主循环

• 主循环中实现了精英保留机制，每一代的适应度最优个体（包含其染色体、冲突数、颜色数）会被直接复制到下一代种群的第一个位置，确保算法性能单调不减。
• 迭代过程同时记录了每一代的“冲突数”和“颜色数”，用于后续的收敛性分析。

结果可视化说明

程序运行结束后会生成两幅图表：

1. 算法收敛性能图：

* 左子图（红色曲线）：显示冲突数随迭代次数的下降情况，验证算法消除冲突的能力。 * 右子图（蓝色曲线）：显示使用颜色总数随迭代次数的优化过程，展示算法寻找最小色数的能力。

1. 图着色结果图：

* 在二维平面上绘制图的拓扑结构。 * 节点根据最终解被赋予不同的颜色。 * 节点中心标记了其索引编号。 * 如果相邻节点颜色区分清晰且总颜色数较少，说明求解成功。