Enhancing Soft Happiness via Evolutionary Algorithms
Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari · 2025
Read Enhancing Soft Happiness via Evolutionary Algorithms by Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20934.txt.
Introduction
Mohammad Hadi Shekarriz, Dhananjay Thiruvady, and Asef Nazari attack a graph coloring puzzle with evolution in a 2025 paper. Soft happy coloring starts from a partly colored network and asks for a full coloring that leaves as many nodes as possible surrounded by enough same-colored neighbors. The puzzle is NP-hard, and its answers mirror community structure, which matters for security and resilience studies.
Pure local search polishes colorings fast but gets trapped in mediocre corners. The team built a memetic algorithm, a hybrid that breeds candidate colorings genetically and refines each by local search. On random graphs with planted community structure, the hybrid beat both plain local search and standard genetic methods, finding happier colorings and cleaner communities. Learning, the authors argue, lets evolution diversify what local search finds.
Catalog record
| CREATOR | Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20934
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enhancing Soft Happiness via Evolutionary Algorithms Mohammad H. Shekarriz, Dhananjay Thiruvady, Asef Nazari Abstract For 0 ≤ ρ ≤ 1 0\leq\rho\leq 1 , a ρ \rho -happy vertex v v in a coloured graph shares colour with at least ρ deg ( v ) \rho\mathrm{deg}(v) of its neighbours. Soft happy colouring of a graph G G with k k colours extends a partial k k -colouring to a complete vertex k 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 Local Maximal Colouring ( LMC ) and Local Search ( 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 generated by LMC or 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 LMC . Moreover, among the competing methods, the evolutionary algorithms identified the greatest number of complete solutions. 1 Introduction Evolutionary algorithms offer an adaptive framework for solving the optimisation challenges inherent in real-world networks, where the complexity of interconnections demands flexible search techniques [ 11 ] . By emulating the fundamental mechanisms of natural selection, including mutation and crossover, these algorithms can effectively navigate large multimodal solution spaces commonly encountered in network design and analysis [ 8 ] . Their ability to optimise configurations across domains such as social networks, cybersecurity, and neural systems has been demonstrated to enhance both system efficiency and resilience [ 2 ] . The flexibility inherent in multi-purpose evolutionary approaches allows the simultaneous balancing of often conflicting requirements, such as performance and robustness, thereby providing practical solutions in dynamic environments [ 8 ] . Our attention here is to use evolutionary algorithms for soft happy colouring , a graph colouring problem that is introduced in 2015 by Zhang and Li [ 25 ] . It seeks to maximise the number of \rho -happy vertices for 0\leq\rho\leq 1 , i.e., those vertices whose portion of same colour neighbours is at least \rho . If \rho=1 , the problem of soft happy colouring is called “happy colouring" and a 1-happy vertex is called a “happy vertex” [ 25 ] . Most published research papers on the subject focus on happy colouring rather than soft happy colouring, see [ 14 , 15 , 22 , 23 , 26 ] . Finding a happy colouring in a connected partially coloured graph presents a significant challenge, and research has predominantly considered the problem. For instance, an integer programming formulation combined with the construct, solve, merge & adapt (CMSA) was used in [ 14 ] , tabu search was used in [ 23 ] and [ 15 ] , and evolutionary algorithms and hybrid approaches combining with mixed integer program techniques were examined in [ 22 ] . The development of happy colouring is motivated by the principle of homophily [ 16 ] in social networks — a concept that is effectively embodied by the community structure of graphs [ 9 ] . A community [ 5 ] in a graph is a group of vertices of sufficient size, within which the interconnections are markedly denser than the connections with vertices outside the group. This concept is illustrated in Figure 1 for a graph with 11 communities. Nevertheless, conventional happy colouring (i.e. \rho=1 ) does not entirely partition the vertex set into happy colour classes in the case of connected graphs. This is primarily because in connected graphs, any colouring that employs more than one colour will inevitably include some unhappy vertices [ 14 ] . The problem is even more pronounced in dense and large graphs, where almost no happy vertices can be found [ 14 ] . However, in soft happy colouring the proportion of happiness , 0\leq\rho\leq 1 , merely pushed this limit and shown to have a strong relation with the community structure of graphs [ 20 ] . More importantly, colour classes of a \rho -happy colouring can represent the graph’s communities [ 19 ] . The colouring of the graph in Figure 1 demonstrates this relation as it is a complete 0.6-happy colouring whose colour classes are aligned with the communities of the graph. Figure 1 : A connected graph with 11 communities, which are grouped together. Grey lines are inter-community edges. The colouring here is aligned with the communities and is a complete 0.6-happy colouring. The objective of community detection is finding such a vertex partition. Real-world networks frequently exhibit community structures. In social networks, for instance, distinct groups often form around common interests or affiliations, thereby facilitating efficient information exchange and collective behaviour [ 18 ] . In the realm of cybersecurity, network architectures often reveal modular divisions that can mirror coordinated clusters of activity [ 24 ] . Similarly, neural networks display community structure through the formation of functionally specialised regions within the brain [ 21 ] . Detecting communities also helps increase the robustness of networks through enhancing the intercommunity links [ 7 ] . These cross-disciplinary examples underscore that community structure is a fundamental attribute of complex systems. By examining evolutionary algorithms for soft happy colouring, it is possible to see whether they are useful in revealing the community structure of graphs. The conventional type of evolutionary algorithms, namely Genetic Algorithms (GAs), utilises only the canonical genetic operators - selection, crossover, and mutation - to evolve a population of initial solutions over successive generations. While they usually offer robust global search capabilities, their convergence tends to be comparatively slow, primarily due to the random nature of their search process and lack of problem-specific refinement [ 4 ] . Another type of evolutionary algorithms, Memetic Algorithms (MAs), have been devised to represent a powerful hybridisation of evolutionary search and local optimisation techniques, to enhance the convergence speed [ 17 ] . The approach of Memetic Algorithms has shown to be successful in diverse areas such as scheduling, routing, and bioinformatics [ 6 ] . We introduce GAs and MAs in Section 3 in details. Algorithms for soft happy colouring consist of Greedy-SoftMHV and Growth-SoftMHV , which were introduced in [ 25 ] , Local Maximal Colouring (LMC) and Neighbour Greedy Colouring (NGC) from [ 20 ] , and three more heuristic-improvement algorithms Local Search ( LS ), Repeated Local Search ( RLS ), and Enhanced Local Search ( ELS ) introduced in [ 19 ] . Among these, LMC and LS (and sometimes RLS , when given a suitable input) proved to be fast and effective, and can be used in designing metaheuristics. In this paper, we introduce Genetic and Memetic Algorithms for soft happy colouring. The initial populations can come from random or fast heuristic solutions such as LMC