公开(公告)号：CN112102438B

公开(公告)日：2024-01-26

申请号：CN202010872880.7

申请日：2020-08-26

Applicant: 东南大学

Inventor： 孙雯 ,  臧宇豪 ,  相璐 ,  时真好 ,  全婧文 ,  任子悦 ,  姜禹

IPC: G06T11/40 ,  G06F16/901 ,  G06N20/00

Abstract: 本发明提供了一种基于精英解驱动的多层级禁忌搜索的图染色问题搜索方法，包括：结合两种局部搜索方案生成性能优异的初始精英解；利用性能优异的精英解缩合当前图，从而依次得到下一层级的较小的图形；根据权重，对缩合阶段以及解缩合阶段的中间图进行权重禁忌染色；将缩合图逐步解缩合，最终得到原始图；采用扰动方法，跳出局部最优区域。本发明采用基于精英解的动态多层级优化方案而不是基于静态图网络结构的多层级方案，并在该动态优化方案、网络结构和历史信息的基础上，在每层级设计权重禁忌搜索方法，从而得到图染色问题性能优异的解决方案。本发明对于图染色问题及相应的问题具有重要的研究和实用价值。

公开(公告)号：CN112102438A

公开(公告)日：2020-12-18

申请号：CN202010872880.7

申请日：2020-08-26

Applicant: 东南大学

Inventor： 孙雯 ,  臧宇豪 ,  相璐 ,  时真好 ,  全婧文 ,  任子悦 ,  姜禹

IPC: G06T11/40 ,  G06F16/901 ,  G06N20/00

Abstract: 本发明提供了一种基于精英解驱动的多层级禁忌搜索的图染色问题搜索方法，包括：结合两种局部搜索方案生成性能优异的初始精英解；利用性能优异的精英解缩合当前图，从而依次得到下一层级的较小的图形；根据权重，对缩合阶段以及解缩合阶段的中间图进行权重禁忌染色；将缩合图逐步解缩合，最终得到原始图；采用扰动方法，跳出局部最优区域。本发明采用基于精英解的动态多层级优化方案而不是基于静态图网络结构的多层级方案，并在该动态优化方案、网络结构和历史信息的基础上，在每层级设计权重禁忌搜索方法，从而得到图染色问题性能优异的解决方案。本发明对于图染色问题及相应的问题具有重要的研究和实用价值。