Many real world applications modelled as complex networks optimize multiple conflicting objective functions that change frequently over time. Solving multi-objective optimization problems (MOP) on complex networks, either static or dynamic, is NP-hard. Evolutionary multi-objective optimization (EMO) heuristics based on Pareto criterion (PC) dominance and non-Pareto criterion (NPC) decomposition techniques have been successfully used to solve dynamic MOP (DMOP). However, addressing both convergence and diversity, simultaneously, in either PC or NPC evolution is a challenge. Moreover, existing metrics are not robust to evaluate EMO algorithms for solving varying real-world applications that exhibit dynamic behaviour.

The contribution of this thesis is therefore two-fold: (i) we propose a co-evolutionary bi-criterion algorithm: Cooperative, Concurrent, Coevolutionary Multi-Objective (Co3_MO), that exploits the strengths of PC and NPC evolution to solve DMOP; (ii) we propose a new evaluation framework and metrics to measure convergence, diversity and dynamism of dynamic EMO algorithms.

We study our proposed algorithm, framework and metrics on the multi-objective travelling salesperson problem (MTSP) incorporating two popular complementary evolutionary techniques (NSGA-II and MOEA/D). We perform various experiments on both static and dynamic MTSP datasets and show that Co3_MO with local search and hybrid operators performs better than stand-alone EMO techniques. We also show that our proposed framework and metrics are flexible to incorporate domain-specific knowledge of an application to capture convergence, diversity and dynamism of the evaluated EMO algorithms.