<commit_before>![Meta Heuristics](https://docs.google.com/drawings/d/1GvSXJfp7RvjN4T2VtgJfQZ9LzGrHRIelw-awrcxYYVo/pub?w=249&h=101)

# MetaHeuristics

A repositorie with an explanation and a comparission of different metaheuristics

## Base Problem - Travelling salesman problem
We must travel from the origin city, go through all the cities and come back to the origin city. For this we should use the shortest path that we can found and we can't pass two times for the same city.

Example representation of the problem

![Search Space](https://docs.google.com/drawings/d/1CqxjTGnPX06tfltqM3eUIMCvVwr4fED_Np9bWlAhzjY/pub?w=469&h=302)

### Representation of Solutions

In the representation of the solution, we assume that we start in city 0 and that we have to return to city 0. So we represent the solution as an ordered array of cities, in which the first element is the city that we are going to visit if we start at city 0, the second element is the city that we should visit if we are at city 1,..

| Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
| -----  | --- | --- | --- | --- | --- | --- | --- | --- |
| City   | 2   | 5   | 7   | 6   | 3   | 1   | 4   | n   |

### Cost of Solution

The cost of the solution is the sum of the distances of traveling from one city to another following the solution path. We must remember that we start at city 0 and we have to return to city 0.

    C = D(0,1) + D(1,2)+ ··· + D(j,k) + ··· + D(k,n-1) + D(n-1,n) + D(n,0)


## Implemented MetaHeuristics

### Local Search

#### First Best
<<<<<<< HEAD
 
In this kind of search, we update the current solution with the first solution found that is better than our current solution, we don't need to search in all the possible search space. 

##### Operators used

- **Permute:** exchanges the position of two cities in the solution array 

    Example:
    
    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | 5   | 7   | 6   | 3   | 1   | 4   | n   |
    
    Permute(2,6)
    
    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | **1**   | 7   | 6   | 3   | **5**   | 4   | n   |
    
##### Algorithm
    
```python
=======

In this kind of search, we update the current solution with the first solution found that is better than our current solution, we don't need to search in all the possible search space.

##### Operators used

- **Permute:** exchanges the position of two cities in the solution array

    Example:

    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | 5   | 7   | 6   | 3   | 1   | 4   | n   |

    Permute(2,6)

    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | **1**   | 7   | 6   | 3   | **5**   | 4   | n   |

##### Stop condition

The algorithm stops once we can't generate a better solution applying an operator to our current solution
 
## HOW TO RUN THE CODE

```bash
python3 main.py
```

## HOW TO RUN THE CODE

### Normal execution

```bash
python3 main.py filewithData
python3 main.py distancias_10.txt
```

### Debugging
#### Providing a file with random numbers

This allows you to replicate a previous simulation, because the program will use the numbers inside the file instead of generate new random numbers

```bash
python3 main.py filewithData fileWithRandomNumbers
python3 main.py distancias_10.txt aleatorios_ls_2016.txt
```<commit_msg>Fixed and Updated Readme.md<commit_after>![Meta Heuristics](https://docs.google.com/drawings/d/1GvSXJfp7RvjN4T2VtgJfQZ9LzGrHRIelw-awrcxYYVo/pub?w=249&h=101)

# MetaHeuristics

A repositorie with an explanation and a comparission of different metaheuristics

## Base Problem - Travelling salesman problem
We must travel from the origin city, go through all the cities and come back to the origin city. For this we should use the shortest path that we can found and we can't pass two times for the same city.

Example representation of the problem

![Search Space](https://docs.google.com/drawings/d/1CqxjTGnPX06tfltqM3eUIMCvVwr4fED_Np9bWlAhzjY/pub?w=469&h=302)

### Representation of Solutions

In the representation of the solution, we assume that we start in city 0 and that we have to return to city 0. So we represent the solution as an ordered array of cities, in which the first element is the city that we are going to visit if we start at city 0, the second element is the city that we should visit if we are at city 1,..

| Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
| -----  | --- | --- | --- | --- | --- | --- | --- | --- |
| City   | 2   | 5   | 7   | 6   | 3   | 1   | 4   | n   |

### Cost of Solution

The cost of the solution is the sum of the distances of traveling from one city to another following the solution path. We must remember that we start at city 0 and we have to return to city 0.

    C = D(0,1) + D(1,2)+ ··· + D(j,k) + ··· + D(k,n-1) + D(n-1,n) + D(n,0)


## Implemented MetaHeuristics

#### First Best
 
In this kind of search, we update the current solution with the first solution found that is better than our current solution, we don't need to search in all the possible search space. 

### Tabu Search

[WIP - description]

### Simulated Annealing

[WIP - description]

### Evolutive Search

[WIP - description]

#### Operators used for all heuristics

- **Permute:** exchanges the position of two cities in the solution array

    Example:

    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | 5   | 7   | 6   | 3   | 1   | 4   | n   |

    Permute(2,6)

    | Order  | 1   | 2   | 3   | 4   | 5   | 6   | 7   | n   |
    | -----  | --- | --- | --- | --- | --- | --- | --- | --- |
    | City   | 2   | **1**   | 7   | 6   | 3   | **5**   | 4   | n   |

##### Stop condition

The algorithm stops once we can't generate a better solution applying an operator to our current solution
 
## HOW TO RUN THE CODE

### Normal execution

```bash
python3 main.py filewithData
python3 main.py distancias_10.txt
```

### Debugging

#### Providing a file with random numbers

This allows you to replicate a previous simulation, because the program will use the numbers inside the file instead of generate new random numbers

```bash
python3 main.py filewithData fileWithRandomNumbers
python3 main.py distancias_10.txt aleatorios_ls_2016.txt
```
{'fraction_non_alphanumeric': 0.1335843373493976, 'fraction_numerical': 0.03237951807228916, 'mean_word_length': 2.266601082144614, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 3, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3154656', 'n_tokens_mistral': 2379, 'n_tokens_neox': 2154, 'n_words': 855}