{'fraction_non_alphanumeric': 0.035153503632528706, 'fraction_numerical': 0.010467932192797437, 'mean_word_length': 4.612450679526524, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
New results of ant algorithms for the Linear Ordering Problem

Ant-based algorithms are successful tools for solving complex problems. One of these problems is the Linear Ordering Problem (LOP). The paper shows new results on some LOP instances, using Ant Colony System (ACS) and the Step-Back Sensitive Ant Model (SB-SAM).


Introduction
Linear Ordering Problem (LOP) is an NP-hard problem [3,10]. In graph theory, LOP is searching for an acyclic tournament having the maximum sum of arc weights in a complete weighted graph. In other words, LOP is seeking a permutation of rows and columns in a given matrix of weights in order to maximize the sum of weights in the upper triangle [10,11].
Several methods were proposed to solve the Linear Ordering Problem. Exact methods [13,15,16] and heuristic methods were proposed to address LOP algorithms. Heuristics are more efficiently in finding near-optimal solutions to LOP: tabu search [9,11], scatter search [2], iterated local search [12], sorting through insertion pattern and permutation reversal [3] and evolutionary algorithms [18].
Some evolutionary approaches to LOP presented and analyzed by Snasel et al [18] use two approaches: mutation only genetic algorithm and higher level chromosome genetic algorithm. These evolutionary methods obtain good results for problem instances from the library proposed by Mitchell and Borchers [13].
Two ant-based models are described for solving LOP: a hybrid model based on the Ant Colony System (ACS) [7,8], called Ant Colony System-Insert Move (ACS-IM) presented in [14]  behaviour, the virtual state transition rule avoids a selection of the next step from the available nodes making the agent to take a step back to the previous node and explore other regions of the search space.
The SB-SAM virtual state based decision making process generates a benefic exploratory behavior of the system which is balanced by the exploitation orientation of the highly sensitive agents in the system. The paper reports new results for the artificial LOP large instances data generated by Mitchell and Bochers [13]. Both ant based techniques produce high-quality results for of LOP competing with two genetic algorithms: Mutation Only Genetic Algorithm (MOGA) and Higher Level Chromosome Genetic Algorithm (HLCGA) [18]. The results reported by SB-SAM are better than those of ACS-IM and the already mentioned genetic algorithms. This is indicating the potential of inducing heterogeneity in ant-based models for better addressing difficult problems where complex behavior patterns are needed.
Numerical experiments on several LOP instances available in the well-known real-world data library LOLIB [19] are reported in [6]. This paper is organized as follows: the linear ordering optimization problem is described; ant colony models are described; numerical experiments and comparisons are discussed and directions for future research are presented.

The Linear Ordering Problem
One of the well-known NP-hard problem is the Linear Ordering Problem (LOP). LOP is equivalent in economics with the triangulation problem for input-output tables in economics [3,9,15]. Single-server scheduling, ranking by aggregation of individual preferences in group decision making, archaeological seriation are other applications [3,11].
In order to introduce LOP, let E = (eij) nxn be a matrix of weights. The value of e ij refers to the cost of having object i before object j in the linear ordering.
LOP aims to find a permutation of the rows and columns π = (π 1 , π 2 , · · · , π n ) such that the total weight (sum of elements above the diagonal) is maximized [11,15]: An acyclic tournament corresponds to a permutation of the graph vertices. Let G = (V, E, w) be a complete graph. V is the set of nodes and E contains the vertices of the graph and w refers to the weight (or cost) associated with an edge (the weight from i to j can be different that the weight of j to i). The function to be maximized in LOP is the following: where π is a permutation of V , i, j ∈ V and ≤ is a total order relation on V .

Ant-based model for solving LOP
The ant-based models involved in the present paper to solving Linear Ordering Problem are described shortly in the following.

A Ant Colony Systems
Ant Colony System (ACS) metaheuristic is introduced in [7,8]. The ACS model replicates the behavior of social insects to the search space represented commonly by a graph. Each edge has an associated weight as well as a pheromone value corresponding to a desirability measure. A problem solution is a complete tour generates a by an ant. The next node in the graph is choose probabilistically based on the weight and the amount of pheromone on the connecting edge [7]. Stronger pheromone trails are preferred by ants and the most promising tours build up higher amounts of pheromone in time.

B Ant Colony System-Insert Move
The ACS model for solving LOP is called Ant Colony System-Insert Move (ACS-IM) [14]. ACS-IM starts with a greedy search. ACS-based rules are applied and a local search mechanism based on insert moves is engaged. The local search mechanism is based on the neighborhood search proposed for LOP [9]. Insert moves (IM) are used to create a neighborhood of permutations for one solution.

C Sensitive Ant Model
The Sensitive Ant Model (SAM) extends ACS by inducing heterogeneity in the ant population [4].
Each ant is endowed with a pheromone sensitivity level (PSL -a real number in the unit interval). Highlysensitive ants are influenced by stigmergic information in the decision making process and thus likely to select strong pheromone trails. The ants with low sensitivity tend to ignore the amount of pheromone and bias the search towards unexplored regions. The new SAM probability of selecting the next node is the same with the ACS one when pheromone sensitivity level (PSL) value is maximum being reduced proportionally with the sensitivity level in the rest of the cases. A virtual state is introduced in SAM corresponding to the lost probability of (1 PSL). The associated virtual state decision rule specifies the action to be taken when the virtual state is selected using the renormalized transition mechanism [4].

D Step-Back Sensitive Ant Model
The Step-Back Sensitive Ant Model (SB-SAM) [5] is based on the Sensitive Ant Model (SAM) [4]. The aim of SB-SAM is to better exploit the potential of the virtual state translating to a more reliable search space exploration. This is achieved by specifying a new action associated with the virtual decision rule inspired by the observed behavior of the ant Lasius niger [1]. Biologistss study emphasize that some Lasius niger suddenly move in the opposite direction making a u-turn and exploiting the geometry of the trail network bifurcation [1]. These u-turns actually contribute more to the selection of a path compared to bi-directional trail laying. SAM reinforce the inherent heterogeneity of the model facilitating a significant increase of diversity in the search. The virtual state transition rule specified by SB-SAM makes the ant to take a step back by selecting the previous node [5]. The pheromone trail is locally updated by decreasing the pheromone intensity on the edge connecting the current node with the previous one. The local virtual state update rule complements is given by the following equation: where τ ji represents the amount of pheromone on edge (j, i) while ρ and τ 0 are the same parameters used in the ACS local updating rule [7]. The search continues from the new current node until a complete tour is built. The probability of an ant to take the virtual state decision is inverse proportionally with the ants sensitivity level: lower PSL means higher chance to take a step back whereas high PSL values favor the application of the ACS-inherited state transition rule. The step-back virtual decision rule generates completely new overall behavior for the system of interacting ants triggering search diversity. A good distribution of PSL values in the population is important to create a balance in the search space between the exploitation and exploration [5].

1) Representation and initialization.
Linear Ordering: Problem solution is a list of vertices, of a complete directed graph with n nodes. The list is constructed in a step by step manner by each ant based on the transition rules specified by the ant model. The algorithm is based on ACS-IM [14]. It is initialized with a greedy solution obtained based on a 2-exchange Neighborhood search, permuting two positions in the ordering [17]. A function w assigns real values (the weights) to edges defining the static matrix of weights W = (w ij ), 1 ≤ i, j ≤ n. The pheromone matrix τ has the same dimensions as W . The pheromone matrix τ is initialized with τ ij = τ 0 , 1 ≤ i, j ≤ n where τ 0 is a small positive constant. The SB-SAM algorithm uses m ants. A PSL value is randomly generated for each ant. The ants are initially randomly placed in the nodes of the graph. 2) Solution construction.
The SAM renormalized transition probabilities [4] guide the selection of the next node in the search process. The probability of choosing the next node u from the current node i for an agent k is given by the following equation: where P SL(k) represents the sensitivity level of agent k and p iu (k) is the ACS state transition probability [7]. The ACS local update pheromone rule [7] is applied to modify the amount of pheromone on the latter edge traversed. The probability of an ant k to make a virtual state transition from a current node i is equal to (1 − p iu (k)). In this case, ant k goes back to the previous node and the local virtual state update rule (3) is applied. Insert moves (IM) [11] are used to improve the final solution detected by an ant. A global update pheromone rule [7] is applied to the edges belonging to the best tour: where C bs is the weight of the best-so-far solution and ρ is a parameter.

