标题： 通过进化算法增强软幸福感 显示英文标题

标题： Enhancing Soft Happiness via Evolutionary Algorithms

摘要： 对于$0\leq \rho\leq 1$，着色图中的一个$\rho$-快乐顶点$v$与至少$\rho\mathrm{deg}(v)$个邻居共享颜色。 柔和颜色图$G$用$k$种颜色扩展部分$k$-颜色，以完成顶点$k$-颜色，使得$\rho$-快乐顶点的数量在所有这样的颜色扩展中最大。 该问题已知是 NP-hard，最优解与图的社区结构有直接关系。 此外，一些启发式方法和局部搜索算法，如{\sf 局部最大着色}({\sf LMC}) 和{\sf 本地 搜索}({\sf LS}) 已经在文献中被介绍。 在本文中，我们设计了遗传算法和进化算法用于软快乐着色，并在大量随机生成的部分着色图上进行了测试。 进化算法产生更多$\rho$-快乐顶点，但遗传算法只有在它们的初始种群通过{\sf LMC}或{\sf 最小二乘法}进行局部改进时才能表现良好。 统计显著的结果表明，当使用{\sf LMC}增强初始种群时，遗传算法和膜算法在社区检测中都能达到高平均准确率。 此外，在竞争方法中，进化算法确定了最多的完整解。 显示英文摘要

摘要： For $0\leq \rho\leq 1$, a $\rho$-happy vertex $v$ in a coloured graph shares colour with at least $\rho\mathrm{deg}(v)$ of its neighbours. Soft happy colouring of a graph $G$ with $k$ colours extends a partial $k$-colouring to a complete vertex $k$-colouring such that the number of $\rho$-happy vertices is maximum among all such colouring extensions. The problem is known to be NP-hard, and an optimal solution has a direct relation with the community structure of the graph. In addition, some heuristics and local search algorithms, such as {\sf Local Maximal Colouring} ({\sf LMC}) and {\sf Local Search} ({\sf LS}), have already been introduced in the literature. In this paper, we design Genetic and Memetic Algorithms for soft happy colouring and test them for a large set of randomly generated partially coloured graphs. Memetic Algorithms yield a higher number of $\rho$-happy vertices, but Genetic Algorithms can perform well only when their initial populations are locally improved by {\sf LMC} or {\sf LS}. Statistically significant results indicate that both Genetic and Memetic Algorithms achieve high average accuracy in community detection when their initial populations are enhanced using {\sf LMC}. Moreover, among the competing methods, the evolutionary algorithms identified the greatest number of complete solutions.