北京大学2025年秋《机器学习》课程项目

项目内容：基于遗传算法解决接吻数问题。实际上这是一个非常复杂的组合优化问题，目前尚无定论。但遗传算法完全可以在一段相当长的时间中找到一个较优解，实现简单（存疑），易于并行化（这里并未并行），且有趣（个人感觉）。

总体思路：在单位超球上寻找尽可能多的点，使得这些点两两之间的距离都不小于1。可以证明该问题与“接吻数问题”等价。

运行说明

该项目没有任何外部依赖，使用C++23标准，因此你的编译指令必须包含 -std=c++23。推荐使用g++编译器，其他编译器未测试，但因为未使用任何特定于编译器的特性，理论上应该也能编译通过。

编译指令示例：

g++ -std=c++23 -O3 main.cc -o ml_cpp
./ml_cpp

代码结构

• main.cc：主程序，包含遗传算法的主循环。
• PIP.hh：包含点、个体和种群的定义与实现。

目前可以优化的内容

目前算法本身是正确的，但是收敛极为缓慢。故而我提出以下几点可能的优化方向：

• 初始化策略，目前的初始化方式是在所有坐标轴上取正负1，这显然不是最优的，可以考虑更合理的初始化方式。
• 适应度策略，目前的适应度函数比较简陋，仅考虑点的数量、点的平均距离。可以考虑更复杂的适应度函数，例如“几何稳定性”等（难以定义）。
• 变异和交叉策略，目前的变异和交叉方式都比较简单，可以考虑更复杂的方式，例如“基于模拟退火、局部搜索的变异和进化”等。
• 调参（绕不开的一环）。
• 并行化，目前的实现是单线程的，可以考虑使用多线程或GPU加速（但这么搞，那就太复杂了，还不如用C重写一遍）。
• 其他更复杂的进化策略，例如“精英保留”、“多样性维护”等。