New results for Mitchell and Bochers Instances (MBLIB)
This is the main section of the paper, reporting new results for the artificial LOP data collection generated by Mitchell and Bochers [13]. Besides comparing the performance of the two ant-based models ACS-IM and SB-SAM, numerical experiments focus on evaluating the proposed ant LOP models against Mutation Only Genetic Algorithm (MOGA) and Higher Level Chromosome Genetic Algorithm (HLCGA) [18].
The following parameters are used for ACS-IM and SB-SAM algorithms: α = 1, β = 2, τ 0 = 0.1,ρ = 0.1, q 0 = 0.5 and m = 10. In the SB-SAM approach, the PSL value for each agent is randomly generated using an uniform distribution. Table 1 shows the results for the instances available in MBLIB [13]. The deviation of the obtained solution from the optimum solution is computed based on the average over five runs of the algorithm with 200 iterations.    Table 2: Deviation error (in %) of ant-based models compared to evolutionary approaches [18] for M BLIB instances.
The analysis of the results for each problem size (100-250) confirms the results obtained for MBLIB (see Figures  2-3). SB-SAM algorithm shows an intensification of search in more complex spaces. The effects of the u-turns specified by the virtual state transition rule in SB-SAM (resulting in search diversification) are more visible for higher dimension problem instances.
In the following the comparison of ant-based models with Mutation Only Genetic Algorithm (MOGA) and Higher Level Chromosome Genetic Algorithm (HLCGA) [18]. Average overall results for MBLIB instances are available for these algorithms in [18]. Table 2 shows the average deviation obtained by all involved algorithms for MBLIB instances. In [9] are proposed also some hybrid models combining variable neighborhood search and different strategies for local search. Local search strategies are limited by the dimension of problem instances.
Further work will focuses on other hybrid ant-based techniques in order to obtain better solution for large LOP instances.

Conclusions
The paper shows new results for Linear Ordering Problem (LOP) using bio-inspired models. The ant-based models for solving LOP are described: the first one is a hybrid Ant Colony System [8], called Ant Colony System-Insert Move (ACS-IM) [14] and the second one uses a new Step-Back Sensitive Ant model [4,5]. The ant models compete with other techniques for solving LOP in terms of solution quality.
Numerical experiments indicate a better performance of SBSAM in solving large Mitchell instances [13], compared to the ACS-IM technique and two genetic algorithms: Mutation Only Genetic Algorithm (MOGA) and Higher Level Chromosome Genetic Algorithm (HLCGA) [18]. Other hybridization techniques for solving NP-hard problems, including Linear Ordering Problem will be developed.