4
\$\begingroup\$

I was looking to learn about AI and found the traveling salesman problem very interesting. I also wanted to learn about genetic algorithms, so it was a fantastic combo. To clarify, this is my second project in Python, so the code might look ugly. I thought it would be better to have someone check the code and give me feedback on what I can do better to refactor or change stuff for my next projects.

The task has some restrictions:

The location id 1 must be the starting and the ending point

The maximum distance allowed is distance <= 9000

The fitness calculation cant exceed 250000


Code:

import numpy as np
import random
import operator
import pandas as pd

val10 = 0
val9 = 0
class Locations:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def dist(self, location):
        x_dist = abs(float(self.x) - float(location.x))
        y_dist = abs(float(self.y) - float(location.y))
        # √( (x2 − x1)^2 + (𝑦2 − 𝑦1)^2 )
        dist = np.sqrt((x_dist ** 2) + (y_dist ** 2))
        return dist

    def __repr__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"


class Fitness:
    def __init__(self, route):
        self.r = route
        self.dist = 0
        self.fit = 0.0

    def route_dist(self):
        if self.dist == 0:
            path_dist = 0
            for i in range(0, len(self.r)):
                from_location = self.r[i]
                to_location = None
                if i + 1 < len(self.r):
                    to_location = self.r[i+1]
                else:
                    to_location = self.r[0]

                path_dist += from_location.dist(to_location)
            self.dist = path_dist
        return self.dist

    def route_fittness(self):
        if self.fit == 0:
            self.fit = 1 / float(self.route_dist())
        global val9
        val9 = val9 + 1    
        return self.fit


def generate_route(location_list):
    route = random.sample(location_list, len(location_list))
    return route


def gen_zero_population(size, location_list):
    population = []

    for i in range(0, size):
        population.append(generate_route(location_list))
    return population


def determine_fit(population):
    result = {}
    for i in range(0, len(population)):
        result[i] = Fitness(population[i]).route_fittness()
    global val10
    val10 = val10 + 1
    return sorted(result.items(), key=operator.itemgetter(1), reverse=True)


def fit_proportionate_selection(top_pop, elite_size):
    result = []
    df = pd.DataFrame(np.array(top_pop), columns=["index", "Fitness"])
    df['cumulative_sum'] = df.Fitness.cumsum()
    df['Sum'] = 100*df.cumulative_sum/df.Fitness.sum()

    for i in range(0, elite_size):
        result.append(top_pop[i][0])
    for i in range(0, len(top_pop) - elite_size):
        select = 100*random.random()
        for i in range(0, len(top_pop)):
            if select <= df.iat[i, 3]:
                result.append(top_pop[i][0])
                break
    return result


def select_mating_pool(populatoin, f_p_s_result):
    mating_pool = []
    for i in range(0, len(f_p_s_result)):
        index = f_p_s_result[i]
        mating_pool.append(populatoin[index])
    return mating_pool


def ordered_crossover(p1, p2):
    child, child_p1, child_p2 = ([] for i in range(3))

    first_gene = int(random.random() * len(p1))
    sec_gene = int(random.random() * len(p2))

    start_gene = min(first_gene, sec_gene)
    end_gene = max(first_gene, sec_gene)

    for i in range(start_gene, end_gene):
        child_p1.append(p1[i])

    child_p2 = [item for item in p2 if item not in child_p1]

    child = child_p1 + child_p2
    return child


def ordered_crossover_pop(mating_pool, elite_size):
    children = []

    leng = (len(mating_pool) - (elite_size))
    pool = random.sample(mating_pool, len(mating_pool))

    for i in range(0, elite_size):
        children.append(mating_pool[i])

    for i in range(0, leng):
        var = len(mating_pool)-i - 1
        child = ordered_crossover(pool[i], pool[var])
        children.append(child)
    return children


def swap_mutation(one_location, mutation_rate):
    for i in range(len(one_location)):
        if (random.random() < mutation_rate):
            swap = int(random.random() * len(one_location))

            location1 = one_location[i]
            location2 = one_location[swap]

            one_location[i] = location2
            one_location[swap] = location1
    return one_location


