as the ∈-dominance (in ∈-NSGA-II (Kollat et al. 2005)) or the reference points (in NSGA-III (Deb and Jain 2014))

### 2.4.4 Hybridization of Meta-heuristics

In order to improve the performance of an algorithm or to fill some of its inconvenient, it may be combined with one or more method. In fact, these cooperative approaches allow the optimization methods combining their benefits to improve their performance in order to obtain better results. Hybrid approaches can be divided into two groups: The hybridization of metaheuristics and the hybridization of exact methods and metaheuristics. In what follows, we present the main hybridization schemes.

#### 2.4.4.1 Hybridization between metaheuristics

This hybrid approach consists in combining several different metaheuristics. Local search, annealing simulated, taboo research and evolutionary algorithms have already been successfully hybridized in several applications. In (Talbi, 1999), the author proposed a classification taxonomy of these different hybridizations. The idea of classification is based on a qualitative comparison of hybrid metaheuristics. The taxonomy has two aspects: A hierarchical classification which allows identifying the structure of hybridization. Then, a general classification which specifies the details of the algorithms involved in hybridization.

* **Hierarchical classification:** This classification is based on two classes: low-level hybridization and high-level hybridization. A low-level hybridization is obtained when a function of a metaheuristic is replaced by another metaheuristic. A high level hybridization is achieved when two metaheuristics are hybridized without relation between their internal functioning. Each of the two previous hybridization classes is subdivided into two other classes: relay hybridization and coevolutionary one. The relay hybridization occurs when metaheuristics are executed sequentially, i.e. a metaheuristic uses the result of the previous one as input. Coevolutionary hybridization occurs when agents cooperate in parallel to explore the solution space. Subsequently, as shown in Figure 2.10, there are four different classes of cooperation of all previously named classes: low-level relay, low-level co-evolutionary, high-level relay and high-level co-evolutionary.

First of all, low-level relay hybridization represents algorithms in which a metaheuristic is incorporated into another single-solution metaheuristic. Then, the low-level co-evolutionary hybridization consists in incorporating an exploitation-based local search algorithm into an exploration-oriented population metaheuristic. Afterward, high-level relay hybridization is achieved when complete metaheuristics are performed sequentially. Finally, high-level coevolutionary hybridization involves a set of metaheuristics that work in parallel and cooperate to find the optimal solution to a problem.

<figure><img src="image_26.png" /><figcaption>Figure 2.10 Classes of Hybridization</figcaption></figure>
* **General classification:** According to (Talbi, 2000), there is widespread classification taxonomy for hybrid metaheuristics with three dichotomies: homogenous vs. heterogeneous, global vs. partial and specialized vs. general hybrid approaches. Hybridization is said to be homogeneous when the combined metaheuristics are identical. Conversely, heterogeneous hybridization combines different metaheuristics. Global hybridization ensures that all metaheuristics explore the entire solution space while partial hybridization decomposes a problem into sub-problems having their specific solution space. Then, each sub-problem is given to an algorithm. Finally, the general hybridizations are those where all the algorithms solve the same optimization problem. On the other hand, the ‘specialized’ hybridizations are those where each algorithm solves a different optimization problem.

### 2.4.4.2 Hybridization of Meta-heuristics and Exact Methods

Exact methods seek to find the optimal solution by explicitly or implicitly examining the entire search space. Typically, exact methods are dedicated to solving small problems, while metaheuristics address a wide range of multi-objective problems. However, hybrid metaheuristic-exact approaches can combine the advantages of these methods to improve their performance and provide optimal solutions. There are several ways of hybridization. (Puchinger and Raidl, 2005) proposed a classification of metaheuristic-exact cooperation that is divided into two categories: collaborative and integrative hybridizations.

* **Collaborative hybridization:** Using this type of hybridization, the algorithms exchange information sequentially, in parallel or in an interlaced manner. Indeed, the sequential execution is done in such a way that the exact method is a pretreatment of the metaheuristic, or vice versa. For the interlaced or parallel performance, the two approaches are independent and deal with different parts of the problem.

* **Integrative hybridization:** The integrative combination of an exact method and a metaheuristic is done in such a way that one of the two algorithms is an integrated component in the other one. Therefore, we can integrate an exact method with a metaheuristic and vice versa.

## 2.4.5 Relationship between the deployment problem and the multi-objective optimization

In this section we justify the choice of using meta-heuristics and evolutionary optimization algorithms as an approach to solve the problem of 3D indoor deployment of nodes. Indeed, the deployment is a real-world complex problem that involves several often antagonistic objectives and different constraints (of localization or routing for example).

The deployment problem is proven to be NP-Hard *Cheng et al. (2008)*. As a result, there is no exact algorithm that can solve it in a polynomial time if the size of the problem exceeds a certain threshold. Most exact algorithms such as branch and bound provide an effective solution for the deployment problem only if it is a small problem (if the number of nodes does not exceed three).

Moreover, compared with geometric approaches (Voronoi Partitions, Virtual Forces) resolving the deployment, the optimization using meta-heuristics allows the user (DM) to choose between multitudes of possible solutions and even to guide the search towards the desired solution/solution set.

In addition, the evolutionary optimization approach is suitable for the deployment problem due to the distributed, dynamic and stochastic nature of this problem; and the existence of a research space containing a large number of possible solutions that are close to each other. The challenge is therefore to choose the closest to optimal solution.

When solving the problem of 3D deployment, aside from the exponential increase in cost (in terms of time and space), even Pareto-based EMOs become inefficient, the same for the recombination operation. Indeed, it was even proven (Purshouse et al., 2007) that, if we
increase the size of the problem (by increasing the number of nodes and the RoI to cover in
our case), the performance of the pareto-based algorithms degrades until the random choice of
node positions becomes more efficient than these latter algorithms. For more details
concerning the difficulties encountered by the multi-objective optimization algorithms when
solving complex real-world problems, refer to the section 2.4.3.6. In this regard, to enhance
the performance of the optimization algorithms to solve the 3D indoor deployment, a set of
modifications and justified hybridization schemes between these algorithms are proposed as
contributions in this dissertation.

**2.5 Multi-agent Systems**

In recent decades, multi-agent systems (MAS) have become increasingly important in computing as well as in artificial intelligence. Thanks to their distributed architecture, MAS become more responsive and have been used in different areas such as information retrieval, robotics or simulation of artificial life. Thus, MAS facilitate the construction of a distributed, heterogeneous, flexible architecture, and they are able to offer a high quality of service in a collective workspace. The fundamental issue of MAS is the theoretical and experimental analysis of mechanisms of self-organization when multiple autonomous entities interact and to the realization of artifacts able of accomplishing complex tasks by cooperation and interaction. A multi-agent system (MAS) is a decentralized system composed of a set of autonomous agents, located in a specific environment to achieve a global goal. MAS derived from the distributed *artificial intelligence* (Carabelea et al., 2004).

**2.5.1 Notion of Distributed Artificial Intelligence**

Distributed Artificial Intelligence (DAI) is a recent variant of artificial intelligence that adds the dimension of interaction and distribution of software components instead of having a single centralized software. The DAI goes from modeling a single intelligent agent to the modeling of a set of agents, generally in a cooperative relationship, to achieve a specific objective. This objective concerns usually a problem to be solved that is distributed and divided into a set of subproblems.

**2.5.2 Concept of agent**

There is no standard definition of an agent. As shown in Figure 2.11, an agent is a physical or
virtual entity capable of acting in a specific environment to which it was designed. A physical
entity like a robot, car, plane, thing (in IoT) and a virtual entity like a software, a computer
module. An agent can communicate directly with another agent through messages or with
stimuli. According to (Carabelea et al., 2004), an agent is defined as follows:

-An entity that perceives its environment and acts on it.

- A computer system, located in an environment, autonomously acting in order to achieve the goals (purpose) for which it was designed.

- An entity that operates continuously in an environment where other processes take place and other agents exist.

An agent has the following characteristics:

- Able to act in an environment.

- Can communicate directly with other agents.

- Has its resources, has skills and offers services.

- Able to perceive (but in a limited way) his environment and has a partial representation of this environment.

- Can reproduce.

- Its behavior tends to meet its objectives, taking into account the resources and skills it has, and according to its perception, its representations and the communications that it receives.
<figure><img src="image_27.png" /><figcaption>Figure 2.11 Schematization of an agent</figcaption></figure>

**2.5.3 Multi-agents systems**

MAS are systems grouping more than two agents and characterized by the following
properties (Xie and Liu, 2017):

- An environment E: each agent can perceive his environment and cannot act in another space.

- A set of object O which defines the agent's entourage.

- A set of object A which forms the set of agents with which an agent can communicate and interact.

- A set of relations R which define the existing relations between agents.

- A set of OP operation enabling the agents to move, communicate, consume, etc.

Hence, MAS (Figure 2.12) are based on the following principle: MAS = {Agent + Environment + Interaction + organization}.

<figure><img src="image_28.png" /><figcaption>Figure 2.12 Multi-agent System</figcaption></figure>

* **MAS characteristics:** Several characteristics are related to the agent concept. The most interesting features are as follows:

- **Autonomy:** this is one of the leading characteristics of MAS. It implies that the elements of MAS have their autonomy. Indeed, agents are not guided either by commands or by the human intervention.

- The capacity to act: an agent is conceived for a specific treatment. Hence, it is guided by a set of objectives. It must not be influenced by the interactions of its environment.

- **Reactivity:** a reactive agent is used to achieve a task for which it receives orders or stimuli from its environment.

- **Perception:** the agent may have a vision of its local environment and the agents in this environment.

- **Sociability:** depending on the nature of the environment, the agent interacts with other agents or human beings to accomplish a task.

- **Anticipation:** the agent can perceive, in a limited way, future events.
- Adaptability: the agent must be adapted to any changes in its environment.

- Communication: the communication between agents is necessary to define when conceiving MAS. In a cognitive system, communication is ensured through messages whereas in a reactive system, the communication is achieved by the diffusion of signals.

- Learning: it allows to agents to acquire new knowledge after the communication phase.

- Cooperation: When cooperating, agents are engaged in a joint action aiming to facilitate and accelerate the execution of common task.

- Interaction: is a primary feature of MAS which serves to define a dynamic relationship between two or several agents. This characteristic gathers the collaboration and the coordination.

- Distribution of tasks: considering the limited capacities of an agent in energetic, computation, and memory resources, and the complexity of problems, agents are forced to divide the problem into sub-problems.

- Decentralization: It makes the MAS more reliable and robust. It can overcome the failure of a single agent.

**\* Advantages and disadvantages of MAS:** The use of MAS has a set of advantages such as the distributed solving of problems and the possibility of obtaining a stable solution following the decomposition of the problem into independent sub-problems and the collection of these partial solutions. Besides, MAS can resolve individual failures of agents without much affecting the performance of the overall solution. These systems also give the possibility of practically realizing situations and experiences which are difficult to achieve in reality. However, MAS has some limitations such as the complexity, the difficulty of modeling, issues related to the gathering of solutions and the implementation.

### 2.5.4 Agents types

Agent differs in the functionality for which they are designed. Agents can be classified as follows:

- **Cognitive agents:** an agent is considered as intelligent, has a knowledge base containing the necessary information for its operation. It has the capacity of reasoning and communicating. Agents can simulate human behavior.

- **Reactive agents:** a reactive agent is guided by a set of rules and reacted only to respond to a query or a stimulus. It does not have any means of memorization.

- **Mobile Agents:** a mobile agent is an agent that moves in its environment to do a treatment or giving information.

- **Collaborative agents:** these are autonomous agents who work together to solve a problem.

- **Internet agents:** this type of agents is more used mainly in the searching, gathering and collecting data, or administering websites.

- **Interface agents:** this type of agents assists the user and can be adapted to its habits.

- **Hybrid agents:** represent agents that combine more than two characteristics such as mobility, responsiveness and collaboration.

### 2.5.5 Software platforms for MAS

A platform is a tool that allows the development of agents. Actually, many platforms exist; the most popular are the following ones:

- **JADE:** it is an open source platform developed in java. Created by Gruppo Telecom laboratory in order to realize cognitive MAS according to the FIPA standard. The latter standard establishes the normative rules that allow to a company of agents to interoperate. Agents communicate with each other using the ACL language.

- **MADKIT:** is an evolutionary platform used to develop MAS, especially MAS based on organizational criteria. It is based on the AGR model (agent/group/role).
- **Jack**: is an environment for the development, execution and integration of commercial MAS. Developed in Java, Jack is characterized by its strong focus on programming agents.

- **Jadex**: a new platform for building goal-oriented agents according to the BDI model (belief-desire-intention).

### 2.5.6 Applications of MAS in WSN

WSN can be used to collect information from environments to which the human being does not always have access. A WSN is a system consisting of several nodes that may acquire data of its environment, to communicate with each other, to achieve a specific number treatment. Most of these features are better resolved with MAS. The use of MAS can solve real-world problems such as routing and energy consumption.

- **Sensor deployment**: (Mekni and Haddad 2010) addressed the problem of sensor web deployment, considered as a spatial problem because of the high-influence of the geographic specificities of the space on the nodes. As an approach, a geo-simulation framework based on a multi-agent system is proposed to simulate sensor deployment in Informed-Virtual-Geographic Environments. Moreover, Qi et al. (2015) aim to resolve the problem of modelling and designing large-scale multi-agent systems deployed in 3D spaces. The proposed method relies on partial differential equations (PDEs) control.

- **Routing**: The routing problem consists in establishing an optimal routing of packets across the network in the sense of a particular performance criterion such as energy consumption. Although, sometimes we do not seek a minimal route but a distributed loads between nodes. MAS composed of a large number of nodes are characterized by an unstable topology. Thus, MAS needs to be adapted to any change in the network and must establish the shortest routes between different nodes. Several routing protocols have been developed.

- **Clustering organization**: when the size of the network is important, its management becomes difficult. Clustering is often used to optimize the energy consumption and the routing. A cluster is defined by a set of nodes according to several criteria such as the geographical position and the connection between nodes.

## 2.6 Preferences incorporation

### 2.6.1 Generalities

In general, the DM needs only a small number of non-dominated solutions, especially for real-world problems. On the other hand, the result of a MaOA is a set of non-dominated uniformly distributed solutions. Moreover, since the user does not need to know all the points on the PF and knowing that the population size and the number of solutions necessary to approximate the hole PF increase exponentially with the number of objectives (Ishibuchi et al. 2008), it is interesting to focus the search on some specific regions according to the user's preferences. Besides, in real-world problems, the size of the population is usually too limited compared to the high-objective space which prevents producing meaningful results (Rachmawati et al. 2006). Hence, incorporating preferences aim at resolving the problem of low selection pressure for convergence by carrying out a preference ordering over non-dominated solutions. In fact, most of the studies presented in literature either focus on only a part of the PF, which improves convergence but decreases diversity, or has a high computational time which increases exponentially as the number of objectives rises. A review that discusses the studies investigating the preference approaches is available in (Ishibuchi et al. 2008).

When designing a preference-based method, two issues must be considered: when integrating the preference information? And what is the model of preference? Different preference models can be cited, such as the *objective rankings*, the *trade-off between objectives* and the *goal specification* (Rachmawati et al. 2006).
Based on the time of integrating the preference information, preference methods can be
classified into three main categories (Jaimes et al. 2011):

- **A priori algorithms** where the preference information which directs the population to converge to a PF subset is known before starting the search for solutions.

- **Interactive algorithms** where the process of optimization asks the DM to introduce the preference information interactively to guide the search to a specific PF subset. In fact, only a few studies aiming at progressively incorporating the user's preferences following the evolving of the new solutions were proposed.

- **A posteriori algorithms** where the preference information is given after executing the MaOEA.

Because they focus the search orientation on the region of interest, the interactive and a priori
algorithms are more likely to pay more attention to preferred solutions and reduce the
computational cost during the search process. A posteriori preference-based approaches might
give a large number of solutions which are non-interesting to the DM. In our works, as an
interactive preference reduction method, we use PI-EMO-PC (Sinha et al. 2014). Despite
their numerous advantages, the major weakness of the interactive techniques is that the
algorithm used in such techniques need to interact frequently with the DM who can become
tired, which leads, in some cases, to misleading information about the preference information
provided by the exhausted user (Gong et al. 2013). Thus, to overcome this limitation in our
work, we suggest a hybrid preference process.

The progressive engagement of the preferences (interactive algorithms) is more efficient since it allows the DM to adjust his preferences during the intermediate generations of an algorithm (Sinha et al. 2013). Therefore, a model based on an enhanced PI-EMO-PC is used as a 'preference method' in our work.

**2.6.2 Interactive preferences (PI-EMO-PC)**

As an instance of interactive preferences methods, we can mention the PI-EMO-VF (Deb et al. 2010) based on an approximate value function where the EMO algorithm dispose of a set of well-sparse non-dominated solutions progressively generated after every few generations and ask the DM to provide his preference information about the relation of one solution over another. Ideally, the DM gives a complete ranking of solutions (from best to worst). Otherwise, he provides partial preference information. The given preference information is employed to construct an increasing polynomial value function. According to the expected progress and the constructed value function, a termination condition is set up. In fact, the proposed PI-EMO-VF is a generic procedure that can be incorporated into any existing EMO. However, as mentioned by its authors, a set of parameters is expected to be specified by the user such as τ (the number of EMO iterations after which the PI-EMO-VF is called), η (the number of desired non-dominated solutions for which a preference information is given) and ds (the expected improvement in the solutions from the current best solution based on the value function. From the aforementioned ideas, we may conclude that PI-EMO-VF method has several drawbacks as it: i) needs a partial or complete ordering of the set of points, ii) requires to solve another optimization problem in order to construct the DM's value function and to know (as a parameter in the algorithm) the number of generations after which the DM call will be performed. Moreover, the unknown number of DM calls at the beginning of the algorithm.

To design our proposed hybrid preference algorithm, as an interactive preference, we use
another recent variant of the PI-EMO, called progressively interactive EMO based on
polyhedral cones (PI-EMO-PC). Indeed, like the PI-EMO-VF procedure, PI-EMO-PC was
implemented on the NSGA-II algorithm. But, it is possible to integrate it with any other multi-
objective EMO algorithm. Besides, PI-EMO-PC can successfully handle the PI-EMO-VF
drawbacks by simultaneously reducing the number of needed parameters in PI-EMO-VF and providing better performance. PI-EMO-PC replaces the process of constructing a value function by using polyhedral cones to modify the domination criteria of an EMO and guides it towards the region of interest which is a single most preferred point on the high-dimensional PF. PI-EMO-PC needs as input a parameter $T_{DM}$, representing the maximum number of times the preference information is required in order to be provided by the DM, and a parameter $|A|^{max}$ designating the maximum archive size. The best member of the archive set is chosen according to the preference information. The archive A is initially empty. Then, after each generation, it will include all the found feasible non-dominated solutions. If the size of the archive exceeds its maximum, a k-mean clustering will be applied to keep the diverse set of $|A|^{max}$ clusters and the rest of the solutions will be deleted. Despite the fact that the PI-EMO-PC procedure was developed using the NSGA-II algorithm, it is a generic procedure which can be integrated into any other multi-objective EMO algorithm. However, the PI-EMO-PC suffers from some drawbacks such as the need to know the number of DM calls in advance and the risk to have wrong directives if the DM becomes tired. To solve these problems, we introduce a hybrid preference procedure which requires fewer parameters and more flexibility when interacting with the DM.

## 2.7 Dimensionality reduction

### 2.7.1 Generalities

As an example of approaches used to overcome the complexity of many-objective problems, we can mention the dimensionality reduction which assumes the existence of a set of redundant objectives in a given M-objective optimization problem. Based on the objective vectors of the obtained non-dominated solutions, the dimensionality reduction approaches aim at identifying the smallest set of conflicting objectives which is smaller than the original set of objectives and that generates the same PF as the original problem. Since the same PF is preserved, the reduction does not cause information loss (Saxena et al. 2013). In these approaches, the resulting objectives are considered as necessary, while others are regarded redundant. Relying on the study of the correlation structure between the objectives and the dominance relations, the dimensionality reduction approaches allow reducing the number of objectives to three or less. Hence, an unsolvable problem will become solvable with a lower computational cost, higher search efficiency and easier visualization. Therefore, if a high-dimensional many-objective problem and a lower-dimensional one have similar PF, then the latter can be optimized instead of the former one.

Considering the time of incorporating it into the MaOEA, a dimensionality reduction method can be classified either as an offline or online method. In offline methods, dimensionality reduction is performed after obtaining Pareto optimal solutions. Offline methods are classified into three sub-categories (Lan et al. 2010): feature selection-based, dominance structure-based and correlation-based methods. However, in online methods, dimensionality reduction is carried out gradually. In other words, in each iteration, a set of solutions is obtained and the dimensionality reduction method is invoked. Applying such methods, the number of objectives can be reduced progressively during the search process.

The current reduction methods can be summarized as follows:

- Machine Learning-based (Deb et al. 2006): consists in using machine learning techniques, such as Maximum Variance Unfolding (MVU) and Principal Component Analysis (PCA), to eliminate the dependencies of the second and higher order in the non-dominated solutions respectively.
- Dominance Relation Preservation-based (DRP): As introduced in (Brockhoff et al. 2006), this reduction method relies on the preservation of the dominance relations in the given non-dominated solutions.

- Pareto Corner Search based (PCS): Singh et al. (2011) proposed a Pareto corner search evolutionary algorithm (PCSEA) which aims at finding only the corners of the PF instead of searching the complete PF assuming to adequately investigate the dependencies of the different objectives.

- Unsupervised Feature Selection-based (UFS): This method proposed in (Jaimes et al. 2008) examines the correlation among objectives by considering the distance between objectives as a metric to evaluate the conflict between them.

The dimensionality reduction methods are efficient in the sense that they: i) can be easily and consistently be combined with other approaches, ii) help the DM understand the many-objective problem by eliminating redundant objectives and iii) minimize the computational cost of the many-objective evolutionary algorithm.

However, dimensionality reduction methods suppose the existence of redundant objectives, which may restrict the applicability of these approaches when the problem to be solved has no redundant objectives. Consequently, dimensionality reduction techniques may fail to minimize the number of objectives or give a set of solutions which does not cover the complete Pareto front. In our works, as a reduction method, we use machine learning techniques MVU-PCA (Principal Component Analysis and Maximum Variance Unfolding) which is an offline correlation-based reduction method.

## 2.7.2 Offline correlation reduction methods based on machine learning for the 3D deployment problem

Machine learning-based objective method is a reduction approach relying on the fact that the structure of a high-dimensional data may be transformed in order to minimize the effect of noise (non-optimal solutions that may be different from those which define the true POF) and dependencies (redundancy) between the different objectives.

Our studied problem, the 3D Deployment of WSNs, can be viewed as a machine learning objective reduction problem due to:

- The redundancy and the presence of non-conflicting and correlated objectives.

- The structure of the PF of our problem which refers to its intrinsic dimensionality (m) and essential components.

- The garbled high-dimensional data which refers to the non-dominated solutions resulting from the EMO algorithm, generally providing a poor POF-approximation. Thus, correlated objectives on the POF can show a partial conflict in the proposed EMO solutions.

## 2.8 Conclusion

