def find_best_path()

in src/genetic_algorithm.py [0:0]

• 56 lines of code
• 5 McCabe index (conditional complexity)

def find_best_path():
    current_generation = create_random_initial_population()
    generation_number = 1

    best_distance_all_time = 99999999
    best_candidate_all_time = None
    best_solution_generation_number = 0
    per_generation_best_scores = []

    # the multiprocessing code doesn't work on Windows
    use_multiprocessing = "win" not in sys.platform or sys.platform == "darwin"
    pool = multiprocessing.Pool()

    job_start_time = time.time()

    while True:

        generation_start_time = time.time()

        uniq_scores = set()

        if use_multiprocessing:
            # this function calls calc_score_for_candidate for each member of current_generation,
            # then combines the results into the scores list:
            scores = pool.map(calc_score_for_candidate, current_generation)
            for index, candidate in enumerate(current_generation):
                candidate.fitness_score = scores[index]
                uniq_scores.add(candidate.fitness_score)
        else:
            for candidate in current_generation:
                # check_candidate_validity(candidate)
                candidate.fitness_score = calc_score_for_candidate(candidate)
                uniq_scores.add(candidate.fitness_score)

        num_uniq_fitness_scores = len(uniq_scores)

        # find the best one this generation
        best_candidate_this_generation = min(current_generation, key=lambda c: c.fitness_score)
        per_generation_best_scores.append(best_distance_all_time)

        # did this generation give us a new all-time best?
        if best_candidate_this_generation.fitness_score < best_distance_all_time:
            # make a copy, since the best candidate of this generation may be used
            # in later generations (and therefore possibly modified)
            best_candidate_all_time = copy.deepcopy(best_candidate_this_generation)
            best_distance_all_time = best_candidate_this_generation.fitness_score
            best_solution_generation_number = generation_number
        else:
            # have we gone many generations without improvement?  If so, we should exit
            if (generation_number - best_solution_generation_number) >= MAX_STAGNANT_GENERATIONS:
                break

        # alternatively, if we've hit the maximum number of generations, exit
        if generation_number > MAX_GENERATIONS:
            break

        # now create the next generation, starting with elites
        num_elites = int(ELITISM_RATE * POPULATION_SIZE)
        current_generation.sort(key=lambda c: c.fitness_score)
        next_generation = [current_generation[i] for i in range(num_elites)]

        # then populate the rest of the next generation
        num_to_add = POPULATION_SIZE - num_elites
        for _ in range(num_to_add):
            parent1, parent2 = select_parents(current_generation)
            child1, child2 = crossover_parents_to_create_children(parent1, parent2)
            mutate_candidate_maybe(child1)
            next_generation.append(child1)
            mutate_candidate_maybe(child2)
            next_generation.append(child2)

        # print per-generation stats
        gen_num_str = '{:>4}'.format(generation_number)
        low_score_str = '{:>6}'.format(str(best_distance_all_time))
        duration = '{:4.1f}'.format(time.time() - generation_start_time)
        uniq_str = '{:>4}'.format(num_uniq_fitness_scores)
        print(f'Gen {gen_num_str}   best: {low_score_str}   uniq: {uniq_str}   dur: {duration}s ')

        # now that the next generation is ready, replace the current generation with it
        current_generation = next_generation
        generation_number += 1

    # we drop out of the loop once we go stagnant, or hit a maximum number of generations
    job_total_time = time.time() - job_start_time
    total_minutes = '{:6.1f}'.format(job_total_time / 60.0)
    print(f'Job complete.  Total duration: {total_minutes} min over {generation_number - 1} generations')

    return best_candidate_all_time, per_generation_best_scores