def pop_mutation(population, mutation_rate):
    result = []

    for i in range(0, len(population)):
        mutaded_res = swap_mutation(population[i], mutation_rate)
        result.append(mutaded_res)
    return result


def next_gen(latest_gen, elite_size, mutation_rate):
    route_rank = determine_fit(latest_gen)
    selection = fit_proportionate_selection(route_rank, elite_size)
    mating_selection = select_mating_pool(latest_gen, selection)
    children = ordered_crossover_pop(mating_selection, elite_size)
    next_generation = pop_mutation(children, mutation_rate)
    return next_generation


def generic_algor(population, pop_size, elite_size, mutation_rate, gen):
    pop = gen_zero_population(pop_size, population)
    print("Initial distance: " + str(1 / determine_fit(pop)[0][1]))

    for i in range(0, gen):
        pop = next_gen(pop, elite_size, mutation_rate)

    print("Final distance: " + str(1 / determine_fit(pop)[0][1]))
    best_route_index = determine_fit(pop)[0][0]
    best_route = pop[best_route_index]
    print(best_route)
    return best_route


def read_file(fn):
    a = []
    with open(fn) as f:
        [next(f) for _ in range(6)]
        for line in f:
            line = line.rstrip()
            if line == 'EOF':
                break

            ID, x, y = line.split()
            a.append(Locations(x=x, y=y))
    return a


location_list = read_file(r'path_of_the_file')

population = location_list
pop_size = 100
elite_size = 40
mutation_rate = 0.01
gen = 100
generic_algor(population, pop_size, elite_size, mutation_rate, gen)

print(val10)
print(val9)

Location file with x and y coordinates

|Locations
|
|52 Locations
|
|Coordinates
|
1 565.0 575.0
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
5 845.0 655.0
6 880.0 660.0
7 25.0 230.0
8 525.0 1000.0
9 580.0 1175.0
10 650.0 1130.0
11 1605.0 620.0 
12 1220.0 580.0
13 1465.0 200.0
14 1530.0 5.0
15 845.0 680.0
16 725.0 370.0
17 145.0 665.0
18 415.0 635.0
19 510.0 875.0  
20 560.0 365.0
21 300.0 465.0
22 520.0 585.0
23 480.0 415.0
24 835.0 625.0
25 975.0 580.0
26 1215.0 245.0
27 1320.0 315.0
28 1250.0 400.0
29 660.0 180.0
30 410.0 250.0
31 420.0 555.0
32 575.0 665.0
33 1150.0 1160.0
34 700.0 580.0
35 685.0 595.0
36 685.0 610.0
37 770.0 610.0
38 795.0 645.0
39 720.0 635.0
40 760.0 650.0
41 475.0 960.0
42 95.0 260.0
43 875.0 920.0
44 700.0 500.0
45 555.0 815.0
46 830.0 485.0
47 1170.0 65.0
48 830.0 610.0
49 605.0 625.0
50 595.0 360.0
51 1340.0 725.0
52 1740.0 245.0
EOF

Result

Initial distance: 26779.322835840427
Final distance: 16291.285326058354
\$\endgroup\$
8
  • \$\begingroup\$ 1) You are getting almost 40% improvement which isn't bad. 2) Remember that this site is not about fixing bugs, just improving coding skills. Someone has already voted to close this question as off-topic because the code doesn't work. The code does work at least to some extent. What was your expected result? \$\endgroup\$
    – pacmaninbw
    Apr 19, 2023 at 13:39
  • \$\begingroup\$ You might find the following interesting: codereview.stackexchange.com/questions/283812/… \$\endgroup\$
    – coderodde
    Apr 19, 2023 at 14:25
  • \$\begingroup\$ @pacmaninbw the requirement is that the distance cant exceed 9000 \$\endgroup\$
    – zellez11
    Apr 19, 2023 at 16:00
  • \$\begingroup\$ Also do add I would still want feedback on the code even if it wont improve the algorithm \$\endgroup\$
    – zellez11
    Apr 19, 2023 at 19:50
  • \$\begingroup\$ 100 isn't very many generations. Running for 1000 generations gets it down to 13179. Also, you need to rotate the solution to put location "1" at the beginning as required. \$\endgroup\$
    – RootTwo
    Apr 19, 2023 at 21:51