This chapter has been devoted to describe the different types of optimization problems and their classifications. A presentation of the various resolution approaches existing in the literature, such as; the aggregation approach, the ε-constraints approach and the goal-based programming approach is given. Indeed, when the number of objectives is higher or the problem is large, meta-heuristics; despite giving approximate solutions; are less demanding in terms of computation time and execution time. Thus, they are the most used for the resolution of real problems. Moreover, we detailed the characteristics of MAS, as well as the dimensionality reduction. And finally, we gave an idea about the incorporation of the user preferences. The next chapter is dedicated to present the proposed mathematical formulation of the 3D indoor deployment problem relying on real assumptions and constraints taken from our real prototyping tests. Then we present the proposed modifications and hybridization schemes aiming at improving the performance of the tested algorithms in the context of many-objective complex real world problems.
# Part II
## Contributions
Chapter 3

Theoretical contributions

<table><tr><td>3.1 Introduction</td><td>62</td></tr><tr><td>3.2 Mathematical model of the 3D indoor deployment in DL-IoT collection networks</td><td>62</td></tr><tr><td>3.2.1 Architecture of nodes, assumptions, notation and objective function</td><td>62</td></tr><tr><td>3.2.1.1 Architecture of nodes</td><td>62</td></tr><tr><td>3.2.1.2 Assumptions</td><td>62</td></tr><tr><td>3.2.1.3 Notation</td><td>63</td></tr><tr><td>3.2.1.4 The objective function</td><td>65</td></tr><tr><td>3.2.2 The details of the objectives</td><td>65</td></tr><tr><td>3.3 Hybridizations and modifications on the optimization approaches for the 3D deployment</td><td>71</td></tr><tr><td>3.3.1 Chromosome coding for the proposed MaOEAs</td><td>71</td></tr><tr><td>3.3.2 Inclusion of diversity</td><td>72</td></tr><tr><td>3.3.2.1 Neighbourhood restriction and adaptive multi-operators</td><td>72</td></tr><tr><td>* Principles of the mutation and recombination with the neighbourhood (AxN and AmN)</td><td>72</td></tr><tr><td>* Implementation of the AxN and AmN strategies on the proposed algorithms</td><td>74</td></tr><tr><td>3.3.2.2 Including single-grid and mutiple scalarizing functions in the aggregation based approach</td><td>76</td></tr><tr><td>3.3.3 Incorporation of Dimensionality Reduction (the NL-MVU-PCA algorithm)</td><td>77</td></tr><tr><td>3.3.3.1 Incorporating L-PCA and NL-MVU-PCA on the tested EMOs</td><td>77</td></tr><tr><td>3.3.3.2 Integrating PI-EMO-PC, Knee points and NL-MVU-PCA on the proposed EMOs</td><td>77</td></tr><tr><td>3.3.4 Incorporation of preferences</td><td>78</td></tr><tr><td>3.3.4.1 PI-NSGA-III-VF (NSGA-III with interactive preferences)</td><td>79</td></tr><tr><td>3.3.4.2 The proposed hybrid PI-EMO-PC-INK algorithm: (PI-EMO-PC-Ideal-Nadir-Knee points)</td><td>81</td></tr><tr><td>3.3.5 AcNSGA-III: a hybrid framework for NSGA-III and Ant system</td><td>82</td></tr><tr><td>3.3.6 The proposed acMaPSO algorithm: including the concept of birds accents in MaOPSO</td><td>84</td></tr><tr><td>3.3.6.1 The bird accent concept</td><td>84</td></tr><tr><td>3.3.6.2 The accent measure</td><td>85</td></tr><tr><td>3.3.6.3 The clustering in multiple Swarms</td><td>85</td></tr><tr><td>3.3.7 Hybridizing Particle Swarm Optimization and Multi-Agent Systems</td><td>86</td></tr><tr><td>3.3.7.1 Multi-agent Systems</td><td>86</td></tr><tr><td>3.3.7.2 The advantage of using the multi-agent approach in our context</td><td>86</td></tr><tr><td>3.3.7.3 The acMaMaPSO: A hybrid algorithm based-on accent multi-agent many-objective PSO</td><td>87</td></tr><tr><td>3.4 Conclusion</td><td>90</td></tr></table>
**3.1 Introduction**

To resolve our problem, we suggest an Integer linear programming formulation. Indeed, a set of constraints, like the distribution of nodes, the number of hops between them, the distances and paths and the quality of links, were considered. Different parameters, such as the initial deployed node locations, the cost of deploying a node, the transmission signal strength and the minimal required power of the received signal to detect a target, were taken into account in our model. Moreover, we illustrate in this chapter the specifications of the proposed modified algorithms. Firstly, we detail the manner of coding the chromosomes used in the evolutionary considered algorithms. Afterwards, we present the proposed modifications incorporated in the many-objective algorithms. Among these modifications, the use of the neighbourhood and an adaptive guided concept for the mutation and recombination operators, and the use of multiple scalarizing functions in the aggregation based approaches. Moreover, we present the different hybridization schemes aiming at improving the behavior of the tested algorithms and enhancing their performances in solving complex real world problems. These hybridization include, among others, the incorporation of the reduction of dimensionality, the users preferences and multi-agent systems.

**3.2 Mathematical model of the 3D indoor deployment in DL-IoT collection networks**

**3.2.1 Architecture of nodes, assumptions, notation and objective function**

**3.2.1.1 Architecture of nodes**

We consider the following types of nodes:

- Stationary nodes composed of the set of fixed nodes initially installed. This type of nodes can be randomly disseminated. But, it is better to adopt a strategy to distribute them according to the applicative objectives.

- Nomad nodes added to enhance the 3D deployment scheme. Their locations are determined by the proposed genetic algorithms.

- Mobile nodes (targets) include a set of persons to control. They are equipped with a sensor transmitting and receiving signals.

**3.2.1.2 Assumptions**

The following assumptions are considered:

- An *anchor node* is defined as a node having a known position. It can be an initial sensor placed in a specific location, a nomad sensor or a sensor attached to a mobile target. This assumption was imposed by the used localization protocol.

- Conforming to the used 3D localization protocol, we supposed that four anchors were needed to locate each mobile target. Indeed, we propose a hybrid localization scheme that improves the used range-free technique (3D DV-Hop) by introducing a range-based localization (RSSI data). First, the 3D DV-Hop used the information of the network connectivity to estimate the 3D positions of the nodes. Then, the RSSI value was applied to correct both these positions found by the 3D DV-Hop according to the signal strength and the distances between each mobile node to be localized and its four nearest anchors. As it will be mentioned later in the experimentations, we measured the RSSI value in two directions: i) that received from other fixed or nomad nodes was measured starting from each mobile node, and ii) that received from the concerned mobile node was measured beginning from each fixed or nomad node. The final admitted RSSI value between the mobile node and each other node is the highest. Figure 3.1 shows the proposed localization principle using the 3D DV-Hop and the RSSI algorithm.
<figure><img src="image_29.png" /><figcaption>Figure 3.1 The 3D DV-HOP and RSSI protocol</figcaption></figure>

- Rooms and halls are supposed to have heterogeneous 3D spaces.

### 3.2.1.3 Notation

The following sets, decision variables and parameters were used:

* **Sets**

S: is the set of potential sites where sensor nodes can be installed, $S = S_a \cup S_b$ such that "$S_a$" is the set of potential sites where stationary sensor nodes can be installed. "$S_b$" is the set of potential sites where the nomad sensor nodes can be installed. Note that a site must not be in both sets. Thus, $S_a \cap S_b = \emptyset$.

N: is a set that denotes the different types of the nodes. Let $N = N_a \cup N_b$ such that "$N_a$" is the set of different types of stationary nodes and "$N_b$" is the set of different types of nomad nodes. We can use various types of sensors having different functionalities which can be gathered in the same sensor like detecting the degree of temperature, the degree of luminosity or the opening and closing of doors.

T: is the set of mobile targets to be detected; “$t_k$” is a target.

V: is the set of nodes having different types in N and deployed in several sites in S.

K is the set of scheduling periods when a sensor $i \in V$ is activated.

* **Decision Variables**

$S_{g_{ss}}$, equal to 1 if the node positioned at a site $s \in S$ receives a signal from another node positioned at a site $s' \in S$ with a power of transmission greater than or equal to the minimum required power to detect it.

