基于树状关系的改进遗传算法：二维排样与ADC0809C应用

本篇论文主要探讨的是基于树状关系的改进遗传算法在二维排样问题中的应用，针对51单片机平台下的ADC0809C程序设计。遗传算法是一种模仿自然选择过程的优化搜索算法，用于解决复杂问题，如排列和组合问题，其中排样问题是一个典型的应用场景。 编码部分是遗传算法的关键步骤，作者采用了两种不同的编码方式。首先，十进制数编码将零件标记为ID号，类似于零件的身份标识，每个ID对应一个零件，通过ID序列确定零件的排列顺序。这种编码方式直观且易于理解，但可能限制了解空间的探索范围。 另一种编码方法是二进制编码，用0和1来表示零件的方向，0代表横放，1代表竖放，这使得算法能够处理零件方向的多样性。这种编码方式更为细致，有助于处理复杂的空间布局问题。 适应度函数的选择对于算法性能至关重要。对于二维排样问题，适应度函数主要考虑零件的利用率，即子板材和初始板材的占有率。由于论文中强调了板宽优先，因此适应度评估依赖于零件在模板上的占用高度，占用高度越高，适应度越低，排样效果越差。适应度函数定义为所有零件占用面积之和除以实际占用面积。 文章中的两种染色体——CH1和二进制染色体，分别代表了不同的信息。CH1记录零件编号的顺序，影响排样的顺序，而二进制染色体则关注零件的排放方向。这两种染色体共同决定了排样方案的最终结果。 整个研究围绕硕士研究生宋开胜在姚念民教授的指导下，针对计算机系统结构领域的计算机科学与技术学院进行的二维排样问题的遗传算法优化。论文提交和答辩时间分别为2010年3月，显示出作者严谨的学术态度和对技术实践的深入研究。论文的原创性和授权使用声明强调了作者对知识产权的认识和尊重，确保了研究的合规性。 这篇论文提供了将遗传算法应用于实际硬件环境（如51单片机）解决二维排样问题的方法，通过精心设计的编码、适应度函数和染色体结构，优化了排样效果并展示了其在工程实践中的可行性。