2 Answers 2

6
\$\begingroup\$

Overall, your code works (as said in the comments, it can reach your target if you tweak the parameters) and is pretty nice to look at, so good job!

There are some things that can be improved, as there always are, here are some that I can see:

Globals

Using globals is dangerous and should be avoided. In your cases, one of these global variable is basically the generation count and the other population size * generation count. They can be removed without losing any value.

Naming

Your variable names need some love. Most of them are fine, but:

  • some are misspelled: populatoin instead of population, generic_algor instead of genetic_algor
  • some are undescriptive: val9, val10, fn
  • some are needlessly abbreviated: pop, dist, genetic_algor

Constants naming conversions:

Constants are usually named in ALL_CAPS, allowing to clearly differentiate them for variables. In your case, these would be the genetic algorithm's parameters and the path to the location list.

Throwaway variables

You assign values to variables and never use them again. This happens in tuple unpacking and in loops. The convention is to use _ as a variable name in cases where this can't be avoided:

for _ in range(foo):
    pass

_, x, y = line.split()

range parameters

When using range, you usually specify 2 parameters, the first one being 0, which should be omitted for readability.

Looping over collections

You loop over indices in for loops:

for i in range(foo):
    # do things with bars[i]

In Python, it is preferred to loop over items in a collection directly:

for bar in bars:
    # do things with bar

List comprehensions

In several places, you create an empty list then repeatedly append values in a loop.

This can usually be replaced by a list comprehension, for better readability and performance:

def gen_zero_population(size, location_list):
    return [generate_route(location_list) for _ in range(size)]


def pop_mutation(population, mutation_rate):
    return [swap_mutation(route, mutation_rate) for route in population]

File parsing

Your input file parsing function is hardcoded to skip the first 6 lines of the file, which are apparently comments. You can expect the actual data line to follow a certain convention, but you can't expect another location list file to have the same number of comments, including blank ones.

The fix would be to skip every line that starts with a comment marker (|in your case) instead. Here's how I would do it:

def read_location_file(path):
    locations = []
    with open(path, 'r') as f:
        for line in f:
            line = line.strip()
            if line.startswith('|'):
                continue
            if line == 'EOF':
                break
            _, x, y = line.split()
            locations.append(Locations(float(x), float(y)))
    return locations

Overkill Pandas dependency

Running the algorithm can get a bit long, which makes tweaking the parameters tedious. Running a profiler on your code shows that more than 70% of execution time is spent getting values in at Pandas dataframe.

Refactoring your fit_proportionate_selection method to work with arrays instead of a dataframe would probably greatly reduce running time.

It would probably be much more efficient to build a cumsum and sum (probably a poor naming choice here, this doesn't look like a sum) array using numpy (see np.cumsum) and index into those arrays instead of building a dataframe and indexing into it.

Alternatively, you could keep the dataframe and take advantage of Pandas' capabilities to access whole ranges at a time.

Overkill Fitness class

There is no point in having a full class to calculate the fitness of a route, and the whole class can be reduced to a simple function:

def fitness(route):
    route_length = sum(route[i].dist(route[(i+1) % len(route)]) 
                       for i in range(len(route)))
    return 1 / route_length

Saving on complexity and allocations.

Seed the RNG

Execution of the algorithm rely on a random number generator. When refactoring/debugging, it can help to have consistent output, in which case you probably want to add a line akin to:

random.seed(1)

at the start of your script.

Use a main guard

You should put all top-level executed statements after a if __name__ == '__main__': guard, allowing you to reuse the function and classes in your module more easily in the future.

Use string interpolation

Instead of concatenating multiple strings with +, use f-strings to interpolate variables inside a string: f'({self.x}, {self.y})' instead of "(" + str(self.x) + "," + str(self.y) + ")".

Don't sort a dict

determine_fit returns a dict sorted by value. Dictionaries are not ordered collections. The fact that they preserve order is merely an implementation detail and can't be guaranteed to work on other implementations (and in fact won't work in older Python/CPython versions).

Using sorted lists is the way to go. See this StackOverflow question (and answers) for recipes on how to do that.

Meet the requirements

