# SSTNDS: A SET-Based Non-Dominated Sorting Algorithm for Multi-Objective Optimization Problems
## 4 Proposed Non-Dominated Sorting Algorithm
### Algorithm Description  
Algorithm 1 describes the whole implementation process of the proposed algorithm. The algorithm mainly contains three steps: population initialization, determination of the dominant set and dominant comparison. Figure 4: Main idea for the proposed algorithm. (**a**) Sorted objective set for solutions. (**b**) Relationships between dominant region \(\Omega\)(\(s\)) and preferential sets \(AP\)(\(s\)). Figure 3: Dominant region of point \(s\). Figure 2: Example for a bi-objective space. ```
Input population \(P\) Output the rank fronts \(F\) for solutions in \(P\)
1 Begin
2[\(N,M\)] \(\leftarrow\) size(\(P\)); %obtain size \(N\) and objective \(M\)
3 for\(j=1\) to \(M\)
4\(A(j)\)\(\leftarrow\) sort(\(P,j\)); % sort \(P\) in an ascending order of objective \(j\);
5 end for
6[\(SA,\mathit{pos\_s}\)] \(\leftarrow\) unique(\(A(1,N^{*}M)\)); % get sequence of solutions and locations
7\(MA\)\(\leftarrow\) repmat(1:\(M\), \(1\), \(N^{*}M\))(\(\mathit{pos\_s}\)); % get objective index of the solutions
8\(PS\)\(\leftarrow\) makeRelation(\(P\), \(SA\), \(A\)); % associate solution with locations
9 for\(i=1\) to \(N\)
10\(s\gets SA(i)\)
11\(m\gets MA(i)\)
12\(\Omega(s)\)\(\leftarrow\) ObtainDominantSet(\(s\), \(m\), \(A\), \(PS\)); % obtain dominant set
13 ifisempty(\(\Omega(s)\)) % ifempty
14\(F(s)\gets 1\)
15 else
16[\(p\), \(F(p)\)] \(\leftarrow\) max\(\{F[\Omega(s)]\}\); % obtain the highest rank in \(\Omega(s)\)
17\(r\leftarrow\) DominateComparision(\(p\), \(s\)); % dominate relation
18\(F(s)\)\(\leftarrow\)\(r+F(p)\); % obtain the rank of \(s\)
19 end for
20
21 end for
```  
**Algorithm 1**Set-based Non-Dominated Sort Algorithm-SETNDS  
The population initialization process is realized in Algorithm 1, lines 2-8. At first, the size and number of objectives of the population \(P\), represented as \(N\) and \(M\), respectively, are obtained (Algorithm 1 line 2). Then, the solutions are sorted by each objective value \(s_{j}\) in the _jth_ objective and the sorted sequence is stored in set \(A_{j}\). If any objective values are the same, then the values of the next objective are considered. This idea comes from the lexicographic order [6] (Algorithm 1 lines 3-5). Certain sequence list \(SA\), which is used to obtain the rank for each solution, is determined from the objective set \(A\). The relative objective sequence list \(MA\) is generated according to \(SA\) and \(A\). The positional information which associates the solution to \(A\) is stored to the location set \(PS\) (Algorithm 1 line 8). The method to find the dominant set (Algorithm 1 line 12) is realized in Algorithm 2. The algorithm starts to find the position \(\mathit{pos\_m}\) of \(s\) from \(PS\). Then, based on \(\mathit{pos\_m}\), a judgement is made on whether to continue searching the preferential sets in other objectives. This is because if \(\mathit{pos\_m}\) equals 1, there will be no other solution better than \(s\) in objective \(m\) and the dominant set of \(s\) will be empty; it is unnecessary to search other objectives once the dominant set is empty. Otherwise, other preferential sets will be intersected to obtain the common solutions composed by the dominant set (Algorithm 2 line 8-12). The dominant set that dominates \(s\) will be back to Algorithm 1 at line 12 and assigned to \(\Omega_{1}(s)\). If \(\Omega_{1}(s)\) is empty, it means there are no solutions better than \(s\) and that the rank of \(s\) is 1 (Algorithm 1 line 14). If \(\Omega_{1}(s)\) is not empty, any solution in \(\Omega_{1}(s)\) dominates \(s\) and the solution with the highest front rank--supposing solution \(p\) has the highest rank \(r\)--determines the rank of \(s\). If there are no identical solutions in population \(P\), the rank of \(s\) is \(r+1\). We will make a dominate comparison in Algorithm 3 for avoiding the identical solutions assigned to different ranks.