In recent years, computing diverse sets of high quality solutions for an optimization problem has become an important topic. The goal of computing diverse sets of high quality solutions is to provide a variety of options to decision makers, allowing them to choose the best solution for their particular problem. We consider the problem of constructing a wireless communication network for a given set of entities. Our goal is to minimize the area covered by the senders' transmissions while also avoiding adversaries that may observe the communication. We provide evolutionary diversity optimization (EDO) algorithms for this problem. We provide a formulation based on minimum spanning forests that are used as a representation and show how this formulation can be turned into a wireless communication network that avoids a given set of adversaries. We evaluate our EDO approach based on a number of benchmark instances and compare the diversity of the obtained populations in respect to the quality criterion of the given solutions as well as the chosen algorithm parameters. Our results demonstrate the effectiveness of our EDO approaches for the detection and concealment of communication networks both in terms of the quality and the diversity of the obtained solutions.
This study proposes Evolutionary Diversity Optimisation (EDO) to Lower the Probability of Detection (LPD) in directed wireless networks. LPD communication aims to communicate between authorised parties, however minimises the probability that an intruder can detect the communication. We represent the problem as a directed graph and our objective is to minimise the area of detectability in a network whilst avoiding adversary nodes to be in the area. We utilise EDO to produce a population of solutions that are of quality i.e., that minimise the area of detectability whilst providing solutions that are diverse. To produce a solution, we find the strongly connected components by running depth-first-search (DFS) twice and extracting the edges traversed from the DFS runs. We use 3 permutation operators (insert, swap, random) to produce different solutions. We propose 2 methods for survival selection - one based on the diversity value and the other on the edge population count. We control the sparsity of the directed graphs by implementing a maximal communication range. Our results show that sparser graphs had smaller areas of detectability, however the final population was less diverse. We also found controlling the maximal communication range an effective strategy to reduce the area of detectability.