$T_{ss'}$, equal to 1 if the node positioned at a site $s \in S$ transmits a signal from another node positioned at a site $s' \in S$ with a power of transmission greater than or equal to the minimum required power to detect it.

$X_{ts}$ equal to 1 if a node positioned at a site $s \in S$ can receive a signal from a target located at a position $t \in T$ with a power of transmission greater than or equal to the minimum power required to detect it.

SP$^{ss'}$ represents the shortest path (in terms of hops) between two nodes situated in two sites $s \in S$ and $s' \in S$.

$L_{ss'}^{ab}$, equal to 1 if the link (s, s') is used to route the traffic flow from source node a $\in S$ to a destination node b $\in S$, knowing that SP$^{ss'}$ is the shortest path (in terms of hops) between a and b.

$Pos_{ijk}$ a real variable representing the 3D coordinates (i,j,k) providing the potential position of a sensor in the indoor space.

$CovP_{ijk}$ equal to 1 if and only if the position $Pos_{ijk}$ is covered by a node with a power of transmission greater than or equal to the minimum required power to detect it.
$Pfx_s^n$ set to 1 if a fixed sensor having a type $n \in N$ is positioned at a site $s \in S$; 0 otherwise.

$Pnd_s^n$ set to 1 if a nomad sensor having a type $n \in N$ is positioned at a site $s \in S$; 0 otherwise.

$Pmb_s^n$ set to 1 if a mobile sensor having a type $n \in N$ is positioned at a site $s \in S$; 0 otherwise.

## Parameters

$r$ corresponds to the radius of a sensor.

nbT denotes the number of mobile targets. “nbF”, is a parameter representing the number of initially-deployed stationary anchors. This number can be set by default to a random number or to $n_{min} \times (nm / 2\Pi r^2)$. “nbN” is a parameter representing the number of nomad nodes needed to be added. Let $N_{max}$ be the maximum number of nodes that can be deployed within the wireless network. Thus $(nbT+nbF+nbN) \le N_{max}$.

$C_s^n$ is the hardware cost of a node (including price) having a type $n \in N$ and installed at a site $s \in S$.

$E_0$ is the initial remaining energy of the sensors. We assume that sensors have the same $E_0$. $Bt_i$ is the remaining energy in the battery of the sensor i at an instant t.

$n_{min}$ stands for the degree of coverage. It defines the minimum number of nodes receiving a signal from a target to localize it. When using the proposed hybrid 3D localization model (based on 3D DV-Hop and RSSI), the parameter $n_{min}$ is generally set to 4.

$\delta_{ss}$ represents the attenuation ratio between two nodes in two sites $s \in S$ and $s' \in S$.

$\gamma_{ts}$ designates the attenuation ratio of the signal from a target $t \in T$ to a site $s \in S$.

$P_t$ represents the power of transmission of a target having a position $t \in T$ (in watts).

$P_{min}^n$ corresponds to the threshold for the receiver power. It is the minimum required power of the signal (RSSI) transmitted by (received from) a node having a type $n \in N$ to detect it.

$hp_{max}$ is a parameter defining the maximum allowed number of hops between any nomad node and a stationary node installed at site $s \in S_a$.

$M_s^m$ stands for the required number of hops between the nomad node ‘m’ and the nearest stationary node installed at the site $s \in S_a$.

$Q_s^m$ designates the number of nodes (stationary or nomad) installed at site $s \in S$ for which a nomad node ‘m’ is critical (all available paths must pass through ‘m’).

$TF_{max}$ is a parameter defining the maximum number of nodes (thus, the maximum quantity of signal) for which a nomad node ‘m’ is critical (all available paths must pass through ‘nm’).

$d_{ts}$ is a parameter representing the distance between two nodes ‘t’ and ‘s’.

$d_{max}$ is a constant representing the maximum distance separating a node i and a target j or separating two nodes i and j so that they could detect each other.

$l$ is a parameter representing the RoI (region of interest) length.

$w$ is a parameter representing the width of the RoI.

$h$ is a parameter representing the height of the RoI.

$Lf > 0$ is the lifetime of the network (i.e. time till the required-degree of coverage is maintained) and $Lfmax$ is an upper bound for $Lf$. $Lf_i$ is the lifetime of the sensor $i \in V$.
$TP_i^r$ representing the transmitted power of the signal (the emitted RSSI) of the sending node $i \in V$.

$RP_i^r$ representing the received power of the signal (the emitted RSSI) at a distance $r$ from the sending node $i \in V$.

### 3.2.1.4 The objective function

The many-objective fitness function is: Maximize $F(\vec{x})$ where $F(\vec{x}) = (f1, ..., f14)$.

## 3.2.2 The details of the objectives

### 3.2.2.1 The number of the added nomad nodes

The number of nomad nodes to be added must be minimized. The following function is proposed for the number of added nomad nodes:

$$f1 = \text{Minimize} \sum_{s \in S_b} Pnd_s^n \quad (1)$$

Subject to

$$\sum_{s \in S} Pfx_s^n \le nbF \quad \forall s \in S, n \in N \quad (2)$$

$$\sum_{s \in S} Pnd_s^n \le nbN \quad \forall s \in S, n \in N \quad (3)$$

$$\sum_{s \in S} Pmb_s^n \le nbT \quad \forall s \in S, n \in N \quad (4)$$

### 3.2.2.2 Energy consumption

A deployed active sensor dissipates energy when transmitting, sensing, receiving, or being idle. Therefore, energy efficiency is considered as a fundamental key in designing a wireless sensor network. Because sensing and being idle energies are negligible compared to the receiving and transmitting energies, we proposed a model where $E_i^{elec}$ represents the dissipated energy to activate the transmitter/receiver circuit and $\epsilon_{amp}$ represents the transmitter amplifier to communicate. The energy consumed to transmit an m-bit packet to a distance d is $E_i^{transm}$ and the energy consumed to receive the same packet is $E_i^{recv}$.

$$f2 = \text{Minimize} \sum E_i^{transm} + \sum E_i^{recv} \quad (5) \text{ where } E_i^{recv} = E_i^{elec} \times m \text{ and } E_i^{transm} =$$

$$E_i^{elec} \times m + \epsilon_{amp} \times m \times d^2 \quad (5) \text{ Subject to the following constraints:}$$

In order to minimize the consumption of energy, we can minimize the interferences during transmission. The interference caused by neighboring nodes can be reduced by limiting the maximum number of neighbors that a sensor/relay can have as shown in (5)

$$\sum_{s=0,n=0} Pfx_s^n + \sum_{s=0,n=0} Pnd_s^n + \sum_{s=0,n=0} Pmb_s^n \le nbT + nbF + nbN + |S| - |S| \times (Pfx_s^n + Pnd_s^n + Pmb_s^n) \quad (6)$$

$$0 \le Bt_i \le E_0 \le E_i^{transm} + E_i^{recv} \quad \forall i \in V \quad (7)$$

Constraint (7) implies that the expenditure of each sensor in energy cannot exceed the available energy in the battery of this sensor.

$L_{ss'}^{ab} \le Z_a^k, \forall a, b, s, s' \in V, k \in K$ (8) where $Z_a^k$ is equal to 1 if the sensor $a$ is activated during a period $k \in K$.
Constraint (8) indicates that if there is a route passing through the sensor ‘a’, then ‘a’ should be in a period of activity.

### 3.2.2.3 Hardware deployment cost

WiNo nodes (Van den Bossche et al. 2016) support the IEEE 802.15.4 protocol and represent a practical solution for indoor generic sensing nodes. The nomad WiNo nodes to be added can be of different heterogeneous types ($n \in N_b$). Even if they are all of homogeneous types, the cost of deploying the same node varies according to the site ($s \in S_b$). For example, deploying a node attached to a wall is considered cheaper than attaching it in the middle of room space. Thus, the deployment cost can be considered as an objective to minimize separately from the minimization of the number of added nomad nodes. Thus:

$$f3 = \text{Minimize} \sum_{s \in S_b} \sum_{n \in N_b} Pnd_s^n C_s^n \quad (9)$$

### 3.2.2.4 Network Utilization

In order to improve the lifetime of the network, many nodes can be placed close to the base station(s) which may result in poor utilization of the network resources and increased cost of deployment. Thus, it is important to maximize the network lifetime while deploying a reasonable number of nodes. The network utilization (NU) is defined as:

$$\text{Maximize} \quad lf / \sum (Pfx_s^n + Pnd_s^n + Pmb_s^n), \quad \forall s \in S, n \in N \quad (10)$$

To linearize our model, we suggest a new variable $\overline{lf} = 1/lf$. Thus, (10) becomes:

$$f4 = \text{Minimize} \quad \overline{lf} \times \sum (Pfx_s^n + Pnd_s^n + Pmb_s^n), \quad \forall s \in S, n \in N \quad (11)$$

$$\text{Subject to} \quad \overline{lf} \times \sum (Pfx_s^n + Pnd_s^n + Pmb_s^n) \le \overline{lf} \max \quad \text{where} \quad \overline{lf} \max = 1/lf \max \quad (12)$$

### 3.2.2.5 Localization rate

We propose a hybrid localization scheme that improves the used range-free technique (3D DV-Hop) by introducing a range based localization RSSI (Received Signal Strength Indication). To guarantee better localization, each target $t \in T$ should be monitored by at least $n_{min}$ anchor nodes. Then, $\sum_{s \in S} x_{ts} \ge n_{min} \forall t \in T$. Thus, the following function (13) is suggested to model the localization:

$$f5 = \text{Maximize} \quad \sum_{t \in T} (\sum_{s \in S} x_{ts} - n_{\min})^+ \quad \text{where} \quad (x)^+ = \max(0,x) \quad (13)$$

$$\text{Subject to} \quad \sum_{s \in S} x_{ts} \ge n_{\min} \forall t \in T \quad (14)$$

Constraint (14) indicates that the number of nodes receiving a signal (calculated by the RSSI) from the target $i$ should be greater than or equal to the minimum necessary to localize it.

### 3.2.2.6 Coverage rate

The coverage rate depends on the targets to cover. The FER (Frame Error Rate) is the metric used to measure the coverage degree. To guarantee a full coverage, each position in the 3D indoor space should be monitored by at least $n_{min}$ nodes. Hence, $\sum_{s \in S} \text{Cov} P_{ijk} \ge n_{min}$. Thus, we suggest the following function (15) to model the coverage:
$$f6= \text{Maximize} \sum_{t \in T} \left( \sum_{s \in S} \text{Cov} P_{ijk} - n_{\min} \right)^{+} \text{ where } (x)^{+} = \max(0,x) \quad (15)$$

### 3.2.2.7 Lifetime

In the literature, the network lifetime can be defined as the time during which the first node totally dissipates its energy or as the time until the first loss of coverage appears. In fact, different factors, such as node density, node transmission, initial energy and routing strategies, can influence the network lifetime. To model the lifetime, we suggest the following function:

$$f7= \text{Maximize} \ Lf \quad (16)$$

Subject to the following constraints:

$$Lf = \min_{i=1,2,...,N_{\max}} Lf_i \quad (17)$$

where $N_{max} = Pfx_s^n + Pnd_s^n + Pmb_s^n$, $\forall s \in S$, $n \in N$ and $Lf_i = Bt_i / \max(E_i^{transm} + E_i^{recv})$, $\forall i \in V$. The lifetime of the network is equal to the minimum lifetime $Lf_i$ among the lifetimes of all sensors.

$$\sum_{s' \in S} L_{ss'}^{ab} \times Lf - \sum_{s' \in S} L_{s's}^{ab} \times Lf = D_s \times Lf \times Pfx_s^n \forall s \in S, n \in N \quad (18)$$

$$\sum_{s' \in S} L_{ss'}^{ab} \times Lf + \sum_{s' \in S} L_{s's}^{ab} \times Lf \le U_{\max} \times Lf \times Pfx_s^n + U_{\max} \times Lf \times Pnd_s^n \forall s \in S, n \in N \quad (19)$$

$$\sum_{s' \in S} E_{i}^{transm} \times L_{ss'}^{ab} \times Lf + \sum_{s' \in S} E_{i}^{recv} \times L_{s's}^{ab} \times Lf + D_{s} \times Lf \times Pfx_{s}^{n} \le Bt_{i} \times Pfx_{s}^{n} + Bt_{i} \times Pnd_{s}^{n} \forall s \in S, n \in N \quad (20)$$

$$\sum_{s \in S} Pfx_s^n + \sum_{s \in S} Pnd_s^n \le N_{\max} + |S| - |S| \times (Pfx_s^n + Pnd_s^n) \forall s \in S, n \in N \quad (21)$$

$$0 \le L_{ss'}^{ab} \times Lf \le U_{ss'} \times Lf \times Pfx_s^n + U_{ss'} \times Lf \times Pnd_s^n \forall s, s' \in S, n \in N \quad (22)$$

where:

$D_s$ is the rate at which the information is generated at a sensor located at $i \in S$.

$U_{max}$ is the node capacity: the maximum amounts of data a node can handle (receive or transmit) per unit time.

$U_{ss'}$ is the capacity of the wireless link ($s, s'$).

### 3.2.2.8 Connectivity rate

If any node can communicate with any other node, the network is considered as connected. Therefore, any node must have at least one incoming and one outgoing link. In addition to the number of nodes and their density, the connectivity probability is typically related to the transmission range and the received signal strength. To model the connectivity rate, we suggest the following function:

$$f8= \text{Maximize} \ RP_i^r \quad (23)$$

Subject to

$$RP_i^r \le T_{ss'} \times S_{g_{ss'}} \times \alpha \times r^{-\omega} \times TP_i^r \quad (24)$$

where $\omega$ is the path loss exponent (generally $2 \le \omega \le 5$) and $r$ is the distance between the sending node and the receiving one.

$$r = r_c \Leftrightarrow RP_i^r = P_{\min}^n \quad (25)$$

Constraint (25) indicates that the sender can be connected to the receiver and the data can be received only when the power at the receiver is greater or equal to $P_{\min}^n$. The transmission range $r_c$ is defined by $RP_i^r (r = r_c) = P_{\min}^n$.
As the wireless connectivity problem is generally abstracted into a graph theory problem, A WSN can be modeled as an undirected graph G(V;E). The probability of connectivity of the graph (then the network) will be: $Pr \circ b^G = (1 - e^{-\lambda \pi r_c^2})^n$ where n is the number of nodes, $\lambda$ is the node density and an edge exists between two nodes within a distance $r_c$. Hence, the transmission range of each sensor $r_c$ must satisfy:

$$ \sqrt{-\ln(1-(Pr \circ b^G)^{1/n}) / \lambda \pi} \le r_c \quad (26) $$ $$ \sum_{s \in S} x_{ts} \le \sum_{n \in N_a} Pfx_s^n + \sum_{n \in N_b} Pnd_s^n \quad (27) $$

Constraint (27) denotes the number of nodes able to detect a target. This number should not exceed the number of the installed nodes in the different sites.

### 3.2.2.9 Robustness and fault tolerance

Robustness and fault tolerance allow the network to continue operating correctly when a failure occurs on some of its nodes, leading to one or more faults. We assume to measure the system fault-tolerance in terms of robustness. Let $Ft_i$ be the measure of robustness of the ith communicating attempt launched by the sensor j and $Tft_j$ the total number of the failed communicating attempts launched by the sensor j. The robustness of the system can be

represented as: $FT = \sum_{j \in V} \sum_{i=1}^{Tft_j} Ft_i$ (28) where a FT value approaching zero indicates a system with no robustness to faults, while a high $FT$ value shows a highly-robust system. Thus, we suggest the following function: $f9= \text{Maximize } FT$ (29).

### 3.2.2.10 Quality of links

The link quality indication (LQI) is a measure which allows characterizing the quality and the strength of received data packets. It is used in many protocol decisions as routing, packet retransmission and recovery as well as transmitted power strength. LQI concerns different layers. For example, the choice of routes on the network layer can be based on the reported LQI levels from the mac layer. Then, LQI is available to the application layer for analysis. Generally, paths having the highest overall LQI are better used to deliver data to their destinations. The LQI measure can be estimated using software in the transceiver as in the equation (30).

$Lqi = (RC - \sigma) \times \tau$ (30) where RC represents the correlation value which is the raw LQI value obtained from the last byte of the message. $\sigma$ and $\tau$ are two empirical parameters based on the Packet Error Rate (PER) measurements as a function of RC.

$f10= \text{Maximize } Lqi$ (31)

Subject to the constraint (32): To have an idea about the communication quality on the network, we propose to calculate, based on the routing protocol, the average communication quality (Alq) obtained by computing the mean path-loss values of direct communications between nodes: $Alq = \sum_{i=1}^{N_{max}} \sum_{j=1}^{N_{max}} |RP_i^r(i, j)| / \sum_{i=1}^{N_{max}} |N_i|$ (32) where $N_i$ is a node with an identifier i,

$N_i \in V$.

### 3.2.2.11 Path loss and fading

Path loss is the attenuation of an emitted signal due to the characteristics of the channel of propagation and the travelled distance. In the case of indoor wireless networks and in order to better model wireless communications, the path loss should be designed as realistic as possible by considering power constraints and signal coverage.
To model the path loss in the 3D space, we use the Volcano Indoor Multi-Wall propagation model which is based on the Cost231 Multi-Walls Multi-Floors propagation model as in (Saunders et al. 2007). This model calculates the path losses by taking into account the indoor building structure. The formula for this model is as follow:

$f11= \text{Minimize } PL(d) \quad (33)$

$$ \text{where } PL(d) = (PL_{fs}(d_0) + 10\alpha \log_{10}(d/d_0)) + PL_c + \sum_{i=1}^{I} N_w \times PL_w \text{ and} $$

$PL_{fs}(d_0)+10\alpha \log_{10}(d/d_0)$ is the path loss corresponding to the unit disk model representing the average path loss at a distance d (in dB), knowing that $PL_{fs}(d_0)$ is the free space path loss at a reference distance $d_0$ from the transmitter and $PL_c$ is an adjustable constant representing the loss. $PL_c$ and $\alpha$ are determined empirically from experimental measurements. I corresponds to the number of wall materials existing in the building, $N_w$ denotes the walls number made from the ith material existing along the transmission path between the receiver and the transmitter, and $PL_w$ corresponds to the loss associated with the signal passing through a wall made of the ith material. In order to overcome the problem of channel fading, a sufficient received power must be guaranteed to minimize the data packet loss rate.

### 3.2.2.12 Packet delivery cost and reliability

There is a relation between the node positions and data transmission, which implies a data delivery cost. To estimate the data delivery cost, an energy-related cost function is used. Thus, the total cost of data delivery denoted by $Dv$ can be given by:

$$ f12= \text{Minimize } Dv = \sum_{i}^{N_{\max}} Dt_i \times c_i \quad (34) $$

where $Dt_i$ is the quantity of data (expressed on bits) transmitted by a sensor i and $c_i$ designates the cost of data transmitted from any sensor i to another sensor. Subject to

$RL(Dv) \ge RL_{min}$ (35) where $RL(Dv)$ is the reliability of transmitting the packets, $RL_{min}$ represents the minimum desired probability for a successfully packet delivery.

$AD(Dv) \le AD_{max}$ (36) where $AD(Dv)$ stands for the average delay for a successful received packet delivery and $D_{max}$ corresponds to the desired maximum average delay.

### 3.2.2.13 Antenna orientation

The used nodes are equipped with omni-directional antennas which radiate radio wave power uniformly in all directions in the 3D space. While omni-directional antennas have no favorite position when transmitting, there will be no perfect omni-directional. Instead, there is always a direction where the transmission power is better than other directions. Indeed, to enhance transmission, the angle between the direction of antennas of the receiver and the transmitter should be as shown in Figure 3.2(a). Let:

Ag(i) $\in$ [0,360[ be the angle representing the orientation of the sensor i.

Angles(i,j) be equal to 1 if $|Ag(i) - Ag(j)| \in [90,270[$, which means that the orientation of the two antennas of the nodes, i and j, is favorable for emission (see Figure 3.2(c)); 0 otherwise.

Dir(i,j) is equal to 1 if i and j did not oppose directions (as in Figure 3.2(b)), means that the orientation of the two antennas of the nodes, i and j, is supposed to be favorable for emission (the phenomena of reflexion is neglected here); 0 otherwise.
<figure><img src="image_30.png" /><figcaption>Figure 3.2 Different orientation positions of antennas</figcaption></figure>

$$f13= \text{Maximize} \quad \sum_{i=0, j=0}^{nbF+nbN+nbT} \text{Angles}(i, j) \times \text{Dir}(i, j) \quad (37)$$

Subject to the following constraints:

The number of nodes with which a node i is properly oriented (has a favorable orientation for emission) in the 3D space can reach Pnd+Pmb+Pfx-1.

$$\{ |\text{Ag}(i) - \text{Ag}(j)| \in [90, 270[, \text{Dir}(i, j) = 1 \} \Rightarrow \{ \sum_{i=0, j=0}^{nbF+nbN+nbT} \text{Angles}(i, j) \times \text{Dir}(i, j) \le nbF + nbN + nbT - 1 \} \quad (38)$$

The number of nodes with which the node i is perfectly oriented for emission in the 3D space is equal to 1 (see Figure 2).

$$\{ |\text{Ag}(i) - \text{Ag}(j)| = 180, \text{Dir}(i, j) = 1 \} \Rightarrow \{ \sum_{i=0, j=0}^{nbF+nbN+nbT} \text{Angles}(i, j) \times \text{Dir}(i, j) = 1 \} \quad (39)$$

### 3.2.2.14 Distance between chromosomes

In many-objective optimization, many searches proved that to improve the crossing, two neighbors should be crossed. Thus, the distance between the chromosomes to cross should be minimized.

$$f14= \text{Minimize } \phi(i, j) \quad \forall i \in V, j \in V \quad (40)$$

i and j are two candidate sensors representing the two chromosomes to cross and $\phi$ is the distance (in the search space) between the two sensors.

### 3.2.2.15 Other general constraints

$$SP^{ab} = \sum_{s \in S} \sum_{s' \in S} L_{ss'}^{ab} \quad (41)$$

Constraint (41) imposes that the path between a source node a and a destination node b is equal to the sum of the connections between nodes s and s' to connect a to b.

$$\{s = s'\} \Rightarrow \{SP^{ss'} = 0\} \quad (42)$$

Constraint (42) imposes no hops (zero hops) to link a node to it-self.

$$M_s^m \le hp_{\max}, m \in N_b, s \in S_a \quad (43)$$

Constraint (43) prevents deploying a new nomad node m in a specific location if the number of hops $M_s^m$ between this node m and the nearest stationary node s exceeds a fixed threshold ($hp_{max}$).

$$Q_s^m \le TF_{\max}, m \in N_b, s \in S_a \quad (44)$$

Constraint (44) prevents using a new nomad node m in a specific location if the traffic passing through m, such that m is critical for this path, exceeds a fixed threshold ($TF_{max}$).
$$d_{ss'} = \alpha \times Sg_{ss'} \times \delta_{ss'}, \alpha \in R, s \in N, s' \in N \quad (45)$$

Constraint (45) links the distance to the power transmission of the signal between two nodes s and s'. α is a real empirically-determined coefficient.

$$(Sg_{ts} = 1) \Rightarrow (d_{ts} \le d_{\max}) \forall t \in N, s \in N \quad (46)$$

Constraint (46) implies that if there is a signal $Sg_{ts}$ between two nodes t and s, the distance ($d_{ij}$) between t and s must not exceed the pre-defined maximum distance ($d_{max}$).

$$\delta_{ss'} \sum_{n \in N} TP_s^r \sum_{n' \in N} Sg_{ss'} \ge \sum_{n' \in N} P_{\min}^{n'} \sum_{n \in N} Sg_{ss'} \quad (47)$$

Constraint (47) defines the power of transmission when a node s detects another node s'. This power should be higher than the minimum necessary transmission power so that s' detects s.

$$\sum_{n \in N} P_{\min}^{n} (Pfx_{s}^{n} + Pnd_{s}^{n}) \le \delta_{ts} P_{t}, \forall s \in S, t \in T \quad (48)$$

Constraint (48) is based on the assumption that if a node installed at a site s is receiving a signal from a target at the position t, this signal should have a power greater than or equal to the minimum power required to detect the node.

$$\left\{ \begin{array}{l} \text{if } s=a: \sum_{s' \in S} L_{ss'}^{ab} = \sum_{s' \in S} L_{s's}^{ab} + 1 \\ \text{if } s=b: \sum_{s' \in S} L_{ss'}^{ab} = \sum_{s' \in S} L_{s's}^{ab} - 1 \\ \text{otherwise: } \sum_{s' \in S} L_{ss'}^{ab} = \sum_{s' \in S} L_{s's}^{ab} \end{array} \right. \quad (49)$$

Constraint (49) concerns the number of hops between nodes according to their positions.

$$(Sg_{ss'} = 1) \Leftrightarrow (\sum_{s \in S} L_{ss'}^{ab} > 0) \quad (50)$$

Constraint (50) indicates that the existence of a used position s is equivalent to the existence of a quantity of information which crossing (s, s').

$$L_{ss'}^{ab} \le Sg_{ss'} \quad (51)$$

Constraint (51) shows that the existence of a connection (s,s') between two nodes (to manage the traffic between a node source a and a node destination b) requires that the node installed at the position s receives a signal from the node installed at the position s' with a sufficient power of transmission.

## 3.3 Hybridizations and modifications on the optimization approaches for the 3D deployment

In what follows, we will illustrate the hybridizations and modifications on the optimization approaches that we suggest in order to achieve a better deployment in a many-objective case (a number of objectives exceeding three).

### 3.3.1 Chromosome coding for the proposed MaOEAs

For all EMOs, the chromosome coding must be specified. Indeed, a 3D position of a node is represented by a chromosome indicating the potential locations of nomad nodes in the RoI. A point (X, Y, Z) models this position. Each gene in the chromosome represents a binary digit resembling the position's value on the X, Y and Z axes. For instance, Figure 3.3 represents the chromosome corresponding to the node which is mapped to the (46, 53, 34) location. Different factors influence choosing the chromosomes population size. The most important ones are the network configuration and the RoI. For example, considering that the node radius is equal to 9 meters and the sensing area is equal to 70×80×120 meters, the number of needed
fixed nodes to deploy can be equal to 661, (because (70×80×120)/(4×π×92)=660,19~≈661),
then the initial population should be equal to 661 chromosomes randomly disseminated in the
coverage area. This value is calculated assuming that 661 sensor nodes can ensure the
coverage of the entire RoI in the case of a uniform deterministic deployment in the 1-coverage
case (each target must be monitored by one node at least). In the case of k-coverage, the initial
population to start with should be equal to 661 × k chromosomes.

<figure><img src="image_31.png" /><figcaption>Figure 3.3 The chromosome representing the sensor in the 3D position (46, 53, 34)</figcaption></figure>

The choice of the binary coding is justified by its easiness of use and its low computational
cost (a low complexity) which is required when resolving MaOPs. Another reason is related
to the use of the neighbourhood in recombination and mutation (as explained in the paragraph
below) in our approach: Indeed, the binary coding allows better than other coding manners, to
assess the differences in genes between two chromosomes. Thus, a better comparison between
chromosomes according to their distances from each other will be possible. Nevertheless, the
binary coding may lead to non-feasible solutions (impossible solutions). These solutions will
be penalized by a weighting coefficient and will not be selected by the algorithm afterwards.

Next, the used EMOs are detailed. So are the modifications proposed to enhance these
algorithms in order to allow them properly handling MaOPs.

**3.3.2 Inclusion of diversity**

**3.3.2.1 Neighbourhood restriction and adaptive multi-operators**

In MaOEAs, due to the high dimensional objective space, the population diversity increases
and mutation and crossover operators becomes inefficient and may create an offspring which
may be not selected as parents. To overcome this problem, we implement a mechanism based
on two strategies: an adaptive multi-recombination operator's with neighbourhood restrictions
(named AxN) and an adaptive multi-mutation operator's strategy with neighbourhood
restrictions (named AmN).

* Principles of the mutation and recombination with the neighbourhood (AxN and AmN)

- The neighbourhood restriction concept

As example of the utility of using the neighbourhood in the operator's variation in MaOEAs,
it is shown in (Ishibuchi et al., 2015) that MaOEAs can often apply effectively recombination
to solutions having relatively similar gene structure where there is a high dependency between
objectives. Thus, the neighbourhood is used aiming at improving the effectiveness of the
mutation/recombination operators by increasing the number of objectives. This helps to
reduce dissimilarities between new individuals since recombining (and mutating) individuals
which are too distinct may be penalizing and could affects the efficiency of the operators. To
achieve this, the proposed neighbourhood concept computes the distance between individuals
in the objective space. Then determines the set of $Nh×|P|$ nearest neighbours for each
individual where $|P|$ is the individual's population and $Nh$ is the neighbourhood size ($Nh =
|P|×0.1$ in our study). Moreover, our proposed strategy facilitates multiple convergences by
permitting higher exploitation of the move-guiding areas.
- **Neighbourhood Crossover (xN):** In EMOs, the crossover operation allows the generation of good individuals as an offspring from parents. Ideally, this offspring must be composed of non-dominated solutions which are uniformly scattered in the population. Initially, the idea of using selection scheme mating supposes that each couple of individuals from the current population can be chosen as parents. Among the drawbacks of such mating scheme, the random choice of individuals and the large Euclidian distance between individuals in the variable space. As a consequence, the obtained solutions are more probably to be dominated. As a solution to this problem, some studies suggest a more determinist selection scheme based on the idea of considering the proximity and picking closer individuals to achieve the recombination which is very interesting for several multi-objective and many-objective problems. Thus, we propose a neighbourhood crossover that selects individuals having short Euclidian distance in the objective space so that the search ability can be reinforced by crossed individuals that are close to each other in the objective space. When crossing adjacent individuals in the variable space, the obtained offspring is generated near parent individuals in terms of their objective values and may be a non-dominated solution, which increase the probability of having population with great diversity. Although, the Euclidian distance in the variable space may not be defined in several cases like combinational functions. In the case of continuous functions, adjacent individuals in the objective space have often a high probability to be adjacent in the variable space. Thus, in our study, crossover is performed on adjacent individuals in the objective space instead of the variable space. This neighbourhood crossover algorithm is shown in Algorithm 3.1.

**Input:** A set of solutions (population) composing the current generation

**Output:** A set of solutions (population) composing the next generation

01: Classify the population according to their closeness from the best individual for one of the function values in the objective space.

02: Switching the sorted individuals in a random way according to a parameter *neigh* controlling the adjusted neighbourhood with a reasonable width of the population size.

03: Choosing two adjacent individuals from the population for performing the crossover.

<caption>**Algorithm 3.1 The Neighbourhood crossover algorithm**</caption>

Step 2 allows escaping from local optima by the switching operation that guarantees the non-conducting with the same pair in every generation. The *neigh* parameter controlling the width of the population size is a percentage that represents the ratio of the size of the population. Thus, if the value of *neigh* is set to 10, the adjusted neighbourhood is conducted using a population width which is equal to 10%. As a consequence, the proximity of individuals is inversely proportional to the *neigh* parameter. Although, increasing too much the proximity among individuals may increase the probability of repeatedly conducting the crossover into the same pair.

- **Neighbourhood mutation (mN):** Same as the neighbourhood crossover, the neighbourhood mutation aim at restricting the production of solutions within the same niche (local area) as their parents which imply inducing a stable niching behaviour. In our study, we aim to minimize $\phi$ (i,j) $\forall i \in V, j \in V$ where i and j are two candidate sensors to cross, and $\phi$ is the distance (in the search space) between the two sensors. To perform the neighbourhood mutation, only one parameter is needed, which is the neighbourhood size *ns*. This parameter specifies the number of members to be considered as mutation vectors in each subpopulation. In this context, the authors in (Qu et al., 2012) investigated the effect of varying neighbourhood size on the behaviour of the algorithm. Their works prove that the preferred range of the neighbourhood size is between: 1/20 and 1/5 of the overall population. For this reason, the neighbourhood size is considered as a special niching parameter which is easy to
choose since it may be taken proportionally to the population size. Thus, as evidenced by our
experimental results, the neighbourhood size does not affect the efficiency of the algorithm.
Among the advantages of this strategy is that it guarantees evolving each individual toward its
nearest optimal point. Another advantage is the performance of the algorithm which is not
dependent on the variation of the neighbourhood size. Also, according to (Qu et al., 2012), the
neighbourhood mutation improves the detection of local optima. The proposed neighbourhood
mutation algorithm is illustrated in Algorithm 3.2.

**Input** A set of solutions (population) composing the current generation

**Output** A set of solutions (population) composing the next generation

01: **For** each individual *i* in the population size (N) **do**

02: Compute the Euclid distances between *i* and other individuals in the population.

03: Create a subpopulation *sp* from the *m* nearest individuals to *i*.

04: Create an offspring *o* using the adaptive mutation strategies applied on *sp* and readjust out-
bounded solutions if exist.

05: Apply the fitness function to evaluate produced offspring *o*.

06: **Endfor**

07: Create the next generation by applying the niching strategy to choose the *N* fittest solutions

<caption>**Algorithm 3.2 The Neighbourhood mutation algorithm**</caption>

Indeed, starting from a population of solutions of the current generation, the proposed
neighbourhood procedure calculates the Euclidean distance between *i* individuals on the
population. Then selects the *n* members having the smallest Euclidean distance to the
individuals *i*. Afterward, an offspring is produced and evaluated using the fitness function, as
a population of solutions for the next generation.

- The adaptive multi-operators concept

There is another problem confronted when MOEAs are used to resolve many objective real-
world problems. This problem is the choice of the appropriate recombination and mutation
operators for each problem. In our proposed strategy, the operator variations are applied
adaptively. The contribution of each operator is taken into account. Indeed, the operator
which succeeded in the last iteration is used to adjust the selection probability of this operator.
Hence, each operator has a selection probability in the next generation which is relative to its
contribution. In the adaptive mutation, the mutation probability is modified while the
algorithm is executed. In our case, we use a directed adaptive mutation (Korejo, 2011), which
uses the feedback information from the previous generation without modifying the
probabilistic nature of the mutation. Thus, new solutions are deterministically generated in the
search space and are guided toward the optimum by earlier individuals.

The proposed AxN strategy is based on a crossover with neighbourhood operation which can
be performed on a pair of parents after the selection step in the EMO algorithm. Indeed, we
propose to use an adaptive multi-operator recombination operator which allows the
improvement of the search and adapt it to the local characteristics of the problem. The AmN
strategy is based on a mutation with neighbourhood operation which is used to avoid the local
optima and to increase the diversity by changing the chromosomes values. The used mutation
operators are chosen adaptively.

* Implementation of the AxN and AmN strategies on the proposed algorithms

- ε-NSGA-II-AxN-AmN

Our proposed adaptive neighbour scheme of the selection operators of the ε-NSGA-II stems
from the selection process of the AMALGAM algorithm (Vrugt and Robinson, 2007), which
uses a set of MOEAs controlled by a master algorithm. The AMALGAM algorithm measures
the contribution of each method in the previous iteration. Then, these methods are admitted
according to their contributions rates exhibiting the most relevant reproductive success.
Stemming from (Nebro et al., 2013), the pseudo code of our proposed ∈-NSGA-II-AxN-AmN
is given in Algorithm 3.3.

**Input:** *s* // the population size
**Output:** Population
**01:** Population ← **Random Population()**
**02:** AuxiliaryPopulation ← ∅
**03:** **while** (termination condition is not fulfilled) **do**
**04:** **for** *i* ← 1 **to** (*s*) **do**
**05:** Parent ← **Selection_two_neighborsParents**(*Population*);
**06:** ProbaRecombinationOp ← **choosing_operator**()
**07:** ProbaMutationOp ← **choosing_operator**()
**08:** offspring ← **Neighborhood_Adaptive_Mutation_AmN** (*Parent*, *ProbaMutationOp*);
**09:** offspring ← **Neighborhood_Adaptive_Recombination_AxN** (*Parent*, *ProbaRecombinationOp*);
**10:** **Evaluate Fitness**(*offspring*);
**11:** **Insert**(*offspring*, *AuxiliaryPopulation*);
**12:** **end for**
**13:** *X* ← Population ∪ AuxiliaryPopulation
**14:** ∈-dominance-Ranking (*X*);
**15:** Population ← **Select Best Individuals**(*X*);
**16:** **Update_archive** (*Population*);
**17:** **Inject_solutions**(*Population*);
**18:** **Doubling the population Size** (*Population*);
**19:** **end while**

<caption>Algorithm 3.3 The proposed ∈-NSGA-II-AxN-AmN algorithm</caption>

The procedure of calculating the probability of each operator is illustrated in Algorithm 3.4. This procedure is used for selecting both mutation and recombination operators. Indeed, considering a set (N) of different operators, the *choosing_operator*() procedure calculates the contribution of all those operators (lines 2-8). The procedure computes the number of solutions produced by each operator that belongs to the population P of the following generation (line 3). To avoid discarding operators generating no solutions in iteration, each operator that has a contribution which is smaller than a predefined threshold, its contribution is set to this threshold (lines 4-6). This operator can have promising contribution later in other phases of the search.

**Input:** The N operators
**Output:** ProbaOp
**01:** TotalContrib ← 0
**02:** **for** 1 ≤ operator ≤ N **do**
**03:** OpContrib ← solutionsInNextPopulation operator,P; //
**04:** **if** OpContrib ≤ threshold **then**
**05:** OpContrib ← threshold;
**06:** **end if**
**07:** TotalContrib ← TotalContrib + OpContrib;
**08:** **end for**
**09:** **for** 1 ≤ operator ≤ N **do**
**10:** ProbaOp ← OpContrib / TotalContrib;
**11:** **end for**

<caption>Algorithm 3.4 Choosing_operator() procedure</caption>

Hence, among differences between the standard ∈-NSGA-II and the proposed ∈-NSGA-II-AxN-AmN, the choice of the appropriate mutation and recombination operator.

- U-NSGA-III-AxN-AmN
The third proposed algorithm is the **U-NSGA-II-AxN-AmN** which is also based on the original U-NSGA-III algorithm (Seada et al., 2016) within a modified neighbourhood mutation and recombination phase which uses adaptively all the previously indicated mutation operators. This the first time such a modification of the U-NSGA-III is proposed. Algorithm 3.5 illustrates the generation *t* of the proposed U-NSGA-III-AxN-AmN algorithm.

**Input:** *H* structured reference points *Z*<sup>s</sup> or supplied aspiration points *Z*<sup>a</sup>, parent population *P*<sub>*t*</sub>

**Output:** $P_{t+1}$

01: // *Initializations identical to the original U-NSGA-III algorithm* (Seada et al., 2016)

02: $P_t = \text{Niching\_and\_Neighbor\_Based\_Selection}(P_t)$

03: ProbaRecombinationOp ← choosing_operator()

04: ProbaMutationOp ← choosing_operator()

05: $Q_t = \text{Neighborhood\_Adaptive\_Mutation\_AmN}(P_t, \text{ProbaMutationOp})$

06: $Q_t = \text{Neighborhood\_Adaptive\_Recombination\_AxN}(Q_t, \text{ProbaRecombinationOp})$

07: // *The rest is the same as the original U-NSGA-III algorithm* (Seada et al., 2016)

<caption>**Algorithm 3.5 The generation *t* of the proposed U-NSGA-III-AxN-AmN algorithm**</caption>

**- MOEA/DD-AxN-AmN**

Despite the original MOEA/DD (Li et al., 2015) rely on a neighbourhood strategy, as in the previous presented algorithms, the same variations of operators are applied to the original MOEA/DD in order to take advantage of our adaptive multi-operators concept. This the first time such a modification of the MOEA/DD is proposed.

**3.3.2.2 Including single-grid and multiple scalarizing functions in the aggregation based approach (MOEA/DD)**

Among the advantages of the algorithms based on scalarizing functions compared to the algorithms based on Pareto dominance, their low-cost computation and its scalability to MaOPs. Different scalarizing functions exist. Choosing the appropriate scalarizing function is a relevant issue to be considered when designing scalarizing function-based algorithms since choosing the suitable scalarizing function is problem-dependent (Ishibuchi 2010). For example, according to Ishibuchi (2009), the weighted sum is generally used when the PF is convex, but it is not suitable for non-convex PFs. The weighted Tchebycheff is often used when the PF is non-convex, but its efficiency could be affected by the increase of the objectives number. Hence, it is interesting, to adapt the MOEA/DD, in order to have the ability to automatically choose between several scalarizing functions for each individual in each generation. Authors in (Ishibuchi 2010) used two ideas for simultaneously using multiple scalarizing functions in a single MOEA/DD algorithm. The first idea is the use of several scalarizing functions in a multi-grid scheme where each scalarizing function has its unique weight vectors complete grid. The second idea is alternately assigning a different scalarizing function to every weight vector in a single grid. Their results showed that, for 0/1 knapsack problems with six-objectives, simultaneously using the weighted Tchebycheff and the weighted sum in MOEA/D outperforms their individual use. However, the number of used scalarizing functions is limited to two. Since it is easier to generalize the single-grid implementation (the second idea), our idea is to use the second implementation based on simultaneously using several scalarizing functions, with more than two scalarizing functions. Indeed, as opposed to the original MOEA/D having a single complete grid with up to 15 weight vectors, our single-grid implementation scheme based on multiple scalarizing functions suppose that each weight vector has a different scalarizing function. The following scalarizing functions are considered: The weighted sum (WS) (Ishibuchi et al., 2009), the weighted Tchebycheff distance (TCB) (Ishibuchi et al., 2009), the penality-based boundary intersection (PBI) (Sato et al., 2009). Other scalarizing functions may be considered such as
the Inverted PBI scalarizing function (iPBI) (Sato et al., 2014) and the vector angle distance (VA) (Tan et al., 2013). The proposed algorithm that uses multiple scalarizing functions is named mMOEA/DD-AxN-AmN.

### 3.3.3 Incorporation of Dimensionality Reduction (the NL-MVU-PCA algorithm)

#### 3.3.3.1 Incorporating L-PCA and NL-MVU-PCA on the tested EMOs

To integrate L-PCA and NL-MVU-PCA on the proposed EMOs, we apply the reduction using the offline linear and non-linear objective reduction algorithms (named respectively L-PCA and NL-PA-MVU).

In order to minimize the effect of noise and dependencies between objectives, the PCA method projects a data D on the eigenvectors of its correlation matrix while preserving its correlation structure. Indeed, PCA method removes the higher order dependencies in the given data D. Thus, PCA may become unable to capture the data sets having structures with non-Gaussian or multi-modal Gaussian distributions (Shlens et al. 2009). In fact, different nonlinear dimensionality reduction approaches, like Graph-based ones (Saul et al. 2006) use a standard kernel function to transform data. Then, they apply PCA in the transformed kernel space. Although, its success is depending on the a priori chosen kernel. In our work, we employ the PCA method, proposed in (Saxena et al., 2013), which overcomes this limitation by deriving the “data-dependent” kernels.

The second used machine learning-based method is the MVU (Weinberger et al. 2006) relying on a graph that computes the low-dimensional representation in order to unfold the high-dimensional manifold data. To perform the unfolding process, Euclidean distances between data points are maximized, while angles and distances between nearby points are locally preserved. Theoretically, this can be modeled as a semi-definite programming problem (SDP) (Weinberger et al. 2006) where the output is the kernel matrix representing the kernel space to which the PCA method is applied.

In our work, we use the framework proposed in (Saxena et al. 2013). In fact, Given an M objective optimization problem with a set of non-dominated solutions, the proposed framework aims at specifying the smallest set of m conflicting objectives ($m \le M$) while preserving the correlation structure among the given solution set. To perform this, the proposed framework is used to eliminate globally correlated objectives and non-conflicting ones along the eigenvectors of the correlation/kernel matrix. Thus, found solutions are estimated as good representative of the PF if there is conformity between the correlation structure of the PF and that of the given

non-dominated solutions. Therefore, essential objective set includes the smallest set of conflictual objectives determined by the framework. This framework is employed to reduce iteratively the objectives until obtaining the same objective set deduced as essential in two successive iterations. More details of this framework were discussed in (Saxena et al. 2013).

#### 3.3.3.2 Integrating PI-EMO-PC, Knee points and NL-MVU-PCA on the proposed EMOs

In order to overcome the previously-mentioned difficulties of EMOs in resolving MaOPs, we suggest a justified hybrid scheme incorporating different approaches. This scheme is illustrated in Figure 3.4.
<figure><img src="image_32.png" /><figcaption>Figure 3.4 The four steps of the proposed hybridization scheme</figcaption></figure>

In this scheme, four classes of MaOEA are combined: aggregation-based, reference point-based, reduction based and preference-based.

Firstly, the MaOA is executed (MOEA/DD, NSGA-III or Two-Arch2) with preserving the diversity using an adaptive neighborhood mechanism. Thus, a set of solutions corresponding to the optimization of the initial set of objectives is obtained. On this set, the dimensionality reduction is performed and a set of solutions corresponding to a smaller set of objectives is provided. Afterwards, the preference procedure is achieved.

Indeed, the preference approaches suppose that no redundant objectives exist in the given problem (Saxena et al., 2013). Thus, in our approach, dimensionality reduction procedure is always performed before applying the decision maker (DM) preferences.

Since the PI-EMO-PC procedure requires a sufficient search window, its input population should be chosen in such a way that the search converges to a solution in accordance with the interactively elicited DM’s preferences. To choose the input population for our preference procedure guaranteeing a balance between the computational efficiency and the convergence to a single solution, we follow the same steps as indicated in (Sinha et al., 2013): The input population is an intermediate population taken at Ng generations (50% of progress) after applying the reduction. After identifying this input population for the preference procedure, only a smaller set representing its members is considered using the k-means clustering. These members serve as the initial population members of the PI-EMO-PC.

### 3.3.4 Incorporation of preferences

When resolving a problem, MaOAs gives a set of non-dominated well-sparse solutions that approximate the whole Pareto Front (PF). In the case of real world problems, the user/decision maker (DM) generally needs a small number of non-dominated solutions. Besides, the number of needed solutions and the size of the population are exponentially dependent on the number of objectives (Ishibuchi et al., 2009). Hence, it is relevant to
concentrate the search on a set of specific regions guided by the user preferences. Based on
the time of incorporating the preference ordering, three main classes of preference algorithms
exist (Jaimes et al., 2011): A priori, interactive and a posteriori algorithms. The second class
based on interactive process is the most relevant since it permits a progressive engagement of
the DM preferences and allows the readjustment of the decisions during intermediate
generations of the algorithm. However, few studies focus on following the evolving of the
new solutions to progressively incorporate the user preferences. In this paper, we are
interested in proposing a novel hybrid scheme relying on hybridizing the NSGA-III with an
interactive preference algorithm (PI-EMO-VF (Deb et al., 2010)) where the DM is asked to
guide the search to a specific subset of the PF by interactively incorporating his preferences.

**3.3.4.1 PI-NSGA-III-VF (NSGA-III with interactive preferences)**

PI-EMO-VF (progressively interactive EMO value function) uses a generic procedure which can be incorporated to any evolutionary multi-objective optimization (EMO) algorithm. PI-EMO-VF uses an approximate value function which is progressively generated. Thus, after every few number of iterations (generations) of the used EMO algorithm, a set of fairly distributed non-dominated solutions is identified and the DM is asked to give his preference informations about the relation between solutions. In an ideal scenario, the DM provides a complete ranking of the solutions (from the best to the worst). Nevertheless, the DM can gives a partial preference-information. This information helps establishing an increasing polynomial value-function. Then, according to this value-function, the stopping condition is set up. The PI-EMO-VF algorithm is detailed in (Deb et al., 2010). Figure 3.5 illustrates the flowchart of the proposed PI-NSGA-III-VF procedure.

**The solution encoding:**

a) *Solution representation:* A NSGA-III candidate solution (chromosome/individual) is a sequence of 3D coordinates representing the nodes disseminated on the 3D indoor space. To represent this solution, a vector-based representation is used. Each dimension of the vector represents an axis of the node coordinates corresponding to its position in the indoor space. For each position, pre- and post-conditions are set to guarantee the feasibility of the solution (its applicability in the indoor space). The initial population is obtained by randomly creating a set of individuals.

b) *Variation of the solution:* In NSGA-III, the variation operators (recombination and mutation) help the search to move toward the optimal solutions. To perform the recombination, a SBX (simulated binary crossover) operator with large distribution index is used. To enhance the search process in the case of many-objective problems, it is recommended to create an offspring that is a neighbor of its parents (Li et al., 2015). Thus, a neighborhood strategy relying on the control of the cutting point of the recombination operator is used. This cutting point is taken either in the first tier of the vector or in its last tier. The mutation operator is based on a bit-flip operator. More details (probability, index, and operators) on the used mutation and recombination are given in section 4.7.1.1.

c) *Evaluation of the solution:* Once the offspring is created, the deployment solution is assessed using the metrics of the objective functions (see f1 to f14 in section 3.2.2) Based on these values, a non-domination rank and a position in the objective space are attributed to the solution which allows it to be assigned to a particular reference point based on a distance computing.

d) *Normalization of the population:* Since the metrics of the objective functions have generally different scales and are incommensurable, a normalization procedure is used in NSGA-III to overcome this problem. Indeed, in each iteration the upper and lower bound values for each metric are retained to use them by the normalization procedure. This latter
procedure permits population members and reference points to have the same range, which is
essential for preserving diversity.

<figure><img src="image_33.png" /><figcaption>Figure 3.5 Flowchart of the PI-NSGA-III-VF (Mnasri et al., 2018a).</figcaption></figure>
### 3.3.4.2 The proposed hybrid preference algorithm PI-EMO-PC-INK: (PI-EMO-PC-Ideal point-Nadir point-Knee points)

Interactive preferences are the most interesting since they are dynamically injected into the selection process in order to continually guide the search for appropriate actions. Figure 3.6 illustrates the proposed hybrid method based on combining implicit and explicit interactive preferences. Firstly, Ideal point and Nadir one are found respectively by using the Extremized-Crowded NSGA-II algorithm (EC-NSGA-II) (Deb et al. 2006) and by minimizing each objective individually in the search space. Then, an explicit algorithm based on PI-EMO-PC is executed if the DM has preferences. Otherwise, an implicit preference process aiming at finding knee regions based on Trade-off-based KR-NSGA-II (TKR-NSGA-II) (Bechikh et al. 2011) is carried out. When using explicit algorithm based on PI-EMO-PC, if the DM is not satisfied but he becomes tired, the procedure performs the process to find the previously-indicated knee regions. Afterward, if the DM is not tired yet, he modifies the aspiration levels of the PI-EMO-PC in order to incorporate new information about his preferences. These processes (PI-EMO-PC and TKR-NSGA-II) will be repeated if the DM is not satisfied or the maximum allowed number of permitted interventions is not reached. In both cases, when the DM becomes satisfied or the maximum allowed number of permitted interventions is reached, the global process will be stopped.

<figure><img src="image_34.png" /><figcaption>Figure 3.6 The proposed hybrid preference algorithm (PI-EMO-PC-INK)</figcaption></figure>

The ideal point is a form of implicit DM preferences. It can be defined as the vector $z' = (z'_1, ..., z'_M)$ composed of the best objective values over the search space $\Omega$. The ideal point may be specified by individually minimizing each objective in the search space. Mathematically, the ideal objective vector is given by $z'_m = \text{Min}_{x \in \Omega} f_m(x), m \in \{1, ..., M\}$ (52).
The nadir point is another form of implicit DM preferences. It can be defined as the vector
$z^N = (z_1^N, ..., z_M^N)$ including the worst objective values over the Pareto optimal set.

Mathematically, the nadir objective vector is given by $z_m^N = \operatorname*{Max}_{x \in P^*} f_m(x), m \in \{1, ..., M\}$ (53).

According to (Branke et al. 2008), several interactive algorithms used the nadir point as a pre-
requisite. However, estimating accurately the nadir point for many objective problems is an
open research issue. In order to help the DM in expressing his preferences, Nadir point is
applied so that each aspiration level will lies between the nadir value and the ideal one.

Nadir point and ideal point assists the DM in expressing his preferences by identifying the
range of the objective functions at the Pareto optimality stage. Both ideal and nadir points are
employed to visualize the optimal Pareto front which facilitate comparing solutions especially
for high dimension problems. Because it is used to avoid the worst instead of achieving the
best, the Nadir point is considered as a more conservative point of view, compared to the use
of the ideal point. Figure 3.7 illustrates the Nadir and ideal points, for a two-objective
problem.

<figure><img src="image_35.png" /><figcaption>Figure 3.7 Nadir and ideal objective points</figcaption></figure>

An important benefit of our approach is that it allows determining “knees” (special points in
the PF where there is a maximal marginal return in the trade-off surface). In fact, knees
represent points where a small improvement in the performance on one goal results in a large
decrease in the performance on another conflicting goal. Due to this property, detecting such
knee points is often extremely valuable and Knee points are generally interesting solutions
because they allow the DM to better know and balance its conflicting internal goals.

**3.3.5 AcNSGA-III: a hybrid framework for NSGA-III and Ant system**

Despite its efficiency, the NSGA-III has some difficulties when solving mono-objective and
two-objective optimization problems. These difficulties concern the low selection pressure
that NSGA-III introduce to non-dominated solutions of a population when resolving two-
objective problems. Moreover, they concern the small population size and the random
selection process when resolving mono-objective problems (Ibrahim et al., 2016). Also, the
ACO algorithm has a main drawback which concerns the convergence into the local optima
(Sim et al., 2003).

Therefore, the idea is to propose a well-justified hybridization scheme using the two
algorithms to take advantage of their strengths and to remedy their drawbacks. When
hybridizing these two algorithms, most of the studies (Huang and Chne, 2013), (Shen 2016),
use the standard and basic version of the genetic algorithm. Besides, most of these studies
sequentially execute the two algorithms (the standard GA then the ACO or the opposite). Thus,
the final solution of one of the two algorithms is the initial solution of the other. Although this
basic scheme of integration enhances the ACO convergence rate, this latter remains converging
excessively which makes the problem of local optimum unsolvable. In our study, we propose a
platform where the two algorithms (NSGA-III and ACO) run at the same time and interact
with the same population. Thus, the ant algorithm steps are injected into the implementation of
the original NSGA-III with incorporation of several modifications of the original NSGA-III.
Among these modifications, the initial population of the NSGA-III which becomes the
population built by the ants in the initial phase of the ACO. It should be mentioned that this is
first time NSGA-III and ACO are integrated into a hybrid platform. Moreover, this is the first
platform using a hybrid genetic algorithm and ACO to resolve the problem of 3D indoor
deployment of nodes. The proposed algorithm, called AcNSGA-III is illustrated in Algorithm
3.6. It is a hybrid ant-Genetic algorithm which performs an ACO optimal selection of nodes, a
dynamic pheromone updating and a mutation strategy. It accelerates the global convergence in
order to speed up the local search which allows finding faster the suitable solutions of the 3D
deployment problem. The global search ability and the randomness of the genetic operators are
guaranteed which ensure conducting the operation of the genetic operator into generating
routes by the ants if the ACO converges quickly. This allows to the latter finding the closing
conditions and exits. Finally, since there is a low probability that ants and the NSGA-III
process produce the same individual in the same iteration: the individual is added to the
population unless it does not exist into it.

**Input:** NS (=2*N<sub>Pop</sub>) size of population,
t (iteration= the number of travels per ant) = 1,
It<sub>max</sub> (Maximum iteration= the maximum number of travels per ant).

Output : P<sub>t</sub>

01: Initialize the parameters of the deployment problem (CvD, F, C<sub>t</sub><sup>f</sup><sub>g</sub>, mx, Ng<sub>0</sub><sup>i</sup>, Expi)

02: Initialize the ACO parameters (NbA, ExP, ExV, EvP, MaxTP, MinTP)

03: P<sub>0</sub>(Initial Population)= Each_ant_builds_aSolution ()

04: V<sub>t</sub> =Evaluate the solutions and choose NPop feasible solutions

05: While t<=It<sub>max</sub> do

06: Create Offspring Q<sub>t</sub>

07: Mutation and recombination on Q<sub>t</sub>

08: Set R<sub>t</sub>=P<sub>t</sub>∪Q<sub>t</sub>

09: Apply non-dominated sorting on R<sub>t</sub> and find F1, F2, ...

10: S<sub>t</sub> = {, i=1;

11: While |S<sub>t</sub>|≤N<sub>Pop</sub> do

12: S<sub>t</sub>=S<sub>t</sub>∪F<sub>i</sub>

13: i=i+1

14: End While

15: If |S<sub>t</sub>|< N<sub>Pop</sub> do

16: P<sub>t+1</sub>=U<sub>i=1</sub><sup>l</sup>F<sub>j</sub>

17: Normalize S<sub>t</sub> using min and intercept points of each objective

18: Associate each member of S<sub>t</sub> to a reference point

19: Choose N<sub>Pop</sub>−|P<sub>t</sub>+1| members from F<sub>t</sub> by niche-preserving operator

20: Else P<sub>t+1</sub>=S<sub>t</sub>

21: End if

22: Update_pheromone()

23: Each_ant_builds_a_newSolution()

24: V<sub>t</sub> = Evaluate the solutions and choose N<sub>Pop</sub> feasible solutions

25: Set P<sub>t+1</sub>=P<sub>t+1</sub>∪V<sub>t</sub>

26: t = t + 1;

27: End While

<caption>Algorithm 3.6 The proposed AcNSGA-III algorithm (Mnasri et al., 2017a)</caption>

The procedure *Each_ant_builds_aSolution()* allows to construct the candidate solutions using a model of pheromone which is a tunable probability of distribution over the space the solution. In our case a solution is a feasible repartition of nodes in the 3D space. The procedure *Update_pheromone()* allows the use of the candidate solutions to update the values of the pheromone in order to ensure moving towards future better solutions. As an optimization, the operation of these two procedures can be summarized and replaced by the algorithmic sequence illustrated in Algorithm 3.7.
01: **For** all the iterations i in 1:i **do**

02: **For** all the construction steps j in 1:J **do**

03: **For** all the ants k in 1:K **do**

04: Choose and move to the next possible position of node

05: Update local pheromone

06: **endFor**

07: **endFor**

08: Update global pheromone values on visited possible position of node

09: **endFor**

<caption>Algorithm 3.7 Operation of *EachBuilds_aSolution()* and *UpdatePheromone()*</caption>

### 3.3.6 The proposed acMaPSO algorithm: including the concept of birds accents in MaOPSO

The proposed modifications of the standard multi-objective PSO are mainly aimed at overcoming the difficulties encountered when solving problems with several local optima. In our approach, changes are made in the swarm topology to avoid the premature character of the standard PSO algorithm: in addition to the use of the entire swarm best position (gbest), we use the best position of the local area around the particle, called the best cluster or best swarm (cbest). Moreover, we create an information link based on the concept of accent between each particle and its neighbors. These links build a graph that represents the topology of the local swarm or local community of birds. In PSO, the neighborhood of a particle represents the social structure that manages its interactions. This neighborhood may be global where each particle is in connection with all other particles or local where *k* neighbors are randomly defined for each particle at each iteration.

#### 3.3.6.1 The bird accent concept

Indeed, according to recent research in biology (Oesel et al., 2017), singing birds have regional accents precisely like human beings. Indeed, the ability to sing and create a complete song that birds possess is inherited in large part from their parents. Experiments have shown that if these birds are reared in silence, they can only scream. Moreover, birds from different regions develop distinct accents. By imitating this biological concept, we propose a PSO algorithm based on a topology of accent categories of singing birds (acMaPSO). The idea is that each accent group has different parameters to accelerate convergence which improves the prevention of local optima. To evaluate the search capabilities of particles in their local areas, this algorithm relies on this new concept of accent where particles belong to different communities or groups (called clusters or swarms). To keep the diversity of the population during research, particles are separated into groups according to their accents. The particles of each accent category can select as neighbors only the least experienced particles (from their own groups or other groups).

In addition, aiming at keeping only the best particles, unlike the biological nature of birds, new bird's particles in our approach are supposed to sing better than their parents (its fitness may be better than the fitness of their parents). As shown in Figure 3.8, our approach is based on the grouping of communities of singers. Each community groups a set of geographical neighbors (parent and child birds). Bird's particles can have six categories of expertise. According to the concept of accent explained above, each bird goes through four main phases: birth, childhood (novice, crier then follower), parenthood (novice singer, singer then pro-singer) and death. Each bird's particle can choose as neighbors birds that do not have the same accent (which are not in its group) but have equivalent or smaller singing levels. Moreover, bird's particles will be penalized if their levels of expertise in singing increase, until being eliminated after they reach the maximum level. Thus, to avoid oscillations around
a local optimum, if the *pbest* value fails to be updated after *μ* iterations, the corresponding particle is penalized and its category is increased: therefore unless its current position is better than the *pbest* one, the bird goes to the next level (category) of singing. After *φ* iterations (*μ*<<*φ*; *φ*=a*μ*, a>5), the clusters (swarms) are updated to allow the search to escape from local optima.

<figure><img src="image_36.png" /><figcaption>Figure 3.8 The choice of the neighborhood of a particle Pa</figcaption></figure>

3.3.6.2 The accent measure

Learning accents in particles reflects the number of iterations after which the **pbest** position of a particle has not been updated. This latter concept can be defined as follows: *if* f(xᵢ) < f(pᵢ) *then* xᵢ.accent = 0 *else* xᵢ.accent = xᵢ.accent + 1 (4.1). In fact, initially a particle is randomly generated with no singing experience and its experience improves (goes to the next level) if it cannot find a better position than its current **pbest**. In the standard PSO, if a particle converges to a local optimum, its **pbest** and current position are not changed. According to the new measure of the experience of particles, if the position of a particle is not updated, its experience will be increased each μ iterations to reach the next level. This rise in the experience of the particle will continue until the particle becomes able to find a better **pbest** position or until reaching the final experience level and being replaced by new one.

3.3.6.3 The clustering in multiple Swarms

One of the means of enhancing the diversity in evolutionary algorithms (EAs) when resolving
dynamic real-world optimization problems is considering multi-populations. In this context,
we adopt a multi-swarm strategy where the population is composed of a set of subpopulations
(clusters) called swarms. In multi-modal functions, one of the methods of tracking local
optima is to divide the whole search space into local multi-population, which are generally
covered by a small number of local optima, then separately search on these subspaces.
Nevertheless, the difficulty lies in the manner of defining the area of each sub-region and the
manner of guiding the particles to promising subregions. Thus, if the area of subregion is too
small, the small isolated subpopulations can converge to local optima and the algorithm may
do not make any progress because of the diversity lost. On the other hand, if a subregion is
very large, this can cause more than one peak within the subregion of a sub-swarm.

Moreover, the optimization algorithm should have a good global search capability to explore
promising subregions. To resolve these issues, the proposed acMaPSO employs a local
search method (a clustering method) to generate a proper number of sub-swarms and a global
search method to detect promising subregions.

- The acMaPSO global search method: Since particles learn information from non-permanent neighbors, the population topology is dynamic. To identify (then avoid) non-promising local regions as possible, geographical neighbors are avoided if it is very close to a local optimum.

- The acMaPSO local search method (clustering method): to accelerate the convergence, local search algorithms (such as K-means, single linkage clustering or average linkage clustering)
were often combined with EAs to fine-tune the obtained solutions. Thus, clustering is used to
introduce diversity and to help in avoiding local optima and non-promising local regions
where no optimal solutions can be found. In our case, a hierarchical clustering algorithm (the
mean linkage clustering UPGMA) is used to identify the centers of the clusters of particles in
the population. The used clustering process should be efficient since it affects the overall
swarm performance. In this context, in addition to the **pbest** and **gbest** parameters of the
standard PSO, we add another parameter named **cbest** (clusterbest or cummunitybest) to keep
the best position of the cluster.

Algorithm 3.8 illustrates the acMaPSO algorithm.

01: Initialize the parameters **n** (number of swarms), **k** (population size of each swarm), **w** (inertia weight), **c1** and **c2** (acceleration coefficients)

02: Set the fitness evaluations counter $C_f = 0$

03: Set the initial accent $a_i$ of initial swarms to *novice*

04: Random generation of **n** initial swarms $s_i \in S$ with size **P**, ($i$ = 1, 2, ..., $P$)

05: **for** i=1 to n **do**

06: Initialize parameters of the swarm i

07: **for** j=1 to k **do**

08: Initialize position and velocity

09: Calculate fitness

10: **end for**

11: **end for**

12: **while** (stop condition is not fulfilled [sufficient good fitness | maximum number of iterations]) **do**

13: **if** highestExperience_category is reached **then**

14: Delete particles having reached the highest experience category and insert new random particles (accent operator)

15: Construct accent-group topology structure (S,a)

16: **end if**

17: **if** (fitness if not evolved in recent μ iterations) **then** (move on to the next category)

18: **end if**

19: **for** i=1 to n **do**

20: **for** i = 1 : P **do**

21: Adjust the inertial weight (S; w; a)

22: Adjust the acceleration constant (S; c1; c2; a)

23: Update position and velocity using equations (14) and (15)

24: Evaluate the fitness (S, C<sub>f</sub>)

25: **if** (fp is better than f(pBest)) **then** (pBest = p)

26: **end if**

27: **end for**

28: $cbest_i$ = best pbest<sub>i</sub> in P //updating cbest<sub>i</sub> (the cbest of the swarm i)

29: **end for**

30: Update accent of particles using the equation (16)

31: gBest = best cbest<sub>i</sub> in P //updating gbest<sub>i</sub> (the gbest of all the swarms)

32: **end while**

<caption>Algorithm 3.8 The acMaPSO algorithm (Mnasri et al., 2018b)</caption>

3.3.7 Hybridizing Particle Swarm Optimization and Multi-Agent Systems

3.3.7.1 Multi-agent Systems

MAS are a decentralized system which is based on a set of agents. An agent is considered as an intelligent, autonomous and reactive entity which is able to learn and cooperate with other agents or components of the environment to achieve common goals. Each agent must be put in an environment where it can react. In general, an agent is characterized by its ability to detect its local environment in which it operates, its dependence to this environment, its ability to respond to the changes of the environment and its autonomy (ability to achieve specific tasks without external intervention).

3.3.7.2 The advantage of using the multi-agent approach in our context

The modeling of agent-based systems consists of establishing a multi-agent organization to
satisfy a set of objectives. Indeed, it is a question of classifying and combining various tasks
and endow the agents with a set of skills (roles and knowledge) enabling them to interact
according to a communication protocol (the contact-net, for example) to achieve their tasks.
The modeling of agents concerns also the description of the complex behaviors of the agent
and their relationships with other agents and with the environment. Recently, with the
development of the distributed control theory, several studies are applying the theory of multi-
agent systems to solve the problems of container terminals. Indeed, these agents have been
used to detect disturbances on daily process plans. Several studies have highlighted the
interest of MAS in solving and optimizing problems.

We propose a multi-agent approach to our problem. Indeed, MAS can reflect in a realistic (and generally efficient) way, the complex relation between the actors of a system and the way in which a solution is organized. In addition, MAS can provide a solution which is acceptable by all the actors involved in the system. The problem of scalability is also less restrictive when using the agent approach which is more appropriate for complex and dynamic systems and environments.

Indeed, the main benefit of using the multi-agent approach is that agents can learn and acquire behaviors leading to a scheduling plan that verifies and respects conflictual constraints in the case of complex and dynamic system. MAS accept and assume different players with different interests; it is a dynamic environment with disruptions.

Among the other advantages of using the multi-agent approach:

- Agents dynamically interact with the changing of the environment which makes the system robust and reliable.

- Agents, as distributed entities, are adapting to the different sizes of the problem, which allow the scalability of the system.

- Agents can access remote and geographically distributed informations.

- The multi-agent approach allows approaching a large search space which is, in most cases, not explorable via conventional resolution methods.

- We can obtain a global solution incrementally built from the partial solutions provided by the agents. Indeed, each agent seeks a locally feasible solution and negotiates its neighbors to make it globally coherent. In some complex systems that can not be modeled explicitly, each agent models a partial aspect and the overall behavior of the system is deduced from the interaction of the agent entities. Yet we often encounter the difficulty of proving the feasibility and the validity of the found solution.

3.3.7.3 The acMaMaPSO: A hybrid algorithm based-on accent multi-agent many-objective PSO

The acMaMaPSO is a new algorithm that combines the main features of acMaPSO and MAS. At first glance, PSO and MAS seem to be similar since both perform cooperative tasks and are population-based. However, particles are very distinct from agents. The first difference is that the agent can quickly and autonomously explore its environment while the particle can only move in the space of the problem following the main algorithm. On the other hand, to improve its computing performance, a particle is designed with smaller capabilities making it less intelligent than an agent relying on learning as a main component. Moreover, to simplify the design, the execution of the particles is synchronous while that of the agents is asynchronous because of the autonomy of agents.

Indeed, the hybridization of PSO with MAS combines the autonomy and learning abilities of MAS with the simplicity of PSO. As a result, particles become more autonomous, smarter and more able to take advantage of their environment. For example, if the evaluation of the fitness function is expensive, it is not necessary to perform it for each visited point and the location of this latter can be updated by communicating with its neighbors. Indeed, each agent represents a particle that reflects the behavior of a bird in its community. Each particle represents a solution in the search space and is represented by a point to which is attached a Boolean value that indicates whether this point has already been visited by an agent. If so, this
point should not be a solution. Unlike the standard PSO, the evaluation of the fitness function of the particles is not always necessary: for example, if an agent particle arrives at a non-optimal already evaluated point (marked as visited); the particle can ignore the evaluation of fitness and updates its position through the information provided by its neighbors. This contributes to the acceleration of the computation and the optimization of the performances in spite of the complexity introduced by the learning and the autonomy of the particle. In the rest of the paper, the terms particle and agent are used interchangeably.

When collaborating together, agents develop a society to achieve a common goal as well as their own individual goals. The decision-making process of the group in MAS corresponds to the fundamental nature of a particle in PSO. Thus, the proposed hybridization provides an opportunity to optimize complex problems. Nevertheless, to resolve complex optimization problems, several specificities must be defined such as the interaction method between the agents and their rules of behavior, the environment and the starting point of the research.

* **Self-Learning of agents**

In addition to their conflicting or cooperative interactions in their local environment, agents can also self-develop knowledge using their own observations and studies of the environment. According to (Wu et al., 2015), having a small range of population in an optimization algorithm positively influences its local search capability. As a result, a small range of search techniques is applied to achieve the self-learning function of agents.

* **Proposed MAS architecture and agents intentions**

The architecture of the proposed MAS is based on three types of agents: environment agent (agEnv), bird agent (agBird or agParticle) and swarm agent (agSwarm or agCommunity). Indeed, after initializing the parameters, agEnv assigns for each agBird a starting position in the problem space and a set of neighbors. Then, bird agents start searching for an optimal solution until a maximum number of iterations or a sufficient fitness is attained.

Firstly, each *agBird* checks if its current position is already visited. If yes, it does not evaluate its fitness function and ask its neighbors about their *pBest* and locations, then ask *agEnv* about the locations of neighboring clusters to calculate its current *pBest* and update its position and velocity. If the current position is not visited, *agBird* evaluates the fitness function, tags the current point as visited and updates its position and velocity. The overall procedure is illustrated in Figure 3.9. For more details, see (Mnasri et al., 2018b).

<figure><img src="image_37.png" /><figcaption>**Figure 3.9 The proposed MAS architecture**</figcaption></figure>
The intentions are used to help the agent optimizing the value of its fitness so that he makes
the appropriate response based on its environment. The fitness of the agent is determined by
the equation (4.1). The details and intentions of each type of agent are as follows:

* **agEnv**: In MAS, the design of the local environment is very relevant since agents sense the information in the local environment and act according to their strategies to achieve their intentions. The environment where the agent lives must be built so that each agent, in addition to the cooperation with its neighbors, can make self-learning and adapt its strategies of action according to its own experiences. To simplify the representation of the environment, we use a 3D cubic structure environment. Each agent occupies one point in this space and has two values that represent its speed and position. The size of the population is denoted *L* (a positive integer). In acMaMaPSO, the environment itself is modeled as an agent and provides other agents with additional informations (about the problem space for example). This environment agent (*agEnv*) applies a clustering algorithm (the UPGMA mean linkage clustering in our case) to discover clusters of labeled points and to provide their characteristics to particle agents (center point, density, etc). The agent *agEnv* is characterized by the following parameters:

- *n* which is the dimension of the problem space.

- *P* which is a set of points in the problem space knowing that $p \in P, p=\{d_1 \times d_2 \times \dots \times d_n, \text{visited}\}$ is a point in the *n* dimensional space and *visited* is a Boolean value indicating if this actual position is visited or not. This information helps the *agEnv* to discover clusters when applying the clustering algorithm.

- $C = \{(p_1, p_2, ..., p_{center}, p_m), d \mid d \ge \epsilon_d\}$ which represents the set of clusters. $p_{center}$ is the center point of the cluster. *d* is the current density of the cluster. $\epsilon_d$ is the minimum density requirement for *agEnv* to consider a group of visited points as a cluster in the problem space. $p_{center}$ and *d* can be requested by an *agBird* in its updating function to calculate its next position.

* **agBird (agParticle)**: Let $Ab_{i,j}$ be the agent bird (or the agent particle) located in the position $(i,j)$, let $N_{i,j}$ be its neighborhood, $pBest$ its best position which represents, among its neighbors, the point in the problem space that is the closest to an optimal solution $gBest$. Indeed, the position of each bird agent represents a point in the search space and a solution to our deployment problem (a set of possible locations of the sensor nodes in the 3D indoor space). Instead of collecting itself informations about its cluster, an agent can simply request them from the environment agent or the corresponding cluster agent. This allows at the same time preserving the simplicity of the original PSO and significantly increasing the performance of the MAS. After the perception of its environment, each agent $Ab_{i,j}$ can perform, among others, the following tasks:

- Obtain the center location and other informations about its swarm (cluster).

- Know the status of the current position (visited or not).

- Mark a point (the current position) in the search space of the problem as visited.

- Communicate its current personal best to its neighbors.

- Request the current personal best locations of its neighbors to calculate its location.

* **agSwarm (agCluster)**: This agent is responsible for synchronizing the communications between *agEnv* and *agBird* agents. Among the tasks of this agent:

- Computing the *cbest* and communicate it to *agBird* agents requesting it.

- Communicating informations about the swarm to *agBird* agents.

- It can also ask *agEnv* to provide informations about other swarms.

**\* Strategies for moving agents according to the concept of accent**

Each agent is in conflict or in cooperation with its neighbors depending on its local
environment and intentions. Let $L_{i,j} = (l_1, l_2, ..., l_n)$ be the set of possible locations in the range
of the optimization solution and $M_{i,j} = (M_1, M_2, ..., Mn)$ the agent having the smallest fitness between four neighboring agents. $L_{i,j}$ is considered a winner only if it satisfies the equation: $F(L_{i,j}) \le F(M_{i,j})$ (17). In this case, its position in the solution space remains the same. Otherwise, its position will change according to the equation: $l'_k = m_k + \delta(m_k - l_k)$, $k = 1, 2, ..., n$ (18) knowing that $\delta$ is a random number in [-1, 1]. If $l'_k < x_{k \min}$ then $l'_k = x_{k \min}$, and if $l'_k > x_{k \max}$, then $l'_k = x_{k \max}$, knowing that $X_{\min}$ is the lower limit and $X_{\max}$ is the upper limit of the possible solution space in the optimization problem. $X_{\min} = (X_{1\min}, X_{2\min}, ..., X_{n\min})$ and $X_{\max} = (X_{1\max}, X_{2\max}, ..., X_{n\max})$.

## 3.4 Conclusion

In this chapter, we gave an integer linear programming formulation as a modeling of the 3D indoor deployment problem. This model is realistic and based on a set of constraints and objectives taken from a real context of use in a deployed DL-IoT collection network. Moreover, different modifications/hybridization schemes were explained. These analysis contributions relies essentially on the use of the neighbourhood and an adaptive guided concept for the mutation and recombination operators; the use of multiple scalarizing functions in the aggregation based approaches; and the incorporation of the reduction of dimensionality, the users preferences and multi-agent systems. Aiming at improving the behavior of the tested algorithms and enhancing theirs performances in solving complex real world problems, these modifications/hybridization are assessed; in the next chapter; using evaluation metrics, simulations and real prototyping.
Chapter 4

Numerical results, simulations and experimentations on testbeds

<table><tr><td>4.1 Introduction</td><td>92</td></tr><tr><td>4.2 Numerical results of incorporating dimensionality reduction and preferences on the deployment problem</td><td>92</td></tr><tr><td>4.2.1 Results on a constrained real world problem: the 3D Deployment in indoor WSNs</td><td>94</td></tr><tr><td>4.2.1.1 Testing the effect of interdependence between objectives</td><td>95</td></tr><tr><td>4.2.1.2 Testing the effect of the population size</td><td>95</td></tr><tr><td>4.2.1.3 Testing the effect of the choice of the scalarizing functions in MOEA/D</td><td>96</td></tr><tr><td>4.2.1.4 Testing the effect of using neighborhood mating and adaptive recombination operators</td><td>97</td></tr><tr><td>4.2.1.5 Testing the effect of hybridizing the 5EMOs with a dimensionality reduction approach</td><td>98</td></tr><tr><td>4.2.1.6 Testing the effect of hybridizing the EMOS with dimensionality reduction and user preferences</td><td>100</td></tr><tr><td>4.2.1.7 Results on PI-NSGA-III-VF</td><td>101</td></tr><tr><td>4.3 Numerical results on unconstrained DTLZ test functions</td><td>102</td></tr><tr><td>4.4 Simulations: Modeling the used protocols, simulation with small and large instances</td><td>109</td></tr><tr><td>4.4.1 Network protocol modeling</td><td>109</td></tr><tr><td>4.4.2 Small-scale simulations of the network with OMNet++</td><td>111</td></tr><tr><td>4.4.3 Large scale network simulations with OMNet++</td><td>114</td></tr><tr><td>4.4.3.1 Variations in the number of nomad nodes added in large-scale simulations</td><td>115</td></tr><tr><td>4.4.3.2 Changes in RSSI rates in large-scale simulations</td><td>116</td></tr><tr><td>4.4.3.3 Variations in FER rates in large-scale simulations</td><td>116</td></tr><tr><td>4.4.3.4 Variations in the number of neighbors in large-scale simulations</td><td>117</td></tr><tr><td>4.4.3.5 Variations in energy consumption and network lifetime in large-scale simulations</td><td>117</td></tr><tr><td>4.4.4 Discussion and interpretations</td><td>118</td></tr><tr><td>4.5 Experimentations on real testbeds</td><td>119</td></tr><tr><td>4.5.1 Experimental parameters and used tools</td><td>119</td></tr><tr><td>4.5.2 Scenario 1: Testing with 11 nodes</td><td>121</td></tr><tr><td>4.5.2.1 Network architecture</td><td>121</td></tr><tr><td>4.5.2.2 Objectives</td><td>123</td></tr><tr><td>4.5.2.3 Variation of the localization</td><td>123</td></tr><tr><td>4.5.2.4 Variation of the coverage</td><td>124</td></tr><tr><td>4.5.2.5 Variation of the number of neighbors</td><td>125</td></tr><tr><td>4.5.2.6 Discussion</td><td>126</td></tr><tr><td>4.5.3 Scenario 2: Ophelia testbed (Testing with 36 nodes)</td><td>127</td></tr><tr><td>4.5.3.1 Experimental scenario and results</td><td>127</td></tr><tr><td>4.5.3.2 Interpretations and discussion</td><td>129</td></tr><tr><td>4.5.4 Results of experimentations on PI-NSGA-III</td><td>129</td></tr><tr><td>4.6 Results on hybridizing ACO and NSGA-III (AcNSGA-III)</td><td>130</td></tr><tr><td>4.6.1 Numerical results of the algorithms</td><td>130</td></tr><tr><td>4.6.2 Comparing simulations and experimentations</td><td>131</td></tr><tr><td>4.7 Results on accentBirdsPSO and on hybridizing PSO and MAS</td><td>134</td></tr><tr><td>4.7.1 Numerical results</td><td>134</td></tr><tr><td>4.7.2 Experimental and simulation results</td><td>136</td></tr><tr><td>4.8 Conclusion</td><td>138</td></tr></table>
## 4.1 Introduction

In the previous chapter, we presented the proposed mathematical formulation of the 3D indoor deployment problem and the different hybridization schemes aimed at improving the behavior of the tested optimized optimization algorithms and enhancing their performances in solving complex real world problems. In this chapter, we will first illustrate the numerical results of the 3D deployment problem after incorporating our proposed scheme of dimensionality reduction and preferences. To prove the applicability of the proposed hybridization on different problems, we will detail, in the next section, the numerical results on the DTLZ unconstrained test functions when using the same scheme of hybridization. In the fourth section, we will propose a study that presents the modeling of the used protocols then simulations with small and large instances. Afterwards, we propose experiments on real testbeds with two scenarios (with small number of nodes then with a larger number). The last two sections of this chapter will describe the obtained results when hybridizing ACO and NSGA-III (AcNSGA-III), then the results of the accent Birds PSO and the PSO-MAS algorithms.

## 4.2 Numerical results of incorporation of Dimensionality Reduction and of preferences on the real world deployment problem

In this section, we present the performance indicators and the parameters setting. Afterwards, we demonstrate the performance of the suggested hybrid approach on real testbeds. In our works, the implementation of the MOEA/DD, NSGA-III and Two_Arch2 in the PlatEmo framework (Tian et al. 2017) is used.

* Performance metrics: To evaluate the approximation sets produced by running a MaOA, several performance metrics can be employed to compare these approximation sets using numeric values. Table 4.1 illustrates the most important performance metrics used to compare many-objective algorithms.

<table><caption>Table 4.1 Comparative table of the most appropriate/recommended metrics for MaOAs</caption><thead><tr><th>Performance Criteria</th><th>Metric</th><th>Expression (according to (Jiang et al. 2014))</th><th>Computational complexity</th><th>Computational comparison set</th><th>Prameter Requirements</th><th>Sets</th><th>Number of citations (according to (Riquelme at al. 2015))</th></tr></thead><tbody><tr><td rowspan="4">Capacity (cardinality) | x | defines the cardinality or the number of elements in the set x ; t=generation index</td><td>ONVG(S)<br>GNVG<br>NVA</td><td>ONVG(S) = |S|<br>GNVG(S) = |S(t)|<br>NVA(S, t) = GNVG(S,t)-GNVG(S, t-1)</td><td>Low</td><td>None</td><td>None</td><td>Unary</td><td>level maintained</td></tr><tr><td>ONVGR<br>GNVGR<br>ER (Error Ratio)</td><td>ONVGR(S, P) = |S|/|P|<br>GNVGR(S, P) = |S(t)|/|P|<br>ER(S, P) = 1 - |S∩P|/|P|</td><td>Low</td><td>Pareto front (P)</td><td></td><td>Unary</td><td></td></tr><tr><td>C1<sub>R</sub><br>C2<sub>R</sub></td><td>C1<sub>R</sub> = |S∩R|/|R|<br>C2<sub>R</sub>(S,R) = |{&#x20D7; ∈ S / ∃!&#x20D7; ∈ R : &#x20D7; &lt; &#x20D7;}| / |S|</td><td>O(m|S|,|R|)</td><td>Reference set (R)</td><td>None</td><td>Unary</td><td>level maintained</td></tr><tr><td>Metric C (Coverage of Two Sets)</td><td>C(S1, S2) = |{&#x20D7;2 ∈ S2 / ∃&#x20D7;1 ∈ S1 : &#x20D7;1 ≤ &#x20D7;2}| / |S2|</td><td>O(m|S1|,|S2|)</td><td>Optimal solution set (S)</td><td>None</td><td>Unary</td><td>level maintained</td></tr><tr><td>Diversity (distribution and spread)</td><td>Δ<sup>*</sup> (S,P)</td><td>Δ<sup>*</sup> (S,P) = <div style="display: inline-block; vertical-align: middle; text-align: center;"><div style="border-bottom: 1px solid black; padding: 0 5px;">&sum;<sub>k=1</sub><sup>m</sup> d(e&#x20D7;<sub>k</sub>, S) + &sum;<sub>i=1</sub><sup>|S|</sup> |d<sub>i</sub> - &#x20D7;|</div><div style="padding: 0 5px;">&sum;<sub>k=1</sub><sup>m</sup> d(e&#x20D7;<sub>k</sub>, S) + (|S|)&#x20D7;</div></div><br>Where<br>d(e&#x20D7;<sub>k</sub>, S) = min<sub>s&#x20D7;∈S</sub> || F(e&#x20D7;<sub>k</sub>) - F(s&#x20D7;)(s&#x20D7;) ||<br>and e&#x20D7;<sub>k</sub> ∈ P<br>is the extreme solutions on the kth objective.<br>d<sub>i</sub> = min<sub>s&#x20D7;∈S<sub>i</sub></sub> || F(s&#x20D7;<sub>i</sub>) - F(s&#x20D7;<sub>j</sub>) ||<br>to identify the closest pairwise solutions in S<br>&#x20D7; is the average of di</td><td>O(m|S|<sup>2</sup>,m|S|,|P|)</td><td>Pareto front (P)</td><td>None</td><td>Unary</td><td>Decreasing</td></tr><tr><td>Convergence</td><td>I<sup>l</sup><sub>ε+</sub> (ε-indicator)</td><td>inf<sub>ε∈R</sub> {&radic;(|&#x20D7;| ∈ P | ∃&#x20D7; ∈ S : &#x20D7; ≤ &#x20D7; + ε)}<br>where ε defines the value required to translate or scale the optimal solution set S such that S</td><td>O(m|S|,|P|)</td><td>Pareto front (P)</td><td>None</td><td>Binary</td><td>Decreasing</td></tr></tbody></table>
<table><tr><td rowspan="2">Convergence -Diversity</td><td>IGD(P,S)</td><td>dominates P<br/>(∑<sub>i=1</sub><sup>|P|</sup> d<sub>i</sub><sup>q</sup>)<sup>1/q</sup><br/>|P|<br/>Where d<sub>i</sub> = min<sub>S∈S</sub> || F(p̃<sub>i</sub>) - F(s̃) ||<br/>p̃<sub>i</sub> ∈ P and q=2<br/>di is the smallest distance of p̃ ∈ P to the closest solutions in S.</td><td>O(m|S|·|P|)</td><td>Pareto front (P)</td><td>None</td><td>Unary</td><td>Increasing</td></tr><tr><td>Hypervolume (HV)</td><td>HV(S,R) = volume(∑<sub>i=1</sub><sup>|S|</sup> v<sub>i</sub>)<br/>where vi is a hypercube constructed with the reference set for each solution s̃<sub>i</sub> ∈ S</td><td>O(|S|<sup>m-1</sup>)</td><td>Reference set (R)</td><td>None</td><td>Unary</td><td>Increasing</td></tr></table>

where:

ONVG: Overall Non-dominated Vector Generation

GNVG: Generational Non-dominated Vector Generation

NVA: Non-dominated Vector Additional

ONVGR: Overall Non-dominated Vector Generation Ratio

GNVGR: Generational Non-dominated Vector Generation Ratio

C1R: Found Ratio of the Reference Points

C2R: Non-dominated Points by Reference Set

Given this variety of metrics, a research issues is questionable: What metrics should we choose when evaluating the performance of MaOPs? : Inverted Generational Distance (IGD) is less costly in calculating then the Hypervolume (HV) especially for high dimensional PFs. Yet, the comparing set ‘P’ in IGD may be more difficult to build than the reference set ‘R’ in HV. If the true Pareto front of the problem is known, the closeness to the true Pareto front can be measured. Otherwise, if no information is available about the true Pareto front, the hyper-volume and space metric can be used. Indeed, there are many metrics that are not suitable to evaluate MaOPs. For instance, we can cite the Δ metric which can be applied only for two-objective problems. On the other hand, although the HV is an expensive computationally metric, it is useful in the case of real world problems that require a prior knowledge of the real Pareto front. As a consequence, various studies (Fonseca et al. 2006), (Beume et al. 2009) were carried out to reduce the computational complexity of the HV. To sum up, the HV is necessary applied to evaluate the MaOPs because it does not require a prior-knowledge of the true Pareto-front which is important when benchmarking on real-world problems. Besides, this metric gives a single measurement to assess both the spread and convergence of solutions. However, the IGD can be used with synthetic problems due to its low computational cost.

The HV introduced in (Zitzler et al. 1999), also known as hyper-area S metric and Lebesgue measure, is a metric representing the volume of the objective space dominated by a solution set. It is a unary metric which is used to measure the size of the objective space covered by an approximation set. The HV is also the unique unary metric having the capability of measuring different aspects such as cardinality, diversity and accuracy. In the case of minimizing the objectives, smaller HV values are better used since they denote smaller difference between the approximation set and the reference set. Since it allows having an idea on both convergence and diversity, HV is a preferred performance metric but its computational cost makes it infeasible in several complex many-objective problems. In fact, it can be adapted to handle the user preferences in MaOAs as in (Wickramasinghe et al. 2010).

The IGD metric (Coello et al. 2002) is the inverted variation of the GD metric. The principal difference is that GD calculates the average distance, while IGD computes the minimum Euclidean distance between the PF and an approximation set A. Moreover, the solutions in the PF are used as reference in IGD instead of the solutions in the set A to calculate the distance between the two sets. Besides, if sufficient members of the PF are known, the IGD metric will be able to measure both convergence and diversity of the set A (Riquelme et al. 2015).

According to (Jiang et al. 2014), the HV metric shows conflicting (similar, respectively) trends to IGD on the 4-dimensional concave (convex, respectively) PFs.
* **Parameters setting:** The setting of the parameters affects considerably the performance of the tested algorithm when resolving a particular problem. Yet, performing a set of experiments using several population sizes, number of objectives, number of generations and operators is necessary when testing each many-objective algorithm separately. The objective number varies between 2 and 8, for the real world problem, and between 3 and 15 for the test functions. In all tested problems (the real world problem and the test functions), the best performance for each instance is shown with a gray background. The considered EMO algorithms have different parameters. Unless a modification in the value of a parameter to test the impact of varying this parameter, the common used values of these parameters can be summarized as follows:

- The reproduction operators: The probability of crossover is $pc=0.9$ with a distribution index $ηc=50$. The probability of mutation is $pm=1/n$ with a distribution index $ηm=30$. $n$ is the problem dimensionality.

- Population Size: Several specifications of the population size and the number of weight vectors for different numbers of objectives are used for each test problem.

- The number of runs: Each algorithm is performed 25 times (25 independent runs) with each configuration. Then, the various configurations are compared based on HV, in the case of the real-world problem, and on IGD in the case of the test functions.

- The termination condition is the maximum number of generations (solution evaluations) varying between 400 and 1500.

- The used scalarizing functions are: Weighted sum, Weighted Tchebycheff and PBI with a penalty parameter ($\theta = 0.01, 0.5, 1.0$ or $5.0$).

- The neighborhood size is set to 20 and the probability to select a parent from the neighborhood is 0.9.

### 4.2.1 Results on a constrained real world problem: the 3D Deployment in indoor WSNs

As application, we use a 3D indoor deployment WSN optimization problem with eight objectives. As described in the modeling (section 3.2), this problem has 10 decision variables as inputs and fourteen objective values as outputs. In this section, due to the complexity of computing the HV, only eight objective values to be optimized are considered. The difficulty of the tested real-world problem (3D Deployment Problem) increases with the number of objectives. Since we apply a high complexity metric (HV) to evaluate our problem, (because of the unknown Pareto front of our real world problem), the number of the used objectives ranges from 3 to 8 objectives among the objectives cited in Table 4.2. Concerning the parameters of the problem, unless indicated, the same parameters detailed in the experimentation (see section 4.5) are used: number of nodes, average number of runs and nodes repartition.

<table><caption>Table 4.2 Used objectives and their significance</caption><thead><tr><td>Obj no</td><td>Signification</td></tr></thead><tbody><tr><td>f1</td><td>Number of the added nomad nodes</td></tr><tr><td>f2</td><td>Energy consumption</td></tr><tr><td>f3</td><td>Hardware deployment cost</td></tr><tr><td>f4</td><td>Network Utilization</td></tr><tr><td>f5</td><td>Localization rate</td></tr><tr><td>f6</td><td>Coverage rate</td></tr><tr><td>f7</td><td>Lifetime</td></tr><tr><td>f8</td><td>Connectivity rate</td></tr><tr><td>f9</td><td>Robustness and fault tolerance</td></tr><tr><td>f10</td><td>Quality of links</td></tr><tr><td>f11</td><td>Path loss and fading</td></tr><tr><td>f12</td><td>Packet delivery cost</td></tr><tr><td>f13</td><td>Antenna orientation</td></tr><tr><td>f14</td><td>Neighborhood distance between parents to be crossed</td></tr></tbody></table>
### 4.2.1.1 Testing the effect of interdependence between objectives

The size of the population is set to 1000 (a large population) which is run for different number of generations. The used scalarizing function (for MOEA/D and MOEA/DD) is PBI (0.5). The mutation probability is 1/400 with an index of 50 (a Bit-flip mutation), and the recombination probability is 0.9 with an index of 5 (a simulated binary crossover (SBX)). No neighbor mating in recombination and the objectives are correlated (For each experiment with N objectives, at least N/2 objectives are correlated). We employ 250 reference points for NSGA-III and MOEA/DD. In order to reduce the computational cost when calculating the HV, the improved dimension-sweep algorithm proposed in (Fonseca et al. 2006) is used to compute the HV. Tables 4.3 and 4.4 illustrate the obtained results.

<table><caption>Table 4.3 Best, average and worst values of HV with non-correlated objectives obtained using 15 independent runs</caption><thead><tr><th>Obj Nbr</th><th>Max Gen</th><th>MOEA/D(PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="3">3</td><td rowspan="3">400</td><td>0.989374</td><td>0.988986</td><td>0.942684</td><td>0.988996</td></tr><tr><td>0.974762</td><td>0.988953</td><td>0.938922</td><td>0.988929</td></tr><tr><td>0.974231</td><td>0.988911</td><td>0.932746</td><td>0.988245</td></tr><tr><td rowspan="3">4</td><td rowspan="3">800</td><td>0.973324</td><td>0.974733</td><td>0.975472</td><td>0.976521</td></tr><tr><td>0.972674</td><td>0.974578</td><td>0.974556</td><td>0.974568</td></tr><tr><td>0.972261</td><td>0.974523</td><td>0.974102</td><td>0.973629</td></tr><tr><td rowspan="3">6</td><td rowspan="3">1200</td><td>0.972943</td><td>0.972783</td><td>0.973631</td><td>0.974320</td></tr><tr><td>0.972556</td><td>0.972692</td><td>0.972647</td><td>0.972655</td></tr><tr><td>0.972186</td><td>0.972541</td><td>0.971876</td><td>0.972654</td></tr><tr><td rowspan="3">8</td><td rowspan="3">1500</td><td>0.962364</td><td>0.964895</td><td>0.965653</td><td>0.945623</td></tr><tr><td>0.961913</td><td>0.964772</td><td>0.960728</td><td>0.944756</td></tr><tr><td>0.961347</td><td>0.964431</td><td>0.960022</td><td>0.944032</td></tr></tbody></table>

<table><caption>Table 4.4 Best, average and worst values of HV with N (N>= Obj Nbr/2) correlated objectives using 15 independent runs</caption><thead><tr><th>Obj Nbr</th><th>Max Gen</th><th>MOEA/D(PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="3">3</td><td rowspan="3">400</td><td>0.994887</td><td>0.994233</td><td>0.940232</td><td>0.988764</td></tr><tr><td>0.993843</td><td>0.993568</td><td>0.939828</td><td>0.988538</td></tr><tr><td>0.983802</td><td>0.993134</td><td>0.939344</td><td>0.988462</td></tr><tr><td rowspan="3">4</td><td rowspan="3">800</td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td></tr><tr><td>0.976416</td><td>0.981426</td><td>0.978574</td><td>0.976422</td></tr><tr><td>0.976328</td><td>0.976124</td><td>0.976231</td><td>0.976346</td></tr><tr><td rowspan="3">6</td><td rowspan="3">1200</td><td>0.971596</td><td>0.977123</td><td>0.978923</td><td>0.974635</td></tr><tr><td>0.971574</td><td>0.974581</td><td>0.972402</td><td>0.974582</td></tr><tr><td>0.971523</td><td>0.973130</td><td>0.972103</td><td>0.974247</td></tr><tr><td rowspan="3">8</td><td rowspan="3">1500</td><td>0.969886</td><td>0.971841</td><td>0.966876</td><td>0.952886</td></tr><tr><td>0.969815</td><td>0.969822</td><td>0.966525</td><td>0.952835</td></tr><tr><td>0.969702</td><td>0.969723</td><td>0.966234</td><td>0.952803</td></tr></tbody></table>

From the obtained results, it can be concluded that, for different numbers of objectives and generations, MOEA/D is more efficient than the NSGA-III and MOEA/DD is generally more efficient than other algorithms. Moreover, the HV increases if there is a correlation between the different objectives, especially in the case of the MOEA/D algorithm having higher relative advantage improvement compared to other algorithms.

### 4.2.1.2 Testing the effect of the population size

In this section, HV values are presented for different population sizes in order to test the effect of the variation in the population size on the behavior of MaOAs. The scalarizing function used in MOEA/D and MOEA/DD is PBI (0.5). The probability of mutation is 1/500 (bit-flip mutation) and the probability of recombination is 0.8 (SBX crossover). No neighbor mating of parents and the objectives are correlated (For each experiment with N objectives, at least N/2 of them are correlated). The number of reference points is chosen according to the size of the population and the number of objectives. Table 4.5 details the best, average and worst HV values when varying the population number and the size population.

<table><caption>Table 4.5 Best, average and worst values of HV with different population sizes and various objectives numbers</caption><thead><tr><th>Obj Nbr</th><th>Population size</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th><th>Number of reference points (MOEA/DD, NSGA-III)</th></tr></thead><tbody><tr><td rowspan="3">100</td><td rowspan="3"></td><td>0.956923</td><td>0.983461</td><td>0.973231</td><td>0.973682</td><td rowspan="3">90</td></tr><tr><td>0.956517</td><td>0.981027</td><td>0.972675</td><td>0.972987</td></tr><tr><td>0.956208</td><td>0.980429</td><td>0.972089</td><td>0.972023</td></tr><tr><td rowspan="3">500</td><td rowspan="3"></td><td>0.972863</td><td>0.985237</td><td>0.977863</td><td>0.985682</td><td rowspan="3">130</td></tr><tr><td>0.972165</td><td>0.984162</td><td>0.977258</td><td>0.976263</td></tr><tr><td>0.972022</td><td>0.984103</td><td>0.977037</td><td>0.976044</td></tr><tr><td></td><td></td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td><td></td></tr></tbody></table>
Chapter 4. Numerical results, simulations and experimentations on testbeds

<table><tbody><tr><td rowspan="3">4</td><td>1000</td><td>0.976412<br>0.976328</td><td>0.981426<br>0.976124</td><td>0.978574<br>0.976231</td><td>0.976422<br>0.976346</td><td>255</td></tr><tr><td>1200</td><td>0.976664<br>0.976586<br>0.972343</td><td>0.986213<br>0.985897<br>0.985251</td><td>0.978683<br>0.978764<br>0.978037</td><td>0.977023<br>0.976986<br>0.976431</td><td>280</td></tr><tr><td>1400</td><td>0.976874<br>0.976758<br>0.974032</td><td>0.986852<br>0.986238<br>0.985140</td><td>0.978985<br>0.978583<br>0.978362</td><td>0.987875<br>0.987244<br>0.977032</td><td>290</td></tr><tr><td rowspan="8">8</td><td rowspan="3">100</td><td>0.969369<br>0.969292<br>0.969083</td><td>0.970145<br>0.969233<br>0.969002</td><td>0.959863<br>0.959467<br>0.959302</td><td>0.952894<br>0.952236<br>0.952035</td><td>90</td></tr><tr><td>500</td><td>0.969963<br>0.969643<br>0.969354</td><td>0.969786<br>0.969645<br>0.969423</td><td>0.960869<br>0.960098<br>0.959326</td><td>0.969878<br>0.952543<br>0.952132</td><td>230</td></tr><tr><td>1000</td><td>0.969886<br>0.969815<br>0.969702</td><td>0.971841<br>0.969822<br>0.969723</td><td>0.966876<br>0.966525<br>0.966234</td><td>0.952886<br>0.952835<br>0.952803</td><td>320</td></tr><tr><td rowspan="3">1200</td><td>0.969894<br>0.969831<br>0.969063</td><td>0.970274<br>0.969962<br>0.969146</td><td>0.967964<br>0.967663<br>0.960022</td><td>0.970623<br>0.953195<br>0.952678</td><td>350</td></tr><tr><td>1400</td><td>0.969965<br>0.969887<br>0.969576</td><td>0.970988<br>0.970231<br>0.969862</td><td>0.968326<br>0.967989<br>0.960374</td><td>0.971589<br>0.953651<br>0.953233</td><td>350</td></tr></tbody></table>

For most numbers of objectives, better results were obtained by MOEA/D and MOEA/DD than NSGA-III. Obtained results demonstrate that the increase of the population size does not affect the ability of search of the MOEA/D. Contrariwise; the MOEA/D efficiency is degraded by the rise in the population size and does not work well with large population sizes. As a result, determining the appropriate size of the population according to the number of considered objectives is an interesting area of research. An important observation is that the efficiency of MOEA/D cannot be influenced by the population size increase due to the multiple neighbors which may be replaced with newly-generated better off-spring.

### 4.2.1.3 Testing the effect of the choice of the scalarizing functions in MOEA/D

Some previous research studies proved that MOEA/D works well on a wide range of test problems despite the fact that its performance depends on the choice of the used scalarizing function. Thus, the choice of the appropriate scalarizing function (or the appropriate scalarizing function set) is an interesting research topic. In our experiments, MOEA/D is applied with the weighted sum, the weighed Tchebycheff and the PBI function ($\theta = 0,01, 0.5, 1.0, 5.0$) to our many-objective problem with $\alpha = 1, 1.01, 1.1$. The performance of each scalarizing function is evaluated by calculating the average HV value over 15 runs. The population size in MOEA/D is specified as 1000. The mutation probability is 1/500 (Bit-flip mutation) and the recombination probability is 0.8 (SBX crossover). No neighbor mating in recombination and the objectives are either non-correlated or correlated (if correlated, at least N/2 objectives are correlated for each experiment with N objectives). The MOEA/D algorithm is tested using the mentioned scalarizing functions then using the adaptive scalarizing functions concept as discussed previously in the approach (see section 3.3.2.2). Table 4.6 shows the HV values when varying the scalarizing functions with different correlation relations between the different objectives.

<table><caption>Table 4.6 Average values of HV with various scalarizing functions and correlation relations between objectives</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="4">Non-Correlated Objectives</th><th colspan="4">Correlated Objectives</th></tr><tr><th>2</th><th>4</th><th>6</th><th>8</th><th>2</th><th>4</th><th>6</th><th>8</th></tr></thead><tbody><tr><td></td><td>Weighted sum</td><td>0.969216</td><td>0.971227</td><td>0.971074</td><td>0.970819</td><td>0.969812</td><td>0.972318</td><td>0.972517</td><td>0.972603</td></tr><tr><td rowspan="3">Weighted Tchebycheff</td><td>α=1</td><td>0.960125</td><td>0.959591</td><td>0.959117</td><td>0.955584</td><td>0.975044</td><td>0.973581</td><td>0.972976</td><td>0.970994</td></tr><tr><td>α=1.01</td><td>0.960314</td><td>0.959783</td><td>0.959374</td><td>0.955702</td><td>0.975210</td><td>0.973816</td><td>0.973112</td><td>0.971253</td></tr><tr><td>α=1.1</td><td>0.960722</td><td>0.959958</td><td>0.959602</td><td>0.955958</td><td>0.975558</td><td>0.974092</td><td>0.973376</td><td>0.971546</td></tr><tr><td rowspan="3">PBI (θ=0.01)</td><td>α=1</td><td>0.969002</td><td>0.968797</td><td>0.968814</td><td>0.968612</td><td>0.969973</td><td>0.969917</td><td>0.969546</td><td>0.969411</td></tr><tr><td>α=1.01</td><td>0.969105</td><td>0.968946</td><td>0.968705</td><td>0.968517</td><td>0.969804</td><td>0.969961</td><td>0.969472</td><td>0.969171</td></tr><tr><td>α=1.1</td><td>0.969289</td><td>0.968984</td><td>0.968462</td><td>0.968584</td><td>0.969882</td><td>0.969983</td><td>0.969482</td><td>0.969277</td></tr><tr><td rowspan="3">PBI (θ=0.5)</td><td>α=1</td><td>0.969458</td><td>0.969101</td><td>0.969215</td><td>0.969547</td><td>0.970135</td><td>0.970798</td><td>0.970814</td><td>0.969984</td></tr><tr><td>α=1.01</td><td>0.969907</td><td>0.969204</td><td>0.968827</td><td>0.968376</td><td>0.970914</td><td>0.970813</td><td>0.970609</td><td>0.969774</td></tr><tr><td>α=1.1</td><td>0.969931</td><td>0.969286</td><td>0.969119</td><td>0.968663</td><td>0.971221</td><td>0.970994</td><td>0.970726</td><td>0.969631</td></tr><tr><td rowspan="3">PBI (θ=1)</td><td>α=1</td><td>0.974432</td><td>0.972526</td><td>0.972971</td><td>0.962134</td><td>0.977083</td><td>0.976089</td><td>0.971938</td><td>0.969967</td></tr><tr><td>α=1.01</td><td>0.974515</td><td>0.972674</td><td>0.972556</td><td>0.961913</td><td>0.977142</td><td>0.976416</td><td>0.971574</td><td>0.969815</td></tr><tr><td>α=1.1</td><td>0.974566</td><td>0.972738</td><td>0.971798</td><td>0.961678</td><td>0.977361</td><td>0.976482</td><td>0.971844</td><td>0.969892</td></tr><tr><td rowspan="3">PBI (θ=5)</td><td>α=1</td><td>0.970682</td><td>0.970025</td><td>0.968718</td><td>0.981823</td><td>0.971058</td><td>0.971083</td><td>0.869988</td><td>0.963776</td></tr><tr><td>α=1.01</td><td>0.970991</td><td>0.970322</td><td>0.968203</td><td>0.961459</td><td>0.971326</td><td>0.971184</td><td>0.969637</td><td>0.963281</td></tr><tr><td>α=1.1</td><td>0.970994</td><td>0.970537</td><td>0.968561</td><td>0.961985</td><td>0.971632</td><td>0.971446</td><td>0.969791</td><td>0.963688</td></tr></tbody></table>
According to the results in Table 4.6, the weighted Tchebycheff is not appropriate for the many-objective problem with no or small correlation relation between objectives. However, it worked well on our many-objective problem when objectives were correlated. Indeed, the performance of the weighted Tchebycheff scalarizing function depends on the value of $\alpha$. If this value is increased from 1 to 1.01 and 1.1, which helps to improve the average HV for all the tested numbers and types (correlated/non-correlated) of objectives.

Concerning the PBI, the parameter $\alpha$ has a variable behavior. For all number of objectives, better results were obtained when these objectives were correlated. Having 2 and 4 objectives, better results (less deterioration) were provided using PBI with $\alpha = 1.01$ and $\alpha = 1.1$. However, having 6 and 8 objectives, promising results were obtained using PBI with $\alpha = 1.0$. As far as $\theta$ parameter is concerned, good results were provided using the PBI function with $\theta = 0.01$, 0.5 and 1, while the PBI with $\theta = 5$ was always the worst.

Another interesting finding is that, for small penalty ($\theta$) values, the deterioration of the performance of the MOEA/D when increasing the objectives number was less clear when using the PBI function than the weighted Tchebycheff one. Moreover, employing a high penalty values ($\theta=5$) with non-correlated objectives, the MOEA/D encountered difficulties in finding better solutions when using the weighted Tchebycheff function, compared to the PBI.

Besides, the experimental findings show that the weighted sum is not suitable for two-objective problems. However, it is a good choice for four to eight many-objective problems. For further investigations, the evolution of the number of non-dominated solutions according to the size of the population, using different scalarizing functions, can be studied.

### 4.2.1.4 Testing the effect of using neighborhood mating restrictions and adaptive recombination operators

In this section, we examine the effect of the proposed strategy for mating similar parent and adaptive mutation and recombination operators (see section 3.3.2.1). The performance of each algorithm is evaluated using the average HV over 15 runs. The population size in MOEA/D is specified as 1000. The mutation probability is 1/500 and the recombination probability is 0.8. Neighbor mating is performed in recombination and the objectives are correlated. The number of reference points is set to 100. Table 4.7 illustrates the obtained results.

<table><caption>Table 4.7 Best, average and worst HV values using adaptive operators</caption><thead><tr><th></th><th>Obj Nbr</th><th>MOEA/D(PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="6">Bit-flip mutation / SBX recombination</td><td rowspan="3">4</td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td></tr><tr><td>0.976416</td><td>0.981426</td><td>0.978574</td><td>0.976422</td></tr><tr><td>0.976328</td><td>0.976124</td><td>0.976231</td><td>0.976346</td></tr><tr><td rowspan="3">8</td><td>0.969886</td><td>0.971841</td><td>0.966876</td><td>0.952886</td></tr><tr><td>0.969815</td><td>0.969822</td><td>0.966525</td><td>0.952835</td></tr><tr><td>0.969702</td><td>0.969723</td><td>0.966234</td><td>0.952803</td></tr><tr><td rowspan="6">Using neighborhood mating restrictions and adaptive operators</td><td rowspan="3">4</td><td>0.978678</td><td>0.983129</td><td>0.979697</td><td>0.977234</td></tr><tr><td>0.978133</td><td>0.981952</td><td>0.979342</td><td>0.976986</td></tr><tr><td>0.976253</td><td>0.980237</td><td>0.979032</td><td>0.976343</td></tr><tr><td rowspan="3">8</td><td>0.970489</td><td>0.971002</td><td>0.971234</td><td>0.953864</td></tr><tr><td>0.969932</td><td>0.970254</td><td>0.967751</td><td>0.953366</td></tr><tr><td>0.963231</td><td>0.968968</td><td>0.963268</td><td>0.953032</td></tr></tbody></table>

The obtained results with different numbers of objectives indicate that the neighborhood mating and the use of adaptive operators improve considerably the search performance. In fact, better results were obtained for different numbers of objectives on the MOEA/DD algorithm. Obviously, when the number of objectives increases, the advantage of the MOEA/DD over the MOEA/D becomes clearer. Nevertheless, MOEA/D improves more considerably the average HV value (with and without similar parent recombination), compared to other algorithms. Moreover, experimental results show that mating similar parents improves the diversity without deteriorating the convergence.
### 4.2.1.5 Testing the effect of hybridizing the 5EMOs with a dimensionality reduction approach

In this section, we investigate the effect of incorporating our proposed approach for dimensionality reduction. In this set of experiments, the HV is calculated and the size of the population is set to 1000. Different adaptive scalarizing functions are used for MOEA/D and MOEA/DD. The mutation probability is set to 1/400 with an index of 50 and the recombination probability is 0.9 with an index of 5. Adaptive mutation and recombination operators are used with neighbor parents mating. 8 correlated objectives are employed (for each experiment with N objectives, at least N/2 objectives are correlated). 250 reference points are applied for NSGA-III. Table 4.8 illustrates the obtained results.

<table><caption>Table 4.8 Best, average and worst HV values obtained before and after applying the dimensionality reduction approach</caption><thead><tr><th></th><th>Initial Obj Nbr</th><th>Obj Nbr after reduction</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="3">Without reduction</td><td rowspan="3">4 / 5</td><td rowspan="3">4 / 5</td><td>0.984426</td><td>0.983652</td><td>0.978863</td><td>0.976498</td></tr><tr><td>0.976416</td><td>0.981426</td><td>0.978574</td><td>0.976422</td></tr><tr><td>0.976328</td><td>0.976124</td><td>0.976231</td><td>0.976346</td></tr><tr><td rowspan="3">Using L- PCA /NL-MVU-PCA</td><td rowspan="3"></td><td rowspan="3">3</td><td>0.994975</td><td>0.982897</td><td>0.982896</td><td>0.989352</td></tr><tr><td>0.991264</td><td>0.982542</td><td>0.982251</td><td>0.987144</td></tr><tr><td>0.980023</td><td>0.982231</td><td>0.982033</td><td>0.986021</td></tr><tr><td rowspan="3">Without reduction</td><td rowspan="3">8</td><td rowspan="3">8</td><td>0.969886</td><td>0.971841</td><td>0.966876</td><td>0.952886</td></tr><tr><td>0.969815</td><td>0.969822</td><td>0.966525</td><td>0.952835</td></tr><tr><td>0.969702</td><td>0.969723</td><td>0.966234</td><td>0.952803</td></tr><tr><td rowspan="3">Using L- PCA /NL-MVU-PCA</td><td rowspan="3"></td><td rowspan="3">4</td><td>0.971978</td><td>0.984986</td><td>0.969897</td><td>0.954237</td></tr><tr><td>0.970951</td><td>0.984158</td><td>0.961152</td><td>0.953654</td></tr><tr><td>0.970236</td><td>0.983943</td><td>0.960364</td><td>0.953028</td></tr></tbody></table>

From the results presented in Table 4.8, for four and eight objectives, the HV values found when using dimensionality reduction approach are higher than those obtained without using this method due to the reduction in the number of objectives from eight to five in the case of our real-world problem. Moreover, the improvement rate of the MOEA/D clearly exceeds those of other algorithms.

In the following, we detail the application of the proposed dimensionality reduction approach (The NL-MVU-PCA algorithm, for non-linear objective reduction, and L-PCA for linear objective reduction) to our real-world problem. Since Two_Arch2 has the best performance, we describe here only the use of the MOEA/DD as a MaOA to test our dimensionality reduction approach on an eight-objective 3D deployment problem. The tables below illustrate the set of the most dominant objectives found after 15-runs of the NL-MVU-PCA and L-PCA. According to (Sinha et al. 2013), starting from an initial set of objectives $F_0=\{f_1, ..., f_M\}$, the NL-MVU-PCA aims at identifying the set $F_T$ of essential objectives by applying the following steps:

**Step 1 (Computing the correlation and the kernel matrix):** Based on the input data, the correlation matrix R (for linear objective reduction (L-PCA)) is plotted, the kernel matrix K (for nonlinear objective reduction (NL-MVU-PCA)) and its principal component (eigenvectors and eigenvalues) are computed. According to (Sinha et al. 2013), $R=(1/M)XX^T$ where M is the number of objectives and X is the input data. K is also calculated according to the formulation in (Sinha et al. 2013). Tables 4.9, 4.10, 4.11 and 4.12 illustrate the values of the matrix R, K as well as their Eigenvectors and eigenvalues.

<table><caption>Table 4.9 The correlation Matrix R on the first iteration</caption><thead><tr><th></th><th>f1</th><th>f2</th><th>f3</th><th>f4</th><th>f5</th><th>f6</th><th>f7</th><th>f8</th></tr></thead><tbody><tr><th>f1</th><td>1</td><td>-0.458</td><td>0.896</td><td>0.985</td><td>-0.258</td><td>0.885</td><td>0.875</td><td>-0.647</td></tr><tr><th>f2</th><td>-0.458</td><td>1</td><td>-0.521</td><td>-0.678</td><td>-0.735</td><td>-0.613</td><td>0.365</td><td>-0.647</td></tr><tr><th>f3</th><td>0.896</td><td>-0.521</td><td>1</td><td>0.982</td><td>-0.385</td><td>0.997</td><td>0.354</td><td>-0.647</td></tr><tr><th>f4</th><td>0.985</td><td>-0.678</td><td>0.982</td><td>1</td><td>-0.392</td><td>0.839</td><td>0.365</td><td>-0.647</td></tr><tr><th>f5</th><td>-0.258</td><td>-0.735</td><td>-0.385</td><td>-0.392</td><td>1</td><td>-0.264</td><td>0.238</td><td>-0.647</td></tr><tr><th>f6</th><td>0.885</td><td>-0.613</td><td>0.997</td><td>0.839</td><td>-0.264</td><td>1</td><td>0.364</td><td>-0.647</td></tr><tr><th>f7</th><td>0.875</td><td>0.365</td><td>0.354</td><td>0.365</td><td>0.238</td><td>0.364</td><td>1</td><td>-0.647</td></tr><tr><th>f8</th><td>-0.647</td><td>-0.647</td><td>-0.647</td><td>-0.647</td><td>-0.647</td><td>-0.647</td><td>-0.647</td><td>1</td></tr></tbody></table>

<table><caption>Table 4.10 The kernel Matrix K</caption><thead><tr><th></th><th>f1</th><th>f2</th><th>f3</th><th>f4</th><th>f5</th><th>f6</th><th>f7</th><th>f8</th></tr></thead><tbody><tr><th>f1</th><td>4.568</td><td>-4.521</td><td>4.895</td><td>6.552</td><td>-7.353</td><td>9.652</td><td>6.548</td><td>-6.365</td></tr><tr><th>f2</th><td>-4.521</td><td>6.021</td><td>-4.257</td><td>-6.215</td><td>-7.985</td><td>-9.245</td><td>9.253</td><td>-6.365</td></tr></tbody></table>
<table><caption>Table 4.11 Eigenvectors and eigenvalues of the matrix R</caption><tr><td>f3</td><td>4.895</td><td>-4.257</td><td>6.892</td><td>6.812</td><td>-7.154</td><td>11.246</td><td>12.568</td><td>-6.365</td></tr><tr><td>f4</td><td>6.552</td><td>-6.215</td><td>6.812</td><td>8.453</td><td>-7.554</td><td>11.246</td><td>12.568</td><td>-8.852</td></tr><tr><td>f5</td><td>-7.353</td><td>-7.985</td><td>-7.154</td><td>-7.554</td><td>12.258</td><td>-11.246</td><td>18.258</td><td>-8.254</td></tr><tr><td>f6</td><td>9.652</td><td>-9.245</td><td>11.246</td><td>11.246</td><td>-11.246</td><td>18.254</td><td>18.891</td><td>-8.852</td></tr><tr><td>f7</td><td>6.548</td><td>9.253</td><td>12.568</td><td>12.568</td><td>18.258</td><td>18.891</td><td>25.547</td><td>-18.255</td></tr><tr><td>f8</td><td>-6.365</td><td>-6.365</td><td>-6.365</td><td>-8.852</td><td>-8.254</td><td>-8.852</td><td>-18.255</td><td>21.541</td></tr></table>

<table><caption>Table 4.12 Eigenvectors and eigenvalues of the matrix K</caption><thead><tr><th>e1=0.646</th><th>e2=0.221</th><th>e3=0.084</th><th>e4=0.003</th></tr><tr><th>v1</th><th>v2</th><th>v3</th><th>v4</th></tr></thead><tbody><tr><td>0.215</td><td>0.886</td><td>0.568</td><td>0.638</td></tr><tr><td>-0.568</td><td>-0.322</td><td>0.546</td><td>-0.457</td></tr><tr><td>0.585</td><td>0.662</td><td>0.531</td><td>-0.891</td></tr><tr><td>0.689</td><td>-0.211</td><td>0.284</td><td>-0.457</td></tr><tr><td>-0.985</td><td>-0.354</td><td>0.893</td><td>0.594</td></tr><tr><td>0.325</td><td>-0.498</td><td>0.045</td><td>0.617</td></tr><tr><td>0.236</td><td>-0.158</td><td>0.104</td><td>0.685</td></tr><tr><td>-0.652</td><td>-0.659</td><td>-0.593</td><td>-0.237</td></tr></tbody></table>

<table><thead><tr><th>e1=0.548</th><th>e2=0.276</th><th>e3=0.048</th><th>e4=0.002</th></tr><tr><th>v1</th><th>v2</th><th>v3</th><th>v4</th></tr></thead><tbody><tr><td>-0.234</td><td>0.056</td><td>0.448</td><td>-0.253</td></tr><tr><td>0.665</td><td>-0.094</td><td>0.125</td><td>0.151</td></tr><tr><td>0.652</td><td>0.114</td><td>0.356</td><td>0.198</td></tr><tr><td>0.745</td><td>0.146</td><td>0.651</td><td>0.235</td></tr><tr><td>0.351</td><td>-0.338</td><td>0.821</td><td>0.358</td></tr><tr><td>0.452</td><td>0.562</td><td>0.886</td><td>0.564</td></tr><tr><td>-0.635</td><td>0.567</td><td>-0.662</td><td>0.282</td></tr><tr><td>0.328</td><td>-0.523</td><td>-0.543</td><td>0.025</td></tr></tbody></table>

**Step 2 (Eigenvalue Analysis):** consists in identifying the set of the important objectives in the initial set of objectives by performing the eigenvalue analysis that identifies the principal components (directions of significant variance) in the data. Table 4.13 (Table 4.14, respectively) depicts the eigenvalue analysis for linear objective reduction (non-linear objective reduction, respectively).

<table><caption>Table 4.13 Eigenvalue Analysis for L-PCA</caption><thead><tr><th>PCA (N°)</th><th>Variance (%)</th><th>Cumulative (%)</th><th colspan="10">Selected objectives</th></tr></thead><tbody><tr><td>1</td><td>64.6</td><td>64.60</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>22.1</td><td>97.09</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>8.4</td><td>99.62</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>0.3</td><td>99.99</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 4.14 Eigenvalue Analysis for NL-MVU-PCA</caption><thead><tr><th>PCA (N°)</th><th>Variance (%)</th><th>Cumulative (%)</th><th colspan="10">Selected objectives</th></tr></thead><tbody><tr><td>1</td><td>54.8</td><td>54.80</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>27.6</td><td>94.45</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>4.8</td><td>99.99</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>0.2</td><td>99.99</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

**Step 3 (Reduced Correlation Matrix Analysis):** consists in identifying the set of identically-correlated subsets by carrying out the reduced correlation matrix analysis. The important objectives in each subset are retained and other objectives are discarded, which allows further reduction of the objective set obtained after step 2. Table 4.15 (Table 4.16, respectively) represents the RCM analysis for linear objective reduction (non-linear objective reduction, respectively). According to (Saxena et al. 2013), $T_{cor} = 1.0 - e_1.(1.0 - M'/M)$ where M' denotes the number of principal components required to account for 95.4% variance and M is the number of the problem objectives.

<table><caption>Table 4.15 RCM analysis for L-PCA</caption><tr><td>Potential identically correlated set(s)</td><td>{f1,f3,f4,f6}</td></tr><tr><td>T<sub>cor</sub> (correlation threshold)</td><td>1.0-0.646(2/8)=0.8385</td></tr><tr><td>Identically correlated set(s)</td><td>{f1,f3,f4,f6}</td></tr></table>

<table><caption>Table 4.16 RCM analysis for NL-MVU-PCA</caption><tr><td>Potential identically correlated set(s)</td><td>{f1,f3,f4,f6}</td></tr><tr><td>T<sub>cor</sub> (correlation threshold)</td><td>1.0-0.548(3/8)=0.7945</td></tr><tr><td>Identically correlated set(s)</td><td>{f1,f3,f4,f6}</td></tr></table>
**Step 4 (Selection scheme):** consists in identifying the most important objective in each set by applying the selection scheme. Table 4.17 (Table 4.18, respectively) demonstrates the selection scheme for linear objective reduction (non-linear objective reduction, respectively).

<table><caption>Table 4.17 Selection scheme for L-PCA</caption><thead><tr><th></th><th>e<sub>1</sub>= 0.646<br>V<sub>1</sub></th><th>e<sub>2</sub>= 0.221<br>V<sub>2</sub></th><th>e<sub>3</sub>= 0.084<br>V<sub>3</sub></th><th>e<sub>4</sub>=0.003<br>V<sub>4</sub></th><th>Objective selection<br>Score</th></tr></thead><tbody><tr><th>f1</th><td>0.215</td><td>0.886</td><td>0.568</td><td>0.638</td><td>0.458</td></tr><tr><th>f1</th><td>-0.568</td><td>-0.322</td><td>0.546</td><td>-0.457</td><td>0.462</td></tr><tr><th>f1</th><td>0.585</td><td>0.662</td><td>0.531</td><td>-0.891</td><td>0.483</td></tr><tr><th>f1</th><td>0.689</td><td>-0.211</td><td>0.284</td><td>-0.457</td><td>0.494</td></tr></tbody></table>

<table><caption>Table 4.18 Selection scheme for NL-MVU-PCA</caption><thead><tr><th></th><th>e<sub>1</sub>= 0.548<br>V<sub>1</sub></th><th>e<sub>2</sub>= 0.276<br>V<sub>2</sub></th><th>e<sub>3</sub>= 0.048<br>V<sub>3</sub></th><th>e<sub>4</sub>=0.002<br>V<sub>4</sub></th><th>Objective selection<br>Score</th></tr></thead><tbody><tr><th>f1</th><td>-0.234</td><td>0.056</td><td>0.448</td><td>-0.253</td><td>0.238</td></tr><tr><th>f1</th><td>0.665</td><td>-0.094</td><td>0.125</td><td>0.151</td><td>0.295</td></tr><tr><th>f1</th><td>0.652</td><td>0.114</td><td>0.356</td><td>0.198</td><td>0.684</td></tr><tr><th>f1</th><td>0.745</td><td>0.146</td><td>0.651</td><td>0.235</td><td>0.793</td></tr></tbody></table>

**Step 5 (Computation of the error):** is to measure the error incurred in one iteration of the proposed framework. This measure calculates the unaccounted left variance when discarding the objectives constituting the redundant objective set. According to the equation proposed in (Saxena et al. 2013), the error for L-PCA (NL-MVU-PCA, respectively) is equal to 0.000239 (0.000458, respectively).

The above-mentioned five-step process is achieved iteratively until the set of necessary objectives will be reduced to two objectives or until it stills the same for two successive iterations.

### 4.2.1.6 Testing the effect of hybridizing the EMOs with dimensionality reduction and user preferences

In this section, we examine the effect of applying our proposed approach to incorporate both dimensionality reduction method and user preference one. In this set of experiments, the HV is calculated with a large population (1000). The used scalarizing function (for MOEA/D and MOEA/DD) is PBI (0.5). The mutation probability is 1/400 with an index of 50, and the recombination probability is 0.9 with an index of 5. Adaptive mutation and recombination operators are employed with neighbor parents mating. 8 correlated objectives are used (for each experiment with N objectives, at least N/2 objectives are correlated). We use 250 reference points for NSGA-III. After applying reduction approach, the preference is applied on a reduced set of objectives. Tables 4.19 and 4.20 show the final solutions specifications (using Two_Arch2 as an EMO). Each run has a different initial population, which is the result of applying our reduction procedure on the concerned EMO. $d_s$ is a user-defined parameter representing the expected improvement in solutions obtained from the current best solution based on the value function, and $d_s = 0.01$. TD<sub>Max</sub> =30 is the maximum number of calls of the preference information introduced by the DM.

<table><caption>Table 4.19 Median obtained solutions (objective values)</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th rowspan="2">The most preferred point satisfying the KKT conditions and used to construct the value function.</th><th colspan="4">Average values</th></tr><tr><th>MOEA/D</th><th>NSGA-III</th><th>Two_Arch2</th><th>MOEA/DD</th></tr></thead><tbody><tr><th>f1</th><td>Number of added nomad nodes</td><td>128.452</td><td>134.161</td><td>142.54</td><td>152.339</td><td>133.581</td></tr><tr><th>f2</th><td>Energy consumption</td><td>3.857</td><td>3.998</td><td>4.021</td><td>4.056</td><td>3.962</td></tr><tr><th>f3 (redundant)</th><td>Hardware deployment cost</td><td>85</td><td>88.468</td><td>96.184</td><td>93.923</td><td>88.646</td></tr><tr><th>f4 (redundant)</th><td>Network Utilization</td><td>1.00</td><td>0.946</td><td>0.796</td><td>0.849</td><td>0.962</td></tr><tr><th>f5</th><td>Localization rate</td><td>3.991</td><td>3.605</td><td>3.882</td><td>3.863</td><td>3.812</td></tr><tr><th>f6 (redundant)</th><td>Coverage rate</td><td>5.865</td><td>4.189</td><td>4.984</td><td>4.235</td><td>5.572</td></tr><tr><th>f7</th><td>Lifetime</td><td>4280</td><td>3885</td><td>3687</td><td>3956</td><td>4065</td></tr><tr><th>f8</th><td>Connectivity rate</td><td>189.89</td><td>168.524</td><td>166.515</td><td>168.542</td><td>174.266</td></tr></tbody></table>

<caption>Table 4.20 Median distance of the solutions obtained from the most preferred solutions</caption>
<table><thead><tr><th></th><th>MOEA/D</th><th>NSGA-III</th><th>Two_Arch2</th><th>MOEA/DD</th></tr></thead><tbody><tr><td>Accuracy</td><td>0.234</td><td>0.419</td><td>0.468</td><td>0.023</td></tr><tr><td>Number of function evaluations</td><td>6321</td><td>7945</td><td>8231</td><td>5895</td></tr><tr><td>Number of required DM calls</td><td>TD<sub>Max</sub></td><td>26</td><td>25</td><td>16</td></tr></tbody></table>

### 4.2.1.7 Results on PI-NSGA-III-VF

In this section, the algorithms parameters and the obtained numerical results are presented. To assess the quality of the results, several metrics can be used. The Hypervolume (HV) (Zitzler et al. 1999) is one of these metrics. Although its computational cost is high, it is ideal in our case (real world problem) because of the unknown true PF. The used parameters setting are detailed in Table 4.21. The platform PlatEMO (Tian et al. 2017) is used to implement NSGA-III and PI-EMO-VF algorithms.

<table><caption>Table 4.21 Parameters setting of the algorithms</caption><thead><tr><th>Parameter</th><th>Value</th></tr></thead><tbody><tr><td>Population size</td><td>300</td></tr><tr><td rowspan="3">Recombination</td><td>Operator</td><td>SBX</td></tr><tr><td>probability</td><td>0.8</td></tr><tr><td>distribution index</td><td>45</td></tr><tr><td rowspan="3">Mutation</td><td>Operator</td><td>bit-flip</td></tr><tr><td>probability</td><td>1/400</td></tr><tr><td>distribution index</td><td>25</td></tr><tr><td>Number of independent runs</td><td>25, on different initial populations</td></tr><tr><td>Number of constraints</td><td>7</td></tr><tr><td>Number of objectives</td><td>Variable, see Table 4.22</td></tr><tr><td>Maximum number of generations</td><td>Variable, see Table 4.22</td></tr><tr><td>maximum number of preference calls</td><td>30</td></tr><tr><td>Improvement in solutions (d<sub>s</sub>)</td><td>0.01</td></tr></tbody></table>

Given the random behavior of the optimization algorithms and aiming at obtaining statistically reliable comparison results, an average of 25 executions of the algorithms is performed. Table 4.22 demonstrates the obtained HV values for different number of objectives and number of generations. Best performances are shown with shaded backgrounds.

<table><caption>Table 4.22 Hypervolume values (Best, average and worst)</caption><thead><tr><th>Number of Objectives</th><th>Max nr of generations</th><th>MOEA/DD</th><th>PI-NSGA-III-VF</th></tr></thead><tbody><tr><td rowspan="3">3</td><td rowspan="3">1300</td><td>0.902231</td><td>0.902458</td></tr><tr><td>0.901658</td><td>0.901896</td></tr><tr><td>0.898235</td><td>0.898023</td></tr><tr><td rowspan="3">4</td><td rowspan="3">1800</td><td>0.974892</td><td>0.974685</td></tr><tr><td>0.974743</td><td>0.974233</td></tr><tr><td>0.973897</td><td>0.973612</td></tr><tr><td rowspan="3">5</td><td rowspan="3">2600</td><td>0.972983</td><td>0.972892</td></tr><tr><td>0.972563</td><td>0.972716</td></tr><tr><td>0.972826</td><td>0.972684</td></tr></tbody></table>

In our real world context, the PI-NSGA-III-VF performs better when the number of objectives exceeds three. This matches the ascertainment of the NSGA-III authors which indicates that the NSGA-III is more appropriate for resolving many-objectives problems. Moreover, better HV values are retained with smaller number of objectives; this is explained by the proportional dependence between the problem complexity and the number of objectives. Tables 4.23 and 4.24 show the final solutions specifications, for $d_s = 0.01$, after applying the preference.

<table><caption>Table 4.23 Average retained objective values</caption><thead><tr><th rowspan="2">Objective</th><th rowspan="2">Mpp*</th><th colspan="2">Average-values</th></tr><tr><th>MOEA/DD</th><th>PI-NSGA-III-VF</th></tr></thead><tbody><tr><td>f4 (Quality of links)</td><td>91</td><td>85.985</td><td>92.223</td></tr><tr><td>f2 (Utilization of network)</td><td>1.000</td><td>0.947</td><td>0.786</td></tr><tr><td>f5 (Rate of localization)</td><td>3.992</td><td>3.602</td><td>3.847</td></tr></tbody></table>
<table><tr><td>f3 (Rate of coverage)</td><td>4.986</td><td>4.194</td><td>4.853</td></tr><tr><td>f1 (Rate of connectivity)</td><td>190.24</td><td>168.633</td><td>166.612</td></tr></table>

$Mpp^*$ is the most preferred point satisfying the KKT conditions and used to construct the value function.

<table><caption>Table 4.24 Average distance between the most preferred solutions and the obtained ones</caption><thead><tr><td></td><td>MOEA/DD</td><td>PI-NSGA-III-VF</td></tr></thead><tbody><tr><td>Accuracy</td><td>0.247</td><td>0.426</td></tr><tr><td>Number of function evaluations</td><td>6343</td><td>7948</td></tr><tr><td>Number of required DM calls</td><td>23</td><td>25</td></tr></tbody></table>

## 4.3 Numerical results on unconstrained DTLZ test functions

After testing our approach on real testbeds, we present the results provided by using a set of benchmark test problems to prove its scalability. Using 15 independent runs in each test, the performances of MOEA/D (Zhang and Li 2007) and those of MOEA/DD (Li et al. 2015), NSGA-III (Deb and Jain 2014) and Two_Arch2 (Wang et al. 2015) are verified. The experiments are conducted on a set of test problems taken from the widely-used test suite DTLZ (Deb et al. 2005). For each test problem, 3, 5, 10 and 15 objectives are considered, respectively. To compare the different algorithms in terms of the quality of the obtained non-dominated solution sets, the IGD indicator is used. As explained above, IGD is a metric which allows measuring both the diversity and the convergence of the obtained non-dominated solutions. It corresponds to the average Euclidean distance separating each reference solution from its closest non-dominated one. As reference solutions, the set of Pareto optimal solutions generated by all algorithms over all runs are used.

The applied test functions are DTLZ1 to DTLZ4 (Deb et al. 2005) and DTLZ(I,M) (Deb and Saxena 2006) from the DTLZ test suite. The main advantages of the DTLZ test problem suite are its scalability and its ability to arbitrary specifying the number of objectives. Indeed, for all DTLZ problems, the number of objectives varies from 3 to 15, i.e., $m \in \{3, 5, 8, 10, 15\}$. For instance, DTLZ1-4 are non-constrained and scalable three- to fifteen-objective problems. According to the recommendations in (Deb et al. 2005), the number of decision variables for DTLZ test instances is set to $n = m + r - 1$, where $r = 5$ for DTLZ1 and $r = 10$ for DTLZ2, DTLZ3 and DTLZ4. Table 4.25 illustrates each test problem features.

<table><caption>Table 4.25 Features of the used DTLZ test problems</caption><thead><tr><td>Used test problem</td><td>Features</td><td>Reducibility of the problem (Redundancy of objectives)</td></tr></thead><tbody><tr><td>DTLZ1</td><td>Scalable, Linear, Multi-modal</td><td>Irreducible problem (conflicting objectives)</td></tr><tr><td>DTLZ2</td><td>Scalable and continuous many-objective minimization problem, Concave Pareto Front</td><td>Irreducible problem (conflicting objectives)</td></tr><tr><td>DTLZ3</td><td>Scalable, Concave, Multi-modal</td><td>Irreducible problem (conflicting objectives)</td></tr><tr><td>DTLZ4</td><td>Scalable, Concave, Biased, favors the diversity of solutions</td><td>Irreducible problem (conflicting objectives)</td></tr><tr><td>DTLZ5(I,M)</td><td>Scalable problem, Non-convex Pareto-optimal front</td><td>Reducible problem (since it has M - 1 + 1 redundant objectives But if I=M-1, then it becomes an irreducible problem)</td></tr></tbody></table>

In our experiments, the DTLZ5 (I, M) test problem suit is also used. In fact, DTLZ5 (I, M) is an improvement of the DTLZ5 test problem characterized by a degraded Pareto front, which represents a good feature for dimensionality reduction. However, non-redundant objectives in DTLZ5 have a fixed number, which does not allow testing properly the efficiency of the algorithms. As a solution, the DTLZ5(I, M) test problem suit was proposed by Deb and Saxena (2006). The DTLZ5 (I, M) allows changing, without influencing to each other, the objectives number in the problem (noted *M*), the non-dominated objectives number (the dimensionality of the Pareto-optimal surface, noted *I*) and the variables number (noted *n*). Moreover, this test problem allows changing the dimensionality (*I*) of the Pareto-optimal front by simply setting *I* to an integer between two and *M*. The first *M* - *I* + 1 objectives are correlated, and the rest are in conflict with the other objectives. For example, having *I* = 2, a minimum of two objectives (the objective $f_M$ and any other one) is sufficient to represent the correct Pareto-optimal front as it is the case when DTLZ5(2,10) problem has 10 objectives
and two-dimensional Pareto-optimal front. Eight of these objectives are redundant and the Pareto-optimal front can be found, for different scales, with the objective f10 and any other objective function. Another instance of the DTLZ(I,M) problem, is the DTLZ5(3,10) involving 10 objectives and having a three-dimensional Pareto-optimal front.

To sum up, in order to investigate the degree of dependence between objectives, we test the propose algorithms on a highly-redundant problem (DTLZ5(2,15)), a moderately-redundant problem (DTLZ5(3,5)) and a non-redundant problem (DTLZ1 to DTLZ4).

Unless it is differently indicated in each experiment, the objectives are correlated (For each experiment with N objectives, at least N/2 of the objectives are correlated).

### 4.3.1 Testing the effect of interdependence between objectives

In this section, we study the effect of having dependencies between objectives. The size of the population is set to 1000 (a large population), which is run for different number of generations. The used scalarizing function (for MOEA/D and MOEA/DD) is PBI (5.0). The mutation probability is 1/400 with an index of 50 (Bit-flip mutation). The recombination probability is 0.9 with an index of 5 (SBX crossover). There are no neighbor mating and adaptive recombination in this set of experiments. The objectives are correlated (for each experiment with N objectives, at least N/2 objectives are correlated). 250 reference points for NSGA-III, with 15 independent runs, are used. Table 4.26 illustrates the median values of IGD on irreducible test functions (DTLZ1-2). Table 4.27 represents the best, average and worst values of IGD on reducible test functions (DTLZ5(2,15) and DTLZ5(3,5)). The best performance for each instance is shown with a gray background.

<table><caption>Table 4.26 Best, average and worst IGD values on DTLZ1-4 problems</caption><thead><tr><th>Test Pb</th><th>Obj Nbr</th><th>Number of generations</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="15">DTLZ1</td><td rowspan="3">3</td><td rowspan="3">400</td><td>4.095E-4</td><td>3.191 E-4</td><td>4.880 E-4</td><td>1.089 E-3</td></tr><tr><td>1.495E-3</td><td>5.848 E-4</td><td>1.308 E-3</td><td>1.228 E-3</td></tr><tr><td>4.743E-3</td><td>6.573 E-4</td><td>4.880 E-3</td><td>1.523 E-3</td></tr><tr><td rowspan="3">5</td><td rowspan="3">600</td><td>3.179E-4</td><td>2.635 E-4</td><td>5.116 E-4</td><td>6.034 E-4</td></tr><tr><td>6.372E-4</td><td>2.916 E-4</td><td>0.980 E-4</td><td>6.372 E-4</td></tr><tr><td>1.635E-3</td><td>3.109 E-4</td><td>1.979 E-3</td><td>6.967 E-4</td></tr><tr><td rowspan="3">10</td><td rowspan="3">1000</td><td>3.872E-3</td><td>1.828 E-3</td><td>2.215 E-3</td><td>2.368 E-3</td></tr><tr><td>5.073E-3</td><td>2.225 E-3</td><td>3.462 E-3</td><td>2.962 E-3</td></tr><tr><td>6.132E-3</td><td>2.467 E-3</td><td>6.869 E-3</td><td>3.101 E-3</td></tr><tr><td rowspan="3">15</td><td rowspan="3">1500</td><td>1.236E-2</td><td>2.867 E-3</td><td>2.649 E-3</td><td>4.346 E-3</td></tr><tr><td>1.431 E-2</td><td>4.203 E-3</td><td>5.063 E-3</td><td>4.927 E-3</td></tr><tr><td>1.692 E-2</td><td>4.609 E-3</td><td>1.123 E-2</td><td>5.239 E-3</td></tr><tr><td rowspan="15">DTLZ2</td><td rowspan="3">3</td><td rowspan="3">250</td><td>5.432 E-4</td><td>6.666 E-4</td><td>1.262 E-3</td><td>6.884 E-4</td></tr><tr><td>6.406 E-4</td><td>8.073 E-4</td><td>1.357 E-3</td><td>7.122 E-4</td></tr><tr><td>8.006 E-4</td><td>1.243 E-3</td><td>2.114 E-3</td><td>7.697 E-4</td></tr><tr><td rowspan="3">5</td><td rowspan="3">350</td><td>1.219 E-3</td><td>1.128 E-3</td><td>4.254 E-3</td><td>4.203 E-4</td></tr><tr><td>1.437 E-3</td><td>1.291 E-3</td><td>4.982 E-3</td><td>4.760 E-4</td></tr><tr><td>1.727 E-3</td><td>1.424 E-3</td><td>5.862 E-3</td><td>4.992 E-4</td></tr><tr><td rowspan="3">10</td><td rowspan="3">750</td><td>2.474 E-3</td><td>3.223 E-3</td><td>1.350 E-2</td><td>1.104 E-2</td></tr><tr><td>2.778 E-3</td><td>3.752 E-3</td><td>1.528 E-2</td><td>1.459 E-2</td></tr><tr><td>3.235 E-3</td><td>4.145 E-3</td><td>1.697 E-2</td><td>1.858 E-2</td></tr><tr><td rowspan="3">15</td><td rowspan="3">1000</td><td>5.254 E-3</td><td>4.577 E-3</td><td>1.360 E-2</td><td>4.263 E-3</td></tr><tr><td>6.005 E-3</td><td>5.863 E-3</td><td>1.726 E-2</td><td>4.726 E-3</td></tr><tr><td>9.409 E-3</td><td>6.929 E-3</td><td>2.114 E-2</td><td>5.294 E-3</td></tr><tr><td rowspan="15">DTLZ3</td><td rowspan="3">3</td><td rowspan="3">1000</td><td>9.773 E-4</td><td>5.690 E-4</td><td>9.751 E-4</td><td>3.237 E-3</td></tr><tr><td>3.426 E-3</td><td>1.892 E-3</td><td>4.007 E-3</td><td>3.742 E-3</td></tr><tr><td>9.113 E-3</td><td>6.231 E-3</td><td>6.665 E-3</td><td>4.123 E-3</td></tr><tr><td rowspan="3">5</td><td rowspan="3">1000</td><td>1.129 E-3</td><td>6.181 E-4</td><td>3.086 E-3</td><td>4.364 E-3</td></tr><tr><td>2.213 E-3</td><td>1.181 E-3</td><td>5.960 E-3</td><td>4.834 E-3</td></tr><tr><td>6.147 E-3</td><td>4.736 E-3</td><td>1.196 E-2</td><td>6.230 E-3</td></tr><tr><td rowspan="3">10</td><td rowspan="3">1500</td><td>2.791 E-3</td><td>1.689 E-3</td><td>8.849 E-3</td><td>9.265 E-3</td></tr><tr><td>4.319 E-3</td><td>2.164 E-3</td><td>1.188 E-2</td><td>9.836 E-3</td></tr><tr><td>1.010 E+0</td><td>3.226 E-3</td><td>2.082 E-2</td><td>2.364 E-2</td></tr><tr><td rowspan="3">15</td><td rowspan="3">2000</td><td>4.360 E-3</td><td>5.716 E-3</td><td>1.401 E-2</td><td>1.632 E-2</td></tr><tr><td>1.664 E-2</td><td>7.461 E-3</td><td>2.145 E-2</td><td>2.068 E-2</td></tr><tr><td>1.260 E+0</td><td>1.138 E-2</td><td>4.195 E-2</td><td>2.894 E-2</td></tr><tr><td rowspan="15">DTLZ4</td><td rowspan="3">3</td><td rowspan="3">600</td><td>2.929 E-1</td><td>1.025 E-4</td><td>2.915 E-4</td><td>5.236 E-4</td></tr><tr><td>4.280 E-1</td><td>1.429 E-4</td><td>5.970 E-4</td><td>5.784 E-4</td></tr><tr><td>5.234 E-1</td><td>1.881 E-4</td><td>4.286 E-1</td><td>7.982 E-4</td></tr><tr><td rowspan="3">5</td><td rowspan="3">1000</td><td>1.080 E-1</td><td>1.097 E-4</td><td>9.849 E-4</td><td>1.032 E-4</td></tr><tr><td>5.787 E-1</td><td>1.296 E-4</td><td>1.255 E-3</td><td>1.225 E-4</td></tr><tr><td>7.348 E-1</td><td>1.532 E-4</td><td>1.721 E-3</td><td>1.687 E-4</td></tr><tr><td rowspan="3">10</td><td rowspan="3">2000</td><td>3.966 E-1</td><td>1.291 E-3</td><td>5.694 E-3</td><td>0.896 E-3</td></tr><tr><td>9.203 E-1</td><td>1.615 E-3</td><td>6.337 E-3</td><td>1.187 E-3</td></tr><tr><td>1.077 E+0</td><td>1.931 E-3</td><td>1.067 E-1</td><td>1.763 E-3</td></tr></tbody></table>
<table><caption>Table 4.27 Best, average and worst IGD values on DTLZ5(2,15) and DTLZ5(3,5) problems</caption><tr><td></td><td>15</td><td>3000</td><td>5.890 E-1</td><td>1.474 E-3</td><td>7.110 E-3</td><td>3.024 E-1</td></tr><tr><td></td><td></td><td></td><td>1.133 E+0</td><td>1.881 E-3</td><td>3.431 E-1</td><td>3.268 E-1</td></tr><tr><td></td><td></td><td></td><td>1.249 E+0</td><td>3.159 E-3</td><td>1.073 E+0</td><td>3.903 E-1</td></tr></table>

<table><thead><tr><th>Test Problem</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th></tr></thead><tbody><tr><td rowspan="3">DTLZ5(2,15)</td><td>1.134 E-2</td><td>1.641 E-3</td><td>2.034 E-3</td><td>1.344 E-3</td></tr><tr><td>1.326 E-2</td><td>3.195 E-3</td><td>4.985 E-3</td><td>2.786 E-3</td></tr><tr><td>1.667 E-2</td><td>4.034 E-3</td><td>9.031 E-3</td><td>4.239 E-3</td></tr><tr><td rowspan="3">DTLZ5(3,5)</td><td>1.194 E-4</td><td>0.634 E-4</td><td>1.985 E-4</td><td>0.736E-4</td></tr><tr><td>1.265 E-4</td><td>3.056 E-4</td><td>3.192 E-4</td><td>0.925E-4</td></tr><tr><td>1.703 E-4</td><td>6.238 E-4</td><td>8.054 E-4</td><td>2.362E-4</td></tr></tbody></table>

In the majority of cases, for different number of objectives and number of generations, MOEA/DD has the minimum (best) IGD value. Generally, MOEA/DD is more performing than NSGA-III. The best amount of improvement in IGD values between correlated and non-correlated objectives is noted for the MOEA/D algorithm. As a consequence, we can conclude that MOEA/D works well on the many-objective case with highly-correlated objectives, which indicates clearly the advantage of using dependent objectives in many-objective problems. This finding proves that algorithms which are not designed for MaOPs (such as MOEA/D) may be efficient in resolving MaOPs if the objectives are correlated. Compared with the IGD values using non-correlated objectives (not presented here due to space constraints), the obtained results illustrated in Table 4.26, show that the IGD values decrease if the objectives are correlated.

### 4.3.2 Testing the effect of the size of the population

In this section, we show the effect of varying the size of the population on the quality of the found solutions. For each test problem, different specifications of the population size in each MOEA are used: 100 (small), 600, 1000 1200 and 1400 (large). PBI (5.0) is employed as a scalarizing function for MOEA/D and MOEA/DD. The mutation probability is 1/400 with an index of 50 (Bit-flip mutation), and the recombination probability is 0.9 with an index of 5 (SBX crossover). No neighbor mating in recombination. We apply 250 reference points for NSGA-III algorithms. Table 4.28 (Table 4.29, respectively) illustrates the results of measuring the IGD on the DTLZ1 and DTLZ2 (DTLZ5(2,15) and DTLZ5(3,5), respectively) test functions using the above-indicated parameters.

<table><caption>Table 4.28 Best, average and worst IGD values on DTLZ1 and DTLZ2 for different population sizes</caption><thead><tr><th>Test Ph</th><th>Obj Nbr</th><th>Population size</th><th>MOEA/D (PBI)</th><th>MOEA/DD</th><th>NSGA-III</th><th>Two_Arch2</th><th>Number of reference points</th></tr></thead><tbody><tr><td rowspan="14">DTLZ1</td><td rowspan="10">5</td><td rowspan="3">100</td><td>3.031 E-4</td><td>1.036 E-4</td><td>0.679 E-3</td><td>2.364 E-4</td><td rowspan="3">90</td></tr><tr><td>6.627 E-4</td><td>4.145 E-4</td><td>1.325 E-3</td><td>6.569 E-4</td></tr><tr><td>9.309 E-4</td><td>8.327 E-4</td><td>1.325 E-3</td><td>1.412 E-4</td></tr><tr><td rowspan="3">600</td><td>6.023 E-4</td><td>2.264 E-4</td><td>4.356 E-4</td><td>2.034 E-4</td><td rowspan="3">130</td></tr><tr><td>6.466 E-4</td><td>3.058 E-4</td><td>0.996 E-3</td><td>6.433 E-4</td></tr><tr><td>6.924 E-4</td><td>4.065 E-3</td><td>7.365 E-3</td><td>9.857 E-4</td></tr><tr><td rowspan="3">1000</td><td>3.179 E-4</td><td>2.635 E-4</td><td>5.116 E-4</td><td>6.034 E-4</td><td rowspan="3">255</td></tr><tr><td>6.372 E-4</td><td>2.916 E-4</td><td>0.980 E-4</td><td>6.372 E-4</td></tr><tr><td>1.635 E-3</td><td>3.109 E-4</td><td>1.979 E-3</td><td>6.967 E-4</td></tr><tr><td rowspan="3">1200</td><td>1.872 E-4</td><td>7.326 E-4</td><td>7.034 E-4</td><td>3.302 E-4</td><td rowspan="3">280</td></tr><tr><td>6.334 E-4</td><td>2.874 E-4</td><td>0.976 E-3</td><td>6.313 E-4</td></tr><tr><td>9.659 E-4</td><td>0.023 E-4</td><td>4.321 E-3</td><td>8.034 E-4</td></tr><tr><td rowspan="3">1400</td><td>2.654 E-4</td><td>0.791 E-4</td><td>4.032 E-4</td><td>9.623 E-4</td><td rowspan="3">290</td></tr><tr><td>6.136 E-4</td><td>2.823 E-4</td><td>0.963 E-3</td><td>6.284 E-4</td></tr><tr><td>7.327 E-4</td><td>5.475 E-4</td><td>3.027 E-3</td><td>9.371 E-4</td></tr><tr><td rowspan="10">10</td><td rowspan="3">100</td><td>5.084 E-3</td><td>2.261 E-3</td><td>3.432 E-3</td><td>2.674 E-3</td><td rowspan="3">270</td></tr><tr><td>5.163 E-3</td><td>2.624 E-3</td><td>3.863 E-3</td><td>2.897 E-3</td></tr><tr><td>5.369 E-3</td><td>2.983 E-3</td><td>3.909 E-3</td><td>2.978 E-3</td></tr><tr><td rowspan="3">600</td><td>5.032 E-3</td><td>2.169 E-3</td><td>3.308 E-3</td><td>2.636 E-3</td><td rowspan="3">290</td></tr><tr><td>5.125 E-3</td><td>2.231 E-3</td><td>3.734 E-3</td><td>2.881 E-3</td></tr><tr><td>5.421 E-3</td><td>2.564 E-3</td><td>3.907 E-3</td><td>2.908 E-3</td></tr><tr><td rowspan="3">1000</td><td>3.872 E-3</td><td>1.828 E-3</td><td>2.215 E-3</td><td>2.368 E-3</td><td rowspan="3">320</td></tr><tr><td>5.073 E-3</td><td>2.225 E-3</td><td>3.462 E-3</td><td>2.962 E-3</td></tr><tr><td>6.132 E-3</td><td>2.467 E-3</td><td>6.869 E-3</td><td>3.101 E-3</td></tr><tr><td rowspan="3">1200</td><td>4.908 E-3</td><td>2.022 E-3</td><td>3.123 E-3</td><td>2.137 E-3</td><td rowspan="3">350</td></tr><tr><td>5.032 E-3</td><td>2.195 E-3</td><td>3.416 E-3</td><td>2.302 E-3</td></tr><tr><td>5.309 E-3</td><td>2.607 E-3</td><td>3.709 E-3</td><td>2.864 E-3</td></tr><tr><td rowspan="3">1400</td><td>4.364 E-3</td><td>2.026 E-3</td><td>3.266 E-3</td><td>2.023 E-3</td><td rowspan="3">350</td></tr><tr><td>4.936 E-3</td><td>2.137 E-3</td><td>3.403 E-3</td><td>2.208 E-3</td></tr><tr><td>5.211 E-3</td><td>2.734 E-3</td><td>3.708 E-3</td><td>2.604 E-3</td></tr></tbody></table>