Your algorithm finds a route with any starting point, which fails to meet one of the requirements:

The location id 1 must be the starting and the ending point

Since the total route length doesn't depend on the starting point, you should add a final step rotating the locations to start at the correct point. Somethings along these lines would work:

`[route[(i + location_1_index) % len(route)] for i in range(len(route))]`
\$\endgroup\$
3
  • \$\begingroup\$ would it be possible for you to show how I would refactor the panda dependency ? \$\endgroup\$
    – zellez11
    Apr 20, 2023 at 17:04
  • \$\begingroup\$ also in one of the comments it said I am not starting at id 1 location and need to rotate the solution \$\endgroup\$
    – zellez11
    Apr 20, 2023 at 20:45
  • 1
    \$\begingroup\$ @zellez I edited my answer to provide a bit more detail. I didn't understand all the details of the algorithm, so I won't go any further. \$\endgroup\$
    – gazoh
    Apr 21, 2023 at 7:47
4
\$\begingroup\$

Profiling

Here's a profiler report for the original code, showing the top 10 functions in terms of cumulative time:

       194783293 function calls (194766155 primitive calls) in 120.190 seconds

 Ordered by: cumulative time
 List reduced from 344 to 10 due to restriction <10>

 ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      1    0.013    0.013  120.190  120.190 2237934625.py:158(generic_algor)
    418    0.008    0.000  116.487    0.279 2237934625.py:149(next_gen)
    418    2.795    0.007  111.185    0.266 2237934625.py:46(fit_proportionate_selection)
3008221    5.275    0.000  106.411    0.000 indexing.py:2093(__getitem__)
3008221    3.382    0.000   95.250    0.000 frame.py:3111(_get_value)
3008221    6.065    0.000   87.374    0.000 frame.py:2934(_ixs)
3009057    4.456    0.000   43.880    0.000 frame.py:3306(_box_col_values)
3010311    5.893    0.000   35.178    0.000 series.py:238(__init__)
3009057    8.272    0.000   27.780    0.000 managers.py:998(iget)
6021040    8.354    0.000   22.660    0.000 generic.py:5467(__setattr__)

The first 3 lines are from functions in the genetic algorithm code. The next 7 lines are Pandas functions. Clearly, a significant amount of time is being spent in the Pandas library.

Here's a revised function to eliminate calls to the Pandas library:

def fit_proportionate_selection(top_pop, elite_size):
    indices, fitness = zip(*top_pop)
    cumulative_sum = list(it.accumulate(fitness))
    total = cumulative_sum[-1]
    weights = [100*cs/total for cs in cumulative_sum]

    result = list(indices[:elite_size])
    
    for i in range(len(top_pop) - elite_size):
        select = random.randrange(100)
        for i, weight in enumerate(weights):
            if select <= weight:
                result.append(top_pop[i][0])
                break
    return result

With the revised code, the profiler report looks like this:

       19554541 function calls in 8.925 seconds

 Ordered by: cumulative time
 List reduced from 55 to 10 due to restriction <10>

 ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      1    0.010    0.010    8.925    8.925 643853473.py:158(generic_algor)
    870    0.003    0.000    7.021    0.008 643853473.py:39(determine_fit)
    870    0.052    0.000    7.005    0.008 643853473.py:40(<listcomp>)
 130500    0.095    0.000    6.953    0.000 643853473.py:26(route_fitness)
 130500    0.707    0.000    6.847    0.000 {built-in method builtins.sum}
6916500    2.004    0.000    6.141    0.000 643853473.py:27(<genexpr>)
    434    0.003    0.000    5.368    0.012 643853473.py:149(next_gen)
6786000    4.137    0.000    4.137    0.000 643853473.py:16(dist)
    434    0.042    0.000    0.860    0.002 643853473.py:111(ordered_crossover_pop)
  43400    0.246    0.000    0.742    0.000 643853473.py:93(ordered_crossover)

As you can see, the run time is now 8 seconds instead of 120.

Putting location 1 first

To put location 1 first, find the index of location 1 then use slicing to rotate the list to put location 1 first.

#rotate `best_route` to put location 1 first
index = best_route.index(location_list[0])
best_route = best_route[index:] + best_route[:index]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.